AFTD Auto-Formalizing Theoretical Domains

int_box_extremal_sequence_counts

theoremverified

If 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) = 1, then (A, B, C) is (0, 0, 0) or (Q(M−1)+M, M(2M−Q), M(2M−1)).

Statement

theorem int_box_extremal_sequence_counts (M Q A B C : ℤ) (hM : 2 ≤ M)
    (hcopMQ : IsCoprime M Q) (hcopZ : IsCoprime (2 * M - 1) (2 * M - Q))
    (hC0 : 0 ≤ C) (hCle : C ≤ M * (2 * M - 1))
    (ex : A * M - B * M + C * (M - Q) = 0) (ey : A * M + B * (M - 1) - C * M = 0) :
    (A = 0 ∧ B = 0 ∧ C = 0) ∨
      (A = Q * (M - 1) + M ∧ B = M * (2 * M - Q) ∧ C = M * (2 * M - 1))
Source
The minimality of S(m) in arXiv:2610.16562 (The Davenport constant of low-dimensional boxes) (proof of Theorem 1): the only zero-sum subsequences of S(m) are empty or all of it.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
Used by 1
  • davenport_constant_int_box_two_geFor 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…

The proof, explained

The proof solves the system of two linear equations in A, B, C by exploiting divisibility and coprimality constraints. Using linear combinations of the equations, coprimality of M and Q implies that M divides both B and C, so we write B = M·B' and C = M·C'. Eliminating A produces the relation B'(2M−1) = C'(2M−Q), which by coprimality of 2M−1 and 2M−Q forces (2M−1) ∣ C', parametrizing C as M(2M−1)j for an integer j. The bounds 0 ≤ C ≤ M(2M−1) restrict j to {0, 1}, yielding the trivial solution (0, 0, 0) when j = 0 and the extremal non-trivial solution when j = 1.

  1. M divides both B and C, allowing us to write B = M * B' and C = M * C' for integers B' and C'.

    From M ≥ 2, we have M > 0. Taking -1 times the second equation (ey) gives B = M * (A + B - C), which shows M ∣ B. Similarly, taking -1 times the first equation (ex) gives C * Q = M * (A - B + C), so M ∣ C * Q. Since M and Q are coprime (hcopMQ), Euclid's lemma implies M ∣ C. We can therefore substitute B = M * B' and C = M * C'.

    lines 7–14

      have hMpos : 0 < M := by linarith
      have hMB : M ∣ B := ⟨A + B - C, by linear_combination -1 * ey⟩
      have hMC : M ∣ C := by
        have : M ∣ C * Q := ⟨A - B + C, by linear_combination -1 * ex⟩
        exact hcopMQ.dvd_of_dvd_mul_right this
      obtain ⟨B', hB'⟩ := hMB
      obtain ⟨C', hC'⟩ := hMC
      subst hB' hC'
  2. A can be expressed in terms of B' and C' as A = C' * M - B' * (M - 1).

    Substituting the expressions for B and C into the second equation (ey) gives M * (A + B' * (M - 1) - C' * M) = 0. Since M ≥ 2 > 0, the zero-product lemma mul_eq_zero.1 eliminates the possibility M = 0, leaving A = C' * M - B' * (M - 1).

    lines 15–20

    uses mul_eq_zero.1

      have hA : A = C' * M - B' * (M - 1) := by
        have : M * (A + B' * (M - 1) - C' * M) = 0 := by linear_combination ey
        rcases mul_eq_zero.1 this with h | h
        · linarith
        · linarith
      subst hA
  3. B' and C' satisfy the relation B' * (2 * M - 1) = C' * (2 * M - Q).

    Substituting the formula for A into the first equation (ex) yields M * (B' * (2 * M - 1) - C' * (2 * M - Q)) = 0. Applying mul_eq_zero.1 and the fact that M ≠ 0 gives B' * (2 * M - 1) = C' * (2 * M - Q).

    lines 21–25

    uses mul_eq_zero.1

      have hrel : B' * (2 * M - 1) = C' * (2 * M - Q) := by
        have : M * (B' * (2 * M - 1) - C' * (2 * M - Q)) = 0 := by linear_combination -1 * ex
        rcases mul_eq_zero.1 this with h | h
        · linarith
        · linarith
  4. 2 * M - 1 divides C', so C' = (2 * M - 1) * j for some integer j.

    From the relation B' * (2 * M - 1) = C' * (2 * M - Q), we see that 2 * M - 1 divides C' * (2 * M - Q). Since 2 * M - 1 and 2 * M - Q are coprime (hcopZ), Euclid's lemma implies (2 * M - 1) ∣ C'. We define j such that C' = (2 * M - 1) * j and substitute it.

    lines 26–30

      have hdvd : (2 * M - 1) ∣ C' := by
        have : (2 * M - 1) ∣ C' * (2 * M - Q) := ⟨B', by linear_combination -1 * hrel⟩
        exact hcopZ.dvd_of_dvd_mul_right this
      obtain ⟨j, hj⟩ := hdvd
      subst hj
  5. The integer parameter j satisfies 0 ≤ j ≤ 1, and 2 * M - 1 > 0.

    Since M ≥ 2, the quantity M * (2 * M - 1) is strictly positive (hP). Since C = M * (2 * M - 1) * j ≥ 0, if j < 0 then C would be strictly negative by mul_neg_of_pos_of_neg, contradiction; thus 0 ≤ j. Similarly, if j > 1 then j ≥ 2, so C ≥ 2 * M * (2 * M - 1) by mul_le_mul_of_nonneg_left, contradicting C ≤ M * (2 * M - 1); thus j ≤ 1. Finally, 2 * M - 1 > 0 follows from M ≥ 2.

    lines 31–40

    uses mul_neg_of_pos_of_neg, mul_le_mul_of_nonneg_left

      have hP : 0 < M * (2 * M - 1) := by nlinarith
      have hj0 : 0 ≤ j := by
        by_contra h
        push_neg at h
        nlinarith [mul_neg_of_pos_of_neg hP h]
      have hj1 : j ≤ 1 := by
        by_contra h
        push_neg at h
        nlinarith [mul_le_mul_of_nonneg_left (show (2 : ℤ) ≤ j by omega) hP.le]
      have h2 : 0 < 2 * M - 1 := by linarith
  6. In the case j = 0, the only solution is (A, B, C) = (0, 0, 0).

    Because 0 ≤ j ≤ 1, the only integer choices are j = 0 and j = 1. When j = 0, we have C' = 0 and thus C = 0. The relation becomes B' * (2 * M - 1) = 0. Since 2 * M - 1 > 0, mul_eq_zero.1 forces B' = 0, hence B = 0. Then A = C' * M - B' * (M - 1) = 0, giving the trivial solution (0, 0, 0).

    lines 41–49

    uses mul_eq_zero.1

      rcases (show j = 0 ∨ j = 1 by omega) with rfl | rfl
      · left
        have hB0 : B' = 0 := by
          have : B' * (2 * M - 1) = 0 := by rw [hrel]; ring
          rcases mul_eq_zero.1 this with h | h
          · exact h
          · linarith
        subst hB0
        refine ⟨by ring, by ring, by ring⟩
  7. In the case j = 1, the solution is (A, B, C) = (Q * (M - 1) + M, M * (2 * M - Q), M * (2 * M - 1)).

    When j = 1, we have C' = 2 * M - 1, so C = M * (2 * M - 1). The relation becomes (2 * M - 1) * (B' - (2 * M - Q)) = 0. Since 2 * M - 1 > 0, mul_eq_zero.1 forces B' = 2 * M - Q, so B = M * (2 * M - Q). Substituting these values into A yields A = (2 * M - 1) * M - (2 * M - Q) * (M - 1) = Q * (M - 1) + M, completing the second solution.

    lines 50–57

    uses mul_eq_zero.1

      · right
        have hB1 : B' = 2 * M - Q := by
          have : (2 * M - 1) * (B' - (2 * M - Q)) = 0 := by linear_combination hrel
          rcases mul_eq_zero.1 this with h | h
          · linarith
          · linarith
        subst hB1
        refine ⟨by ring, by ring, by ring⟩
mul_eq_zero.1
If a product of two numbers is zero, at least one of the factors is zero (a * b = 0 → a = 0 ∨ b = 0).
mul_neg_of_pos_of_neg
The product of a strictly positive number and a strictly negative number is strictly negative (0 < a → b < 0 → a * b < 0).
mul_le_mul_of_nonneg_left
Multiplying an inequality b ≤ c on the left by a non-negative number a ≥ 0 preserves the inequality (a * b ≤ a * c).

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 int_box_extremal_sequence_counts (M Q A B C : ℤ) (hM : 2 ≤ M)    (hcopMQ : IsCoprime M Q) (hcopZ : IsCoprime (2 * M - 1) (2 * M - Q))    (hC0 : 0 ≤ C) (hCle : C ≤ M * (2 * M - 1))    (ex : A * M - B * M + C * (M - Q) = 0) (ey : A * M + B * (M - 1) - C * M = 0) :    (A = 0 ∧ B = 0 ∧ C = 0) ∨      (A = Q * (M - 1) + M ∧ B = M * (2 * M - Q) ∧ C = M * (2 * M - 1)) := by  have hMpos : 0 < M := by linarith  have hMB : M ∣ B := ⟨A + B - C, by linear_combination -1 * ey⟩  have hMC : M ∣ C := by    have : M ∣ C * Q := ⟨A - B + C, by linear_combination -1 * ex⟩    exact hcopMQ.dvd_of_dvd_mul_right this  obtain ⟨B', hB'⟩ := hMB  obtain ⟨C', hC'⟩ := hMC  subst hB' hC'  have hA : A = C' * M - B' * (M - 1) := by    have : M * (A + B' * (M - 1) - C' * M) = 0 := by linear_combination ey    rcases mul_eq_zero.1 this with h | h    · linarith    · linarith  subst hA  have hrel : B' * (2 * M - 1) = C' * (2 * M - Q) := by    have : M * (B' * (2 * M - 1) - C' * (2 * M - Q)) = 0 := by linear_combination -1 * ex    rcases mul_eq_zero.1 this with h | h    · linarith    · linarith  have hdvd : (2 * M - 1) ∣ C' := by    have : (2 * M - 1) ∣ C' * (2 * M - Q) := ⟨B', by linear_combination -1 * hrel⟩    exact hcopZ.dvd_of_dvd_mul_right this  obtain ⟨j, hj⟩ := hdvd  subst hj  have hP : 0 < M * (2 * M - 1) := by nlinarith  have hj0 : 0 ≤ j := by    by_contra h    push_neg at h    nlinarith [mul_neg_of_pos_of_neg hP h]  have hj1 : j ≤ 1 := by    by_contra h    push_neg at h    nlinarith [mul_le_mul_of_nonneg_left (show (2 : ℤ) ≤ j by omega) hP.le]  have h2 : 0 < 2 * M - 1 := by linarith  rcases (show j = 0 ∨ j = 1 by omega) with rfl | rfl  · left    have hB0 : B' = 0 := by      have : B' * (2 * M - 1) = 0 := by rw [hrel]; ring      rcases mul_eq_zero.1 this with h | h      · exact h      · linarith    subst hB0    refine ⟨by ring, by ring, by ring⟩  · right    have hB1 : B' = 2 * M - Q := by      have : (2 * M - 1) * (B' - (2 * M - Q)) = 0 := by linear_combination hrel      rcases mul_eq_zero.1 this with h | h      · linarith      · linarith    subst hB1    refine ⟨by ring, by ring, by ring⟩
See it in the graphDiscuss this resultChallenge it