AFTD Auto-Formalizing Theoretical Domains

zero_sum_w_bad_concat_box_complement_length_le

theoremverified

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.

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

    lines 7–17

    uses Finset.not_nonempty_iff_eq_empty.mp

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

    lines 18–21

    uses integer_box_completion_card_le, List.mem_append.mpr, Or.inr, List.get_mem, Fintype.card_fin

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

    lines 22–23

      intro s c hcb hdiv j
      obtain ⟨I, hI⟩ := hbox c hcb
  4. 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.

    lines 24–29

    uses List.length_append, Fin.ext, congrArg

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

    lines 30–38

    uses List.getElem_append_left, List.getElem_append_right

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

    lines 39–46

    uses Finset.disjoint_left, Finset.mem_map.mp, congrArg, Fin.val

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

    lines 47–51

    uses Finset.sum_union, Finset.sum_map

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

    lines 52–57

      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.

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