AFTD Auto-Formalizing Theoretical Domains

finite_array_card_le_of_subset_square_mod_lt

theoremverified

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
Used by 1

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

  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.

    lines 8–12

    uses nat_sum_lt_of_subset_square_mod_lt

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

    lines 13–18

    uses Finset.sum_le_sum, Finset.sum_comm

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

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