int_box_extremal_sequence_counts
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- 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.
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'.
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'
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).
uses
mul_eq_zero.1have 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
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).
uses
mul_eq_zero.1have 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
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.
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
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.
uses
mul_neg_of_pos_of_neg,mul_le_mul_of_nonneg_lefthave 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
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).
uses
mul_eq_zero.1rcases (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⟩
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.
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
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 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⟩