integer_box_completion_card_le
An admissible integer vector family with the full-box completion property has at most r(n-1) terms.
Statement
theorem integer_box_completion_card_le {ι : Type*} [Fintype ι] [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ) (ha : ∀ i, ∃ j, ¬ (n : ℤ) ∣ a i j) (hbad : ∀ s : Finset ι, ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) → (∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j) → ∀ j, (n : ℤ) ^ 2 ∣ c j + ∑ i ∈ s, a i j) : Fintype.card ι ≤ 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 2
- finite_array_card_le_of_subset_square_mod_ltA nonzero nonnegative array whose entries and all coordinate subset-sum residues modulo n squared are below n has at most r(n-1) rows.
- integer_box_completion_subset_emod_ltIf every subset completed by an integer vector in the box [0,n-1]^r that vanishes modulo n also vanishes modulo n squared, each negative…
- Used by 2
- order_prefix_zeroFor any ordering bijection e of a finite type α, the prefix of length zero is empty: order_prefix e 0 = ∅.
- zero_sum_w_bad_concat_box_complement_length_leIf 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…
The proof, explained
The proof establishes the cardinality bound |ι| ≤ r(n - 1) by reducing to finite_array_card_le_of_subset_square_mod_lt, a known bound for natural-number vector arrays. We construct non-negative vectors v by setting v i j = (-a i j) % n^2. The three required conditions—that coordinates are bounded by n, that each vector is non-zero, and that all subset sums modulo n^2 are strictly less than n—are verified using the admissibility condition ha together with the singleton and general cases of integer_box_completion_subset_emod_lt.
Define a natural-number vector array v by v i j = (-a i j % n^2) and verify that its integer cast matches this remainder.
We define v : ι → Fin r → ℕ by taking the remainder (-a i j) % n^2 and converting it to a natural number. Since 1 < n, n^2 is non-zero, so the integer remainder is non-negative by Int.emod_nonneg. Converting a non-negative integer to ℕ via Int.toNat_of_nonneg preserves its value, establishing that the integer cast of v i j is canonically equal to (-a i j) % n^2 (hcanon).
uses
Int.toNat_of_nonneg,Int.emod_nonneglet v : ι → Fin r → ℕ := fun i j => ((-a i j) % (n : ℤ) ^ 2).toNat have hnz : (1 : ℤ) < n := by exact_mod_cast hn have hcanon : ∀ i j, (v i j : ℤ) = (-a i j) % (n : ℤ) ^ 2 := by intro i j exact Int.toNat_of_nonneg (Int.emod_nonneg _ (by positivity))
Each coordinate v i j satisfies v i j < n.
Applying the helper lemma integer_box_completion_subset_emod_lt to the singleton subset {i} and coordinate j gives (-∑ k ∈ {i}, a k j) % n^2 < n. Simplifying the singleton sum with Finset.sum_singleton yields (-a i j) % n^2 < n. Replacing this remainder with the integer cast of v i j via hcanon and casting to ℕ establishes v i j < n.
uses
integer_box_completion_subset_emod_lt,Finset.sum_singletonhave hsmall : ∀ i j, v i j < n := by intro i j have h := integer_box_completion_subset_emod_lt n r hn a hbad {i} j simp only [Finset.sum_singleton] at h rw [← hcanon i j] at h exact_mod_cast h
For every index i, the sum of coordinates ∑ j, v i j is strictly positive.
By the admissibility hypothesis ha, for each i there is a coordinate j such that n does not divide a i j. If v i j were zero, then (-a i j) % n^2 = 0 by hcanon, which implies n^2 ∣ -a i j by Int.dvd_of_emod_eq_zero. Since n ∣ n^2 (via pow_two and dvd_mul_right), transitivity dvd_trans would imply n ∣ -a i j, and hence n ∣ a i j by dvd_neg.mpr, a contradiction. Thus v i j > 0. Since every coordinate of v is non-negative (Nat.zero_le), Finset.single_le_sum and Finset.mem_univ show that the sum over all coordinates is bounded below by v i j > 0, giving strict positivity by lt_of_lt_of_le.
uses
Int.dvd_of_emod_eq_zero,pow_two,dvd_mul_right,dvd_neg.mpr,dvd_trans,lt_of_lt_of_le,Finset.single_le_sum,Nat.zero_le,Finset.mem_univhave hpos : ∀ i, 0 < ∑ j, v i j := by intro i obtain ⟨j, hj⟩ := ha i have hv : 0 < v i j := by by_contra h have hz : v i j = 0 := by omega have hem : (-a i j) % (n : ℤ) ^ 2 = 0 := by simpa [hz] using (hcanon i j).symm have hd : (n : ℤ) ^ 2 ∣ -a i j := Int.dvd_of_emod_eq_zero hem have hdn : (n : ℤ) ∣ (n : ℤ) ^ 2 := by simpa [pow_two] using (dvd_mul_right (n : ℤ) (n : ℤ)) exact hj (by simpa using dvd_neg.mpr (dvd_trans hdn hd)) exact lt_of_lt_of_le hv (Finset.single_le_sum (fun j _ => Nat.zero_le (v i j)) (Finset.mem_univ j))
It suffices to show that for every subset s ⊆ ι and coordinate j, the subset sum modulo n^2 satisfies (∑ i ∈ s, v i j) % n^2 < n.
We apply finite_array_card_le_of_subset_square_mod_lt. Having shown that 1 < n, that all coordinates satisfy v i j < n, and that each vector has a positive sum ∑ j, v i j > 0, this lemma reduces the goal Fintype.card ι ≤ r * (n - 1) to bounding the subset sums of v modulo n^2.
uses
finite_array_card_le_of_subset_square_mod_ltapply finite_array_card_le_of_subset_square_mod_lt n r hn v hsmall hposFor any subset s ⊆ ι and coordinate j, the sum of v modulo n^2 equals the negation of the sum of a modulo n^2.
We proceed by induction on s using Finset.induction_on. For the empty set, both sides are 0. For the inductive step insert i s with i ∉ s, the component v i j is congruent to -a i j modulo n^2 by definition and Int.emod_emod. Adding this congruence to the induction hypothesis and rewriting the sums using Finset.sum_insert and neg_add proves that the equality of remainders holds for insert i s.
uses
Finset.induction_on,Int.emod_emod,Finset.sum_insert,neg_addintro s j have he : (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 = (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 := by induction s using Finset.induction_on with | empty => simp | @insert i s hi ih => have hi' : (v i j : ℤ) ≡ -a i j [ZMOD (n : ℤ) ^ 2] := by change (v i j : ℤ) % (n : ℤ) ^ 2 = (-a i j) % (n : ℤ) ^ 2 rw [hcanon, Int.emod_emod] have hs' : (∑ i ∈ s, (v i j : ℤ)) ≡ -∑ i ∈ s, a i j [ZMOD (n : ℤ) ^ 2] := ih simpa only [Finset.sum_insert hi, neg_add] using (hi'.add hs').eq
The subset sum of v modulo n^2 satisfies (∑ i ∈ s, v i j) % n^2 < n, completing the proof.
The full-box completion property integer_box_completion_subset_emod_lt gives (-∑ i ∈ s, a i j) % n^2 < n. Replacing this with the sum of v using the modular equality just proved, and moving between ℤ and ℕ, gives the required bound (∑ i ∈ s, v i j) % n^2 < n.
uses
integer_box_completion_subset_emod_lthave hb := integer_box_completion_subset_emod_lt n r hn a hbad s j rw [← he] at hb have hc : (((∑ i ∈ s, v i j) % n ^ 2 : ℕ) : ℤ) = (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 := by simp rw [← hc] at hb exact_mod_cast hb
Int.toNat_of_nonneg- For any non-negative integer a, casting its non-negative conversion a.toNat back to ℤ yields a.
Int.emod_nonneg- For any integer a and non-zero integer b, the remainder a % b is non-negative.
integer_box_completion_subset_emod_lt- Under the full-box completion property, for any finite subset of indices s and coordinate j, the remainder (-∑ i ∈ s, a i j) % n^2 is strictly less than n.
Finset.sum_singleton- The sum of a function over a singleton set {a} equals the value of the function at a.
Int.dvd_of_emod_eq_zero- If the integer remainder of b modulo a is zero, then a divides b.
pow_two- The square of an element equals the element multiplied by itself (a ^ 2 = a * a).
dvd_mul_right- An element divides its product with any other element on the right (a ∣ a * b).
dvd_neg.mpr- If a divides b, then a divides -b.
dvd_trans- Divisibility is transitive: if a ∣ b and b ∣ c, then a ∣ c.
lt_of_lt_of_le- If a < b and b ≤ c, then a < c.
Finset.single_le_sum- In a finite sum of non-negative elements, any single summand is bounded above by the total sum.
Nat.zero_le- Every natural number is greater than or equal to zero.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
finite_array_card_le_of_subset_square_mod_lt- A family of non-negative vectors in ℕ^r indexed by a finite type ι has size at most r(n - 1), provided each coordinate is less than n, each vector has a positive sum, and every subset sum modulo n^2 is less than n.
Finset.induction_on- A property holds for all finite sets if it holds for the empty set and is preserved when inserting a new element.
Int.emod_emod- Taking the integer remainder modulo b is idempotent: (a % b) % b = a % b.
Finset.sum_insert- The sum of a function over insert a s equals f a + ∑ x ∈ s, f x, provided a ∉ s.
neg_add- The negation of a sum equals the sum of the negations: -(a + b) = -a + -b.
- Formal cast management between ℕ and ℤ is required because finite_array_card_le_of_subset_square_mod_lt expects vectors with natural-number entries, whereas the ambient vector family a and the modulus arithmetic are defined over ℤ.
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 integer_box_completion_card_le {ι : Type*} [Fintype ι] [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (a : ι → Fin r → ℤ) (ha : ∀ i, ∃ j, ¬ (n : ℤ) ∣ a i j) (hbad : ∀ s : Finset ι, ∀ c : Fin r → ℤ, (∀ j, 0 ≤ c j ∧ c j < n) → (∀ j, (n : ℤ) ∣ c j + ∑ i ∈ s, a i j) → ∀ j, (n : ℤ) ^ 2 ∣ c j + ∑ i ∈ s, a i j) : Fintype.card ι ≤ r * (n - 1) := by let v : ι → Fin r → ℕ := fun i j => ((-a i j) % (n : ℤ) ^ 2).toNat have hnz : (1 : ℤ) < n := by exact_mod_cast hn have hcanon : ∀ i j, (v i j : ℤ) = (-a i j) % (n : ℤ) ^ 2 := by intro i j exact Int.toNat_of_nonneg (Int.emod_nonneg _ (by positivity)) have hsmall : ∀ i j, v i j < n := by intro i j have h := integer_box_completion_subset_emod_lt n r hn a hbad {i} j simp only [Finset.sum_singleton] at h rw [← hcanon i j] at h exact_mod_cast h have hpos : ∀ i, 0 < ∑ j, v i j := by intro i obtain ⟨j, hj⟩ := ha i have hv : 0 < v i j := by by_contra h have hz : v i j = 0 := by omega have hem : (-a i j) % (n : ℤ) ^ 2 = 0 := by simpa [hz] using (hcanon i j).symm have hd : (n : ℤ) ^ 2 ∣ -a i j := Int.dvd_of_emod_eq_zero hem have hdn : (n : ℤ) ∣ (n : ℤ) ^ 2 := by simpa [pow_two] using (dvd_mul_right (n : ℤ) (n : ℤ)) exact hj (by simpa using dvd_neg.mpr (dvd_trans hdn hd)) exact lt_of_lt_of_le hv (Finset.single_le_sum (fun j _ => Nat.zero_le (v i j)) (Finset.mem_univ j)) apply finite_array_card_le_of_subset_square_mod_lt n r hn v hsmall hpos intro s j have he : (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 = (-∑ i ∈ s, a i j) % (n : ℤ) ^ 2 := by induction s using Finset.induction_on with | empty => simp | @insert i s hi ih => have hi' : (v i j : ℤ) ≡ -a i j [ZMOD (n : ℤ) ^ 2] := by change (v i j : ℤ) % (n : ℤ) ^ 2 = (-a i j) % (n : ℤ) ^ 2 rw [hcanon, Int.emod_emod] have hs' : (∑ i ∈ s, (v i j : ℤ)) ≡ -∑ i ∈ s, a i j [ZMOD (n : ℤ) ^ 2] := ih simpa only [Finset.sum_insert hi, neg_add] using (hi'.add hs').eq have hb := integer_box_completion_subset_emod_lt n r hn a hbad s j rw [← he] at hb have hc : (((∑ i ∈ s, v i j) % n ^ 2 : ℕ) : ℤ) = (∑ i ∈ s, (v i j : ℤ)) % (n : ℤ) ^ 2 := by simp rw [← hc] at hb exact_mod_cast hb