AFTD Auto-Formalizing Theoretical Domains

zero_sum_w

def

w_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 (mod n²) (⊤ if there is no such N).

Statement

noncomputable def zero_sum_w (r n : ℕ) : ℕ∞
Defined in
arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems), Sec. 1 (w_r(n), Sun's Definition 1.3).
Verified
15 Oct 2026
Axioms
none listed
Built on 2
  • zero_sum_admissibleA sequence A of vectors in ℤ^r is admissible modulo n when no term is ≡ 0 (mod n).
  • zero_sum_good_subseqA nonempty set I of positions of A is good when Σ_{i∈I} a_i ≡ 0 (mod n) but Σ_{i∈I} a_i ≢ 0 (mod n²) (condition (1.2)).
Used by 4
  • 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…
  • zero_sum_w_twoFor every r ≥ 1, w_r(2) = 2r + 1.
  • zero_sum_w_gew_r(n) ≥ 2r(n−1) + 1 for all r ≥ 1 and n > 1.
  • zero_sum_w_three_threew_3(3) = 13: every admissible sequence (no term ≡ 0 mod 3) of 13 vectors in ℤ^3 has a nonempty subsequence whose sum is ≡ 0 (mod 3) but ≢…

Lean source view module on GitHub

/-- `w_r(n)`, the least length forcing a subsequence with (1.2). -/
noncomputable def zero_sum_w (r n : ℕ) : ℕ∞ :=
  ⨅ (N : ℕ) (_ : ∀ A : List (Fin r → ℤ), A.length = N → zero_sum_admissible n A →
    ∃ I, zero_sum_good_subseq n A I), (N : ℕ∞)
See it in the graphDiscuss this resultChallenge it