zero_sum_w_ge
w_r(n) ≥ 2r(n−1) + 1 for all r ≥ 1 and n > 1.
Statement
theorem zero_sum_w_ge (r n : ℕ) (hn : 1 < n) : ((2 * r * (n - 1) + 1 : ℕ) : ℕ∞) ≤ zero_sum_w r n- Formalizes
- arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems), Lemma 3.1 (consequence).
- Verified
- 15 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_basis_seq_w_badFor n > 1 and r ≥ 1, the admissible sequence E_{r,n} (length 2r(n−1)) has no nonempty subsequence whose sum is ≡ 0 (mod n) but ≢ 0 (mod n²).
- 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)).
- zero_sum_w_badAn admissible sequence is w-bad when no nonempty subsequence satisfies (1.2).
- zero_sum_basis_seqE_{r,n} = Π_j e_j^{[n−1]} (−e_j)^{[n−1]}: n−1 copies of each standard basis vector e_j of ℤ^r and n−1 copies of −e_j.
- Used by 2
- zero_sum_w_twoFor every r ≥ 1, w_r(2) = 2r + 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 ≢…
The proof, explained
The constant $w_r(n)$ is defined as the infimum of all sequence lengths $N$ such that every admissible sequence in $(\mathbb{Z}/n^2\mathbb{Z})^r$ of length $N$ contains a good zero-sum subsequence. To establish the lower bound $w_r(n) \ge 2r(n-1)+1$, it suffices to show that any such length $N$ satisfies $N \ge 2r(n-1)+1$. Assuming for contradiction that $N \le 2r(n-1)$, we truncate the known admissible sequence `zero_sum_basis_seq r n` of length $2r(n-1)$ to its first $N$ elements. This prefix is an admissible sequence of length $N$ and must therefore contain a good subsequence; but embedding this subsequence back into the original sequence produces a good subsequence of `zero_sum_basis_seq r n`, contradicting the fact that this sequence was constructed to contain none.
To show $w_r(n) \ge 2r(n-1) + 1$, it suffices to show that any candidate length $N$ guaranteeing a good subsequence satisfies $N \ge 2r(n-1) + 1$.
Unfolding the definition of $w_r(n)$, it is the infimum over all sequence lengths $N$ such that every admissible sequence of length $N$ has a good subsequence. By `le_iInf₂`, a number is a lower bound for this infimum if it is bounded above by every such $N$.
uses
le_iInf₂unfold zero_sum_w refine le_iInf₂ (fun N hN => ?_)
Assume for contradiction that $N \le 2r(n-1)$.
Assuming for contradiction that $2r(n-1) + 1 \le N$ is false, `not_le` gives $N < 2r(n-1) + 1$. Stripping the coercion to $\mathbb{N}_\infty$ using `Nat.cast_lt`, linear arithmetic (`omega`) implies $N \le 2r(n-1)$.
uses
not_le,Nat.cast_ltby_contra hlt rw [not_le] at hlt have hle : N ≤ 2 * r * (n - 1) := by have := (Nat.cast_lt (α := ℕ∞)).mp hlt omega
The prefix of length $N$ of `zero_sum_basis_seq r n` is admissible and must contain a good subsequence indexed by $I$.
By `zero_sum_basis_seq_w_bad`, there is an admissible sequence `zero_sum_basis_seq r n` of length $2r(n-1)$ that contains no good subsequence. Since $N \le 2r(n-1)$, taking its prefix of length $N$ gives a sequence of length exactly $N$. Every vector in this prefix is in the original sequence (`List.mem_of_mem_take`), so the prefix is also admissible. By the hypothesis on $N$, this prefix must contain a good subsequence, giving a nonempty index set $I$ whose coordinate sums are divisible by $n$, with some coordinate $j$ not divisible by $n^2$.
uses
zero_sum_basis_seq_w_bad,List.mem_of_mem_takeobtain ⟨hbad, hlen⟩ := zero_sum_basis_seq_w_bad r n hn have htl : ((zero_sum_basis_seq r n).take N).length ≤ (zero_sum_basis_seq r n).length := by simp obtain ⟨I, hIne, hIdiv, j, hj⟩ := hN ((zero_sum_basis_seq r n).take N) (by simp [hlen]; omega) (fun a ha => hbad.1 a (List.mem_of_mem_take ha))
The coordinate sums over $I$ in the prefix equal the coordinate sums over the embedded indices in the full sequence.
Because the prefix length $N$ is at most the total length, indices of the prefix embed injectively into indices of the full sequence via `Fin.castLE`. Using `Finset.sum_map`, the sum over the mapped indices equals the sum over $I$ evaluated at the mapped positions. Since the prefix shares its elements at each index with the full sequence (`List.getElem_take`), `Finset.sum_congr` confirms that every coordinate sum is preserved.
uses
Fin.castLE,Fin.castLE_injective,Finset.sum_map,Finset.sum_congr,List.getElem_takehave hsum : ∀ j, ∑ i ∈ I.map ⟨Fin.castLE htl, Fin.castLE_injective htl⟩, (zero_sum_basis_seq r n).get i j = ∑ i ∈ I, ((zero_sum_basis_seq r n).take N).get i j := by intro j rw [Finset.sum_map] refine Finset.sum_congr rfl (fun i _ => ?_) simp [List.getElem_take]
The embedded subsequence is a good subsequence of `zero_sum_basis_seq r n`, yielding a contradiction.
The image of $I$ under the embedding is nonempty because $I$ is nonempty. Rewriting the coordinate sums of the full sequence to those of the prefix, the sums are all divisible by $n$, and the $j$-th coordinate sum is not divisible by $n^2$. Thus the mapped index set is a good subsequence of `zero_sum_basis_seq r n`, contradicting the fact that `zero_sum_basis_seq r n` has no good subsequence.
uses
Fin.castLE,Fin.castLE_injectiveapply hbad.2 (I.map ⟨Fin.castLE htl, Fin.castLE_injective htl⟩) refine ⟨hIne.map, fun j => ?_, j, ?_⟩ · rw [hsum]; exact hIdiv j · rw [hsum]; exact hj
le_iInf₂- A lower bound for all terms in a doubly indexed family is a lower bound for its infimum.
not_le- In a linear order, $\neg (a \le b)$ is equivalent to $b < a$.
Nat.cast_lt- The strict inequality $m < n$ between natural numbers is preserved under coercion to $\mathbb{N}_\infty$.
zero_sum_basis_seq_w_bad- The canonical sequence `zero_sum_basis_seq r n` has length $2r(n-1)$ and is bad: it is admissible, but contains no good subsequence.
List.mem_of_mem_take- Any element belonging to a prefix `List.take i l` is also an element of the original list $l$.
Fin.castLE- Embeds $\text{Fin } n$ into $\text{Fin } m$ whenever $n \le m$.
Fin.castLE_injective- The canonical embedding from $\text{Fin } n$ to $\text{Fin } m$ when $n \le m$ is injective.
Finset.sum_map- Summing a function over the image of a finite set under an embedding equals summing the pull-back of that function over the original finite set.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on each index.
List.getElem_take- The $i$-th element of a prefix `List.take j xs` is equal to the $i$-th element of the list `xs`.
- The quantity $w_r(n)$ takes values in $\mathbb{N}_\infty = \mathbb{N} \cup \{\infty\}$, where an empty infimum evaluates to $\infty$. The lower bound is therefore stated and proven in $\mathbb{N}_\infty$.
- Vectors in the group are formalized as integer-valued functions $\text{Fin } r \to \mathbb{Z}$, and a subsequence of a list $A$ is represented by a set of position indices $I \subseteq \text{Fin } A.\text{length}$.
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_ge (r n : ℕ) (hn : 1 < n) : ((2 * r * (n - 1) + 1 : ℕ) : ℕ∞) ≤ zero_sum_w r n := by unfold zero_sum_w refine le_iInf₂ (fun N hN => ?_) by_contra hlt rw [not_le] at hlt have hle : N ≤ 2 * r * (n - 1) := by have := (Nat.cast_lt (α := ℕ∞)).mp hlt omega obtain ⟨hbad, hlen⟩ := zero_sum_basis_seq_w_bad r n hn have htl : ((zero_sum_basis_seq r n).take N).length ≤ (zero_sum_basis_seq r n).length := by simp obtain ⟨I, hIne, hIdiv, j, hj⟩ := hN ((zero_sum_basis_seq r n).take N) (by simp [hlen]; omega) (fun a ha => hbad.1 a (List.mem_of_mem_take ha)) have hsum : ∀ j, ∑ i ∈ I.map ⟨Fin.castLE htl, Fin.castLE_injective htl⟩, (zero_sum_basis_seq r n).get i j = ∑ i ∈ I, ((zero_sum_basis_seq r n).take N).get i j := by intro j rw [Finset.sum_map] refine Finset.sum_congr rfl (fun i _ => ?_) simp [List.getElem_take] apply hbad.2 (I.map ⟨Fin.castLE htl, Fin.castLE_injective htl⟩) refine ⟨hIne.map, fun j => ?_, j, ?_⟩ · rw [hsum]; exact hIdiv j · rw [hsum]; exact hj