davenport_box_three_even_sequence_minimal
For m ≥ 2 even, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
Statement
theorem davenport_box_three_even_sequence_minimal (m : ℕ) (hm : 2 ≤ m) (heven : Even m) :
multiset_is_minimal_zero_sum (davenport_box_three_even_sequence m)- Source
- The core of the proof of Theorem 3 of arXiv:2610.16562 (even m).
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_sumThe sequence T(m) (even case) is a zero-sum sequence, for every m ≥ 2.
- 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.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- davenport_constant_support_four_int_box_three_ge_evenTheorem 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…
The proof, explained
The proof establishes that the sequence $T(m)$ is nonempty (its cardinality is positive) and has zero sum (by a previously proven lemma). To show that any zero-sum sub-multiset $t \le T(m)$ with $t \ne 0$ must equal $T(m)$, the three coordinate equations of the vector sum $\sum t = 0$ are linearly combined to show that the multiplicities $(a, b, c, d)$ of the four vectors in $t$ are proportional to their total counts $(k_1, k_2, k_3, k_4)$ in $T(m)$. Using an explicit Bézout identity $\sum_{i=1}^4 c_i k_i = 1$, the ratio $q = a / k_1$ is shown to be an integer satisfying $0 \le q \le 1$. Finally, $q = 0$ is ruled out because $t \ne 0$, forcing $q = 1$ and therefore $t = T(m)$.
Definition of the four vectors and their multiplicity polynomials, cast into $\mathbb{Z}$
We introduce the integer $M = (m : \mathbb{Z}) \ge 2$, define the four basis vectors $v_1, v_2, v_3, v_4 \in \mathbb{Z}^3$, and define the counts $k_1, k_2, k_3, k_4 \in \mathbb{N}$ as polynomials in $m$. To ensure that the truncated subtractions in $\mathbb{N}$ match the ordinary integer subtractions, we verify the required inequalities via non-linear arithmetic (`nlinarith`) and cast the polynomial expressions into $\mathbb{Z}$ using `Nat.cast_sub`, producing the identities `hk1Z` through `hk4Z`.
uses
Nat.cast_subhave _ := heven set M : ℤ := (m : ℤ) with hM have hM2 : 2 ≤ M := by rw [hM]; exact_mod_cast hm set v1 : Fin 3 → ℤ := ![-M, -M, -M] with hv1 set v2 : Fin 3 → ℤ := ![-M, M - 1, M] with hv2 set v3 : Fin 3 → ℤ := ![M, -(M - 1), M - 1] with hv3 set v4 : Fin 3 → ℤ := ![M - 1, M, -M] with hv4 set k1 := 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 with hk1 set k2 := 4 * m ^ 3 - 4 * m ^ 2 + 2 * m with hk2 set k3 := 4 * m ^ 3 - 2 * m ^ 2 + m with hk3 set k4 := 4 * m ^ 3 - 4 * m ^ 2 + m with hk4 have hk1Z : (k1 : ℤ) = 4 * M ^ 3 - 6 * M ^ 2 + 4 * M - 1 := by rw [hk1, hM] have h1 : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have h2 : 1 ≤ 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by have : 6 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega rw [Nat.cast_sub h2] push_cast rw [Nat.cast_sub h1] push_cast ring have hk2Z : (k2 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + 2 * M := by rw [hk2, hM] have h3 : 4 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring have hk3Z : (k3 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + M := by rw [hk3, hM] have h3 : 2 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring have hk4Z : (k4 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + M := by rw [hk4, hM] have h3 : 4 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring
The sequence is a multiset sum of four pairwise distinct vectors, with an explicit counting formula
We express the sequence $S = T(m)$ as the multiset sum of $k_i$ copies of $v_i$ for $i \in \{1, 2, 3, 4\}$. Evaluating individual components shows that $v_1, v_2, v_3, v_4$ are pairwise distinct. Consequently, for any multiset composed of copies of these four vectors, the multiplicity of any element $x$ is given by `hcount`: it is the corresponding coefficient if $x$ matches one of the $v_i$, and $0$ otherwise.
uses
congrFun,Multiset.count_add,Multiset.count_replicate,eq_commhave hS : davenport_box_three_even_sequence m = Multiset.replicate k1 v1 + Multiset.replicate k2 v2 + Multiset.replicate k3 v3 + Multiset.replicate k4 v4 := rfl have h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [hv1, hv2] at this; omega have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [hv1, hv3] at this; omega have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [hv1, hv4] at this; omega have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [hv2, hv3] at this; omega have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [hv2, hv4] at this; omega have h34 : v3 ≠ v4 := by intro h; have := congrFun h 0; simp [hv3, hv4] at this; omega have hcount : ∀ (a b c d : ℕ) (x : Fin 3 → ℤ), (Multiset.replicate a v1 + Multiset.replicate b v2 + Multiset.replicate c v3 + Multiset.replicate d v4).count x = (if x = v1 then a else 0) + (if x = v2 then b else 0) + (if x = v3 then c else 0) + (if x = v4 then d else 0) := by intro a b c d x simp only [Multiset.count_add, Multiset.count_replicate, @eq_comm _ v1 x, @eq_comm _ v2 x, @eq_comm _ v3 x, @eq_comm _ v4 x]
$T(m)$ is nonempty and sums to zero in $\mathbb{Z}^3$
We split the goal `multiset_is_minimal_zero_sum` into three parts: nonemptiness, zero sum, and subsequence minimality. Nonemptiness holds because the total cardinality is strictly positive (as $k_2 = 4m^3 - 4m^2 + 2m > 0$ for $m \ge 2$). The condition that $T(m)$ sums to zero is provided by the previously established lemma `davenport_box_three_even_sequence_sum`.
uses
congrArg,Multiset.card,Multiset.card_add,Multiset.card_replicate,davenport_box_three_even_sequence_sumrefine ⟨?_, ?_, ?_⟩ · intro h have hc := congrArg Multiset.card h dsimp [davenport_box_three_even_sequence] at hc simp only [Multiset.card_add, Multiset.card_replicate] at hc have : 0 < 4 * m ^ 3 - 4 * m ^ 2 + 2 * m := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega omega · exact davenport_box_three_even_sequence_sum m hm
Any sub-multiset $t \le T(m)$ is supported on $\{v_1, v_2, v_3, v_4\}$ and its coordinate sum yields three linear equations
Let $t \le S$ be a sub-multiset with $t \ne 0$ and $\sum t = 0$. Let $a, b, c, d \in \mathbb{N}$ be the multiplicities of $v_1, v_2, v_3, v_4$ in $t$. Since every element of $t$ must belong to $S$ and $S$ contains only these four vectors, $t = a[v_1] + b[v_2] + c[v_3] + d[v_4]$ and $a \le k_1$. Expanding the zero-sum condition $\sum t = 0$ along the three coordinate axes gives three linear equations `he0`, `he1`, `he2` in the multiplicities.
uses
Multiset.count_eq_zero,Multiset.mem_of_le,Multiset.mem_add,Multiset.mem_replicate,Multiset.count_le_of_le,congrFun,Multiset.sum_add,Multiset.sum_replicate· intro t ht ht0 hts rw [hS] at ht ⊢ set a := t.count v1 set b := t.count v2 set c := t.count v3 set d := t.count v4 have hteq : t = Multiset.replicate a v1 + Multiset.replicate b v2 + Multiset.replicate c v3 + Multiset.replicate d v4 := by ext x rw [hcount] by_cases h1 : x = v1 · rw [h1, if_pos rfl, if_neg h12, if_neg h13, if_neg h14] simp only [add_zero] rfl by_cases h2 : x = v2 · rw [h2, if_neg h12.symm, if_pos rfl, if_neg h23, if_neg h24] simp only [zero_add, add_zero] rfl by_cases h3 : x = v3 · rw [h3, if_neg h13.symm, if_neg h23.symm, if_pos rfl, if_neg h34] simp only [zero_add, add_zero] rfl by_cases h4 : x = v4 · rw [h4, if_neg h14.symm, if_neg h24.symm, if_neg h34.symm, if_pos rfl] simp only [zero_add] rfl simp only [h1, h2, h3, h4, if_false, add_zero] rw [Multiset.count_eq_zero] intro hx have := Multiset.mem_of_le ht hx simp only [Multiset.mem_add, Multiset.mem_replicate] at this rcases this with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩) <;> contradiction have ha : a ≤ k1 := by have := Multiset.count_le_of_le v1 ht rwa [hcount, if_pos rfl, if_neg h12, if_neg h13, if_neg h14, add_zero, add_zero, add_zero] at this rw [hteq] at hts have he0 := congrFun hts (0 : Fin 3) have he1 := congrFun hts (1 : Fin 3) have he2 := congrFun hts (2 : Fin 3) simp [Multiset.sum_add, Multiset.sum_replicate, hv1, hv2, hv3, hv4] at he0 he1 he2
The sub-multiset multiplicities $(A, B, C, D)$ are proportional to $(K_1, K_2, K_3, K_4)$
Letting $A, B, C, D, K_1, K_2, K_3, K_4$ denote the integer casts of the multiplicities and total counts, we use linear combinations of the three coordinate equations `he0`, `he1`, `he2` to eliminate variables. This establishes the cross-multiplication identities $B K_1 = A K_2$, $C K_1 = A K_3$, and $D K_1 = A K_4$.
set A : ℤ := (a : ℤ) set B : ℤ := (b : ℤ) set C : ℤ := (c : ℤ) set D : ℤ := (d : ℤ) set K1 : ℤ := (k1 : ℤ) set K2 : ℤ := (k2 : ℤ) set K3 : ℤ := (k3 : ℤ) set K4 : ℤ := (k4 : ℤ) have hrel2 : B * K1 = A * K2 := by rw [hk1Z, hk2Z] linear_combination (2 * M ^ 2 - 2 * M + 1) * he1 + (2 * M ^ 2 - 2 * M + 1) * he2 have hrel3 : C * K1 = A * K3 := by rw [hk1Z, hk3Z] linear_combination (2 * M ^ 2 - M) * he0 + M * he1 + (2 * M ^ 2 - 2 * M + 1) * he2 have hrel4 : D * K1 = A * K4 := by rw [hk1Z, hk4Z] linear_combination (2 * M ^ 2 - 3 * M + 1) * he0 + (2 * M ^ 2 - M) * he1
A Bézout identity implies $A = K_1 q$ for an integer $q \in \{0, 1\}$
We define polynomial integer coefficients $c_1 = -1$, $c_2 = 4M^2 - 6M + 4$, $c_3 = 0$, $c_4 = -(4M^2 - 6M + 4)$ and verify by ring arithmetic that $\sum_{i=1}^4 c_i K_i = 1$. Multiplying this identity by $A$ and substituting the proportionality relations gives $A = K_1 \cdot q$, where $q = c_1 A + c_2 B + c_3 C + c_4 D \in \mathbb{Z}$. Because $K_1 > 0$ and $0 \le A \le K_1$, the ratio $q$ must satisfy $0 \le q \le 1$.
uses
Nat.cast_nonneg,Nat.cast_le.mprset c1 : ℤ := -1 set c2 : ℤ := 4 * M ^ 2 - 6 * M + 4 set c3 : ℤ := 0 set c4 : ℤ := -(4 * M ^ 2 - 6 * M + 4) have hbez : c1 * K1 + c2 * K2 + c3 * K3 + c4 * K4 = 1 := by dsimp [c1, c2, c3, c4] rw [hk1Z, hk2Z, hk3Z, hk4Z] ring have hAK1 : A = K1 * (c1 * A + c2 * B + c3 * C + c4 * D) := by calc A = A * 1 := by ring _ = A * (c1 * K1 + c2 * K2 + c3 * K3 + c4 * K4) := by rw [hbez] _ = c1 * A * K1 + c2 * (A * K2) + c3 * (A * K3) + c4 * (A * K4) := by ring _ = c1 * A * K1 + c2 * (B * K1) + c3 * (C * K1) + c4 * (D * K1) := by rw [← hrel2, ← hrel3, ← hrel4] _ = K1 * (c1 * A + c2 * B + c3 * C + c4 * D) := by ring have hK1pos : 0 < K1 := by rw [hk1Z] have : 4 * M ^ 3 - 6 * M ^ 2 + 4 * M - 1 = 2 * M ^ 2 * (2 * M - 3) + 4 * M - 1 := by ring rw [this] have : 0 ≤ 2 * M - 3 := by omega have : 0 ≤ 2 * M ^ 2 := by nlinarith have : 0 ≤ 2 * M ^ 2 * (2 * M - 3) := by nlinarith omega have hK1ne : K1 ≠ 0 := by linarith set q : ℤ := c1 * A + c2 * B + c3 * C + c4 * D have hq0 : 0 ≤ q := by have : 0 ≤ A := Nat.cast_nonneg a have : 0 ≤ K1 * q := by rw [← hAK1]; exact this nlinarith have hq1 : q ≤ 1 := by have : A ≤ K1 := Nat.cast_le.mpr ha have : K1 * q ≤ K1 * 1 := by rw [← hAK1]; linarith nlinarith
The ratio $q$ cannot be $0$ and must be $1$, which forces $t = T(m)$
Since $q \in \mathbb{Z}$ and $0 \le q \le 1$, either $q = 0$ or $q = 1$. If $q = 0$, then $A = 0$, which through the proportionality relations and $K_1 \ne 0$ forces $B = C = D = 0$; hence $a = b = c = d = 0$, giving $t = 0$, which contradicts the assumption $t \ne 0$. Thus $q = 1$, which gives $A = K_1$, and canceling $K_1$ from the proportionality relations yields $B = K_2$, $C = K_3$, and $D = K_4$. Translating back to natural numbers gives $a = k_1, b = k_2, c = k_3, d = k_4$, which proves $t = T(m)$.
uses
mul_eq_zero.mp,Nat.cast_eq_zero.mp,mul_comm,mul_right_cancel₀,Nat.cast_inj.mprcases (show q = 0 ∨ q = 1 by omega) with hq | hq · exfalso apply ht0 have hA0 : A = 0 := by rw [hAK1, hq]; ring have hB0 : B = 0 := by have : B * K1 = 0 := by rw [hrel2, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have hC0 : C = 0 := by have : C * K1 = 0 := by rw [hrel3, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have hD0 : D = 0 := by have : D * K1 = 0 := by rw [hrel4, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have ha0 : a = 0 := Nat.cast_eq_zero.mp hA0 have hb0 : b = 0 := Nat.cast_eq_zero.mp hB0 have hc0 : c = 0 := Nat.cast_eq_zero.mp hC0 have hd0 : d = 0 := Nat.cast_eq_zero.mp hD0 rw [hteq, ha0, hb0, hc0, hd0] simp · have hA1 : A = K1 := by rw [hAK1, hq]; ring have hB1 : B = K2 := by have : B * K1 = K2 * K1 := by rw [hrel2, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have hC1 : C = K3 := by have : C * K1 = K3 * K1 := by rw [hrel3, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have hD1 : D = K4 := by have : D * K1 = K4 * K1 := by rw [hrel4, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have ha1 : a = k1 := Nat.cast_inj.mp hA1 have hb1 : b = k2 := Nat.cast_inj.mp hB1 have hc1 : c = k3 := Nat.cast_inj.mp hC1 have hd1 : d = k4 := Nat.cast_inj.mp hD1 rw [hteq, ha1, hb1, hc1, hd1]
Nat.cast_sub- For natural numbers $m \le n$, the cast of their difference $(n - m)$ into an additive group with one equals the difference of their casts, $\uparrow n - \uparrow m$.
congrFun- Equal functions take equal values at the same input: if $f = g$, then $f(a) = g(a)$.
Multiset.count_add- The multiplicity of an element in a sum of multisets $s + t$ is the sum of its multiplicities in $s$ and in $t$.
Multiset.count_replicate- The multiplicity of an element $a$ in $n$ replicated copies of $b$ is $n$ if $b = a$, and $0$ otherwise.
eq_comm- Equality is symmetric: $a = b \iff b = a$.
congrArg- Functions preserve equality: if $a = b$, then $f(a) = f(b)$.
Multiset.card- The cardinality (total number of elements counted with multiplicity) of a multiset.
Multiset.card_add- The cardinality of the sum of two multisets is the sum of their cardinalities: $|s + t| = |s| + |t|$.
Multiset.card_replicate- The cardinality of $n$ replicated copies of an element is $n$.
davenport_box_three_even_sequence_sum- For any integer $m \ge 2$, the sequence $T(m)$ sums to zero in $\mathbb{Z}^3$.
Multiset.count_eq_zero- The multiplicity of an element in a multiset is zero if and only if the element is not in the multiset.
Multiset.mem_of_le- If a multiset $s$ is a sub-multiset of $t$ ($s \le t$) and $x \in s$, then $x \in t$.
Multiset.mem_add- An element belongs to the sum of two multisets $s + t$ if and only if it belongs to $s$ or to $t$.
Multiset.mem_replicate- An element $b$ belongs to $n$ copies of $a$ if and only if $n \ne 0$ and $b = a$.
Multiset.count_le_of_le- If $s \le t$, then the multiplicity of any element in $s$ is at most its multiplicity in $t$.
Multiset.sum_add- The sum of the elements in the multiset sum $s + t$ equals the sum of the elements in $s$ plus the sum of the elements in $t$.
Multiset.sum_replicate- The sum of $n$ copies of an element $a$ in an additive monoid is $n \cdot a$.
Nat.cast_nonneg- The cast of a natural number into an ordered ring is non-negative ($0 \le \uparrow n$).
Nat.cast_le.mpr- If $a \le b$ in $\mathbb{N}$, then $\uparrow a \le \uparrow b$ in $\mathbb{Z}$.
mul_eq_zero.mp- If a product is zero in a domain or with zero multiplication, at least one factor is zero ($x y = 0 \implies x = 0 \lor y = 0$).
Nat.cast_eq_zero.mp- If the integer cast of a natural number is zero ($\uparrow n = 0$), then the natural number itself is zero ($n = 0$).
mul_comm- Multiplication is commutative: $a \cdot b = b \cdot a$.
mul_right_cancel₀- In a domain, nonzero factors can be canceled on the right: if $b \ne 0$ and $a \cdot b = c \cdot b$, then $a = c$.
Nat.cast_inj.mp- Injectivity of the natural-to-integer cast: if $\uparrow a = \uparrow b$, then $a = b$.
- The hypothesis `heven : Even m` is recorded at line 3 (`have _ := heven`) but is not used in the proof; the minimality of $T(m)$ holds for all integers $m \ge 2$.
- In Step 5 (lines 113–129), the proportionality relations between multiplicities are found by the `linear_combination` tactic, which automatically determines the polynomial multipliers needed to eliminate variables from the system of coordinate equations.
- In Step 6 (lines 130–162), the Bézout identity `hbez` ($\sum_{i=1}^4 c_i K_i = 1$) is verified using polynomial ring arithmetic (`ring`).
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_box_three_even_sequence_minimal (m : ℕ) (hm : 2 ≤ m) (heven : Even m) : multiset_is_minimal_zero_sum (davenport_box_three_even_sequence m) := by have _ := heven set M : ℤ := (m : ℤ) with hM have hM2 : 2 ≤ M := by rw [hM]; exact_mod_cast hm set v1 : Fin 3 → ℤ := ![-M, -M, -M] with hv1 set v2 : Fin 3 → ℤ := ![-M, M - 1, M] with hv2 set v3 : Fin 3 → ℤ := ![M, -(M - 1), M - 1] with hv3 set v4 : Fin 3 → ℤ := ![M - 1, M, -M] with hv4 set k1 := 4 * m ^ 3 - 6 * m ^ 2 + 4 * m - 1 with hk1 set k2 := 4 * m ^ 3 - 4 * m ^ 2 + 2 * m with hk2 set k3 := 4 * m ^ 3 - 2 * m ^ 2 + m with hk3 set k4 := 4 * m ^ 3 - 4 * m ^ 2 + m with hk4 have hk1Z : (k1 : ℤ) = 4 * M ^ 3 - 6 * M ^ 2 + 4 * M - 1 := by rw [hk1, hM] have h1 : 6 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith have h2 : 1 ≤ 4 * m ^ 3 - 6 * m ^ 2 + 4 * m := by have : 6 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega rw [Nat.cast_sub h2] push_cast rw [Nat.cast_sub h1] push_cast ring have hk2Z : (k2 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + 2 * M := by rw [hk2, hM] have h3 : 4 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring have hk3Z : (k3 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + M := by rw [hk3, hM] have h3 : 2 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring have hk4Z : (k4 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + M := by rw [hk4, hM] have h3 : 4 * m ^ 2 ≤ 4 * m ^ 3 := by nlinarith push_cast rw [Nat.cast_sub h3] push_cast ring have hS : davenport_box_three_even_sequence m = Multiset.replicate k1 v1 + Multiset.replicate k2 v2 + Multiset.replicate k3 v3 + Multiset.replicate k4 v4 := rfl have h12 : v1 ≠ v2 := by intro h; have := congrFun h 1; simp [hv1, hv2] at this; omega have h13 : v1 ≠ v3 := by intro h; have := congrFun h 0; simp [hv1, hv3] at this; omega have h14 : v1 ≠ v4 := by intro h; have := congrFun h 1; simp [hv1, hv4] at this; omega have h23 : v2 ≠ v3 := by intro h; have := congrFun h 0; simp [hv2, hv3] at this; omega have h24 : v2 ≠ v4 := by intro h; have := congrFun h 2; simp [hv2, hv4] at this; omega have h34 : v3 ≠ v4 := by intro h; have := congrFun h 0; simp [hv3, hv4] at this; omega have hcount : ∀ (a b c d : ℕ) (x : Fin 3 → ℤ), (Multiset.replicate a v1 + Multiset.replicate b v2 + Multiset.replicate c v3 + Multiset.replicate d v4).count x = (if x = v1 then a else 0) + (if x = v2 then b else 0) + (if x = v3 then c else 0) + (if x = v4 then d else 0) := by intro a b c d x simp only [Multiset.count_add, Multiset.count_replicate, @eq_comm _ v1 x, @eq_comm _ v2 x, @eq_comm _ v3 x, @eq_comm _ v4 x] refine ⟨?_, ?_, ?_⟩ · intro h have hc := congrArg Multiset.card h dsimp [davenport_box_three_even_sequence] at hc simp only [Multiset.card_add, Multiset.card_replicate] at hc have : 0 < 4 * m ^ 3 - 4 * m ^ 2 + 2 * m := by have : 4 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega omega · exact davenport_box_three_even_sequence_sum m hm · intro t ht ht0 hts rw [hS] at ht ⊢ set a := t.count v1 set b := t.count v2 set c := t.count v3 set d := t.count v4 have hteq : t = Multiset.replicate a v1 + Multiset.replicate b v2 + Multiset.replicate c v3 + Multiset.replicate d v4 := by ext x rw [hcount] by_cases h1 : x = v1 · rw [h1, if_pos rfl, if_neg h12, if_neg h13, if_neg h14] simp only [add_zero] rfl by_cases h2 : x = v2 · rw [h2, if_neg h12.symm, if_pos rfl, if_neg h23, if_neg h24] simp only [zero_add, add_zero] rfl by_cases h3 : x = v3 · rw [h3, if_neg h13.symm, if_neg h23.symm, if_pos rfl, if_neg h34] simp only [zero_add, add_zero] rfl by_cases h4 : x = v4 · rw [h4, if_neg h14.symm, if_neg h24.symm, if_neg h34.symm, if_pos rfl] simp only [zero_add] rfl simp only [h1, h2, h3, h4, if_false, add_zero] rw [Multiset.count_eq_zero] intro hx have := Multiset.mem_of_le ht hx simp only [Multiset.mem_add, Multiset.mem_replicate] at this rcases this with (((⟨_, rfl⟩ | ⟨_, rfl⟩) | ⟨_, rfl⟩) | ⟨_, rfl⟩) <;> contradiction have ha : a ≤ k1 := by have := Multiset.count_le_of_le v1 ht rwa [hcount, if_pos rfl, if_neg h12, if_neg h13, if_neg h14, add_zero, add_zero, add_zero] at this rw [hteq] at hts have he0 := congrFun hts (0 : Fin 3) have he1 := congrFun hts (1 : Fin 3) have he2 := congrFun hts (2 : Fin 3) simp [Multiset.sum_add, Multiset.sum_replicate, hv1, hv2, hv3, hv4] at he0 he1 he2 set A : ℤ := (a : ℤ) set B : ℤ := (b : ℤ) set C : ℤ := (c : ℤ) set D : ℤ := (d : ℤ) set K1 : ℤ := (k1 : ℤ) set K2 : ℤ := (k2 : ℤ) set K3 : ℤ := (k3 : ℤ) set K4 : ℤ := (k4 : ℤ) have hrel2 : B * K1 = A * K2 := by rw [hk1Z, hk2Z] linear_combination (2 * M ^ 2 - 2 * M + 1) * he1 + (2 * M ^ 2 - 2 * M + 1) * he2 have hrel3 : C * K1 = A * K3 := by rw [hk1Z, hk3Z] linear_combination (2 * M ^ 2 - M) * he0 + M * he1 + (2 * M ^ 2 - 2 * M + 1) * he2 have hrel4 : D * K1 = A * K4 := by rw [hk1Z, hk4Z] linear_combination (2 * M ^ 2 - 3 * M + 1) * he0 + (2 * M ^ 2 - M) * he1 set c1 : ℤ := -1 set c2 : ℤ := 4 * M ^ 2 - 6 * M + 4 set c3 : ℤ := 0 set c4 : ℤ := -(4 * M ^ 2 - 6 * M + 4) have hbez : c1 * K1 + c2 * K2 + c3 * K3 + c4 * K4 = 1 := by dsimp [c1, c2, c3, c4] rw [hk1Z, hk2Z, hk3Z, hk4Z] ring have hAK1 : A = K1 * (c1 * A + c2 * B + c3 * C + c4 * D) := by calc A = A * 1 := by ring _ = A * (c1 * K1 + c2 * K2 + c3 * K3 + c4 * K4) := by rw [hbez] _ = c1 * A * K1 + c2 * (A * K2) + c3 * (A * K3) + c4 * (A * K4) := by ring _ = c1 * A * K1 + c2 * (B * K1) + c3 * (C * K1) + c4 * (D * K1) := by rw [← hrel2, ← hrel3, ← hrel4] _ = K1 * (c1 * A + c2 * B + c3 * C + c4 * D) := by ring have hK1pos : 0 < K1 := by rw [hk1Z] have : 4 * M ^ 3 - 6 * M ^ 2 + 4 * M - 1 = 2 * M ^ 2 * (2 * M - 3) + 4 * M - 1 := by ring rw [this] have : 0 ≤ 2 * M - 3 := by omega have : 0 ≤ 2 * M ^ 2 := by nlinarith have : 0 ≤ 2 * M ^ 2 * (2 * M - 3) := by nlinarith omega have hK1ne : K1 ≠ 0 := by linarith set q : ℤ := c1 * A + c2 * B + c3 * C + c4 * D have hq0 : 0 ≤ q := by have : 0 ≤ A := Nat.cast_nonneg a have : 0 ≤ K1 * q := by rw [← hAK1]; exact this nlinarith have hq1 : q ≤ 1 := by have : A ≤ K1 := Nat.cast_le.mpr ha have : K1 * q ≤ K1 * 1 := by rw [← hAK1]; linarith nlinarith rcases (show q = 0 ∨ q = 1 by omega) with hq | hq · exfalso apply ht0 have hA0 : A = 0 := by rw [hAK1, hq]; ring have hB0 : B = 0 := by have : B * K1 = 0 := by rw [hrel2, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have hC0 : C = 0 := by have : C * K1 = 0 := by rw [hrel3, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have hD0 : D = 0 := by have : D * K1 = 0 := by rw [hrel4, hA0, zero_mul] exact mul_eq_zero.mp this |>.resolve_right hK1ne have ha0 : a = 0 := Nat.cast_eq_zero.mp hA0 have hb0 : b = 0 := Nat.cast_eq_zero.mp hB0 have hc0 : c = 0 := Nat.cast_eq_zero.mp hC0 have hd0 : d = 0 := Nat.cast_eq_zero.mp hD0 rw [hteq, ha0, hb0, hc0, hd0] simp · have hA1 : A = K1 := by rw [hAK1, hq]; ring have hB1 : B = K2 := by have : B * K1 = K2 * K1 := by rw [hrel2, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have hC1 : C = K3 := by have : C * K1 = K3 * K1 := by rw [hrel3, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have hD1 : D = K4 := by have : D * K1 = K4 * K1 := by rw [hrel4, hA1, mul_comm] exact mul_right_cancel₀ hK1ne this have ha1 : a = k1 := Nat.cast_inj.mp hA1 have hb1 : b = k2 := Nat.cast_inj.mp hB1 have hc1 : c = k3 := Nat.cast_inj.mp hC1 have hd1 : d = k4 := Nat.cast_inj.mp hD1 rw [hteq, ha1, hb1, hc1, hd1]