AFTD Auto-Formalizing Theoretical Domains

finset_nat_card_mul_succ_le_two_mul_sum_of_pos

theoremverified

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
Used by 1

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.

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

    lines 3–5

    uses finset_nat_mul_card_mul_succ_le_two_mul_sum, one_mul

      have := finset_nat_mul_card_mul_succ_le_two_mul_sum 1 S (by
        intro v hv
        rw [one_mul]
  2. 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.

    lines 6–11

    uses card_le_card, mem_filter, mem_Icc

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

    line 12

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

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