davenport_box_three_odd_sequence_minimal
For m ≥ 2 odd, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
Statement
theorem davenport_box_three_odd_sequence_minimal (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) :
multiset_is_minimal_zero_sum (davenport_box_three_odd_sequence m)- Source
- The core of the proof of Theorem 3 of arXiv:2610.16562 (odd m).
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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_sumThe sequence T(m) (odd 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_oddTheorem 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…
The proof, explained
To show that T(m) is a minimal zero-sum sequence for odd m ≥ 2, the proof first verifies that T(m) is nonempty (its cardinality is positive) and that its elements sum to zero. For any nonempty zero-sum sub-multiset t ≤ T(m) with vector multiplicities a, b, c, d, the coordinate-wise zero-sum equations imply that the vector of counts (a, b, c, d) is proportional to (k₁, k₂, k₃, k₄). Because m is odd, an explicit integer Bézout relation c₁ k₁ + c₂ k₂ + c₃ k₃ = 1 holds, showing that a must be an integer multiple of k₁, say a = q k₁. The bounds 0 ≤ a ≤ k₁ and k₁ > 0 force q ∈ {0, 1}; q = 0 contradicts nonemptiness of t, while q = 1 forces t = T(m).
Define the sequence parameters, the four vectors, their multiplicities, and verify their integer casts.
Set M = (m : ℤ) ≥ 2. Define the four vectors v₁ = (-M, -M, -M), v₂ = (-M, M-1, M), v₃ = (M, -M, M-2), and v₄ = (M-1, M, -M) in ℤ³. Define the natural number counts k₁, k₂, k₃, k₄ and verify with helper lemmas davenport_box_three_odd_sequence_sum_cast1 through cast4 that their integer casts equal the corresponding polynomials in M. Identify T(m) as the multiset sum of kᵢ copies of vᵢ.
uses
davenport_box_three_odd_sequence_sum_cast1,davenport_box_three_odd_sequence_sum_cast2,davenport_box_three_odd_sequence_sum_cast3,davenport_box_three_odd_sequence_sum_cast4set 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, M - 2] with hv3 set v4 : Fin 3 → ℤ := ![M - 1, M, -M] with hv4 set k1 := 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 with hk1 set k2 := 4 * m ^ 3 - 2 * 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 + 2 * m with hk4 have hk1Z : (k1 : ℤ) = 4 * M ^ 3 - 8 * M ^ 2 + 5 * M - 2 := by rw [hk1, hM]; exact davenport_box_three_odd_sequence_sum_cast1 m hm have hk2Z : (k2 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + 2 * M := by rw [hk2, hM]; exact davenport_box_three_odd_sequence_sum_cast2 m hm have hk3Z : (k3 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + M := by rw [hk3, hM]; exact davenport_box_three_odd_sequence_sum_cast3 m hm have hk4Z : (k4 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + 2 * M := by rw [hk4, hM]; exact davenport_box_three_odd_sequence_sum_cast4 m hm have hS : davenport_box_three_odd_sequence m = Multiset.replicate k1 v1 + Multiset.replicate k2 v2 + Multiset.replicate k3 v3 + Multiset.replicate k4 v4 := rfl
The four vectors v₁, v₂, v₃, v₄ are pairwise distinct.
Assume for contradiction that two vectors are equal. Evaluating both vectors at a coordinate where they differ via congrFun gives an integer equality (such as -M = M - 1 or -M = M) that cannot hold for M ≥ 2, which linear integer arithmetic (omega) refutes.
uses
congrFunhave 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 1; simp [hv3, hv4] at this; omega
The count of any vector in a multiset sum of replicates of v₁, v₂, v₃, v₄ is the sum of the counts of the vectors that match it.
By induction on multiset addition (Multiset.count_add) and replication (Multiset.count_replicate), the count of any x in a • v₁ + b • v₂ + c • v₃ + d • v₄ is (if x = v₁ then a else 0) + (if x = v₂ then b else 0) + (if x = v₃ then c else 0) + (if x = v₄ then d else 0).
uses
Multiset.count_add,Multiset.count_replicate,eq_commhave 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]
To prove T(m) is a minimal zero-sum sequence, it suffices to prove nonemptiness, zero sum, and minimality.
By definition of multiset_is_minimal_zero_sum, we split the goal into three subgoals: T(m) ≠ 0, T(m).sum = 0, and any nonempty zero-sum sub-multiset t ≤ T(m) equals T(m).
refine ⟨?_, ?_, ?_⟩The sequence T(m) is nonempty.
If T(m) = 0, taking multiset cardinality via congrArg would mean the sum of the four counts is 0. But k₂ = 4m³ - 2m² + 2m is strictly positive for m ≥ 2, a contradiction.
uses
congrArg,Multiset.card_add,Multiset.card_replicate· intro h have hc := congrArg Multiset.card h dsimp [davenport_box_three_odd_sequence] at hc simp only [Multiset.card_add, Multiset.card_replicate] at hc have : 0 < 4 * m ^ 3 - 2 * m ^ 2 + 2 * m := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega omega
The sequence T(m) sums to zero.
This is established directly by the lemma davenport_box_three_odd_sequence_sum.
uses
davenport_box_three_odd_sequence_sum· exact davenport_box_three_odd_sequence_sum m hmAny sub-multiset t ≤ T(m) is of the form a • v₁ + b • v₂ + c • v₃ + d • v₄ with a ≤ k₁.
Let a, b, c, d be the multiplicities of v₁, v₂, v₃, v₄ in t. Since every element of t must be in T(m) (Multiset.mem_of_le), no other vector can occur in t, so t = a • v₁ + b • v₂ + c • v₃ + d • v₄. In addition, t ≤ T(m) implies a ≤ k₁ (Multiset.count_le_of_le).
uses
if_pos,if_neg,add_zero,zero_add,if_false,Multiset.count_eq_zero,Multiset.mem_of_le,Multiset.mem_add,Multiset.mem_replicate,Multiset.count_le_of_le· 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
The counts A, B, C, D are proportional to K₁, K₂, K₃, K₄.
Evaluating the zero-sum condition t.sum = 0 at coordinates 0, 1, and 2 yields three integer linear equations. Taking suitable linear combinations of these equations eliminates variables to prove B * K₁ = A * K₂, C * K₁ = A * K₃, and D * K₁ = A * K₄.
uses
congrFun,Multiset.sum_add,Multiset.sum_replicaterw [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) * he0 + (2 * M ^ 2 - 3 * M + 2) * he1 + (2 * M ^ 2 - M) * 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 + 2) * he0 + (2 * M ^ 2 - 2 * M) * he1 + M * he2
There exist integers c₁, c₂, c₃ such that c₁ K₁ + c₂ K₂ + c₃ K₃ = 1, and consequently A = K₁ * (c₁ A + c₂ B + c₃ C).
Since m is odd, write M = 2j + 1. Setting c₁ = j, c₂ = 1 - j(4M² - 8M + 5), and c₃ = -c₂, polynomial algebra verifies the Bézout identity c₁ K₁ + c₂ K₂ + c₃ K₃ = 1. Multiplying this identity by A and substituting the proportionality relations B * K₁ = A * K₂ and C * K₁ = A * K₃ shows that A = K₁ * (c₁ A + c₂ B + c₃ C).
obtain ⟨j, hj⟩ : ∃ j : ℤ, M = 2 * j + 1 := by obtain ⟨j, rfl⟩ := hodd use (j : ℤ) rw [hM] push_cast ring set c1 : ℤ := j set c2 : ℤ := 1 - j * (4 * M ^ 2 - 8 * M + 5) set c3 : ℤ := -c2 have hbez : c1 * K1 + c2 * K2 + c3 * K3 = 1 := by dsimp [c1, c2, c3] rw [hk1Z, hk2Z, hk3Z, hj] ring have hAK1 : A = K1 * (c1 * A + c2 * B + c3 * C) := by calc A = A * 1 := by ring _ = A * (c1 * K1 + c2 * K2 + c3 * K3) := by rw [hbez] _ = c1 * A * K1 + c2 * (A * K2) + c3 * (A * K3) := by ring _ = c1 * A * K1 + c2 * (B * K1) + c3 * (C * K1) := by rw [← hrel2, ← hrel3] _ = K1 * (c1 * A + c2 * B + c3 * C) := by ring
The integer q = c₁ A + c₂ B + c₃ C satisfies 0 ≤ q ≤ 1.
Rewriting K₁ as 4M²(M - 2) + 5M - 2 shows K₁ > 0 for M ≥ 2, hence K₁ ≠ 0. Because 0 ≤ A ≤ K₁ and A = K₁ * q with K₁ > 0, dividing by K₁ implies 0 ≤ q ≤ 1.
uses
mul_nonneg,Nat.cast_nonneg,Nat.cast_le.mprhave hK1pos : 0 < K1 := by rw [hk1Z] have : 4 * M ^ 3 - 8 * M ^ 2 + 5 * M - 2 = 4 * M ^ 2 * (M - 2) + 5 * M - 2 := by ring rw [this] have h1 : 0 ≤ M - 2 := by linarith have h2 : 0 ≤ 4 * M ^ 2 := by nlinarith have h3 : 0 ≤ 4 * M ^ 2 * (M - 2) := mul_nonneg h2 h1 linarith have hK1ne : K1 ≠ 0 := by linarith set q : ℤ := c1 * A + c2 * B + c3 * C 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 case q = 0 is impossible.
If q = 0, then A = K₁ * 0 = 0. The proportionality relations then force B = C = D = 0 since K₁ ≠ 0. Thus a = b = c = d = 0, meaning t = 0, which contradicts the hypothesis t ≠ 0.
uses
zero_mul,mul_eq_zero.mp,Nat.cast_eq_zero.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
The case q = 1 forces t = T(m).
If q = 1, then A = K₁. Cancelling K₁ ≠ 0 in the proportionality relations gives B = K₂, C = K₃, and D = K₄. Injectivity of the cast from ℕ to ℤ yields a = k₁, b = k₂, c = k₃, and d = k₄, so t = T(m).
uses
mul_comm,mul_right_cancel₀,Nat.cast_inj.mp· 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]
congrFun- Equal functions evaluate to equal values at any argument: if f = g then f a = g a.
congrArg- A function applied to equal arguments yields equal values: if a₁ = a₂ then f a₁ = f a₂.
eq_comm- Equality is symmetric: a = b ↔ b = a.
Multiset.count_add- The multiplicity of an element in the sum of two multisets is the sum of its multiplicities in each.
Multiset.count_replicate- The multiplicity of a in n copies of b is n if b = a, and 0 otherwise.
Multiset.card_add- The cardinality of the sum of two multisets is the sum of their cardinalities.
Multiset.card_replicate- A multiset of n replicated copies of an element has cardinality n.
Multiset.count_eq_zero- An element has multiplicity zero in a multiset if and only if it does not belong to the multiset.
Multiset.mem_of_le- If s ≤ t as multisets, then any element of s is an element of t.
Multiset.mem_add- An element belongs to s + t if and only if it belongs to s or to t.
Multiset.mem_replicate- An element belongs to n copies of a if and only if n ≠ 0 and the element equals a.
Multiset.count_le_of_le- If s ≤ 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 s + t is the sum of the sum of s and the sum of t.
Multiset.sum_replicate- The sum of n copies of an element a is n • a.
davenport_box_three_odd_sequence_sum_cast1- For m ≥ 2, the integer cast of 4m³ - 8m² + 5m - 2 equals 4M³ - 8M² + 5M - 2.
davenport_box_three_odd_sequence_sum_cast2- For m ≥ 2, the integer cast of 4m³ - 2m² + 2m equals 4M³ - 2M² + 2M.
davenport_box_three_odd_sequence_sum_cast3- For m ≥ 2, the integer cast of 4m³ - 2m² + m equals 4M³ - 2M² + M.
davenport_box_three_odd_sequence_sum_cast4- For m ≥ 2, the integer cast of 4m³ - 4m² + 2m equals 4M³ - 4M² + 2M.
davenport_box_three_odd_sequence_sum- For m ≥ 2, the sequence T(m) sums to zero.
if_pos- An if-then-else expression evaluates to the then-branch when the condition is true.
if_neg- An if-then-else expression evaluates to the else-branch when the condition is false.
if_false- An if-then-else expression with condition False evaluates to the else-branch.
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a.
zero_add- Adding zero on the left leaves an element unchanged: 0 + a = a.
mul_nonneg- The product of two non-negative elements is non-negative.
Nat.cast_nonneg- The cast of any natural number to an ordered ring is non-negative.
Nat.cast_le.mpr- An inequality between natural numbers is preserved under integer cast: a ≤ b implies ↑a ≤ ↑b.
zero_mul- Multiplying by zero on the left yields zero: 0 * a = 0.
mul_eq_zero.mp- If a product is zero, at least one of the factors is zero: a * b = 0 implies a = 0 or b = 0.
Nat.cast_eq_zero.mp- If the integer cast of a natural number is zero, the natural number itself is zero.
mul_comm- Multiplication is commutative: a * b = b * a.
mul_right_cancel₀- A non-zero factor on the right can be cancelled in a multiplication: b ≠ 0 and a * b = c * b imply a = c.
Nat.cast_inj.mp- The cast from natural numbers to integers is injective: ↑a = ↑b implies a = b.
- The Bézout identity c₁ K₁ + c₂ K₂ + c₃ K₃ = 1 and the proportionality relations are verified in Lean using algebraic automation (ring and linear_combination) rather than explicit step-by-step polynomial division.
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_odd_sequence_minimal (m : ℕ) (hm : 2 ≤ m) (hodd : Odd m) : multiset_is_minimal_zero_sum (davenport_box_three_odd_sequence m) := by 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, M - 2] with hv3 set v4 : Fin 3 → ℤ := ![M - 1, M, -M] with hv4 set k1 := 4 * m ^ 3 - 8 * m ^ 2 + 5 * m - 2 with hk1 set k2 := 4 * m ^ 3 - 2 * 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 + 2 * m with hk4 have hk1Z : (k1 : ℤ) = 4 * M ^ 3 - 8 * M ^ 2 + 5 * M - 2 := by rw [hk1, hM]; exact davenport_box_three_odd_sequence_sum_cast1 m hm have hk2Z : (k2 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + 2 * M := by rw [hk2, hM]; exact davenport_box_three_odd_sequence_sum_cast2 m hm have hk3Z : (k3 : ℤ) = 4 * M ^ 3 - 2 * M ^ 2 + M := by rw [hk3, hM]; exact davenport_box_three_odd_sequence_sum_cast3 m hm have hk4Z : (k4 : ℤ) = 4 * M ^ 3 - 4 * M ^ 2 + 2 * M := by rw [hk4, hM]; exact davenport_box_three_odd_sequence_sum_cast4 m hm have hS : davenport_box_three_odd_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 1; 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_odd_sequence] at hc simp only [Multiset.card_add, Multiset.card_replicate] at hc have : 0 < 4 * m ^ 3 - 2 * m ^ 2 + 2 * m := by have : 2 * m ^ 2 < 4 * m ^ 3 := by nlinarith omega omega · exact davenport_box_three_odd_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) * he0 + (2 * M ^ 2 - 3 * M + 2) * he1 + (2 * M ^ 2 - M) * 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 + 2) * he0 + (2 * M ^ 2 - 2 * M) * he1 + M * he2 obtain ⟨j, hj⟩ : ∃ j : ℤ, M = 2 * j + 1 := by obtain ⟨j, rfl⟩ := hodd use (j : ℤ) rw [hM] push_cast ring set c1 : ℤ := j set c2 : ℤ := 1 - j * (4 * M ^ 2 - 8 * M + 5) set c3 : ℤ := -c2 have hbez : c1 * K1 + c2 * K2 + c3 * K3 = 1 := by dsimp [c1, c2, c3] rw [hk1Z, hk2Z, hk3Z, hj] ring have hAK1 : A = K1 * (c1 * A + c2 * B + c3 * C) := by calc A = A * 1 := by ring _ = A * (c1 * K1 + c2 * K2 + c3 * K3) := by rw [hbez] _ = c1 * A * K1 + c2 * (A * K2) + c3 * (A * K3) := by ring _ = c1 * A * K1 + c2 * (B * K1) + c3 * (C * K1) := by rw [← hrel2, ← hrel3] _ = K1 * (c1 * A + c2 * B + c3 * C) := by ring have hK1pos : 0 < K1 := by rw [hk1Z] have : 4 * M ^ 3 - 8 * M ^ 2 + 5 * M - 2 = 4 * M ^ 2 * (M - 2) + 5 * M - 2 := by ring rw [this] have h1 : 0 ≤ M - 2 := by linarith have h2 : 0 ≤ 4 * M ^ 2 := by nlinarith have h3 : 0 ≤ 4 * M ^ 2 * (M - 2) := mul_nonneg h2 h1 linarith have hK1ne : K1 ≠ 0 := by linarith set q : ℤ := c1 * A + c2 * B + c3 * C 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]