davenport_constant_int_box_two_ge
For every m ≥ 2, the Davenport constant of the box ⟦−m, m⟧² is at least 4m² − q(m), q(m) the smallest prime not dividing m: S(m) is a minimal zero-sum sequence of that length.
Statement
theorem davenport_constant_int_box_two_ge (m : ℕ) (hm : 2 ≤ m) :
((4 * m ^ 2 - nat_least_prime_not_dvd m : ℕ) : ℕ∞) ≤
davenport_constant (↑(int_box_two m) : Set (ℤ × ℤ))- Formalizes
- arXiv:2610.16562 (The Davenport constant of low-dimensional boxes), Corollary 2 (via Theorem 1's sequence S(m)); the proof here checks minimality of S(m) directly.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- davenport_constantThe Davenport constant D(X) of a subset X of an abelian group: the supremum (in ℕ ∪ {∞}) of the lengths of minimal zero-sum sequences with…
- int_box_twoThe two-dimensional integer box ⟦−m, m⟧² = {(x, y) ∈ ℤ² : |x|, |y| ≤ m}.
- nat_least_prime_not_dvdq(m): the smallest prime number not dividing m (0 by convention for m = 0, which no prime fails to divide).
- davenport_box_extremal_sequenceThe sequence S(m): q(m)(m−1)+m copies of (m, m), 2m² − m·q(m) copies of (−m, m−1), and 2m² − m copies of (m − q(m), −m).
- 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.
- int_box_extremal_sequence_countsIf integers A, B, C with 0 ≤ C ≤ M(2M−1) satisfy A·(M, M) + B·(−M, M−1) + C·(M−Q, −M) = 0, where M ≥ 2, gcd(M, Q) = 1 and gcd(2M−1, 2M−Q)…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
To prove that the Davenport constant of the box ⟦-m, m⟧² is at least 4m² - q(m), where q(m) is the smallest prime not dividing m, the proof constructs an explicit minimal zero-sum sequence S(m) of that length. The sequence is supported on three vectors: v₁ = (m, m), v₂ = (-m, m - 1), and v₃ = (m - q, -m), which lie in the box because Bertrand's postulate guarantees q < 2m. Multiplicities k₁, k₂, k₃ are chosen to yield a zero sum of total length 4m² - q, and minimality is established by showing via Diophantine coprimality arguments that the zero-sum system has no non-trivial proper submultiset solutions.
The smallest prime not dividing m, denoted q, is well-defined, prime, satisfies q ∤ m, is minimal among such primes, and satisfies q ≥ 2.
By the infinitude of primes (Nat.exists_infinite_primes), there is a prime p ≥ m + 1, which cannot divide m (Nat.le_of_dvd), so the set of primes not dividing m is nonempty. Its infimum q belongs to the set (Nat.sInf_mem), is minimal (Nat.sInf_le), and satisfies q ≥ 2 since all primes are at least 2.
uses
Nat.exists_infinite_primes,Nat.le_of_dvd,Nat.sInf_mem,Nat.sInf_leset q := nat_least_prime_not_dvd m with hqdef -- the smallest prime not dividing `m` have hne : {p | p.Prime ∧ ¬ p ∣ m}.Nonempty := by obtain ⟨p, hp1, hp2⟩ := Nat.exists_infinite_primes (m + 1) exact ⟨p, hp2, fun h => by have := Nat.le_of_dvd (by omega) h; omega⟩ have hq : q.Prime ∧ ¬ q ∣ m := Nat.sInf_mem hne have hqmin : ∀ p, p.Prime → ¬ p ∣ m → q ≤ p := fun p hp hpd => Nat.sInf_le ⟨hp, hpd⟩ have hq2 : 2 ≤ q := hq.1.two_le
q < 2m, and every prime p < q divides m.
By Bertrand's postulate (Nat.exists_prime_lt_and_le_two_mul), there is a prime p with m < p ≤ 2m. Since p > m, p cannot divide m, so q ≤ p ≤ 2m by the minimality of q. If q = 2m, then 2m is prime, forcing m = 1 (Nat.prime_mul_iff), contradicting m ≥ 2; hence q < 2m. Furthermore, any prime strictly less than q must divide m, as otherwise q would not be the smallest prime not dividing m.
uses
Nat.exists_prime_lt_and_le_two_mul,Nat.prime_mul_iffhave hqle : q ≤ 2 * m := by obtain ⟨p, hp, hmp, hp2m⟩ := Nat.exists_prime_lt_and_le_two_mul m (by omega) exact (hqmin p hp (fun h => by have := Nat.le_of_dvd (by omega) h; omega)).trans hp2m have hqne : q ≠ 2 * m := by intro h have := hq.1 rw [h, Nat.prime_mul_iff] at this rcases this with ⟨_, h1⟩ | ⟨_, h1⟩ <;> omega have hsmall : ∀ p, p.Prime → p < q → p ∣ m := by intro p hp hpq by_contra hpd exact absurd (hqmin p hp hpd) (by omega)
2m - 1 and q - 1 are coprime, and q and m are coprime.
Any common prime divisor p of 2m - 1 and q - 1 would satisfy p ≤ q - 1 < q, so p ∣ m. Then p divides 2m and 2m - 1, hence divides their difference 2m - (2m - 1) = 1 (Nat.dvd_sub), impossible for a prime. Thus 2m - 1 and q - 1 are coprime (Nat.coprime_of_dvd). Similarly, q and m are coprime because q is prime and does not divide m (Nat.Prime.coprime_iff_not_dvd).
uses
Nat.coprime_of_dvd,Nat.dvd_sub,dvd_mul_of_dvd_right,Nat.Prime.coprime_iff_not_dvdhave hcop1 : Nat.Coprime (2 * m - 1) (q - 1) := by apply Nat.coprime_of_dvd intro p hp h1 h2 have hpq : p < q := by have := Nat.le_of_dvd (by omega) h2 omega have hpm := hsmall p hp hpq have : p ∣ 2 * m - (2 * m - 1) := Nat.dvd_sub (dvd_mul_of_dvd_right hpm 2) h1 rw [show 2 * m - (2 * m - 1) = 1 by omega] at this exact hp.one_lt.ne' (Nat.dvd_one.1 this) have hcopqm : Nat.Coprime q m := (Nat.Prime.coprime_iff_not_dvd hq.1).2 hq.2
The integer counterparts M = (m : ℤ) and Q = (q : ℤ) satisfy 2 ≤ M, 2 ≤ Q, Q < 2M, IsCoprime (2M - 1) (2M - Q), and IsCoprime M Q.
The inequalities follow by casting from ℕ. The integer coprimality IsCoprime (2M - 1) (2M - Q) follows from the coprimality of 2m - 1 and q - 1 because 2M - Q = (2M - 1) + (-1)(Q - 1) and adding a multiple of (2M - 1) preserves coprimality (IsCoprime.add_mul_left_right). Integer coprimality of M and Q follows similarly from q and m being coprime.
uses
lt_of_le_of_ne,Nat.cast_sub,IsCoprime.add_mul_left_right-- integer versions set M : ℤ := (m : ℤ) with hM set Q : ℤ := (q : ℤ) with hQ have hM2 : 2 ≤ M := by rw [hM]; exact_mod_cast hm have hQ2 : 2 ≤ Q := by rw [hQ]; exact_mod_cast hq2 have hQle : Q < 2 * M := by rw [hM, hQ]; exact_mod_cast (lt_of_le_of_ne hqle hqne) have hcopZ : IsCoprime (2 * M - 1) (2 * M - Q) := by have h1 : IsCoprime ((2 * m - 1 : ℕ) : ℤ) ((q - 1 : ℕ) : ℤ) := Nat.isCoprime_iff_coprime.2 hcop1 push_cast [Nat.cast_sub (show 1 ≤ 2 * m by omega), Nat.cast_sub (show 1 ≤ q by omega)] at h1 have : 2 * M - Q = (2 * M - 1) + (-1) * (Q - 1) := by ring rw [this] exact (h1.neg_right.mul_add_left_right 1).symm.symm |> fun h => by simpa [add_comm, mul_comm] using (IsCoprime.add_mul_left_right h1.neg_right 1) have hcopMQ : IsCoprime M Q := by rw [hM, hQ]; exact Nat.isCoprime_iff_coprime.2 hcopqm.symm
The candidate extremal sequence S(m) is defined as the multiset k₁ • v₁ + k₂ • v₂ + k₃ • v₃ with v₁ = (M, M), v₂ = (-M, M - 1), v₃ = (M - Q, -M), where k₁ = Q(M - 1) + M, k₂ = M(2M - Q), and k₃ = M(2M - 1).
The vectors v₁, v₂, v₃ in ℤ² and their natural multiplicities k₁, k₂, k₃ are set, and their integer values are cast and simplified algebraically. S(m) is defined by replicate additions of these vectors.
uses
Nat.cast_subset v₁ : ℤ × ℤ := (M, M) with hv₁ set v₂ : ℤ × ℤ := (-M, M - 1) with hv₂ set v₃ : ℤ × ℤ := (M - Q, -M) with hv₃ set k₁ := q * (m - 1) + m with hk₁ set k₂ := 2 * m ^ 2 - m * q with hk₂ set k₃ := 2 * m ^ 2 - m with hk₃ have hk₁Z : (k₁ : ℤ) = Q * (M - 1) + M := by rw [hk₁]; push_cast [Nat.cast_sub (show 1 ≤ m by omega)]; ring have hk₂Z : (k₂ : ℤ) = M * (2 * M - Q) := by rw [hk₂] have : m * q ≤ 2 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this]; ring have hk₃Z : (k₃ : ℤ) = M * (2 * M - 1) := by rw [hk₃] have : m ≤ 2 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this]; ring have hS : davenport_box_extremal_sequence m = Multiset.replicate k₁ v₁ + Multiset.replicate k₂ v₂ + Multiset.replicate k₃ v₃ := rfl
The vectors v₁, v₂, v₃ are pairwise distinct, and the sum and counts of a v₁ + b v₂ + c v₃ are given by explicit formulas.
Comparing coordinates confirms v₁ ≠ v₂, v₁ ≠ v₃, and v₂ ≠ v₃. The multiset sum distributes over replication and addition to yield (aM - bM + c(M - Q), aM + b(M - 1) - cM), and the element count of x in such a sum is a if x = v₁, b if x = v₂, c if x = v₃, and 0 otherwise.
have h12 : v₁ ≠ v₂ := by intro h; have := congrArg Prod.fst h; simp only [hv₁, hv₂] at this; omega have h13 : v₁ ≠ v₃ := by intro h; have := congrArg Prod.snd h; simp only [hv₁, hv₃] at this; omega have h23 : v₂ ≠ v₃ := by intro h; have := congrArg Prod.snd h; simp only [hv₂, hv₃] at this; omega have hsum3 : ∀ a b c : ℕ, (Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃).sum = ((a : ℤ) * M - b * M + c * (M - Q), (a : ℤ) * M + b * (M - 1) - c * M) := by intro a b c simp only [Multiset.sum_add, Multiset.sum_replicate, hv₁, hv₂, hv₃, Prod.smul_mk, Prod.mk_add_mk, nsmul_eq_mul] ext <;> simp <;> ring have hcount : ∀ (a b c : ℕ) (x : ℤ × ℤ), (Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃).count x = (if x = v₁ then a else 0) + (if x = v₂ then b else 0) + (if x = v₃ then c else 0) := by intro a b c x rw [Multiset.count_add, Multiset.count_add, Multiset.count_replicate, Multiset.count_replicate, Multiset.count_replicate] simp only [@eq_comm _ v₁ x, @eq_comm _ v₂ x, @eq_comm _ v₃ x]
S(m) is nonempty and has zero sum: ∑ S(m) = (0, 0).
The cardinality of S(m) is strictly positive, so S(m) ≠ ∅. Substituting a = k₁, b = k₂, and c = k₃ into the coordinate sum formulas gives 0 in both coordinates by polynomial ring identity.
have hmin : multiset_is_minimal_zero_sum (davenport_box_extremal_sequence m) := by refine ⟨?_, ?_, ?_⟩ · rw [hS] intro h have := congrArg Multiset.card h simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_zero] at this omega · rw [hS, hsum3, hk₁Z, hk₂Z, hk₃Z] ext <;> simp <;> ring
S(m) is minimal: any nonempty submultiset t ≤ S(m) with ∑ t = (0, 0) must equal S(m).
Any submultiset t ≤ S(m) is of the form a • v₁ + b • v₂ + c • v₃ with counts 0 ≤ a ≤ k₁, 0 ≤ b ≤ k₂, 0 ≤ c ≤ k₃ = M(2M - 1). The condition ∑ t = (0, 0) translates into the linear system aM - bM + c(M - Q) = 0 and aM + b(M - 1) - cM = 0. By the uniqueness theorem int_box_extremal_sequence_counts, the only non-negative integer solutions with c ≤ M(2M - 1) are (0, 0, 0) and (k₁, k₂, k₃). Since t is nonempty, the counts must be (k₁, k₂, k₃), so t = S(m).
uses
int_box_extremal_sequence_counts· intro t ht ht0 hts rw [hS] at ht ⊢ set a := t.count v₁ set b := t.count v₂ set c := t.count v₃ have hteq : t = Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃ := by ext x rw [hcount] by_cases h1 : x = v₁ · rw [h1, if_pos rfl, if_neg h12, if_neg h13] simp only [add_zero] rfl by_cases h2 : x = v₂ · rw [h2, if_neg h12.symm, if_pos rfl, if_neg h23] simp only [zero_add, add_zero] rfl by_cases h3 : x = v₃ · rw [h3, if_neg h13.symm, if_neg h23.symm, if_pos rfl] simp only [zero_add] rfl simp only [h1, h2, h3, 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 tauto have ha : a ≤ k₁ := by have := Multiset.count_le_of_le v₁ ht rwa [hcount, if_pos rfl, if_neg h12, if_neg h13, add_zero, add_zero] at this have hb : b ≤ k₂ := by have := Multiset.count_le_of_le v₂ ht rwa [hcount, if_neg h12.symm, if_pos rfl, if_neg h23, zero_add, add_zero] at this have hc : c ≤ k₃ := by have := Multiset.count_le_of_le v₃ ht rwa [hcount, if_neg h13.symm, if_neg h23.symm, if_pos rfl, zero_add, zero_add] at this rw [hteq, hsum3] at hts have ex := congrArg Prod.fst hts have ey := congrArg Prod.snd hts simp only [Prod.fst_zero, Prod.snd_zero] at ex ey set A : ℤ := (a : ℤ) with hAd set B : ℤ := (b : ℤ) with hBd set C : ℤ := (c : ℤ) with hCd have hA0 : 0 ≤ A := Nat.cast_nonneg _ have hB0 : 0 ≤ B := Nat.cast_nonneg _ have hC0 : 0 ≤ C := Nat.cast_nonneg _ have hCle : C ≤ M * (2 * M - 1) := by rw [← hk₃Z, hCd]; exact_mod_cast hc rcases int_box_extremal_sequence_counts M Q A B C hM2 hcopMQ hcopZ hC0 hCle (by linear_combination ex) (by linear_combination ey) with ⟨hA, hB, hC⟩ | ⟨hA, hB, hC⟩ · exfalso have ha0 : a = 0 := by rw [hAd] at hA; exact_mod_cast hA have hb0 : b = 0 := by rw [hBd] at hB; exact_mod_cast hB have hc0 : c = 0 := by rw [hCd] at hC; exact_mod_cast hC apply ht0 rw [hteq, ha0, hb0, hc0] simp · have ha1 : a = k₁ := by have : A = (k₁ : ℤ) := by rw [hA, hk₁Z] rw [hAd] at this exact_mod_cast this have hb1 : b = k₂ := by have : B = (k₂ : ℤ) := by rw [hB, hk₂Z] rw [hBd] at this exact_mod_cast this have hc1 : c = k₃ := by have : C = (k₃ : ℤ) := by rw [hC, hk₃Z] rw [hCd] at this exact_mod_cast this rw [hteq, ha1, hb1, hc1]
All elements of S(m) belong to the box ⟦-m, m⟧².
The vectors v₁ = (m, m) and v₂ = (-m, m - 1) trivially lie in [-m, m]². For v₃ = (m - q, -m), the bound 2 ≤ q < 2m implies -m < m - q ≤ m - 2 < m, so both coordinates of v₃ also lie in [-m, m].
have hbox : ∀ x ∈ davenport_box_extremal_sequence m, x ∈ int_box_two m := by intro x hx rw [hS] at hx simp only [Multiset.mem_add, Multiset.mem_replicate] at hx simp only [int_box_two, Finset.mem_product, Finset.mem_Icc] rcases hx with (⟨-, rfl⟩ | ⟨-, rfl⟩) | ⟨-, rfl⟩ <;> simp only [hv₁, hv₂, hv₃] <;> constructor <;> constructor <;> omega
The multiset cardinality of S(m) is 4m² - q.
The total number of elements is k₁ + k₂ + k₃ = (Q(M - 1) + M) + M(2M - Q) + M(2M - 1) = 4M² - Q = 4m² - q.
uses
Nat.cast_subhave hcard : Multiset.card (davenport_box_extremal_sequence m) = 4 * m ^ 2 - q := by rw [hS] simp only [Multiset.card_add, Multiset.card_replicate] have h1 : ((k₁ + k₂ + k₃ : ℕ) : ℤ) = ((4 * m ^ 2 - q : ℕ) : ℤ) := by have : q ≤ 4 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this] rw [hk₁Z, hk₂Z, hk₃Z] ring exact_mod_cast h1
The Davenport constant of ⟦-m, m⟧² is at least 4m² - q(m).
By definition, the Davenport constant is the supremum of lengths of minimal zero-sum sequences with elements in the set. Since S(m) is such a sequence of length 4m² - q in ⟦-m, m⟧², the Davenport constant is at least 4m² - q by le_sSup.
uses
le_sSupunfold davenport_constant apply le_sSup exact ⟨_, fun x hx => hbox x hx, hmin, by rw [hcard]⟩
Nat.exists_infinite_primes- For any natural number n, there exists a prime p with n ≤ p.
Nat.le_of_dvd- If n is positive and m divides n, then m ≤ n.
Nat.sInf_mem- If a set of natural numbers is nonempty, its infimum belongs to the set.
Nat.sInf_le- If a natural number belongs to a set, then the infimum of the set is at most that number.
Nat.exists_prime_lt_and_le_two_mul- Bertrand's postulate: for any positive natural number n, there exists a prime p with n < p ≤ 2n.
Nat.prime_mul_iff- A product of natural numbers is prime if and only if one factor is prime and the other is 1.
Nat.coprime_of_dvd- Two natural numbers are coprime if no prime divides both of them.
Nat.dvd_sub- If k divides m and k divides n, then k divides m - n.
dvd_mul_of_dvd_right- If a divides b, then a divides c * b for any c.
Nat.Prime.coprime_iff_not_dvd- A prime p is coprime to n if and only if p does not divide n.
lt_of_le_of_ne- In a partial order, a ≤ b and a ≠ b imply a < b.
Nat.cast_sub- The cast of a difference of natural numbers n - m equals the difference of casts, provided m ≤ n.
IsCoprime.add_mul_left_right- In a commutative ring, if x and y are coprime, then x and y + x * z are coprime for any z.
int_box_extremal_sequence_counts- For integers M, Q, A, B, C satisfying the coprimality and range conditions of the extremal configuration, the only non-negative integer solutions to the zero-sum system are (0, 0, 0) and (k₁, k₂, k₃).
le_sSup- An element of a set in a complete semilattice is bounded above by the supremum of the set.
- The proof relies on an auxiliary lemma, `int_box_extremal_sequence_counts`, which classifies the non-negative integer solutions to the two-dimensional zero-sum linear system.
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_int_box_two_ge (m : ℕ) (hm : 2 ≤ m) : ((4 * m ^ 2 - nat_least_prime_not_dvd m : ℕ) : ℕ∞) ≤ davenport_constant (↑(int_box_two m) : Set (ℤ × ℤ)) := by set q := nat_least_prime_not_dvd m with hqdef -- the smallest prime not dividing `m` have hne : {p | p.Prime ∧ ¬ p ∣ m}.Nonempty := by obtain ⟨p, hp1, hp2⟩ := Nat.exists_infinite_primes (m + 1) exact ⟨p, hp2, fun h => by have := Nat.le_of_dvd (by omega) h; omega⟩ have hq : q.Prime ∧ ¬ q ∣ m := Nat.sInf_mem hne have hqmin : ∀ p, p.Prime → ¬ p ∣ m → q ≤ p := fun p hp hpd => Nat.sInf_le ⟨hp, hpd⟩ have hq2 : 2 ≤ q := hq.1.two_le have hqle : q ≤ 2 * m := by obtain ⟨p, hp, hmp, hp2m⟩ := Nat.exists_prime_lt_and_le_two_mul m (by omega) exact (hqmin p hp (fun h => by have := Nat.le_of_dvd (by omega) h; omega)).trans hp2m have hqne : q ≠ 2 * m := by intro h have := hq.1 rw [h, Nat.prime_mul_iff] at this rcases this with ⟨_, h1⟩ | ⟨_, h1⟩ <;> omega have hsmall : ∀ p, p.Prime → p < q → p ∣ m := by intro p hp hpq by_contra hpd exact absurd (hqmin p hp hpd) (by omega) have hcop1 : Nat.Coprime (2 * m - 1) (q - 1) := by apply Nat.coprime_of_dvd intro p hp h1 h2 have hpq : p < q := by have := Nat.le_of_dvd (by omega) h2 omega have hpm := hsmall p hp hpq have : p ∣ 2 * m - (2 * m - 1) := Nat.dvd_sub (dvd_mul_of_dvd_right hpm 2) h1 rw [show 2 * m - (2 * m - 1) = 1 by omega] at this exact hp.one_lt.ne' (Nat.dvd_one.1 this) have hcopqm : Nat.Coprime q m := (Nat.Prime.coprime_iff_not_dvd hq.1).2 hq.2 -- integer versions set M : ℤ := (m : ℤ) with hM set Q : ℤ := (q : ℤ) with hQ have hM2 : 2 ≤ M := by rw [hM]; exact_mod_cast hm have hQ2 : 2 ≤ Q := by rw [hQ]; exact_mod_cast hq2 have hQle : Q < 2 * M := by rw [hM, hQ]; exact_mod_cast (lt_of_le_of_ne hqle hqne) have hcopZ : IsCoprime (2 * M - 1) (2 * M - Q) := by have h1 : IsCoprime ((2 * m - 1 : ℕ) : ℤ) ((q - 1 : ℕ) : ℤ) := Nat.isCoprime_iff_coprime.2 hcop1 push_cast [Nat.cast_sub (show 1 ≤ 2 * m by omega), Nat.cast_sub (show 1 ≤ q by omega)] at h1 have : 2 * M - Q = (2 * M - 1) + (-1) * (Q - 1) := by ring rw [this] exact (h1.neg_right.mul_add_left_right 1).symm.symm |> fun h => by simpa [add_comm, mul_comm] using (IsCoprime.add_mul_left_right h1.neg_right 1) have hcopMQ : IsCoprime M Q := by rw [hM, hQ]; exact Nat.isCoprime_iff_coprime.2 hcopqm.symm set v₁ : ℤ × ℤ := (M, M) with hv₁ set v₂ : ℤ × ℤ := (-M, M - 1) with hv₂ set v₃ : ℤ × ℤ := (M - Q, -M) with hv₃ set k₁ := q * (m - 1) + m with hk₁ set k₂ := 2 * m ^ 2 - m * q with hk₂ set k₃ := 2 * m ^ 2 - m with hk₃ have hk₁Z : (k₁ : ℤ) = Q * (M - 1) + M := by rw [hk₁]; push_cast [Nat.cast_sub (show 1 ≤ m by omega)]; ring have hk₂Z : (k₂ : ℤ) = M * (2 * M - Q) := by rw [hk₂] have : m * q ≤ 2 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this]; ring have hk₃Z : (k₃ : ℤ) = M * (2 * M - 1) := by rw [hk₃] have : m ≤ 2 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this]; ring have hS : davenport_box_extremal_sequence m = Multiset.replicate k₁ v₁ + Multiset.replicate k₂ v₂ + Multiset.replicate k₃ v₃ := rfl have h12 : v₁ ≠ v₂ := by intro h; have := congrArg Prod.fst h; simp only [hv₁, hv₂] at this; omega have h13 : v₁ ≠ v₃ := by intro h; have := congrArg Prod.snd h; simp only [hv₁, hv₃] at this; omega have h23 : v₂ ≠ v₃ := by intro h; have := congrArg Prod.snd h; simp only [hv₂, hv₃] at this; omega have hsum3 : ∀ a b c : ℕ, (Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃).sum = ((a : ℤ) * M - b * M + c * (M - Q), (a : ℤ) * M + b * (M - 1) - c * M) := by intro a b c simp only [Multiset.sum_add, Multiset.sum_replicate, hv₁, hv₂, hv₃, Prod.smul_mk, Prod.mk_add_mk, nsmul_eq_mul] ext <;> simp <;> ring have hcount : ∀ (a b c : ℕ) (x : ℤ × ℤ), (Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃).count x = (if x = v₁ then a else 0) + (if x = v₂ then b else 0) + (if x = v₃ then c else 0) := by intro a b c x rw [Multiset.count_add, Multiset.count_add, Multiset.count_replicate, Multiset.count_replicate, Multiset.count_replicate] simp only [@eq_comm _ v₁ x, @eq_comm _ v₂ x, @eq_comm _ v₃ x] have hmin : multiset_is_minimal_zero_sum (davenport_box_extremal_sequence m) := by refine ⟨?_, ?_, ?_⟩ · rw [hS] intro h have := congrArg Multiset.card h simp only [Multiset.card_add, Multiset.card_replicate, Multiset.card_zero] at this omega · rw [hS, hsum3, hk₁Z, hk₂Z, hk₃Z] ext <;> simp <;> ring · intro t ht ht0 hts rw [hS] at ht ⊢ set a := t.count v₁ set b := t.count v₂ set c := t.count v₃ have hteq : t = Multiset.replicate a v₁ + Multiset.replicate b v₂ + Multiset.replicate c v₃ := by ext x rw [hcount] by_cases h1 : x = v₁ · rw [h1, if_pos rfl, if_neg h12, if_neg h13] simp only [add_zero] rfl by_cases h2 : x = v₂ · rw [h2, if_neg h12.symm, if_pos rfl, if_neg h23] simp only [zero_add, add_zero] rfl by_cases h3 : x = v₃ · rw [h3, if_neg h13.symm, if_neg h23.symm, if_pos rfl] simp only [zero_add] rfl simp only [h1, h2, h3, 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 tauto have ha : a ≤ k₁ := by have := Multiset.count_le_of_le v₁ ht rwa [hcount, if_pos rfl, if_neg h12, if_neg h13, add_zero, add_zero] at this have hb : b ≤ k₂ := by have := Multiset.count_le_of_le v₂ ht rwa [hcount, if_neg h12.symm, if_pos rfl, if_neg h23, zero_add, add_zero] at this have hc : c ≤ k₃ := by have := Multiset.count_le_of_le v₃ ht rwa [hcount, if_neg h13.symm, if_neg h23.symm, if_pos rfl, zero_add, zero_add] at this rw [hteq, hsum3] at hts have ex := congrArg Prod.fst hts have ey := congrArg Prod.snd hts simp only [Prod.fst_zero, Prod.snd_zero] at ex ey set A : ℤ := (a : ℤ) with hAd set B : ℤ := (b : ℤ) with hBd set C : ℤ := (c : ℤ) with hCd have hA0 : 0 ≤ A := Nat.cast_nonneg _ have hB0 : 0 ≤ B := Nat.cast_nonneg _ have hC0 : 0 ≤ C := Nat.cast_nonneg _ have hCle : C ≤ M * (2 * M - 1) := by rw [← hk₃Z, hCd]; exact_mod_cast hc rcases int_box_extremal_sequence_counts M Q A B C hM2 hcopMQ hcopZ hC0 hCle (by linear_combination ex) (by linear_combination ey) with ⟨hA, hB, hC⟩ | ⟨hA, hB, hC⟩ · exfalso have ha0 : a = 0 := by rw [hAd] at hA; exact_mod_cast hA have hb0 : b = 0 := by rw [hBd] at hB; exact_mod_cast hB have hc0 : c = 0 := by rw [hCd] at hC; exact_mod_cast hC apply ht0 rw [hteq, ha0, hb0, hc0] simp · have ha1 : a = k₁ := by have : A = (k₁ : ℤ) := by rw [hA, hk₁Z] rw [hAd] at this exact_mod_cast this have hb1 : b = k₂ := by have : B = (k₂ : ℤ) := by rw [hB, hk₂Z] rw [hBd] at this exact_mod_cast this have hc1 : c = k₃ := by have : C = (k₃ : ℤ) := by rw [hC, hk₃Z] rw [hCd] at this exact_mod_cast this rw [hteq, ha1, hb1, hc1] have hbox : ∀ x ∈ davenport_box_extremal_sequence m, x ∈ int_box_two m := by intro x hx rw [hS] at hx simp only [Multiset.mem_add, Multiset.mem_replicate] at hx simp only [int_box_two, Finset.mem_product, Finset.mem_Icc] rcases hx with (⟨-, rfl⟩ | ⟨-, rfl⟩) | ⟨-, rfl⟩ <;> simp only [hv₁, hv₂, hv₃] <;> constructor <;> constructor <;> omega have hcard : Multiset.card (davenport_box_extremal_sequence m) = 4 * m ^ 2 - q := by rw [hS] simp only [Multiset.card_add, Multiset.card_replicate] have h1 : ((k₁ + k₂ + k₃ : ℕ) : ℤ) = ((4 * m ^ 2 - q : ℕ) : ℤ) := by have : q ≤ 4 * m ^ 2 := by nlinarith push_cast [Nat.cast_sub this] rw [hk₁Z, hk₂Z, hk₃Z] ring exact_mod_cast h1 unfold davenport_constant apply le_sSup exact ⟨_, fun x hx => hbox x hx, hmin, by rw [hcard]⟩