zero_sum_w_bad_concat_box_complement_length_le
If B++A is w-bad and every vector of [0,n-1]^r is the exact sum of a subsequence of B, then the complementary list A has length at most r(n-1).
Statement
theorem zero_sum_w_bad_concat_box_complement_length_le
(n r : ℕ) (hn : 1 < n) (B A : List (Fin r → ℤ))
(hbad : zero_sum_w_bad n (B ++ A))
(hbox : ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) →
∃ I : Finset (Fin B.length), ∀ j, ∑ i ∈ I, B.get i j = c j) :
A.length ≤ r * (n - 1)- Source
- Supporting lemmas for OP-259, arXiv:2610.19965 Question 3.1, deep session IN-185. This is the restricted full-box completion route; no claim that an arbitrary long bad sequence contains such a box.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- integer_box_completion_card_leAn admissible integer vector family with the full-box completion property has at most r(n-1) terms.
- zero_sum_w_badAn admissible sequence is w-bad when no nonempty subsequence satisfies (1.2).
- 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)).
The proof, explained
The proof bounds the length of A by r(n-1) using the box-completion theorem integer_box_completion_card_le, which reduces the problem to showing that any sum of a box vector c ∈ [0, n-1]ʳ with a subsequence of A divisible by n coordinatewise must also be divisible by n² coordinatewise. By assumption, every box vector c is the exact sum of a subsequence of B; concatenating this with the subsequence of A gives a subsequence of B ++ A. Because B ++ A is w-bad, any of its subsequences with sum divisible by n coordinatewise must also have sum divisible by n² coordinatewise, which completes the required divisibility check for A.
Any subsequence of B ++ A whose sum is divisible by n coordinatewise must also be divisible by n² coordinatewise.
By definition, a list is w-bad if it contains no non-empty subsequence whose sum is divisible by n coordinatewise but not divisible by n² in some coordinate. Given any index set P whose sum is divisible by n in every coordinate, if it were not divisible by n² in some coordinate j, it could not be empty (since the empty sum 0 is divisible by n²). But a non-empty such P would be a good subsequence, contradicting the second clause of hbad.
uses
Finset.not_nonempty_iff_eq_empty.mpclassical have hgood : ∀ P : Finset (Fin (B ++ A).length), (∀ j, (n : ℤ) ∣ ∑ i ∈ P, (B ++ A).get i j) → ∀ j, (n : ℤ) ^ 2 ∣ ∑ i ∈ P, (B ++ A).get i j := by intro P hp j by_contra h have hne : P.Nonempty := by by_contra he have he' : P = ∅ := Finset.not_nonempty_iff_eq_empty.mp he simpa [he'] using h exact hbad.2 P ⟨hne, hp, j, h⟩
To show A.length ≤ r * (n - 1), it suffices to prove that for any subset s of indices of A and any box vector c ∈ [0, n-1]ʳ, if n divides c + ∑_{i ∈ s} A[i] coordinatewise, then n² also divides it coordinatewise.
We invoke the box-completion theorem integer_box_completion_card_le for the sequence of vectors in A indexed by Fin A.length. Every element of A belongs to B ++ A, hence satisfies the admissibility condition by the first clause of hbad. Simplifying Fintype.card (Fin A.length) to A.length reduces the goal to verifying the box-completion divisibility condition for A.
uses
integer_box_completion_card_le,List.mem_append.mpr,Or.inr,List.get_mem,Fintype.card_finhave hc := integer_box_completion_card_le n r hn (fun i : Fin A.length => A.get i) (fun i => hbad.1 (A.get i) (List.mem_append.mpr (Or.inr (List.get_mem A i)))) simp only [Fintype.card_fin] at hc apply hc
Given a subset s of indices of A, a box vector c, and coordinatewise divisibility of c + ∑_{i ∈ s} A[i] by n, there is a subset I of indices of B whose elements sum to c.
We fix the subset s, the box vector c ∈ [0, n-1]ʳ, the divisibility hypothesis hdiv, and a coordinate j. By the hypothesis hbox, every vector in [0, n-1]ʳ is the exact sum of a subsequence of B, which yields an index set I ⊆ Fin B.length such that ∑_{i ∈ I} B[i] = c.
intro s c hcb hdiv j obtain ⟨I, hI⟩ := hbox c hcb
There are injective embeddings fB and fA identifying the indices of B and A with disjoint ranges in B ++ A.
We define fB mapping index i of B to i in B ++ A, and fA mapping index i of A to B.length + i in B ++ A. In both cases, the index remains within bounds because |B ++ A| = |B| + |A|, and injectivity follows by arithmetic on natural numbers.
uses
List.length_append,Fin.ext,congrArglet fB : Fin B.length ↪ Fin (B ++ A).length := ⟨fun i => ⟨i.val, by simp only [List.length_append]; omega⟩, fun i k h => Fin.ext (congrArg (fun q : Fin (B ++ A).length => q.val) h)⟩ let fA : Fin A.length ↪ Fin (B ++ A).length := ⟨fun i => ⟨B.length + i.val, by simp only [List.length_append]; omega⟩, fun i k h => Fin.ext (by have := congrArg (fun q : Fin (B ++ A).length => q.val) h; change B.length + i.val = B.length + k.val at this; omega)⟩
The elements of B ++ A at the embedded indices equal the corresponding elements of B and A.
For any index i of B, the i-th element of B ++ A is B[i] by List.getElem_append_left. For any index i of A, the (B.length + i)-th element of B ++ A is A[i] by List.getElem_append_right.
uses
List.getElem_append_left,List.getElem_append_righthave hgetB : ∀ i, (B ++ A).get (fB i) = B.get i := by intro i change (B ++ A)[i.val] = B[i.val] exact List.getElem_append_left i.isLt have hgetA : ∀ i, (B ++ A).get (fA i) = A.get i := by intro i change (B ++ A)[B.length + i.val] = A[i.val] rw [List.getElem_append_right (by omega)] simp
The mapped index sets fB(I) and fA(s) are disjoint in B ++ A.
An element x in both fB(I) and fA(s) would satisfy x = i for some i < B.length and x = B.length + k for some k ≥ 0, which would require i = B.length + k, an arithmetic contradiction.
uses
Finset.disjoint_left,Finset.mem_map.mp,congrArg,Fin.valhave hd : Disjoint (I.map fB) (s.map fA) := by rw [Finset.disjoint_left] intro x hx hy obtain ⟨i, _, hi⟩ := Finset.mem_map.mp hx obtain ⟨k, _, hk⟩ := Finset.mem_map.mp hy have he := congrArg Fin.val (hi.trans hk.symm) change i.val = B.length + k.val at he omega
The sum of B ++ A over P = fB(I) ∪ fA(s) equals c + ∑_{i ∈ s} A[i].
Because fB(I) and fA(s) are disjoint, the sum over their union splits into the sum over fB(I) plus the sum over fA(s). Rewriting each sum via the embeddings and using ∑_{i ∈ I} B[i] = c gives exactly c + ∑_{i ∈ s} A[i].
uses
Finset.sum_union,Finset.sum_maplet P := I.map fB ∪ s.map fA have hsum : ∀ j, ∑ i ∈ P, (B ++ A).get i j = c j + ∑ i ∈ s, A.get i j := by intro j rw [Finset.sum_union hd, Finset.sum_map, Finset.sum_map] simp only [hgetB, hgetA, hI]
n² divides c_j + ∑_{i ∈ s} A[i]_j.
Since c + ∑_{i ∈ s} A[i] is divisible coordinatewise by n, the sum over P in B ++ A is divisible coordinatewise by n. By hgood, this sum must also be divisible by n² in coordinate j. Rewriting this sum back to c_j + ∑_{i ∈ s} A[i]_j yields the required divisibility by n², which completes the proof.
have hp : ∀ j, (n : ℤ) ∣ ∑ i ∈ P, (B ++ A).get i j := by intro j rw [hsum] exact hdiv j have h := hgood P hp j rwa [hsum] at h
Finset.not_nonempty_iff_eq_empty.mp- A finite set is not nonempty if and only if it is empty.
integer_box_completion_card_le- If an admissible sequence of vectors in ℤʳ satisfies the property that any sum with a box vector in [0, n-1]ʳ that is divisible by n coordinatewise is also divisible by n² coordinatewise, then its index set has cardinality at most r(n-1).
List.mem_append.mpr- An element belonging to either the left or the right list belongs to their concatenation.
Or.inr- If b holds, then the disjunction a ∨ b holds.
List.get_mem- The element at any valid index of a list belongs to the list.
Fintype.card_fin- The cardinality of Fin n is n.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
Fin.ext- Two elements of Fin n are equal if and only if their underlying natural values are equal.
congrArg- Functions preserve equality of arguments.
List.getElem_append_left- For i < |as|, the i-th element of as ++ bs is the i-th element of as.
List.getElem_append_right- For i ≥ |as|, the i-th element of as ++ bs is the (i - |as|)-th element of bs.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first belongs to the second.
Finset.mem_map.mp- An element in the image of a finite set under an embedding comes from some element in the domain set.
Fin.val- The projection mapping an element of Fin n to its underlying natural number.
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.
Finset.sum_map- The sum of a function over the image of a set under an embedding equals the sum over the original set.
- In mathematical writing, concatenating disjoint index sets of two lists into an index set of their concatenation is immediate; in Lean, this requires explicitly defining the embeddings fB and fA and verifying their injectivity and disjointness via index arithmetic.
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_w_bad_concat_box_complement_length_le (n r : ℕ) (hn : 1 < n) (B A : List (Fin r → ℤ)) (hbad : zero_sum_w_bad n (B ++ A)) (hbox : ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) → ∃ I : Finset (Fin B.length), ∀ j, ∑ i ∈ I, B.get i j = c j) : A.length ≤ r * (n - 1) := by classical have hgood : ∀ P : Finset (Fin (B ++ A).length), (∀ j, (n : ℤ) ∣ ∑ i ∈ P, (B ++ A).get i j) → ∀ j, (n : ℤ) ^ 2 ∣ ∑ i ∈ P, (B ++ A).get i j := by intro P hp j by_contra h have hne : P.Nonempty := by by_contra he have he' : P = ∅ := Finset.not_nonempty_iff_eq_empty.mp he simpa [he'] using h exact hbad.2 P ⟨hne, hp, j, h⟩ have hc := integer_box_completion_card_le n r hn (fun i : Fin A.length => A.get i) (fun i => hbad.1 (A.get i) (List.mem_append.mpr (Or.inr (List.get_mem A i)))) simp only [Fintype.card_fin] at hc apply hc intro s c hcb hdiv j obtain ⟨I, hI⟩ := hbox c hcb let fB : Fin B.length ↪ Fin (B ++ A).length := ⟨fun i => ⟨i.val, by simp only [List.length_append]; omega⟩, fun i k h => Fin.ext (congrArg (fun q : Fin (B ++ A).length => q.val) h)⟩ let fA : Fin A.length ↪ Fin (B ++ A).length := ⟨fun i => ⟨B.length + i.val, by simp only [List.length_append]; omega⟩, fun i k h => Fin.ext (by have := congrArg (fun q : Fin (B ++ A).length => q.val) h; change B.length + i.val = B.length + k.val at this; omega)⟩ have hgetB : ∀ i, (B ++ A).get (fB i) = B.get i := by intro i change (B ++ A)[i.val] = B[i.val] exact List.getElem_append_left i.isLt have hgetA : ∀ i, (B ++ A).get (fA i) = A.get i := by intro i change (B ++ A)[B.length + i.val] = A[i.val] rw [List.getElem_append_right (by omega)] simp have hd : Disjoint (I.map fB) (s.map fA) := by rw [Finset.disjoint_left] intro x hx hy obtain ⟨i, _, hi⟩ := Finset.mem_map.mp hx obtain ⟨k, _, hk⟩ := Finset.mem_map.mp hy have he := congrArg Fin.val (hi.trans hk.symm) change i.val = B.length + k.val at he omega let P := I.map fB ∪ s.map fA have hsum : ∀ j, ∑ i ∈ P, (B ++ A).get i j = c j + ∑ i ∈ s, A.get i j := by intro j rw [Finset.sum_union hd, Finset.sum_map, Finset.sum_map] simp only [hgetB, hgetA, hI] have hp : ∀ j, (n : ℤ) ∣ ∑ i ∈ P, (B ++ A).get i j := by intro j rw [hsum] exact hdiv j have h := hgood P hp j rwa [hsum] at h