zero_sum_basis_seq_w_bad
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- zero_sum_w_gew_r(n) ≥ 2r(n−1) + 1 for all r ≥ 1 and n > 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²).
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.
uses
List.flatMap,List.sum_flatten,Function.comp_def,Pi.single_apply,Fin.sum_univ_defhave 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]
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.
uses
List.flatMap,List.sum_flatten,Function.comp_def,Pi.single_apply,Fin.sum_univ_defhave 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]
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.
uses
Nat.cast_subhave hcast : ((n - 1 : ℕ) : ℤ) = (n : ℤ) - 1 := by push_cast [Nat.cast_sub hn.le]; ring
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.
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_negrefine ⟨⟨?_, ?_⟩, ?_⟩ · 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
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).
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 linarithNo 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.
uses
lt_trichotomy,mul_zero,dvd_zeroobtain ⟨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 _
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).
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.
- In the formalization, zero_sum_w_bad n A defines a sequence A to be admissible with no 'good' subsequence, where a subsequence is defined as 'good' if its sum is ≡ 0 (mod n) but ≢ 0 (mod n²). Thus, proving zero_sum_w_bad establishes that no such subsequence exists.
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.
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