zero_sum_even_subsets_card_ge
For 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}.
Statement
theorem zero_sum_even_subsets_card_ge {ι : Type*} [Fintype ι] [DecidableEq ι] (r : ℕ) (a : ι → Fin r → ℤ) : 2 ^ Fintype.card ι ≤ 2 ^ r * ((Finset.univ : Finset (Finset ι)).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j)).card
- Source
- Step toward zero_sum_w_two_le. 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- Used by 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 collection of subsets of ι forms an abelian group under symmetric difference ∆, and reducing coordinate sums modulo 2 defines a group homomorphism P : 𝒫(ι) → (ℤ/2ℤ)^r. The subsets whose coordinate sums are all even correspond exactly to the kernel K = P⁻¹(0). For every vector v, translating any subset in the fiber P⁻¹(v) by a fixed witness I₀ via I ↦ I ∆ I₀ injects P⁻¹(v) into K, showing that every fiber has size at most |K|. Partitioning the 2^{|ι|} subsets into the 2^r fibers of P immediately yields 2^{|ι|} ≤ 2^r * |K|, or equivalently |K| ≥ 2^{|ι| - r}.
The symmetric difference I ∆ J can be expressed as (I ∪ J) \ (I ∩ J).
An element belongs to the symmetric difference I ∆ J if and only if it belongs to I ∪ J but not I ∩ J. This set equality is verified by extensionality followed by propositional logic on the membership definition of symmDiff.
uses
symmDiff_defhave hsymm : I ∆ J = (I ∪ J) \ (I ∩ J) := by ext x simp [symmDiff_def] tauto
Finite sums decompose along unions and differences, and adding any element to itself in ℤ/2ℤ yields zero.
Since I ∩ J ⊆ I ∪ J (Finset.inter_subset_union), splitting the sum over I ∪ J gives ∑_{(I ∪ J) \ (I ∩ J)} f + ∑_{I ∩ J} f = ∑_{I ∪ J} f (Finset.sum_sdiff). Inclusion-exclusion gives ∑_{I ∪ J} f + ∑_{I ∩ J} f = ∑_I f + ∑_J f (Finset.sum_union_inter). Furthermore, in the ℤ/2ℤ-module, doubling the sum over I ∩ J yields 0 (ZModModule.add_self).
uses
Finset.inter_subset_union,Finset.sum_sdiff,Finset.sum_union_inter,ZModModule.add_selfhave hsub : I ∩ J ⊆ I ∪ J := Finset.inter_subset_union have h1 := Finset.sum_sdiff (s₁ := I ∩ J) (s₂ := I ∪ J) (f := f) hsub have h2 := Finset.sum_union_inter (s₁ := I) (s₂ := J) (f := f) rw [hsymm] have hC : (∑ x ∈ I ∩ J, f x) + (∑ x ∈ I ∩ J, f x) = 0 := ZModModule.add_self _
The sum of f over I ∆ J equals the sum over I plus the sum over J in ℤ/2ℤ.
Rewriting I ∆ J as (I ∪ J) \ (I ∩ J), we add and subtract ∑_{I ∩ J} f (which cancels since x + x = 0 by add_assoc and add_zero). We then substitute the sum over I ∪ J and apply inclusion-exclusion to obtain ∑_I f + ∑_J f.
uses
add_assoc,add_zerocalc ∑ x ∈ (I ∪ J) \ (I ∩ J), f x = ((∑ x ∈ (I ∪ J) \ (I ∩ J), f x) + (∑ x ∈ I ∩ J, f x)) + (∑ x ∈ I ∩ J, f x) := by rw [add_assoc, hC, add_zero] _ = (∑ x ∈ I ∪ J, f x) + (∑ x ∈ I ∩ J, f x) := by rw [h1] _ = ∑ x ∈ I, f x + ∑ x ∈ J, f x := h2
We define the coordinate-wise parity map P : 𝒫(ι) → (Fin r → ℤ/2ℤ) and its kernel K.
For every subset I ⊆ ι and coordinate j, P(I)(j) is the sum of a_i(j) modulo 2. The set K is defined as the fiber P⁻¹(0), representing the subsets whose coordinate sums are all even.
classical let P : Finset ι → (Fin r → ZMod 2) := fun I j => ∑ i ∈ I, (a i j : ZMod 2) let K : Finset (Finset ι) := (Finset.univ : Finset (Finset ι)).filter (fun I => P I = 0)
The subsets whose coordinate sums are even in ℤ are precisely the elements of K.
For any coordinate j, the integer sum being divisible by 2 is equivalent to its reduction modulo 2 being zero in ℤ/2ℤ (Int.cast_sum, ZMod.intCast_zmod_eq_zero_iff_dvd, congrFun). Thus, filtering all subsets by evenness in every coordinate coincides with K (Finset.filter_congr), reducing the theorem to bounding |K|.
uses
Finset.filter_congr,Int.cast_sum,ZMod.intCast_zmod_eq_zero_iff_dvd,congrFunhave hK : (Finset.univ : Finset (Finset ι)).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j) = K := by dsimp [K] apply Finset.filter_congr intro I hI dsimp [P] constructor · intro h funext j change (∑ i ∈ I, (a i j : ZMod 2)) = 0 rw [← Int.cast_sum] rw [ZMod.intCast_zmod_eq_zero_iff_dvd] exact h j · intro h j rw [show (2 : ℤ) = ((2 : ℕ) : ℤ) by norm_num] rw [← ZMod.intCast_zmod_eq_zero_iff_dvd] rw [Int.cast_sum] exact congrFun h j rw [hK]
Every fiber P⁻¹(v) has cardinality at most |K|.
If a fiber P⁻¹(v) is non-empty, choose an element I₀ ∈ P⁻¹(v). The map I ↦ I ∆ I₀ maps P⁻¹(v) into K because P(I ∆ I₀)(j) = P(I)(j) + P(I₀)(j) = v(j) + v(j) = 0 by zero_sum_even_subsets_card_ge_sum_symmDiff and ZModModule.add_self. This map is injective by symmDiff_left_inj.mp, so |P⁻¹(v)| ≤ |K| (Finset.card_le_card_of_injOn). If the fiber is empty (Finset.filter_false_of_mem), its cardinality is 0, which is also at most |K|.
uses
Finset.card_le_card_of_injOn,Finset.coe_filter,Set.mem_ofPred_eq,Finset.mem_univ,true_and,Finset.mem_coe,Finset.mem_filter,zero_sum_even_subsets_card_ge_sum_symmDiff,congrFun,ZModModule.add_self,symmDiff_left_inj.mp,Finset.filter_false_of_memhave hfiber_le : ∀ v : Fin r → ZMod 2, ((Finset.univ : Finset (Finset ι)).filter (fun I => P I = v)).card ≤ K.card := by intro v by_cases hv : ∃ I0, P I0 = v · obtain ⟨I0, hI0⟩ := hv apply Finset.card_le_card_of_injOn (fun I => I ∆ I0) · intro I hI simp only [Finset.coe_filter, Set.mem_ofPred_eq, Finset.mem_univ, true_and] at hI dsimp [K] simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] funext j change (∑ i ∈ I ∆ I0, (a i j : ZMod 2)) = 0 rw [zero_sum_even_subsets_card_ge_sum_symmDiff] have hIv : (∑ i ∈ I, (a i j : ZMod 2)) = v j := congrFun hI j have hI0v : (∑ i ∈ I0, (a i j : ZMod 2)) = v j := congrFun hI0 j rw [hIv, hI0v] exact ZModModule.add_self (v j) · intro I hI I' hI' hEq exact symmDiff_left_inj.mp hEq · have hv' : ∀ I : Finset ι, P I ≠ v := fun I h => hv ⟨I, h⟩ have hempty : (Finset.univ : Finset (Finset ι)).filter (fun I => P I = v) = ∅ := Finset.filter_false_of_mem (by intro I hI; exact hv' I) rw [hempty] simp
The total number of subsets 𝒫(ι) is the sum of all fiber sizes, and the codomain has size 2^r.
Partitioning the power set 𝒫(ι) into fibers of P gives |𝒫(ι)| = ∑_v |P⁻¹(v)| (Finset.card_eq_sum_card_fiberwise). The codomain (Fin r → ℤ/2ℤ) has cardinality |ℤ/2ℤ|^r = 2^r by ZMod.card and Fintype.card_fin.
uses
Finset.card_eq_sum_card_fiberwise,ZMod.card,Fintype.card_finhave hsum := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Finset ι))) (f := P) (t := (Finset.univ : Finset (Fin r → ZMod 2))) (by intro I hI; simp) have hcard_codomain : Fintype.card (Fin r → ZMod 2) = 2 ^ r := by simp [ZMod.card, Fintype.card_fin]
2^{|ι|} ≤ 2^r * |K|, which completes the proof.
The total number of subsets of ι is 2^{|ι|} (Fintype.card_finset, Finset.card_univ). Substituting the fiberwise sum and bounding each of the 2^r fiber sizes by |K| (Finset.sum_le_sum) yields a sum of 2^r copies of |K|, which equals 2^r * |K| (Finset.sum_const, nsmul_eq_mul).
uses
Fintype.card_finset,Finset.card_univ,Finset.sum_le_sum,Finset.sum_const,nsmul_eq_mulcalc 2 ^ Fintype.card ι = Fintype.card (Finset ι) := by rw [Fintype.card_finset] _ = (Finset.univ : Finset (Finset ι)).card := by rw [Finset.card_univ] _ = ∑ v ∈ (Finset.univ : Finset (Fin r → ZMod 2)), ((Finset.univ : Finset (Finset ι)).filter (fun I => P I = v)).card := hsum _ ≤ ∑ v ∈ (Finset.univ : Finset (Fin r → ZMod 2)), K.card := by apply Finset.sum_le_sum intro v hv exact hfiber_le v _ = 2 ^ r * K.card := by rw [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hcard_codomain] simp
symmDiff_def- The symmetric difference of two sets a and b is the union of their differences, (a \ b) ∪ (b \ a).
Finset.inter_subset_union- The intersection of two finite sets is a subset of their union.
Finset.sum_sdiff- For a subset s₁ ⊆ s₂, the sum over s₂ \ s₁ plus the sum over s₁ equals the sum over s₂.
Finset.sum_union_inter- The sum over the union plus the sum over the intersection of two finite sets equals the sum of the individual sums.
ZModModule.add_self- In any module over ℤ/2ℤ, adding an element to itself yields zero (x + x = 0).
add_assoc- Addition is associative: (a + b) + c = a + (b + c).
add_zero- Adding zero to an element leaves it unchanged: a + 0 = a.
Finset.filter_congr- If two predicates are equivalent on all elements of a finite set s, filtering s by either predicate produces the same finset.
Int.cast_sum- The cast of a finite sum of integers into a ring equals the sum of the casted values.
ZMod.intCast_zmod_eq_zero_iff_dvd- An integer cast to ℤ/bℤ is zero if and only if b divides the integer.
congrFun- Equal functions take equal values at any argument.
Finset.card_le_card_of_injOn- If a map f maps a finite set s into a finite set t and is injective on s, then |s| ≤ |t|.
Finset.coe_filter- The set coercion of a filtered finset consists of all elements of s satisfying the filtering predicate.
Set.mem_ofPred_eq- An element x belongs to the set-builder {y | p y} if and only if p x holds.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
true_and- True ∧ p is equivalent to p.
Finset.mem_coe- An element belongs to the set coercion of a finset if and only if it belongs to the finset.
Finset.mem_filter- An element belongs to a filtered finset if and only if it is in the original set and satisfies the predicate.
zero_sum_even_subsets_card_ge_sum_symmDiff- For any function f into ℤ/2ℤ, the sum over the symmetric difference I ∆ J equals the sum over I plus the sum over J.
symmDiff_left_inj.mp- Symmetric difference with a fixed set on the right is injective: a ∆ b = c ∆ b implies a = c.
Finset.filter_false_of_mem- Filtering a finite set by a predicate that is false for all members yields the empty set.
Finset.card_eq_sum_card_fiberwise- The cardinality of a finite set s is the sum of the cardinalities of the fibers of any map f on s over the codomain t.
ZMod.card- The cardinality of the finite ring ℤ/nℤ is n.
Fintype.card_fin- The cardinality of Fin n is n.
Fintype.card_finset- The number of subsets of a finite type α is 2^(|α|).
Finset.card_univ- The cardinality of Finset.univ for a finite type α equals Fintype.card α.
Finset.sum_le_sum- A sum over a finite set is bounded above by another sum if the inequality holds term-by-term.
Finset.sum_const- The sum of a constant value b over a finite set s equals |s| • b.
nsmul_eq_mul- Scalar multiplication of a ring element by a natural number n equals multiplication by n.
- The equivalence between coordinate sums being even in ℤ and vanishing in ℤ/2ℤ is mediated by standard integer casting and divisibility lemmas.
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.
open scoped symmDifflemma zero_sum_even_subsets_card_ge_sum_symmDiff {ι : Type*} [DecidableEq ι] (f : ι → ZMod 2) (I J : Finset ι) : ∑ i ∈ I ∆ J, f i = ∑ i ∈ I, f i + ∑ i ∈ J, f i := by have hsymm : I ∆ J = (I ∪ J) \ (I ∩ J) := by ext x simp [symmDiff_def] tauto have hsub : I ∩ J ⊆ I ∪ J := Finset.inter_subset_union have h1 := Finset.sum_sdiff (s₁ := I ∩ J) (s₂ := I ∪ J) (f := f) hsub have h2 := Finset.sum_union_inter (s₁ := I) (s₂ := J) (f := f) rw [hsymm] have hC : (∑ x ∈ I ∩ J, f x) + (∑ x ∈ I ∩ J, f x) = 0 := ZModModule.add_self _ calc ∑ x ∈ (I ∪ J) \ (I ∩ J), f x = ((∑ x ∈ (I ∪ J) \ (I ∩ J), f x) + (∑ x ∈ I ∩ J, f x)) + (∑ x ∈ I ∩ J, f x) := by rw [add_assoc, hC, add_zero] _ = (∑ x ∈ I ∪ J, f x) + (∑ x ∈ I ∩ J, f x) := by rw [h1] _ = ∑ x ∈ I, f x + ∑ x ∈ J, f x := h2theorem zero_sum_even_subsets_card_ge {ι : Type*} [Fintype ι] [DecidableEq ι] (r : ℕ) (a : ι → Fin r → ℤ) : 2 ^ Fintype.card ι ≤ 2 ^ r * ((Finset.univ : Finset (Finset ι)).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j)).card := by classical let P : Finset ι → (Fin r → ZMod 2) := fun I j => ∑ i ∈ I, (a i j : ZMod 2) let K : Finset (Finset ι) := (Finset.univ : Finset (Finset ι)).filter (fun I => P I = 0) have hK : (Finset.univ : Finset (Finset ι)).filter (fun I => ∀ j, (2 : ℤ) ∣ ∑ i ∈ I, a i j) = K := by dsimp [K] apply Finset.filter_congr intro I hI dsimp [P] constructor · intro h funext j change (∑ i ∈ I, (a i j : ZMod 2)) = 0 rw [← Int.cast_sum] rw [ZMod.intCast_zmod_eq_zero_iff_dvd] exact h j · intro h j rw [show (2 : ℤ) = ((2 : ℕ) : ℤ) by norm_num] rw [← ZMod.intCast_zmod_eq_zero_iff_dvd] rw [Int.cast_sum] exact congrFun h j rw [hK] have hfiber_le : ∀ v : Fin r → ZMod 2, ((Finset.univ : Finset (Finset ι)).filter (fun I => P I = v)).card ≤ K.card := by intro v by_cases hv : ∃ I0, P I0 = v · obtain ⟨I0, hI0⟩ := hv apply Finset.card_le_card_of_injOn (fun I => I ∆ I0) · intro I hI simp only [Finset.coe_filter, Set.mem_ofPred_eq, Finset.mem_univ, true_and] at hI dsimp [K] simp only [Finset.mem_coe, Finset.mem_filter, Finset.mem_univ, true_and] funext j change (∑ i ∈ I ∆ I0, (a i j : ZMod 2)) = 0 rw [zero_sum_even_subsets_card_ge_sum_symmDiff] have hIv : (∑ i ∈ I, (a i j : ZMod 2)) = v j := congrFun hI j have hI0v : (∑ i ∈ I0, (a i j : ZMod 2)) = v j := congrFun hI0 j rw [hIv, hI0v] exact ZModModule.add_self (v j) · intro I hI I' hI' hEq exact symmDiff_left_inj.mp hEq · have hv' : ∀ I : Finset ι, P I ≠ v := fun I h => hv ⟨I, h⟩ have hempty : (Finset.univ : Finset (Finset ι)).filter (fun I => P I = v) = ∅ := Finset.filter_false_of_mem (by intro I hI; exact hv' I) rw [hempty] simp have hsum := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Finset ι))) (f := P) (t := (Finset.univ : Finset (Fin r → ZMod 2))) (by intro I hI; simp) have hcard_codomain : Fintype.card (Fin r → ZMod 2) = 2 ^ r := by simp [ZMod.card, Fintype.card_fin] calc 2 ^ Fintype.card ι = Fintype.card (Finset ι) := by rw [Fintype.card_finset] _ = (Finset.univ : Finset (Finset ι)).card := by rw [Finset.card_univ] _ = ∑ v ∈ (Finset.univ : Finset (Fin r → ZMod 2)), ((Finset.univ : Finset (Finset ι)).filter (fun I => P I = v)).card := hsum _ ≤ ∑ v ∈ (Finset.univ : Finset (Fin r → ZMod 2)), K.card := by apply Finset.sum_le_sum intro v hv exact hfiber_le v _ = 2 ^ r * K.card := by rw [Finset.sum_const, Finset.card_univ, nsmul_eq_mul, hcard_codomain] simp