finite_array_card_le_of_subset_square_mod_lt
A nonzero nonnegative array whose entries and all coordinate subset-sum residues modulo n squared are below n has at most r(n-1) rows.
Statement
theorem finite_array_card_le_of_subset_square_mod_lt {ι : Type*} [Fintype ι] [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (v : ι → Fin r → ℕ) (hv : ∀ i j, v i j < n) (hpos : ∀ i, 0 < ∑ j, v i j) (hmod : ∀ s : Finset ι, ∀ j, (∑ i ∈ s, v i j) % n ^ 2 < n) : 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 1
- nat_sum_lt_of_subset_square_mod_ltIf all summands are below n and every subset sum has residue below n modulo n squared, then their total is below n.
- Used by 1
- integer_box_completion_card_leAn admissible integer vector family with the full-box completion property has at most r(n-1) terms.
The proof, explained
The proof establishes the row-count bound by double-counting the sum of all entries in the array. First, an auxiliary lemma shows that the subset-sum condition modulo n² forces each of the r column sums to be strictly less than n, hence at most n - 1. Because every row sum is strictly positive, each row contributes at least 1 to the total sum, bounding the number of rows |ι| by the sum of all column sums, which is at most r(n - 1).
For every column j, the column sum ∑ i, v i j is at most n - 1.
Fix an arbitrary column j. Applying nat_sum_lt_of_subset_square_mod_lt to the universe of row indices Finset.univ, using the assumptions that each entry v i j < n and every subcollection sum modulo n² is less than n, shows that the entire column sum ∑ i, v i j is strictly less than n. Since the sum is a natural number, linear integer arithmetic (omega) deduces that it is at most n - 1.
uses
nat_sum_lt_of_subset_square_mod_lthave hsum : ∀ j, ∑ i, v i j ≤ n - 1 := by intro j have h := nat_sum_lt_of_subset_square_mod_lt n hn Finset.univ (fun i => v i j) (fun i _ => hv i j) (fun s _ => hmod s j) omega
The number of rows satisfies |ι| ≤ r * (n - 1).
We bound the cardinality |ι| via a double-counting calculation on the sum of all entries of the array. First, |ι| = ∑ i, 1. Since each row sum is strictly positive (hpos), each row sum is at least 1, so ∑ i, 1 ≤ ∑ i, ∑ j, v i j by Finset.sum_le_sum. Exchanging the order of summation using Finset.sum_comm yields ∑ j, ∑ i, v i j. Because each of the r columns has sum at most n - 1 (hsum), Finset.sum_le_sum bounds this double sum by ∑ j, (n - 1). Finally, summing the constant n - 1 over the r column indices simplifies to r * (n - 1).
uses
Finset.sum_le_sum,Finset.sum_commcalc Fintype.card ι = ∑ _i : ι, 1 := by simp _ ≤ ∑ i, ∑ j, v i j := Finset.sum_le_sum (fun i _ => hpos i) _ = ∑ j, ∑ i, v i j := Finset.sum_comm _ ≤ ∑ _j : Fin r, (n - 1) := Finset.sum_le_sum (fun j _ => hsum j) _ = r * (n - 1) := by simp
nat_sum_lt_of_subset_square_mod_lt- If all elements of a finite collection are strictly less than n (for n > 1) and the sum of every subcollection modulo n² is strictly less than n, then the sum of the entire collection is strictly less than n.
Finset.sum_le_sum- If f(x) ≤ g(x) for all x in a finite set s, then the sum of f over s is at most the sum of g over s.
Finset.sum_comm- The order of summation in a finite double sum can be swapped: summing over the first index then the second equals summing over the second then the first.
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 finite_array_card_le_of_subset_square_mod_lt {ι : Type*} [Fintype ι] [DecidableEq ι] (n r : ℕ) (hn : 1 < n) (v : ι → Fin r → ℕ) (hv : ∀ i j, v i j < n) (hpos : ∀ i, 0 < ∑ j, v i j) (hmod : ∀ s : Finset ι, ∀ j, (∑ i ∈ s, v i j) % n ^ 2 < n) : Fintype.card ι ≤ r * (n - 1) := by have hsum : ∀ j, ∑ i, v i j ≤ n - 1 := by intro j have h := nat_sum_lt_of_subset_square_mod_lt n hn Finset.univ (fun i => v i j) (fun i _ => hv i j) (fun s _ => hmod s j) omega calc Fintype.card ι = ∑ _i : ι, 1 := by simp _ ≤ ∑ i, ∑ j, v i j := Finset.sum_le_sum (fun i _ => hpos i) _ = ∑ j, ∑ i, v i j := Finset.sum_comm _ ≤ ∑ _j : Fin r, (n - 1) := Finset.sum_le_sum (fun j _ => hsum j) _ = r * (n - 1) := by simp