AFTD Auto-Formalizing Theoretical Domains

zero_sum_even_subsets_card_ge

theoremverified

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

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

    lines 6–9

    uses symmDiff_def

      have hsymm : I ∆ J = (I ∪ J) \ (I ∩ J) := by
        ext x
        simp [symmDiff_def]
        tauto
  2. 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).

    lines 10–14

    uses Finset.inter_subset_union, Finset.sum_sdiff, Finset.sum_union_inter, ZModModule.add_self

      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 _
  3. 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.

    lines 15–20

    uses add_assoc, add_zero

      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 := h2
  4. 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.

    lines 26–28

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

    lines 29–47

    uses Finset.filter_congr, Int.cast_sum, ZMod.intCast_zmod_eq_zero_iff_dvd, congrFun

      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]
  6. 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|.

    lines 48–71

    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_mem

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

    lines 72–75

    uses Finset.card_eq_sum_card_fiberwise, ZMod.card, Fintype.card_fin

      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]
  8. 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).

    lines 76–87

    uses Fintype.card_finset, Finset.card_univ, Finset.sum_le_sum, Finset.sum_const, nsmul_eq_mul

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

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

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