nat_sum_lt_of_subset_square_mod_lt
If all summands are below n and every subset sum has residue below n modulo n squared, then their total is below n.
Statement
theorem nat_sum_lt_of_subset_square_mod_lt {ι : Type*} [DecidableEq ι] (n : ℕ) (hn : 1 < n) (s : Finset ι) (v : ι → ℕ) (hv : ∀ i ∈ s, v i < n) (hmod : ∀ t ⊆ s, (∑ i ∈ t, v i) % n ^ 2 < n) : ∑ i ∈ s, v i < n
- 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
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- 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.
The proof, explained
We proceed by induction on the finite set $s$. In the base case $s = \emptyset$, the empty sum is $0 < n$ because $n > 1$. In the inductive step with $\{a\} \cup s$ where $a \notin s$, the induction hypothesis gives $\sum_{i \in s} v(i) < n$, which together with $v(a) < n$ implies that the sum over the new set is at most $2n - 2 < n^2$. Applying the subset modular hypothesis to $\{a\} \cup s$ itself gives a remainder below $n$, and since the sum is strictly below $n^2$, it equals its own remainder, completing the inductive step.
The theorem holds for the empty set: $\sum_{i \in \emptyset} v(i) < n$.
We proceed by induction on the finite set $s$ using `Finset.induction_on`. In the base case $s = \emptyset$, the empty sum evaluates to $0$. Since $1 < n$, we have $0 < n$ by arithmetic (`omega`), which simplifies to the required inequality.
uses
Finset.induction_oninduction s using Finset.induction_on with | empty => simpa using (show 0 < n by omega)
In the inductive step for $\{a\} \cup s$ with $a \notin s$, both $\sum_{i \in s} v(i) < n$ and $v(a) < n$ hold.
Assume the result holds for $s$ and that $a \notin s$. Every element of $s$ belongs to $\{a\} \cup s$ by `Finset.mem_insert_of_mem`, so $v(i) < n$ holds for all $i \in s$. Furthermore, any subset $t \subseteq s$ is also a subset of $\{a\} \cup s$ via transitivity with `Finset.subset_insert`, so the subset modular condition holds for all subsets of $s$. The induction hypothesis `ih` therefore gives $\sum_{i \in s} v(i) < n$. Additionally, $a \in \{a\} \cup s$ by `Finset.mem_insert_self`, so $v(a) < n$ as well.
uses
Finset.mem_insert_of_mem,Finset.subset_insert,Finset.mem_insert_self| @insert a s ha ih => have hs : ∑ i ∈ s, v i < n := ih (fun i hi => hv i (Finset.mem_insert_of_mem hi)) (fun t ht => hmod t (ht.trans (Finset.subset_insert a s))) have ha' : v a < n := hv a (Finset.mem_insert_self a s)$v(a) + \sum_{i \in s} v(i) < n^2$.
Since $v(a) \le n - 1$ and $\sum_{i \in s} v(i) \le n - 1$, their sum is at most $2n - 2$. In the integers, $(n - 1)^2 \ge 0$ by `sq_nonneg`, which implies $n^2 \ge 2n - 1$ via `nlinarith`. Linear integer arithmetic (`omega`) combines these bounds to show that $(v(a) : \mathbb{Z}) + \sum_{i \in s} v(i) < n^2$. The tactic `exact_mod_cast` transfers this strict inequality back to $\mathbb{N}$.
uses
sq_nonneghave hsmall : v a + ∑ i ∈ s, v i < n ^ 2 := by have hsq : 0 ≤ (n - 1 : ℤ) ^ 2 := sq_nonneg _ have hnn : (n : ℤ) ^ 2 ≥ 2 * n - 1 := by nlinarith have : (v a : ℤ) + (∑ i ∈ s, v i : ℕ) < (n : ℤ) ^ 2 := by omega exact_mod_cast this
$\sum_{i \in \{a\} \cup s} v(i) < n$.
Applying the hypothesis `hmod` to the subset $\{a\} \cup s \subseteq \{a\} \cup s$ using `Finset.Subset.refl` gives $(\sum_{i \in \{a\} \cup s} v(i)) \bmod n^2 < n$. We split the sum into $v(a) + \sum_{i \in s} v(i)$ using `Finset.sum_insert`. Because this sum is strictly less than $n^2$, its remainder modulo $n^2$ is the sum itself by `Nat.mod_eq_of_lt`. This yields $v(a) + \sum_{i \in s} v(i) < n$, which recombines to $\sum_{i \in \{a\} \cup s} v(i) < n$.
uses
Finset.Subset.refl,Finset.sum_insert,Nat.mod_eq_of_lthave h := hmod (insert a s) (Finset.Subset.refl _) rw [Finset.sum_insert ha, Nat.mod_eq_of_lt hsmall] at h simpa only [Finset.sum_insert ha] using h
Finset.induction_on- Every property of finite sets that holds for the empty set and is preserved under adjoining a new element holds for all finite sets.
Finset.mem_insert_of_mem- If an element belongs to a finite set, it also belongs to the set with an element adjoined.
Finset.subset_insert- A finite set is a subset of the set obtained by inserting an element into it.
Finset.mem_insert_self- An element belongs to the set obtained by inserting it into a finite set.
sq_nonneg- The square of any element in an ordered semiring (such as the integers) is non-negative.
Finset.Subset.refl- Every set is a subset of itself.
Finset.sum_insert- If an element is not in a finite set, the sum over the set with that element inserted is the value at that element plus the sum over the set.
Nat.mod_eq_of_lt- If a natural number $a$ is strictly less than $b$, then $a \bmod b = a$.
- The bound $v(a) + \sum_{i \in s} v(i) < n^2$ is established by temporarily embedding the natural numbers into $\mathbb{Z}$ to take advantage of algebraic and linear arithmetic tactics (`sq_nonneg`, `nlinarith`, `omega`), and then cast back to $\mathbb{N}$ using `exact_mod_cast`.
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 nat_sum_lt_of_subset_square_mod_lt {ι : Type*} [DecidableEq ι] (n : ℕ) (hn : 1 < n) (s : Finset ι) (v : ι → ℕ) (hv : ∀ i ∈ s, v i < n) (hmod : ∀ t ⊆ s, (∑ i ∈ t, v i) % n ^ 2 < n) : ∑ i ∈ s, v i < n := by induction s using Finset.induction_on with | empty => simpa using (show 0 < n by omega) | @insert a s ha ih => have hs : ∑ i ∈ s, v i < n := ih (fun i hi => hv i (Finset.mem_insert_of_mem hi)) (fun t ht => hmod t (ht.trans (Finset.subset_insert a s))) have ha' : v a < n := hv a (Finset.mem_insert_self a s) have hsmall : v a + ∑ i ∈ s, v i < n ^ 2 := by have hsq : 0 ≤ (n - 1 : ℤ) ^ 2 := sq_nonneg _ have hnn : (n : ℤ) ^ 2 ≥ 2 * n - 1 := by nlinarith have : (v a : ℤ) + (∑ i ∈ s, v i : ℕ) < (n : ℤ) ^ 2 := by omega exact_mod_cast this have h := hmod (insert a s) (Finset.Subset.refl _) rw [Finset.sum_insert ha, Nat.mod_eq_of_lt hsmall] at h simpa only [Finset.sum_insert ha] using h