zero_sum_w_two_le
Upper 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 but not 0 mod 4.
Statement
theorem zero_sum_w_two_le (r : ℕ) : zero_sum_w r 2 ≤ ((2 * r + 1 : ℕ) : ℕ∞)- Formalizes
- arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems of new types), Theorem 1.2(i) w_r(2) = 2r + 1; the paper's upper bound classifies the w-bad sequences mod 4 (Theorem 3.1); this route replaces the classification by a counting argument.
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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_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)).
- finset_family_card_sq_le_of_inter_symm_diffA family K of subsets of a finite set U that contains the empty set, is closed under intersection and symmetric difference, and contains…
- zero_sum_even_subsets_card_geFor vectors a_i in Z^r indexed by a finite set, the index subsets whose sum is even in every coordinate number at least 2^{|ι| - r}.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 1
- zero_sum_w_twoFor every r ≥ 1, w_r(2) = 2r + 1.
The proof, explained
The proof establishes the upper bound w_r(2) ≤ 2r + 1 by contradiction. Given an admissible sequence of 2r + 1 vectors in ℤ^r (each nonzero mod 2), let K be the family of index subsets whose vector sum is 0 mod 2 in all coordinates. Assuming no good subsequence exists, every sum for I ∈ K must actually be 0 mod 4. Using an algebraic identity relating sums over I △ J, I ∩ J, I, and J, this mod 4 property implies that K is closed under both symmetric difference and intersection; combined with the absence of singletons in K, a set-system inequality forces |K|² ≤ 2^(2r + 1). On the other hand, linear algebra mod 2 yields 2^(2r + 1) ≤ 2^r |K|, which together imply |K| ≤ 2^r and hence 2^(2r + 1) ≤ 2^(2r), an impossibility.
For any integer-valued function f and finite sets I and J, ∑_{i ∈ I △ J} f(i) + 2 ∑_{i ∈ I ∩ J} f(i) = ∑_{i ∈ I} f(i) + ∑_{i ∈ J} f(i).
We decompose the sums over I and J into sums over their intersection I ∩ J and set differences I \ J and J \ I using Finset.sum_inter_add_sum_sdiff. Because I \ J and J \ I are disjoint (Finset.disjoint_left, Finset.mem_sdiff), their union is the symmetric difference I △ J (Finset.symmDiff_def), and the sum over I △ J is the sum of the two differences (Finset.sum_union). Adding the two decompositions together yields the desired identity by linear integer arithmetic (omega).
uses
Finset.sum_inter_add_sum_sdiff,Finset.inter_comm,Finset.disjoint_left,Finset.mem_sdiff,Finset.symmDiff_def,Finset.sum_unionhave h1 := Finset.sum_inter_add_sum_sdiff I J f have h2 := Finset.sum_inter_add_sum_sdiff J I f rw [Finset.inter_comm J I] at h2 have hdisj : Disjoint (I \ J) (J \ I) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_sdiff] at hx hx' exact hx.2 hx'.1 have h3 : ∑ i ∈ I \ J, f i + ∑ i ∈ J \ I, f i = ∑ i ∈ symmDiff I J, f i := by rw [Finset.symmDiff_def, Finset.sum_union hdisj] omega
To prove w_r(2) ≤ 2r + 1, it suffices to assume there exists an admissible sequence A of length 2r + 1 with no good subsequence, and derive a contradiction.
The invariant w_r(2) is defined as the infimum of lengths N ensuring the existence of a good subsequence for every admissible sequence of length N. By iInf₂_le, specializing to N = 2r + 1 suffices. We then assume for contradiction that there exists an admissible list A of length 2r + 1 such that no index set I forms a good subsequence.
uses
iInf₂_lerefine iInf₂_le (f := fun (N : ℕ) (_ : ∀ A : List (Fin r → ℤ), A.length = N → zero_sum_admissible 2 A → ∃ I, zero_sum_good_subseq 2 A I) => (N : ℕ∞)) (2 * r + 1) ?_ intro A hlen hadm by_contra hcon push Not at hcon
We define K to be the family of index sets I ⊆ {0, …, 2r} whose vector sum ∑_{i ∈ I} A_i is divisible by 2 in every coordinate.
We let a_i denote the i-th vector A_i in ℤ^r, and define K by filtering the powerset of indices for those subsets whose sum is even in all coordinates j. We record the characterization I ∈ K ↔ ∀ j, 2 ∣ ∑_{i ∈ I} a_i(j).
set a : Fin A.length → Fin r → ℤ := fun i j => A.get i j with ha set K : Finset (Finset (Fin A.length)) := (Finset.univ : Finset (Finset (Fin A.length))).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j) with hK have hKmem : ∀ I : Finset (Fin A.length), I ∈ K ↔ ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j := by intro I rw [hK] simp
For every set I ∈ K and every coordinate j, the sum ∑_{i ∈ I} a_i(j) is divisible by 4.
If I is empty, the sum is 0, which is divisible by 4. If I is nonempty and some coordinate sum were not divisible by 4, then I would be a nonempty subsequence summing to 0 mod 2 and not to 0 mod 4—which is precisely the definition of a good subsequence (zero_sum_good_subseq). This contradicts the assumption that no good subsequence exists.
uses
Finset.eq_empty_or_nonempty,zero_sum_good_subseqhave hbad : ∀ I ∈ K, ∀ j, (4 : ℤ) ∣ ∑ i ∈ I, a i j := by intro I hI j have hev := (hKmem I).1 hI rcases Finset.eq_empty_or_nonempty I with h | hne · subst h simp · by_contra h4 refine hcon I ?_ rw [zero_sum_good_subseq] refine ⟨hne, fun j => hev j, j, ?_⟩ norm_num exact h4
The family K is closed under symmetric difference: if I, J ∈ K, then I △ J ∈ K.
By the helper identity zero_sum_w_two_le_sum_symmDiff, ∑_{i ∈ I △ J} a_i(j) = ∑_{i ∈ I} a_i(j) + ∑_{i ∈ J} a_i(j) - 2 ∑_{i ∈ I ∩ J} a_i(j). Since I, J ∈ K, the first two sums are divisible by 2, and the third term is an explicit multiple of 2. Thus the sum over I △ J is divisible by 2 in every coordinate (dvd_sub, dvd_add, dvd_mul_right), proving I △ J ∈ K.
uses
zero_sum_w_two_le_sum_symmDiff,dvd_sub,dvd_add,dvd_mul_righthave hKsd : ∀ I ∈ K, ∀ J ∈ K, symmDiff I J ∈ K := by intro I hI J hJ rw [hKmem] intro j have e1 : (2 : ℤ) ∣ ∑ i ∈ I, a i j := (hKmem I).1 hI j have e2 : (2 : ℤ) ∣ ∑ i ∈ J, a i j := (hKmem J).1 hJ j have hid := zero_sum_w_two_le_sum_symmDiff (f := fun i => a i j) I J have hEq : ∑ i ∈ symmDiff I J, a i j = ∑ i ∈ I, a i j + ∑ i ∈ J, a i j - 2 * ∑ i ∈ I ∩ J, a i j := by linarith rw [hEq] exact dvd_sub (dvd_add e1 e2) (dvd_mul_right 2 _)
The family K is closed under intersection: if I, J ∈ K, then I ∩ J ∈ K.
Rearranging the summation identity gives 2 ∑_{i ∈ I ∩ J} a_i(j) = ∑_{i ∈ I} a_i(j) + ∑_{i ∈ J} a_i(j) - ∑_{i ∈ I △ J} a_i(j). Since I, J ∈ K and I △ J ∈ K, Step 4 implies that all three sums on the right are divisible by 4. Therefore 2 ∑_{i ∈ I ∩ J} a_i(j) is divisible by 4 (dvd_sub, dvd_add), so the sum over I ∩ J is divisible by 2, meaning I ∩ J ∈ K.
uses
zero_sum_w_two_le_sum_symmDiff,dvd_sub,dvd_addhave hKinter : ∀ I ∈ K, ∀ J ∈ K, I ∩ J ∈ K := by intro I hI J hJ rw [hKmem] intro j have hid := zero_sum_w_two_le_sum_symmDiff (f := fun i => a i j) I J have eI := hbad I hI j have eJ := hbad J hJ j have eS := hbad (symmDiff I J) (hKsd I hI J hJ) j have hEq : 2 * ∑ i ∈ I ∩ J, a i j = ∑ i ∈ I, a i j + ∑ i ∈ J, a i j - ∑ i ∈ symmDiff I J, a i j := by linarith have h4 : (4 : ℤ) ∣ 2 * ∑ i ∈ I ∩ J, a i j := by rw [hEq] exact dvd_sub (dvd_add eI eJ) eS obtain ⟨k, hk⟩ := h4 exact ⟨k, by linarith⟩
The family K satisfies |K|² ≤ 2^(2r + 1).
We apply finset_family_card_sq_le_of_inter_symm_diff: K contains ∅, is closed under intersection and symmetric difference, and contains no singletons {x} (since admissibility implies that every vector A_x has a coordinate not divisible by 2, so {x} ∉ K). Hence |K|² ≤ 2^|U| = 2^(2r + 1).
uses
finset_family_card_sq_le_of_inter_symm_diff,Finset.subset_univ,List.get_memhave h1 : K.card ^ 2 ≤ 2 ^ (Finset.univ : Finset (Fin A.length)).card := by refine finset_family_card_sq_le_of_inter_symm_diff (Finset.univ : Finset (Fin A.length)) K (fun I _ => Finset.subset_univ I) ?_ hKinter hKsd ?_ · rw [hKmem]; intro j; simp · intro x hx rw [hKmem] at hx obtain ⟨j, hj⟩ := hadm (A.get x) (List.get_mem A x) exact hj (by simpa [ha] using hx j)
The family K satisfies 2^(2r + 1) ≤ 2^r * |K|, and |K| > 0.
By zero_sum_even_subsets_card_ge, any sequence of length N in ℤ^r has at least 2^N / 2^r subsets whose sum is even in all coordinates, giving 2^(2r + 1) ≤ 2^r * |K|. In addition, ∅ ∈ K because the empty sum is 0, so |K| > 0 (Finset.card_pos).
uses
zero_sum_even_subsets_card_ge,Finset.card_poshave h2 : 2 ^ (Finset.univ : Finset (Fin A.length)).card ≤ 2 ^ r * K.card := by have h := zero_sum_even_subsets_card_ge (ι := Fin A.length) r a simpa [hK] using h have hcard_pos : 0 < K.card := by rw [Finset.card_pos] refine ⟨∅, ?_⟩ rw [hKmem] intro j simp
|K| ≤ 2^r, and consequently 2^(2r + 1) ≤ 2^r * 2^r.
Combining |K|² ≤ 2^(2r + 1) ≤ 2^r * |K| gives |K|² ≤ 2^r * |K| (le_trans). Since |K| > 0, we can cancel one factor of |K| to get |K| ≤ 2^r (Nat.le_of_mul_le_mul_right, pow_two). Multiplying by 2^r gives 2^r * |K| ≤ 2^r * 2^r (Nat.mul_le_mul_left), which along with 2^(2r + 1) ≤ 2^r * |K| yields 2^(2r + 1) ≤ 2^r * 2^r (le_trans), using |A| = 2r + 1 (Fintype.card_fin).
uses
le_trans,pow_two,Nat.le_of_mul_le_mul_right,Nat.mul_le_mul_left,Fintype.card_finhave hKle : K.card ≤ 2 ^ r := by have h3 : K.card ^ 2 ≤ 2 ^ r * K.card := le_trans h1 h2 rw [pow_two] at h3 exact Nat.le_of_mul_le_mul_right h3 hcard_pos have h4 : 2 ^ (2 * r + 1) ≤ 2 ^ r * 2 ^ r := by have h3 : 2 ^ (Finset.univ : Finset (Fin A.length)).card ≤ 2 ^ r * K.card := h2 have h5 : 2 ^ r * K.card ≤ 2 ^ r * 2 ^ r := Nat.mul_le_mul_left _ hKle have h6 : (Finset.univ : Finset (Fin A.length)).card = 2 * r + 1 := by simp [Fintype.card_fin, hlen] rw [h6] at h3 exact le_trans h3 h5
Contradiction: 2 * 2^(2r) ≤ 2^(2r) for positive 2^(2r).
Since 2^r * 2^r = 2^(2r) (pow_add) and 2^(2r + 1) = 2 * 2^(2r) (pow_succ), the inequality simplifies to 2 * 2^(2r) ≤ 2^(2r). Since 2^(2r) > 0 (pow_pos), this contradicts 2 ≤ 1 (omega).
uses
pow_add,pow_succ,pow_poshave h5 : 2 ^ r * 2 ^ r = 2 ^ (2 * r) := by rw [← pow_add] ring_nf rw [h5] at h4 have h6 : 2 ^ (2 * r + 1) = 2 * 2 ^ (2 * r) := by rw [pow_succ] ring rw [h6] at h4 have hpos : 0 < 2 ^ (2 * r) := pow_pos (by norm_num) _ omega
Finset.sum_inter_add_sum_sdiff- For finite sets s and t, the sum of a function over s ∩ t plus the sum over s \ t equals the sum over s.
Finset.inter_comm- Set intersection is commutative: s₁ ∩ s₂ = s₂ ∩ s₁.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Finset.symmDiff_def- The symmetric difference of s and t is the union of (s \ t) and (t \ s).
Finset.sum_union- The sum of a function over the union of two disjoint finite sets is the sum of the sums over each set.
iInf₂_le- An indexed infimum over two indices is bounded above by any specific instance.
Finset.eq_empty_or_nonempty- Every finite set is either empty or nonempty.
zero_sum_good_subseq- Definition of a good zero-sum subsequence: a nonempty index set I whose vector sum is divisible by n in every coordinate, but not divisible by n² in at least one coordinate.
zero_sum_w_two_le_sum_symmDiff- For any integer function f and finite sets I, J, the sum over I △ J plus twice the sum over I ∩ J equals the sum over I plus the sum over J.
dvd_sub- If a divides b and a divides c, then a divides b - c.
dvd_add- If a divides b and a divides c, then a divides b + c.
dvd_mul_right- Any number a divides a * b.
finset_family_card_sq_le_of_inter_symm_diff- If a family of subsets K ⊆ P(U) contains ∅, is closed under intersection and symmetric difference, and contains no singletons, then |K|² ≤ 2^|U|.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of the universal set.
List.get_mem- The element obtained from a list at any valid index belongs to the list.
zero_sum_even_subsets_card_ge- For any family of vectors in ℤ^r indexed by a finite set ι, the number of index subsets whose sum is even in every coordinate is at least 2^|ι| / 2^r.
Finset.card_pos- A finite set has strictly positive cardinality if and only if it is nonempty.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
pow_two- The square a² equals a * a.
Nat.le_of_mul_le_mul_right- For natural numbers, if a * c ≤ b * c and c > 0, then a ≤ b.
Nat.mul_le_mul_left- Multiplication by a natural number preserves inequality: if n ≤ m, then k * n ≤ k * m.
Fintype.card_fin- The cardinality of Fin n is n.
pow_add- Powers add under multiplication: a^(m + n) = a^m * a^n.
pow_succ- The successor power satisfies a^(n + 1) = a^n * a.
pow_pos- A positive base raised to any natural power is strictly positive.
- The quantity zero_sum_w is formally defined as an infimum in ℕ∞, so proving the upper bound at 2r + 1 requires invoking iInf₂_le to specialize the infimum.
- The summation identity over symmetric differences, zero_sum_w_two_le_sum_symmDiff, is proved as a helper lemma immediately before the main theorem.
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.
/-- For integers, the sum over the symmetric difference plus twice the sum over theintersection equals the sum of the two sums. -/lemma zero_sum_w_two_le_sum_symmDiff {ι : Type*} [DecidableEq ι] (f : ι → ℤ) (I J : Finset ι) : ∑ i ∈ symmDiff I J, f i + 2 * ∑ i ∈ I ∩ J, f i = ∑ i ∈ I, f i + ∑ i ∈ J, f i := by have h1 := Finset.sum_inter_add_sum_sdiff I J f have h2 := Finset.sum_inter_add_sum_sdiff J I f rw [Finset.inter_comm J I] at h2 have hdisj : Disjoint (I \ J) (J \ I) := by rw [Finset.disjoint_left] intro x hx hx' simp only [Finset.mem_sdiff] at hx hx' exact hx.2 hx'.1 have h3 : ∑ i ∈ I \ J, f i + ∑ i ∈ J \ I, f i = ∑ i ∈ symmDiff I J, f i := by rw [Finset.symmDiff_def, Finset.sum_union hdisj] omegatheorem zero_sum_w_two_le (r : ℕ) : zero_sum_w r 2 ≤ ((2 * r + 1 : ℕ) : ℕ∞) := by refine iInf₂_le (f := fun (N : ℕ) (_ : ∀ A : List (Fin r → ℤ), A.length = N → zero_sum_admissible 2 A → ∃ I, zero_sum_good_subseq 2 A I) => (N : ℕ∞)) (2 * r + 1) ?_ intro A hlen hadm by_contra hcon push Not at hcon set a : Fin A.length → Fin r → ℤ := fun i j => A.get i j with ha set K : Finset (Finset (Fin A.length)) := (Finset.univ : Finset (Finset (Fin A.length))).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j) with hK have hKmem : ∀ I : Finset (Fin A.length), I ∈ K ↔ ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j := by intro I rw [hK] simp have hbad : ∀ I ∈ K, ∀ j, (4 : ℤ) ∣ ∑ i ∈ I, a i j := by intro I hI j have hev := (hKmem I).1 hI rcases Finset.eq_empty_or_nonempty I with h | hne · subst h simp · by_contra h4 refine hcon I ?_ rw [zero_sum_good_subseq] refine ⟨hne, fun j => hev j, j, ?_⟩ norm_num exact h4 have hKsd : ∀ I ∈ K, ∀ J ∈ K, symmDiff I J ∈ K := by intro I hI J hJ rw [hKmem] intro j have e1 : (2 : ℤ) ∣ ∑ i ∈ I, a i j := (hKmem I).1 hI j have e2 : (2 : ℤ) ∣ ∑ i ∈ J, a i j := (hKmem J).1 hJ j have hid := zero_sum_w_two_le_sum_symmDiff (f := fun i => a i j) I J have hEq : ∑ i ∈ symmDiff I J, a i j = ∑ i ∈ I, a i j + ∑ i ∈ J, a i j - 2 * ∑ i ∈ I ∩ J, a i j := by linarith rw [hEq] exact dvd_sub (dvd_add e1 e2) (dvd_mul_right 2 _) have hKinter : ∀ I ∈ K, ∀ J ∈ K, I ∩ J ∈ K := by intro I hI J hJ rw [hKmem] intro j have hid := zero_sum_w_two_le_sum_symmDiff (f := fun i => a i j) I J have eI := hbad I hI j have eJ := hbad J hJ j have eS := hbad (symmDiff I J) (hKsd I hI J hJ) j have hEq : 2 * ∑ i ∈ I ∩ J, a i j = ∑ i ∈ I, a i j + ∑ i ∈ J, a i j - ∑ i ∈ symmDiff I J, a i j := by linarith have h4 : (4 : ℤ) ∣ 2 * ∑ i ∈ I ∩ J, a i j := by rw [hEq] exact dvd_sub (dvd_add eI eJ) eS obtain ⟨k, hk⟩ := h4 exact ⟨k, by linarith⟩ have h1 : K.card ^ 2 ≤ 2 ^ (Finset.univ : Finset (Fin A.length)).card := by refine finset_family_card_sq_le_of_inter_symm_diff (Finset.univ : Finset (Fin A.length)) K (fun I _ => Finset.subset_univ I) ?_ hKinter hKsd ?_ · rw [hKmem]; intro j; simp · intro x hx rw [hKmem] at hx obtain ⟨j, hj⟩ := hadm (A.get x) (List.get_mem A x) exact hj (by simpa [ha] using hx j) have h2 : 2 ^ (Finset.univ : Finset (Fin A.length)).card ≤ 2 ^ r * K.card := by have h := zero_sum_even_subsets_card_ge (ι := Fin A.length) r a simpa [hK] using h have hcard_pos : 0 < K.card := by rw [Finset.card_pos] refine ⟨∅, ?_⟩ rw [hKmem] intro j simp have hKle : K.card ≤ 2 ^ r := by have h3 : K.card ^ 2 ≤ 2 ^ r * K.card := le_trans h1 h2 rw [pow_two] at h3 exact Nat.le_of_mul_le_mul_right h3 hcard_pos have h4 : 2 ^ (2 * r + 1) ≤ 2 ^ r * 2 ^ r := by have h3 : 2 ^ (Finset.univ : Finset (Fin A.length)).card ≤ 2 ^ r * K.card := h2 have h5 : 2 ^ r * K.card ≤ 2 ^ r * 2 ^ r := Nat.mul_le_mul_left _ hKle have h6 : (Finset.univ : Finset (Fin A.length)).card = 2 * r + 1 := by simp [Fintype.card_fin, hlen] rw [h6] at h3 exact le_trans h3 h5 have h5 : 2 ^ r * 2 ^ r = 2 ^ (2 * r) := by rw [← pow_add] ring_nf rw [h5] at h4 have h6 : 2 ^ (2 * r + 1) = 2 * 2 ^ (2 * r) := by rw [pow_succ] ring rw [h6] at h4 have hpos : 0 < 2 ^ (2 * r) := pow_pos (by norm_num) _ omega