AFTD Auto-Formalizing Theoretical Domains

davenport_constant_int_box_two_ge

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

  1. 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.

    lines 4–11

    uses Nat.exists_infinite_primes, Nat.le_of_dvd, Nat.sInf_mem, Nat.sInf_le

      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
  2. 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.

    lines 12–23

    uses Nat.exists_prime_lt_and_le_two_mul, Nat.prime_mul_iff

      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)
  3. 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).

    lines 24–34

    uses Nat.coprime_of_dvd, Nat.dvd_sub, dvd_mul_of_dvd_right, Nat.Prime.coprime_iff_not_dvd

      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
  4. 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.

    lines 35–49

    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
  5. 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.

    lines 50–67

    uses Nat.cast_sub

      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
  6. 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.

    lines 68–87

      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]
  7. 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.

    lines 88–96

      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
  8. 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).

    lines 97–166

    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]
  9. 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].

    lines 167–173

      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
  10. 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.

    lines 174–182

    uses Nat.cast_sub

      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
  11. 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.

    lines 183–185

    uses le_sSup

      unfold 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.

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

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]⟩
See it in the graphDiscuss this resultChallenge it