finset_nat_card_mul_succ_le_two_mul_sum_of_pos
The sum of q distinct positive integers is at least q(q+1)/2.
Statement
theorem finset_nat_card_mul_succ_le_two_mul_sum_of_pos (S : Finset ℕ) (h : ∀ v ∈ S, 0 < v) :
S.card * (S.card + 1) ≤ 2 * ∑ v ∈ S, v- Source
- Step (3) of the proof of Lemma 1 in arXiv:2610.15860 (A note on the Slater–Vélez permutation).
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- finset_nat_mul_card_mul_succ_le_two_mul_sumIf S is a finite set of natural numbers in which every v is at least c times its rank (the number of elements of S that are ≤ v), then…
- Used by 1
- perm_distinct_abs_diffs_ascent_count_sub_half_unboundedFor any permutation (a_n) of the positive integers whose consecutive absolute differences are pairwise distinct, A(X) − X/2 is unbounded…
The proof, explained
The proof specializes the general inequality `finset_nat_mul_card_mul_succ_le_two_mul_sum` with $c = 1$. The required premise asks that for every $v \in S$, the number of elements in $S$ that are at most $v$ is bounded by $v$. Because every element in $S$ is strictly positive, these elements all lie in the discrete interval $[1, v]$, which has size $v$. Simplifying the leading factor of 1 then completes the proof.
To apply `finset_nat_mul_card_mul_succ_le_two_mul_sum` with $c = 1$, it suffices to show that $|\{x \in S \mid x \le v\}| \le v$ for every $v \in S$.
We instantiate the general inequality `finset_nat_mul_card_mul_succ_le_two_mul_sum` with scaling factor $c = 1$. For any element $v \in S$, the required condition $1 \cdot |\{x \in S \mid x \le v\}| \le v$ simplifies to $|\{x \in S \mid x \le v\}| \le v$ by `one_mul`.
uses
finset_nat_mul_card_mul_succ_le_two_mul_sum,one_mulhave := finset_nat_mul_card_mul_succ_le_two_mul_sum 1 S (by intro v hv rw [one_mul]
For every $v \in S$, $|\{x \in S \mid x \le v\}| \le v$, which implies $1 \cdot (|S|(|S| + 1)) \le 2 \sum_{v \in S} v$.
We bound the size of $\{x \in S \mid x \le v\}$ by comparing it to the closed interval $[1, v]$. Any $w$ in the filtered set belongs to $S$ and satisfies $w \le v$ by `mem_filter`. By hypothesis $h$, every element of $S$ is strictly positive, so $1 \le w \le v$, which means $w \in [1, v]$ by `mem_Icc`. Hence $\{x \in S \mid x \le v\} \subseteq [1, v]$, and by `card_le_card`, its cardinality is at most $|[1, v]|$. The interval $[1, v]$ contains exactly $v$ integers (evaluated by `simp`), establishing $|\{x \in S \mid x \le v\}| \le v$ and completing the premise for the general bound.
uses
card_le_card,mem_filter,mem_Icccalc (S.filter (· ≤ v)).card ≤ (Icc 1 v).card := by apply card_le_card intro w hw rw [mem_filter] at hw exact mem_Icc.2 ⟨h w hw.1, hw.2⟩ _ = v := by simp)
$|S|(|S| + 1) \le 2 \sum_{v \in S} v$.
Simplifying the redundant factor of $1$ on the left-hand side of $1 \cdot (|S|(|S| + 1)) \le 2 \sum_{v \in S} v$ yields the theorem statement.
simpa using this
finset_nat_mul_card_mul_succ_le_two_mul_sum- For any natural number $c$ and finite set of natural numbers $S$, if every $v \in S$ satisfies $c \cdot |\{x \in S \mid x \le v\}| \le v$, then $c \cdot |S|(|S| + 1) \le 2 \sum_{v \in S} v$.
one_mul- Multiplying by 1 on the left leaves an element unchanged: $1 \cdot a = a$.
card_le_card- If a finite set $s$ is a subset of a finite set $t$, then $|s| \le |t|$.
mem_filter- An element $a$ belongs to $\{x \in s \mid p(x)\}$ if and only if $a \in s$ and $p(a)$ holds.
mem_Icc- An element $x$ belongs to the closed interval $[a, b]$ if and only if $a \le x$ and $x \le b$.
- The intermediate factor of 1 on the left-hand side, $1 \cdot (|S|(|S| + 1))$, is a formal artifact of specializing the more general lemma `finset_nat_mul_card_mul_succ_le_two_mul_sum` with $c = 1$.
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 finset_nat_card_mul_succ_le_two_mul_sum_of_pos (S : Finset ℕ) (h : ∀ v ∈ S, 0 < v) : S.card * (S.card + 1) ≤ 2 * ∑ v ∈ S, v := open Finset in by have := finset_nat_mul_card_mul_succ_le_two_mul_sum 1 S (by intro v hv rw [one_mul] calc (S.filter (· ≤ v)).card ≤ (Icc 1 v).card := by apply card_le_card intro w hw rw [mem_filter] at hw exact mem_Icc.2 ⟨h w hw.1, hw.2⟩ _ = v := by simp) simpa using this