zero_sum_w_two
For every r ≥ 1, w_r(2) = 2r + 1.
Statement
theorem zero_sum_w_two (r : ℕ) (hr : 1 ≤ r) : zero_sum_w r 2 = ((2 * r + 1 : ℕ) : ℕ∞)- Formalizes
- arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems), Theorem 1.2 (i). The case n = 2 of Question 3.1 (list entry OP-259).
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- zero_sum_ww_r(n): the least N such that every admissible sequence of length N in ℤ^r has a nonempty subsequence whose sum is ≡ 0 (mod n) but ≢ 0…
- zero_sum_w_gew_r(n) ≥ 2r(n−1) + 1 for all r ≥ 1 and n > 1.
- zero_sum_w_two_leUpper bound w_r(2) <= 2r + 1: every sequence of 2r + 1 vectors of Z^r, each nonzero mod 2, has a nonempty subsequence whose sum is 0 mod 2…
The proof, explained
The theorem establishes w_r(2) = 2r + 1 by proving matching lower and upper bounds. The lower bound follows from the general theorem w_r(n) ≥ 2r(n - 1) + 1 specialized to n = 2, while the upper bound w_r(2) ≤ 2r + 1 is provided by zero_sum_w_two_le. Antisymmetry of the partial order on ℕ∞ then concludes that the two sides are equal.
2 * r * (2 - 1) + 1 ≤ zero_sum_w r 2
Applying the general lower bound `zero_sum_w_ge` with n = 2 (where the requirement 1 < 2 is proved by numerical evaluation) yields the lower bound 2 * r * (2 - 1) + 1 ≤ w_r(2).
uses
zero_sum_w_gehave _ := hr have hge := zero_sum_w_ge r 2 (by norm_num)
zero_sum_w r 2 ≤ 2 * r + 1
The lemma `zero_sum_w_two_le` gives the matching upper bound w_r(2) ≤ 2 * r + 1 for any r.
uses
zero_sum_w_two_lehave hle := zero_sum_w_two_le r2 * r + 1 ≤ zero_sum_w r 2
The linear arithmetic identity 2 * r * (2 - 1) + 1 = 2 * r + 1 is proved using `omega`, and rewriting the lower bound with this identity simplifies it to 2 * r + 1 ≤ w_r(2).
have heq : 2 * r * (2 - 1) + 1 = 2 * r + 1 := by omega rw [heq] at hge
zero_sum_w r 2 = 2 * r + 1
Combining the upper bound w_r(2) ≤ 2 * r + 1 and the lower bound 2 * r + 1 ≤ w_r(2) using the antisymmetry of ≤ (`le_antisymm`) establishes equality.
uses
le_antisymmexact le_antisymm hle hge
zero_sum_w_ge- For any r and any n > 1, the zero-sum constant w_r(n) is at least 2r(n - 1) + 1.
zero_sum_w_two_le- For any r, the zero-sum constant w_r(2) is at most 2r + 1.
le_antisymm- In a partially ordered type, if a ≤ b and b ≤ a, then a = b.
- Line 2 (`have _ := hr`) references the hypothesis `hr : 1 ≤ r` to avoid an unused variable warning; mathematically, the lower and upper bounds both hold for all r without needing r ≥ 1.
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 zero_sum_w_two (r : ℕ) (hr : 1 ≤ r) : zero_sum_w r 2 = ((2 * r + 1 : ℕ) : ℕ∞) := by have _ := hr have hge := zero_sum_w_ge r 2 (by norm_num) have hle := zero_sum_w_two_le r have heq : 2 * r * (2 - 1) + 1 = 2 * r + 1 := by omega rw [heq] at hge exact le_antisymm hle hge