AFTD Auto-Formalizing Theoretical Domains

zero_sum_w_two_le

theoremverifiedformalization

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 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.

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

    lines 6–16

    uses Finset.sum_inter_add_sum_sdiff, Finset.inter_comm, Finset.disjoint_left, Finset.mem_sdiff, Finset.symmDiff_def, Finset.sum_union

      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]
      omega
  2. 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.

    lines 19–23

    uses iInf₂_le

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

    lines 24–31

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

    lines 32–43

    uses Finset.eq_empty_or_nonempty, zero_sum_good_subseq

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

    lines 44–54

    uses zero_sum_w_two_le_sum_symmDiff, dvd_sub, dvd_add, dvd_mul_right

      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 _)
  6. 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.

    lines 55–69

    uses zero_sum_w_two_le_sum_symmDiff, dvd_sub, dvd_add

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

    lines 70–77

    uses finset_family_card_sq_le_of_inter_symm_diff, Finset.subset_univ, List.get_mem

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

    lines 78–86

    uses zero_sum_even_subsets_card_ge, Finset.card_pos

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

    lines 87–97

    uses le_trans, pow_two, Nat.le_of_mul_le_mul_right, Nat.mul_le_mul_left, Fintype.card_fin

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

    lines 98–107

    uses pow_add, pow_succ, pow_pos

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

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

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