davenport_constant_support_four_int_box_three_ge_even
Theorem 3 of arXiv:2610.16562, even m: for every even 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 + 8m - 1.
Statement
theorem davenport_constant_support_four_int_box_three_ge_even (m : ℕ) (hm : 2 ≤ m) (heven : Even m) :
((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ≤
davenport_constant_support 4 (int_box_three m)- Formalizes
- arXiv:2610.16562 Theorem 3 (even 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_even_sequenceThe sequence T(m) for even m: (-m,-m,-m) repeated 4m^3-6m^2+4m-1 times, (-m,m-1,m) repeated 4m^3-4m^2+2m times, (m,-(m-1),m-1) repeated…
- davenport_box_three_even_sequence_minimalFor m ≥ 2 even, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
- davenport_box_three_even_sequence_cardThe sequence T(m) (even case) has length 16m^3 - 16m^2 + 8m - 1.
- 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 proof establishes the lower bound by exhibiting an explicit sequence s (defined as `davenport_box_three_even_sequence m`) of vectors in [[-m, m]]³. The sequence is composed of four distinct vectors with positive multiplicities that sum to 16m³ - 16m² + 8m - 1. With minimality of s supplied by a companion lemma, the proof verifies that each vector is in [[-m, m]]³, that all four multiplicities are non-zero, and that the vectors are pairwise distinct, showing that the support has size 4. Consequently, this length belongs to the set whose supremum defines the Davenport constant, yielding the desired lower bound.
The candidate length 16m³ - 16m² + 8m - 1 belongs to the set of lengths of 4-supported minimal zero-sum sequences in [[-m, m]]³, provided the explicit sequence s satisfies the required conditions.
We let s be the explicit multiset `davenport_box_three_even_sequence m` and show that 16m³ - 16m² + 8m - 1 is in the set of lengths defining the Davenport constant by witnessing it with s. Minimality of s as a zero-sum sequence is supplied by `davenport_box_three_even_sequence_minimal`, leaving three subgoals: showing all elements of s are in [[-m, m]]³, that s has support of size 4, and that the cardinality of s equals 16m³ - 16m² + 8m - 1.
uses
davenport_box_three_even_sequence_minimallet s := davenport_box_three_even_sequence m have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ∈ {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_even_sequence_minimal m hm heven, ?_, ?_⟩
Every vector appearing in s has all coordinates in the interval [-m, m].
Since s is a sum of replicate multisets, any element x ∈ s must be one of the four vectors defining s. For each of the four vectors, we check that each coordinate index i ∈ {0, 1, 2} has its value bounded between -m and m using coordinate case analysis and integer linear arithmetic.
uses
Multiset.mem_add,Multiset.mem_replicate,Nat.cast_le.mpr· intro x hx dsimp [davenport_box_three_even_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 four constituent vectors v₁, v₂, v₃, v₄ have strictly positive multiplicities in s.
We name the four vectors v₁ = (-m, -m, -m), v₂ = (-m, m - 1, m), v₃ = (m, -(m - 1), m - 1), and v₄ = (m - 1, m, -m). For m ≥ 2, non-linear arithmetic shows that each of the four polynomial coefficients (4m³ - 6m² + 4m - 1, 4m³ - 4m² + 2m, 4m³ - 2m² + m, and 4m³ - 4m² + m) is strictly positive, hence non-zero.
· set v1 : Fin 3 → ℤ := ![-(m : ℤ), -m, -m] set v2 : Fin 3 → ℤ := ![-(m : ℤ), m - 1, m] set v3 : Fin 3 → ℤ := ![(m : ℤ), -(m - 1), m - 1] set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m] have hk1 : 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 ≠ 0 := by have : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have : 1 < 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by zify [this] nlinarith omega have hk2 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by have : 4 * 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 + m ≠ 0 := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega
The support set of s is {v₁, v₂, v₃, v₄}.
Unfolding s as a sum of four replicates, since all four multiplicities are non-zero, the support of each replicate multiset is the singleton {vᵢ}. The support of the sum of multisets is the union of their supports, yielding {v₁} ∪ {v₂} ∪ {v₃} ∪ {v₄} = {v₁, v₂, v₃, v₄}.
uses
Multiset.toFinset_add,Multiset.toFinset_replicate,if_neghave hS : s = Multiset.replicate (4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1) v1 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v2 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 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 vectors v₁, v₂, v₃, v₄ are pairwise distinct, so the support set has cardinality 4.
For each pair of vectors, assuming they are equal leads to a contradiction by evaluating at a coordinate where they differ. Using these distinctness relations, we see that v₃ ∉ {v₄}, v₂ ∉ {v₃, v₄}, and v₁ ∉ {v₂, v₃, v₄}, and build up the cardinality of {v₁, v₂, v₃, v₄} to 4 by repeated singleton insertions.
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 multiset s has cardinality 16m³ - 16m² + 8m - 1.
Applying the lemma `davenport_box_three_even_sequence_card` computes the sum of the four multiplicities to be exactly 16m³ - 16m² + 8m - 1.
uses
davenport_box_three_even_sequence_card· rw [davenport_box_three_even_sequence_card m hm]The Davenport constant with support 4 on [[-m, m]]³ is at least 16m³ - 16m² + 8m - 1.
The Davenport constant is defined as the supremum of the lengths of valid sequences. Having exhibited s in the set of candidate lengths, `le_sSup` shows that this value is bounded above by the supremum.
uses
le_sSupexact le_sSup hmem
davenport_box_three_even_sequence_minimal- For any even integer m ≥ 2, `davenport_box_three_even_sequence m` is a minimal zero-sum multiset.
Multiset.mem_add- An element belongs to the sum of two multisets if and only if it belongs to at least one of them.
Multiset.mem_replicate- An element belongs to n copies of a if and only if n ≠ 0 and the element equals a.
Nat.cast_le.mpr- An inequality between natural numbers carries over when they are cast to integers.
Multiset.toFinset_add- The support (set of distinct elements) of the sum of two multisets is the union of their supports.
Multiset.toFinset_replicate- The support of n copies of a is {a} if n ≠ 0, and ∅ if n = 0.
if_neg- If a condition is false, an if-then-else expression evaluates to its else branch.
congrFun- Equal functions evaluate to equal values on any argument.
Finset.card_insert_of_notMem- Inserting an element into a finite set not containing it increases its cardinality by 1.
Finset.card_singleton- A singleton finite set has cardinality 1.
davenport_box_three_even_sequence_card- For m ≥ 2, the total length (cardinality with multiplicity) of `davenport_box_three_even_sequence m` equals 16m³ - 16m² + 8m - 1.
le_sSup- Any element of a set is less than or equal to the supremum of the set.
- The minimality of the zero-sum multiset s is proved separately in `davenport_box_three_even_sequence_minimal` and cited directly here.
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_even (m : ℕ) (hm : 2 ≤ m) (heven : Even m) : ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ≤ davenport_constant_support 4 (int_box_three m) := by let s := davenport_box_three_even_sequence m have hmem : ((16 * m ^ 3 - 16 * m ^ 2 + 8 * m - 1 : ℕ) : ℕ∞) ∈ {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_even_sequence_minimal m hm heven, ?_, ?_⟩ · intro x hx dsimp [davenport_box_three_even_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 - 1), m - 1] set v4 : Fin 3 → ℤ := ![(m : ℤ) - 1, m, -m] have hk1 : 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 ≠ 0 := by have : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have : 1 < 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by zify [this] nlinarith omega have hk2 : 4 * m ^ 3 - 4 * m ^ 2 + 2 * m ≠ 0 := by have : 4 * 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 + m ≠ 0 := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega have hS : s = Multiset.replicate (4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1) v1 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 2 + 2 * m) v2 + Multiset.replicate (4 * m ^ 3 - 2 * m ^ 2 + m) v3 + Multiset.replicate (4 * m ^ 3 - 4 * m ^ 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_even_sequence_card m hm] exact le_sSup hmem