AFTD Auto-Formalizing Theoretical Domains

zero_sum_basis_seq_w_bad

theoremverifiedformalization

For 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²).

Statement

theorem zero_sum_basis_seq_w_bad (r n : ℕ) (hn : 1 < n) :
    zero_sum_w_bad n (zero_sum_basis_seq r n) ∧ (zero_sum_basis_seq r n).length = 2 * r * (n - 1)
Formalizes
arXiv:2610.19965 (Proofs and disproofs of some conjectures on zero-sum problems), Lemma 3.1 (first part; the bound on w_r(n) is zero_sum_w_ge).
Verified
15 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • 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.
  • 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)).
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

The proof, explained

The sequence E_{r,n} is formed by concatenating n - 1 copies of e_j and n - 1 copies of -e_j for each of the r standard basis vectors, giving total length 2r(n - 1). Every element has a coordinate of ±1, which cannot be divisible by n > 1, so the sequence is admissible. For any subsequence and any coordinate j, the coordinate sum is bounded between -(n - 1) and n - 1 because the positive and negative entries across the entire sequence each sum to n - 1. Any integer in this range divisible by n must be 0, which is divisible by n², precluding any subsequence whose sum is ≡ 0 (mod n) but ≢ 0 (mod n²).

  1. For every coordinate j, the sum of the positive parts max(a j, 0) over all vectors a in the sequence equals n - 1.

    Unfolding the definition of the sequence, each basis direction i contributes n - 1 copies of e_i and n - 1 copies of -e_i. Projecting onto coordinate j and taking max(·, 0), only the n - 1 copies of e_j contribute a value of 1, while all -e_i and all other e_i (i ≠ j) contribute 0. Summing across all indices yields (n - 1) · 1 = n - 1.

    lines 3–12

    uses List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply, Fin.sum_univ_def

      have hpos : ∀ j : Fin r,
          ((zero_sum_basis_seq r n).map (fun a => max (a j) 0)).sum = ((n - 1 : ℕ) : ℤ) := by
        intro j
        simp [zero_sum_basis_seq, List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply]
        rw [← Fin.sum_univ_def, ← Fin.sum_univ_def]
        have h1 : ∀ i : Fin r, max (if j = i then (1 : ℤ) else 0) 0 = if j = i then 1 else 0 := by
          intro i; split_ifs <;> simp
        have h2 : ∀ i : Fin r, max (-if j = i then (1 : ℤ) else 0) 0 = 0 := by
          intro i; split_ifs <;> simp
        simp [h1, h2]
  2. For every coordinate j, the sum of the negative parts max(-a j, 0) over all vectors a in the sequence equals n - 1.

    Similarly, taking max(-a j, 0) isolates negative entries. At coordinate j, only the n - 1 copies of -e_j evaluate to 1, while all other vectors evaluate to 0, giving a total sum of n - 1.

    lines 13–22

    uses List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply, Fin.sum_univ_def

      have hneg : ∀ j : Fin r,
          ((zero_sum_basis_seq r n).map (fun a => max (-a j) 0)).sum = ((n - 1 : ℕ) : ℤ) := by
        intro j
        simp [zero_sum_basis_seq, List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply]
        rw [← Fin.sum_univ_def, ← Fin.sum_univ_def]
        have h1 : ∀ i : Fin r, max (if j = i then (1 : ℤ) else 0) 0 = if j = i then 1 else 0 := by
          intro i; split_ifs <;> simp
        have h2 : ∀ i : Fin r, max (-if j = i then (1 : ℤ) else 0) 0 = 0 := by
          intro i; split_ifs <;> simp
        simp [h1, h2]
  3. The cast of n - 1 from ℕ to ℤ equals (n : ℤ) - 1.

    Since n > 1, we have 1 ≤ n, so natural subtraction n - 1 commutes with the integer cast.

    line 23

    uses Nat.cast_sub

      have hcast : ((n - 1 : ℕ) : ℤ) = (n : ℤ) - 1 := by push_cast [Nat.cast_sub hn.le]; ring
  4. The goal is split into admissibility, absence of good subsequences, and sequence length, and admissibility is established.

    The proof decomposes into three conjuncts. To show admissibility, any vector a in the sequence is either e_j or -e_j for some index j. Its j-th coordinate is therefore 1 or -1. Since n > 1, n cannot divide 1 or -1 (which would force n ≤ 1), so coordinate j is not divisible by n.

    lines 24–38

    uses List.mem_flatMap, List.mem_finRange, true_and, List.mem_append, List.mem_replicate, Pi.single_eq_same, Int.le_of_dvd, one_pos, Pi.neg_apply, Int.dvd_neg

      refine ⟨⟨?_, ?_⟩, ?_⟩
      · intro a ha
        simp only [zero_sum_basis_seq, List.mem_flatMap, List.mem_finRange, true_and, List.mem_append,
          List.mem_replicate] at ha
        obtain ⟨j, (⟨-, rfl⟩ | ⟨-, rfl⟩)⟩ := ha
        · refine ⟨j, ?_⟩
          simp only [Pi.single_eq_same]
          intro h
          have := Int.le_of_dvd one_pos h
          omega
        · refine ⟨j, ?_⟩
          simp only [Pi.neg_apply, Pi.single_eq_same]
          intro h
          have := Int.le_of_dvd one_pos ((Int.dvd_neg).mp h)
          omega
  5. For any subsequence I and any coordinate j, the coordinate sum is bounded between -(n - 1) and n - 1.

    For the upper bound, each entry A_i(j) is bounded by max(A_i(j), 0). Summing over the subcollection I is at most summing over the entire sequence (since max(·, 0) ≥ 0), which equals n - 1 by the earlier positive sum calculation. Similarly, summing -A_i(j) over I is at most n - 1 by the negative sum calculation, which negates to the lower bound -(n - 1) ≤ ∑_{i ∈ I} A_i(j).

    lines 39–63

    uses Finset.sum_le_sum, le_max_left, Finset.sum_le_sum_of_subset_of_nonneg, Finset.subset_univ, le_max_right, Fin.sum_univ_fun_getElem, Finset.sum_neg_distrib

      · rintro I ⟨-, hdiv, j, hj⟩
        apply hj
        have hup : ∑ i ∈ I, (zero_sum_basis_seq r n).get i j ≤ ((n - 1 : ℕ) : ℤ) := by
          calc ∑ i ∈ I, (zero_sum_basis_seq r n).get i j
              ≤ ∑ i ∈ I, max ((zero_sum_basis_seq r n).get i j) 0 :=
                Finset.sum_le_sum (fun i _ => le_max_left _ _)
            _ ≤ ∑ i, max ((zero_sum_basis_seq r n).get i j) 0 :=
                Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)
                  (fun i _ _ => le_max_right _ _)
            _ = ((zero_sum_basis_seq r n).map (fun a => max (a j) 0)).sum := by
                simpa using Fin.sum_univ_fun_getElem (zero_sum_basis_seq r n) (fun a => max (a j) 0)
            _ = _ := hpos j
        have hlo : -((n - 1 : ℕ) : ℤ) ≤ ∑ i ∈ I, (zero_sum_basis_seq r n).get i j := by
          have : ∑ i ∈ I, -(zero_sum_basis_seq r n).get i j ≤ ((n - 1 : ℕ) : ℤ) := by
            calc ∑ i ∈ I, -(zero_sum_basis_seq r n).get i j
                ≤ ∑ i ∈ I, max (-(zero_sum_basis_seq r n).get i j) 0 :=
                  Finset.sum_le_sum (fun i _ => le_max_left _ _)
              _ ≤ ∑ i, max (-(zero_sum_basis_seq r n).get i j) 0 :=
                  Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)
                    (fun i _ _ => le_max_right _ _)
              _ = ((zero_sum_basis_seq r n).map (fun a => max (-a j) 0)).sum := by
                  simpa using Fin.sum_univ_fun_getElem (zero_sum_basis_seq r n) (fun a => max (-a j) 0)
              _ = _ := hneg j
          rw [Finset.sum_neg_distrib] at this
          linarith
  6. No subsequence has all coordinate sums divisible by n and at least one not divisible by n².

    Suppose for contradiction that I is such a subsequence, so n divides every coordinate sum, but n² does not divide the sum at some coordinate j. Writing the j-th coordinate sum as n · k for an integer k, the bounds -(n - 1) ≤ n · k ≤ n - 1 together with n > 1 force k = 0 (as k ≤ -1 gives n · k ≤ -n < -(n - 1) and k ≥ 1 gives n · k ≥ n > n - 1). Thus the sum is 0, which is divisible by n², a contradiction.

    lines 64–74

    uses lt_trichotomy, mul_zero, dvd_zero

        obtain ⟨k, hk⟩ := hdiv j
        rw [hk] at hup hlo ⊢
        rw [hcast] at hup hlo
        have hn' : (1 : ℤ) < n := by exact_mod_cast hn
        have hk0 : k = 0 := by
          rcases lt_trichotomy k 0 with h | h | h
          · nlinarith
          · exact h
          · nlinarith
        rw [hk0, mul_zero]
        exact dvd_zero _
  7. The sequence has length 2 * r * (n - 1).

    The sequence consists of r blocks, each containing two sublists of length n - 1, giving total length r · ((n - 1) + (n - 1)) = 2 · r · (n - 1).

    lines 75–76

    uses List.length_flatMap

      · simp [zero_sum_basis_seq, List.length_flatMap]
        ring
