AFTD Auto-Formalizing Theoretical Domains

zero_sum_w_two

theoremverifiedformalization

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.

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

    lines 2–3

    uses zero_sum_w_ge

      have _ := hr
      have hge := zero_sum_w_ge r 2 (by norm_num)
  2. 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.

    line 4

    uses zero_sum_w_two_le

      have hle := zero_sum_w_two_le r
  3. 2 * 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).

    lines 5–6

      have heq : 2 * r * (2 - 1) + 1 = 2 * r + 1 := by omega
      rw [heq] at hge
  4. 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.

    line 7

    uses le_antisymm

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

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