AFTD Auto-Formalizing Theoretical Domains

nat_sum_lt_of_subset_square_mod_lt

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 6–7

    uses Finset.induction_on

      induction s using Finset.induction_on with
      | empty => simpa using (show 0 < n by omega)
  2. 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.

    lines 8–12

    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)
  3. $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}$.

    lines 13–17

    uses sq_nonneg

        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
  4. $\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$.

    lines 18–20

    uses Finset.Subset.refl, Finset.sum_insert, Nat.mod_eq_of_lt

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

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