Fin.sum_univ_def
The sum of a function over Fin n equals the sum over the list of all indices in Fin n.
Fin.sum_univ_fun_getElem
The sum of f evaluated at each element of a list l equals the sum of the mapped list l.map f.
Finset.sum_le_sum
If f i ≤ g i for all i in a finite set, then ∑ i, f i ≤ ∑ i, g i.
Finset.sum_le_sum_of_subset_of_nonneg
If s ⊆ t and f is non-negative on t \ s, then the sum of f over s is at most the sum of f over t.
Finset.sum_neg_distrib
The sum of -f i over a finite set equals the negation of the sum of f i.
Finset.subset_univ
Any finite subset of a finite type is a subset of the full universe Finset.univ.
Function.comp_def
The definition of function composition: (f ∘ g)(x) = f(g(x)).
Int.dvd_neg
An integer divides -b if and only if it divides b.
Int.le_of_dvd
If b > 0 and a divides b, then a ≤ b.
List.flatMap
Maps a function that returns lists over a list and flattens the resulting list of lists.
List.length_flatMap
The length of a flat-mapped list is the sum of the lengths of the resulting sublists.
List.mem_append
An element belongs to the concatenation s ++ t if and only if it belongs to s or to t.
List.mem_finRange
Every element of Fin n belongs to List.finRange n.
List.mem_flatMap
An element belongs to a flat-mapped list if and only if it belongs to the image list of some element in the original list.
List.mem_replicate
An element b belongs to List.replicate n a if and only if n ≠ 0 and b = a.
List.sum_flatten
The sum of the elements of a concatenated list of lists equals the sum of the sums of each inner list.
Nat.cast_sub
For m ≤ n, casting n - m to an additive group with one yields ↑n - ↑m.
Pi.neg_apply
Pointwise negation of a function: (-f) i = -f i.
Pi.single_apply
The indicator function Pi.single i x evaluated at index i' equals x if i' = i and 0 otherwise.
Pi.single_eq_same
The indicator function Pi.single i x evaluated at the same index i equals x.
dvd_zero
Any element divides zero.
le_max_left
Any element a satisfies a ≤ max a b.
le_max_right
Any element b satisfies b ≤ max a b.
lt_trichotomy
In any linear order, exactly one of a < b, a = b, or b < a holds.
mul_zero
Multiplying any element by zero yields zero: a * 0 = 0.
one_pos
0 < 1 in any nontrivial ordered semiring.
true_and
True ∧ p is equivalent to p.

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

