AFTD Auto-Formalizing Theoretical Domains

finset_nat_mul_card_mul_succ_le_two_mul_sum

theoremverified

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

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.

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

    lines 4–5

    uses Finset.induction_on_max

      induction S using Finset.induction_on_max with
      | empty => simp
  2. 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`.

    lines 6–8

    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]
  3. 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`.

    lines 9–18

    uses mem_insert_self, filter_true_of_mem, le_rfl, card_insert_of_notMem

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

    lines 19–26

    uses mem_insert_of_mem, filter_insert, if_neg

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

    lines 27–30

        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.

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