finset_nat_mul_card_mul_succ_le_two_mul_sum
If 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 c·|S|(|S|+1) ≤ 2·Σ_{v∈S} v.
Statement
theorem finset_nat_mul_card_mul_succ_le_two_mul_sum (c : ℕ) (S : Finset ℕ)
(h : ∀ v ∈ S, c * (S.filter (· ≤ v)).card ≤ v) :
c * (S.card * (S.card + 1)) ≤ 2 * ∑ v ∈ S, v- Source
- Step (2)–(3) of the proof of Lemma 1 in arXiv:2610.15860 (A note on the Slater–Vélez permutation): sums of sets with growing elements.
- Verified
- 14 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 2
- 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…
- finset_nat_card_mul_succ_le_two_mul_sum_of_posThe sum of q distinct positive integers is at least q(q+1)/2.
The proof, explained
The theorem is proved by induction on the finite set S, repeatedly adjoining a maximal element m strictly greater than all existing elements. For the inductive step S' = {m} ∪ S, the target inequality splits algebraically into the induction hypothesis on S and the bound c(|S| + 1) ≤ m. The latter follows directly from the hypothesis applied to the maximum element m, whose rank in S' is the full cardinality |S| + 1. The induction hypothesis applies to S because any element v ∈ S is strictly smaller than m, so m does not contribute to the rank of v.
The inequality holds for the empty set. automation
We proceed by induction on S using `Finset.induction_on_max`, which constructs any finite set of natural numbers by starting from ∅ and successively adjoining an element strictly greater than all elements currently in the set. In the base case S = ∅, the cardinality |∅| and the empty sum are both 0, so both sides vanish and the inequality simplifies to 0 ≤ 0.
uses
Finset.induction_on_maxinduction S using Finset.induction_on_max with | empty => simp
In the inductive step S' = {m} ∪ S where every x ∈ S satisfies x < m, the maximum element m is not in S, and the goal expands to c · (|S| + 1)(|S| + 2) ≤ 2(m + ∑_{v ∈ S} v).
Because strict order is irreflexive (`lt_irrefl`), the assumption that x < m for all x ∈ S implies that m ∉ S. Since m is fresh, the cardinality |{m} ∪ S| is |S| + 1 by `card_insert_of_notMem`, and the sum over {m} ∪ S splits as m + ∑_{v ∈ S} v by `sum_insert`.
uses
lt_irrefl,card_insert_of_notMem,sum_insert| insert m S hlt ih => have hm : m ∉ S := fun hm => lt_irrefl _ (hlt m hm) rw [card_insert_of_notMem hm, sum_insert hm]c · (|S| + 1) ≤ m.
Applying the rank hypothesis to m ∈ {m} ∪ S (using `mem_insert_self`) gives c · |{x ∈ {m} ∪ S | x ≤ m}| ≤ m. Since m is strictly greater than every element of S and equal to itself (by `le_rfl`), every element of {m} ∪ S is ≤ m. Thus filtering by (· ≤ m) retains the entire set {m} ∪ S (`filter_true_of_mem`), which has cardinality |S| + 1 by `card_insert_of_notMem`.
uses
mem_insert_self,filter_true_of_mem,le_rfl,card_insert_of_notMemhave h1 : c * (S.card + 1) ≤ m := by have := h m (mem_insert_self m S) have hf : (insert m S).filter (· ≤ m) = insert m S := by apply filter_true_of_mem intro x hx rcases mem_insert.1 hx with rfl | hx · exact le_rfl · exact (hlt x hx).le rw [hf, card_insert_of_notMem hm] at this exact this
c · |S|(|S| + 1) ≤ 2 ∑_{v ∈ S} v.
By the induction hypothesis `ih`, it suffices to verify the rank condition for S: for every v ∈ S, c · |{x ∈ S | x ≤ v}| ≤ v. For any v ∈ S, we have v ∈ {m} ∪ S by `mem_insert_of_mem`, so the original hypothesis gives c · |{x ∈ {m} ∪ S | x ≤ v}| ≤ v. Because v < m, the condition m ≤ v is false; hence filtering {m} ∪ S for elements ≤ v discards m (by `filter_insert` and `if_neg`), leaving exactly {x ∈ S | x ≤ v}. Substituting this equality into the bound establishes the inductive premise.
uses
mem_insert_of_mem,filter_insert,if_neghave h2 : c * (S.card * (S.card + 1)) ≤ 2 * ∑ v ∈ S, v := by apply ih intro v hv have := h v (mem_insert_of_mem hv) have hf : (insert m S).filter (· ≤ v) = S.filter (· ≤ v) := by rw [filter_insert, if_neg (not_le.2 (hlt v hv))] rw [hf] at this exact this
c · (|S| + 1)(|S| + 2) ≤ 2(m + ∑_{v ∈ S} v), completing the inductive step. automation
Ring arithmetic expands c(|S| + 1)(|S| + 2) as c|S|(|S| + 1) + 2c(|S| + 1). Rewriting the left-hand side with this identity, the inequality becomes c|S|(|S| + 1) + 2c(|S| + 1) ≤ 2m + 2∑_{v ∈ S} v. The `omega` tactic completes the proof by combining the induction hypothesis c|S|(|S| + 1) ≤ 2∑_{v ∈ S} v with twice the bound c(|S| + 1) ≤ m.
have e : c * ((S.card + 1) * (S.card + 1 + 1)) = c * (S.card * (S.card + 1)) + 2 * (c * (S.card + 1)) := by ring rw [e] omega
Finset.induction_on_max- A property holds for all finite subsets of a linearly ordered type if it holds for the empty set and is preserved whenever an element strictly greater than all existing elements is adjoined.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself (¬ a < a).
card_insert_of_notMem- Inserting an element into a finite set that does not contain it increases the cardinality of the set by 1.
sum_insert- The sum of a function over a finite set with a new element inserted equals the value at that element plus the sum over the original set.
mem_insert_self- An element always belongs to the set obtained by inserting it into any finite set.
filter_true_of_mem- Filtering a finite set by a predicate that is satisfied by every element in the set returns the original set.
le_rfl- Inequality is reflexive: every element is less than or equal to itself (a ≤ a).
mem_insert_of_mem- If an element belongs to a finite set, it also belongs to the set after inserting another element.
filter_insert- Filtering {a} ∪ S by a predicate p yields {a} ∪ (S filtered by p) if p(a) holds, and S filtered by p if p(a) is false.
if_neg- An if-then-else expression evaluates to its else branch when the condition is false.
- The inductive step relies on `Finset.induction_on_max`, which carries out induction on finite subsets of a linear order by adjoining a new maximum element at each step.
- The final arithmetic combination of the induction hypothesis and the bound on the maximum element is automated by the `omega` decision procedure.
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_mul_card_mul_succ_le_two_mul_sum (c : ℕ) (S : Finset ℕ) (h : ∀ v ∈ S, c * (S.filter (· ≤ v)).card ≤ v) : c * (S.card * (S.card + 1)) ≤ 2 * ∑ v ∈ S, v := open Finset in by induction S using Finset.induction_on_max with | empty => simp | insert m S hlt ih => have hm : m ∉ S := fun hm => lt_irrefl _ (hlt m hm) rw [card_insert_of_notMem hm, sum_insert hm] have h1 : c * (S.card + 1) ≤ m := by have := h m (mem_insert_self m S) have hf : (insert m S).filter (· ≤ m) = insert m S := by apply filter_true_of_mem intro x hx rcases mem_insert.1 hx with rfl | hx · exact le_rfl · exact (hlt x hx).le rw [hf, card_insert_of_notMem hm] at this exact this have h2 : c * (S.card * (S.card + 1)) ≤ 2 * ∑ v ∈ S, v := by apply ih intro v hv have := h v (mem_insert_of_mem hv) have hf : (insert m S).filter (· ≤ v) = S.filter (· ≤ v) := by rw [filter_insert, if_neg (not_le.2 (hlt v hv))] rw [hf] at this exact this have e : c * ((S.card + 1) * (S.card + 1 + 1)) = c * (S.card * (S.card + 1)) + 2 * (c * (S.card + 1)) := by ring rw [e] omega