sum_le_card_mul_of_subset_Icc
If A is a subset of {1, ..., N} and B is a subset of A, then the sum of the elements of B is at most the cardinality of A multiplied by N.
Statement
theorem sum_le_card_mul_of_subset_Icc (N : ℕ) (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 N)
(B : Finset ℕ) (hB : B ⊆ A) : B.sum id ≤ A.card * N- Source
- arXiv:2610.34372, Proof of Lemma 2.1
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- admissible_card_sq_add_five_leIf A is a nonempty admissible subset of {1, ..., N}, then the square of the cardinality of A plus 5 is at most 6 times N.
Read back from the Lean
For any natural number $N$, any finite set of natural numbers $A \subseteq \{1, \dots, N\}$ (the closed interval from 1 to $N$), and any finite set of natural numbers $B \subseteq A$, the sum of the elements of $B$ is less than or equal to $|A| \cdot N$ (the cardinality of $A$ multiplied by $N$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To bound the sum of the elements in $B$, we first observe that each element of $B$ is at most $N$ because $B \subseteq A \subseteq \{1, \dots, N\}$, which bounds the sum by $|B| \cdot N$. Since $B \subseteq A$, the cardinality of $B$ is at most that of $A$, and multiplying this inequality by $N$ yields the final bound $|A| \cdot N$.
Every element of $B$ is at most $N$.
Given any element $x \in B$, chaining the inclusions $B \subseteq A$ and $A \subseteq \{1, \dots, N\}$ shows that $x \in \{1, \dots, N\}$. By the definition of a closed discrete interval (`Finset.mem_Icc.mp`), this means $1 \le x$ and $x \le N$, providing the upper bound $x \le N$.
uses
Finset.mem_Icc.mphave h1 : ∀ x ∈ B, id x ≤ N := fun x hx => (Finset.mem_Icc.mp (hA (hB hx))).2
The sum of the elements in $B$ is at most $|A| \cdot N$.
Since every element of $B$ is at most $N$, `Finset.sum_le_card_nsmul` bounds the sum of elements in $B$ by $|B| \cdot N$. Furthermore, because $B \subseteq A$, the cardinality of $B$ is at most that of $A$ (`Finset.card_le_card`), so multiplying by $N$ gives $|B| \cdot N \le |A| \cdot N$ (`Nat.mul_le_mul_right`). Chaining these two bounds by transitivity completes the proof.
uses
Finset.sum_le_card_nsmul,Nat.mul_le_mul_right,Finset.card_le_cardexact (Finset.sum_le_card_nsmul B id N h1).trans (Nat.mul_le_mul_right N (Finset.card_le_card hB))
Finset.mem_Icc.mp- an element $x$ belonging to a closed interval $[a, b]$ satisfies $a \le x$ and $x \le b$
Finset.sum_le_card_nsmul- if every element $x$ in a finite set $s$ satisfies $f(x) \le n$, then the sum of $f$ over $s$ is at most $|s| \cdot n$
Nat.mul_le_mul_right- for natural numbers, if $n \le m$, then $n \cdot k \le m \cdot k$
Finset.card_le_card- if a finite set $s$ is a subset of $t$, then $|s| \le |t|$
- In `Finset.sum_le_card_nsmul`, the bound is formulated using scalar multiplication `s.card • n`, which for the natural numbers is identical to ordinary multiplication `s.card * n`.
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.
/-- Every subset sum of a subset of {1, ..., N} of size m is at most m * N. -/theorem sum_le_card_mul_of_subset_Icc (N : ℕ) (A : Finset ℕ) (hA : A ⊆ Finset.Icc 1 N) (B : Finset ℕ) (hB : B ⊆ A) : B.sum id ≤ A.card * N := by have h1 : ∀ x ∈ B, id x ≤ N := fun x hx => (Finset.mem_Icc.mp (hA (hB hx))).2 exact (Finset.sum_le_card_nsmul B id N h1).trans (Nat.mul_le_mul_right N (Finset.card_le_card hB))