theorem zero_sum_basis_seq_w_bad (r n : ℕ) (hn : 1 < n) :    zero_sum_w_bad n (zero_sum_basis_seq r n) ∧ (zero_sum_basis_seq r n).length = 2 * r * (n - 1) := by  have hpos : ∀ j : Fin r,      ((zero_sum_basis_seq r n).map (fun a => max (a j) 0)).sum = ((n - 1 : ℕ) : ℤ) := by    intro j    simp [zero_sum_basis_seq, List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply]    rw [← Fin.sum_univ_def, ← Fin.sum_univ_def]    have h1 : ∀ i : Fin r, max (if j = i then (1 : ℤ) else 0) 0 = if j = i then 1 else 0 := by      intro i; split_ifs <;> simp    have h2 : ∀ i : Fin r, max (-if j = i then (1 : ℤ) else 0) 0 = 0 := by      intro i; split_ifs <;> simp    simp [h1, h2]  have hneg : ∀ j : Fin r,      ((zero_sum_basis_seq r n).map (fun a => max (-a j) 0)).sum = ((n - 1 : ℕ) : ℤ) := by    intro j    simp [zero_sum_basis_seq, List.flatMap, List.sum_flatten, Function.comp_def, Pi.single_apply]    rw [← Fin.sum_univ_def, ← Fin.sum_univ_def]    have h1 : ∀ i : Fin r, max (if j = i then (1 : ℤ) else 0) 0 = if j = i then 1 else 0 := by      intro i; split_ifs <;> simp    have h2 : ∀ i : Fin r, max (-if j = i then (1 : ℤ) else 0) 0 = 0 := by      intro i; split_ifs <;> simp    simp [h1, h2]  have hcast : ((n - 1 : ℕ) : ℤ) = (n : ℤ) - 1 := by push_cast [Nat.cast_sub hn.le]; ring  refine ⟨⟨?_, ?_⟩, ?_⟩  · intro a ha    simp only [zero_sum_basis_seq, List.mem_flatMap, List.mem_finRange, true_and, List.mem_append,      List.mem_replicate] at ha    obtain ⟨j, (⟨-, rfl⟩ | ⟨-, rfl⟩)⟩ := ha    · refine ⟨j, ?_⟩      simp only [Pi.single_eq_same]      intro h      have := Int.le_of_dvd one_pos h      omega    · refine ⟨j, ?_⟩      simp only [Pi.neg_apply, Pi.single_eq_same]      intro h      have := Int.le_of_dvd one_pos ((Int.dvd_neg).mp h)      omega  · rintro I ⟨-, hdiv, j, hj⟩    apply hj    have hup : ∑ i ∈ I, (zero_sum_basis_seq r n).get i j ≤ ((n - 1 : ℕ) : ℤ) := by      calc ∑ i ∈ I, (zero_sum_basis_seq r n).get i j          ≤ ∑ i ∈ I, max ((zero_sum_basis_seq r n).get i j) 0 :=            Finset.sum_le_sum (fun i _ => le_max_left _ _)        _ ≤ ∑ i, max ((zero_sum_basis_seq r n).get i j) 0 :=            Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)              (fun i _ _ => le_max_right _ _)        _ = ((zero_sum_basis_seq r n).map (fun a => max (a j) 0)).sum := by            simpa using Fin.sum_univ_fun_getElem (zero_sum_basis_seq r n) (fun a => max (a j) 0)        _ = _ := hpos j    have hlo : -((n - 1 : ℕ) : ℤ) ≤ ∑ i ∈ I, (zero_sum_basis_seq r n).get i j := by      have : ∑ i ∈ I, -(zero_sum_basis_seq r n).get i j ≤ ((n - 1 : ℕ) : ℤ) := by        calc ∑ i ∈ I, -(zero_sum_basis_seq r n).get i j            ≤ ∑ i ∈ I, max (-(zero_sum_basis_seq r n).get i j) 0 :=              Finset.sum_le_sum (fun i _ => le_max_left _ _)          _ ≤ ∑ i, max (-(zero_sum_basis_seq r n).get i j) 0 :=              Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ _)                (fun i _ _ => le_max_right _ _)          _ = ((zero_sum_basis_seq r n).map (fun a => max (-a j) 0)).sum := by              simpa using Fin.sum_univ_fun_getElem (zero_sum_basis_seq r n) (fun a => max (-a j) 0)          _ = _ := hneg j      rw [Finset.sum_neg_distrib] at this      linarith    obtain ⟨k, hk⟩ := hdiv j    rw [hk] at hup hlo ⊢    rw [hcast] at hup hlo    have hn' : (1 : ℤ) < n := by exact_mod_cast hn    have hk0 : k = 0 := by      rcases lt_trichotomy k 0 with h | h | h      · nlinarith      · exact h      · nlinarith    rw [hk0, mul_zero]    exact dvd_zero _  · simp [zero_sum_basis_seq, List.length_flatMap]    ring
See it in the graphDiscuss this resultChallenge it