davenport_constant_support_four_int_box_three_ge_odd
Theorem 3 of arXiv:2610.16562, odd m: for every odd m ≥ 2, the maximal length of a minimal zero-sum sequence over [[-m,m]]^3 with support of size 4 is at least 16m^3 - 16m^2 + 10m - 2.
Statement
theorem davenport_constant_support_four_int_box_three_ge_odd (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) :
((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ≤
davenport_constant_support 4 (int_box_three m)- Formalizes
- arXiv:2610.16562 Theorem 3 (odd case).
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- davenport_constant_supportD^{(k)}(X): the maximal length (a supremum in ℕ∞) of a minimal zero-sum sequence over X whose support has exactly k elements.
- int_box_threeThe box [[-m, m]]^3 of integer vectors in ℤ^3 with every coordinate between -m and m.
- davenport_box_three_odd_sequenceThe sequence T(m) for odd m: (-m,-m,-m) repeated 4m^3-8m^2+5m-2 times, (-m,m-1,m) repeated 4m^3-2m^2+2m times, (m,-m,m-2) repeated…
- davenport_box_three_odd_sequence_minimalFor m ≥ 2 odd, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
- davenport_box_three_odd_sequence_cardThe sequence T(m) (odd case) has length 16m^3 - 16m^2 + 10m - 2.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - multiset_is_minimal_zero_sumA minimal zero-sum sequence: a nonempty finite sequence (multiset) with sum zero, no nonempty proper subsequence of which has sum zero.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The Davenport constant with support size 4 for the box [[-m, m]]³ is bounded below by exhibiting an explicit witness sequence s = davenport_box_three_odd_sequence m of length 16m³ - 16m² + 10m - 2. The proof verifies that all vectors in s belong to [[-m, m]]³ and that its support consists of exactly 4 distinct vectors whose multiplicities are strictly positive. An existing theorem provides the minimality of s as a zero-sum sequence, and the lower bound follows by showing that this length belongs to the set whose supremum defines the Davenport constant.
The target length 16m³ - 16m² + 10m - 2 belongs to the set of lengths of minimal zero-sum sequences in [[-m, m]]³ of support size 4, provided the witness sequence s satisfies the remaining subgoals.
We define the witness sequence s = davenport_box_three_odd_sequence m. We refine the existential statement using s and supply davenport_box_three_odd_sequence_minimal to establish that s is a minimal zero-sum sequence, reducing the goal to three remaining requirements: elements of s lie in the box [[-m, m]]³, s has support size 4, and its length is the target polynomial.
uses
davenport_box_three_odd_sequence_minimallet s := davenport_box_three_odd_sequence m have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ∈ {n | ∃ s : Multiset (Fin 3 → ℤ), (∀ x ∈ s, x ∈ int_box_three m) ∧ multiset_is_minimal_zero_sum s ∧ s.toFinset.card = 4 ∧ (Multiset.card s : ℕ∞) = n} := by refine ⟨s, ?_, davenport_box_three_odd_sequence_minimal m hm hodd, ?_, ?_⟩
Every element of the sequence s belongs to [[-m, m]]³.
Let x ∈ s. Unfolding s with Multiset.mem_add and Multiset.mem_replicate shows that x must be one of the four vectors v₁ = (-m, -m, -m), v₂ = (-m, m-1, m), v₃ = (m, -m, m-2), or v₄ = (m-1, m, -m). Casting m ≥ 2 to ℤ via Nat.cast_le.mpr, we check coordinate by coordinate (i ∈ {0, 1, 2}) that each component lies in [-m, m], which holds by linear integer arithmetic.
uses
Multiset.mem_add,Multiset.mem_replicate,Nat.cast_le.mpr· intro x hx dsimp [davenport_box_three_odd_sequence, s] at hx simp only [Multiset.mem_add, Multiset.mem_replicate] at hx have hmZ : (2 : ℤ) ≤ m := Nat.cast_le.mpr hm rcases hx with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩) · intro i; fin_cases i <;> simp · intro i; fin_cases i <;> { simp; try omega } · intro i; fin_cases i <;> { simp; try omega } · intro i; fin_cases i <;> { simp; try omega }
The multiplicities of the four vectors v₁, v₂, v₃, v₄ defining s are all non-zero.
We define v₁ through v₄ and show that their coefficients k₁ = 4m³ - 8m² + 5m - 2, k₂ = 4m³ - 2m² + 2m, k₃ = 4m³ - 2m² + m, and k₄ = 4m³ - 4m² + 2m are non-zero. Since m ≥ 2, the leading term 4m³ dominates the quadratic terms (e.g. 8m² ≤ 4m³), making each polynomial strictly positive by non-linear arithmetic.
· set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m] set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m] set v3 : Fin 3 → ℤ := ![(m : ℤ), -m, m - 2] set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m] have hk1 : 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 ≠ 0 := by have : 8 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have : 2 < 4 * m ^ 3 - 8 * m ^ 2 + 5 * m := by zify [this] nlinarith omega have hk2 : 4 * m ^ 3 - 2 * m ^ 2 + 2 * m ≠ 0 := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hk3 : 4 * m ^ 3 - 2 * m ^ 2 + m ≠ 0 := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hk4 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega
The support of s equals the four-element set {v₁, v₂, v₃, v₄}.
Expressing s as the sum of the replicated vectors and converting to a finset with Multiset.toFinset_add and Multiset.toFinset_replicate, the nonzeroness of the multiplicities (via if_neg) simplifies the support to {v₁} ∪ {v₂} ∪ {v₃} ∪ {v₄}. Extensionality confirms this is equal to {v₁, v₂, v₃, v₄}.
uses
Multiset.toFinset_add,Multiset.toFinset_replicate,if_neghave hS : s = Multiset.replicate (4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2) v1 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + 2 * m) v2 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v4 := rfl rw [hS] simp only [Multiset.toFinset_add, Multiset.toFinset_replicate, if_neg hk1, if_neg hk2, if_neg hk3, if_neg hk4] have heq : ({v1} ∪ {v2} ∪ {v3} ∪ {v4} : Finset (Fin 3 → ℤ)) = {v1, v2, v3, v4} := by ext x simp rw [heq]
The support of s has cardinality 4.
We show that v₁, v₂, v₃, v₄ are pairwise distinct: for each of the six pairs, an equality between vectors would imply equality at a specific coordinate via congrFun, which contradicts m ≥ 2. Consequently, v₃ ∉ {v₄}, v₂ ∉ {v₃, v₄}, and v₁ ∉ {v₂, v₃, v₄}. Successive applications of Finset.card_insert_of_notMem and Finset.card_singleton establish that |{v₁, v₂, v₃, v₄}| = 4.
uses
congrFun,Finset.card_insert_of_notMem,Finset.card_singletonhave h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [v1, v2] at this; omega have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [v1, v3] at this; omega have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [v1, v4] at this; omega have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [v2, v3] at this; omega have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [v2, v4] at this; omega have h34 : v3 ≠ v4 := by intro h; have := congrFun h 1; simp [v3, v4] at this; omega have h3 : v3 ∉ ({v4} : Finset (Fin 3 → ℤ)) := by simp [h34] have h2 : v2 ∉ ({v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h23, h24] have h1 : v1 ∉ ({v2, v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h12, h13, h14] rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2, Finset.card_insert_of_notMem h3, Finset.card_singleton]
The length of the multiset s is 16m³ - 16m² + 10m - 2.
Rewriting by the lemma davenport_box_three_odd_sequence_card confirms that the multiset cardinality of s equals 16m³ - 16m² + 10m - 2, completing the verification of membership hypothesis hmem.
uses
davenport_box_three_odd_sequence_card· rw [davenport_box_three_odd_sequence_card m hm]The Davenport constant with support 4 on [[-m, m]]³ is at least 16m³ - 16m² + 10m - 2.
The Davenport constant is defined as the supremum of the lengths of all minimal zero-sum sequences in [[-m, m]]³ with support 4. Since the target length was proved in hmem to be achieved by s, le_sSup concludes that it is bounded above by the supremum.
uses
le_sSupexact le_sSup hmem
davenport_box_three_odd_sequence_minimal- For every odd integer m ≥ 2, the sequence davenport_box_three_odd_sequence m is a minimal zero-sum sequence.
Multiset.mem_add- An element belongs to the sum of two multisets if and only if it belongs to at least one of the summands.
Multiset.mem_replicate- An element b belongs to the multiset formed by replicating a for n times if and only if n ≠ 0 and b = a.
Nat.cast_le.mpr- For natural numbers a and b, if a ≤ b then their casts to ℤ satisfy (a : ℤ) ≤ (b : ℤ).
Multiset.toFinset_add- The support (underlying finset) of the sum of two multisets is the union of their support finsets.
Multiset.toFinset_replicate- The support finset of n copies of a is {a} if n ≠ 0, and the empty set ∅ if n = 0.
if_neg- If a condition c is false, the expression (if c then t else e) evaluates to e.
congrFun- If two functions f and g are equal, their values f(a) and g(a) are equal for any input a.
Finset.card_insert_of_notMem- If an element a does not belong to a finset s, the cardinality of insert a s is |s| + 1.
Finset.card_singleton- A singleton finset {a} has cardinality 1.
davenport_box_three_odd_sequence_card- For m ≥ 2, the total length (cardinality) of davenport_box_three_odd_sequence m is 16m³ - 16m² + 10m - 2.
le_sSup- Any member of a set is less than or equal to the supremum of that set.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem davenport_constant_support_four_int_box_three_ge_odd (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) : ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ≤ davenport_constant_support 4 (int_box_three m) := by let s := davenport_box_three_odd_sequence m have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 10 * m - 2 : ℕ) : ℕ∞) ∈ {n | ∃ s : Multiset (Fin 3 → ℤ), (∀ x ∈ s, x ∈ int_box_three m) ∧ multiset_is_minimal_zero_sum s ∧ s.toFinset.card = 4 ∧ (Multiset.card s : ℕ∞) = n} := by refine ⟨s, ?_, davenport_box_three_odd_sequence_minimal m hm hodd, ?_, ?_⟩ · intro x hx dsimp [davenport_box_three_odd_sequence, s] at hx simp only [Multiset.mem_add, Multiset.mem_replicate] at hx have hmZ : (2 : ℤ) ≤ m := Nat.cast_le.mpr hm rcases hx with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩) · intro i; fin_cases i <;> simp · intro i; fin_cases i <;> { simp; try omega } · intro i; fin_cases i <;> { simp; try omega } · intro i; fin_cases i <;> { simp; try omega } · set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m] set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m] set v3 : Fin 3 → ℤ := ![(m : ℤ), -m, m - 2] set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m] have hk1 : 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 ≠ 0 := by have : 8 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have : 2 < 4 * m ^ 3 - 8 * m ^ 2 + 5 * m := by zify [this] nlinarith omega have hk2 : 4 * m ^ 3 - 2 * m ^ 2 + 2 * m ≠ 0 := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hk3 : 4 * m ^ 3 - 2 * m ^ 2 + m ≠ 0 := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hk4 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hS : s = Multiset.replicate (4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2) v1 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + 2 * m) v2 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v4 := rfl rw [hS] simp only [Multiset.toFinset_add, Multiset.toFinset_replicate, if_neg hk1, if_neg hk2, if_neg hk3, if_neg hk4] have heq : ({v1} ∪ {v2} ∪ {v3} ∪ {v4} : Finset (Fin 3 → ℤ)) = {v1, v2, v3, v4} := by ext x simp rw [heq] have h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [v1, v2] at this; omega have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [v1, v3] at this; omega have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [v1, v4] at this; omega have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [v2, v3] at this; omega have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [v2, v4] at this; omega have h34 : v3 ≠ v4 := by intro h; have := congrFun h 1; simp [v3, v4] at this; omega have h3 : v3 ∉ ({v4} : Finset (Fin 3 → ℤ)) := by simp [h34] have h2 : v2 ∉ ({v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h23, h24] have h1 : v1 ∉ ({v2, v3, v4} : Finset (Fin 3 → ℤ)) := by simp [h12, h13, h14] rw [Finset.card_insert_of_notMem h1, Finset.card_insert_of_notMem h2, Finset.card_insert_of_notMem h3, Finset.card_singleton] · rw [davenport_box_three_odd_sequence_card m hm] exact le_sSup hmem