AFTD Auto-Formalizing Theoretical Domains

exists_le_mul_of_le_sum

theoremverified

Let α be a type, let F be a finite subset of α with cardinality k where 1 ≤ k, and let f : α → ℕ be a function. If S ≤ ∑ x ∈ F, f x, then there exists an element x ∈ F such that S ≤ k * f x.

Statement

lemma exists_le_mul_of_le_sum {α : Type*} (F : Finset α) (f : α → ℕ) (k : ℕ) (hk : 1 ≤ k)
    (hcard : F.card = k) (S : ℕ) (hsum : S ≤ ∑ x ∈ F, f x) :
    ∃ x ∈ F, S ≤ k * f x
Source
arXiv:2610.37315 Claim 1.2
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1
  • exists_mem_card_filter_subset_le_mulLet α be a type with decidable equality, let k ≥ 1 be a natural number, and let ℱ be a finite family of finite subsets of α such that for…

Read back from the Lean

For any type α, any finite set F : Finset α, any function f : α → ℕ, any natural number k satisfying 1 ≤ k such that the cardinality of F is k, and any natural number S such that S ≤ ∑ x ∈ F, f x, there exists an element x ∈ F such that S ≤ k * f x.

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

The lemma is an averaging principle: if the sum of k terms is at least S, then at least one term must be at least the average S/k (or equivalently, S ≤ k * f x). First, the set F is shown to be nonempty since its cardinality is k ≥ 1. Next, multiplying the hypothesis S ≤ ∑ x ∈ F, f x by k yields an inequality between the sum of the constant S over F and the sum of k * f x. Finally, the pigeonhole lemma for sums (Finset.exists_le_of_sum_le) guarantees the existence of a witness x ∈ F.

  1. F is nonempty

    Because F has cardinality k (by hcard) and 1 ≤ k (by hk), the cardinality of F is strictly positive (0 < k). By Finset.card_pos, a finite set with strictly positive cardinality is nonempty.

    lines 5–7

    uses Finset.card_pos

      have hne : F.Nonempty := by
        rw [← Finset.card_pos, hcard]
        exact hk
  2. ∑ x ∈ F, S ≤ ∑ x ∈ F, (k * f x)

    Summing the constant S over F gives |F| * S = k * S using Finset.sum_const, nsmul_eq_mul, and hcard. Factoring k out of the right-hand sum gives k * ∑ x ∈ F, f x using Finset.mul_sum. Multiplying both sides of the assumption S ≤ ∑ x ∈ F, f x (hsum) on the left by k via Nat.mul_le_mul_left then establishes the inequality.

    lines 8–10

    uses Finset.sum_const, nsmul_eq_mul, Finset.mul_sum, Nat.mul_le_mul_left

      have h_sum_le : ∑ x ∈ F, S ≤ ∑ x ∈ F, (k * f x) := by
        rw [Finset.sum_const, nsmul_eq_mul, hcard, ← Finset.mul_sum]
        exact Nat.mul_le_mul_left k hsum
  3. There exists an element x ∈ F such that S ≤ k * f x

    Applying the averaging principle Finset.exists_le_of_sum_le to the nonempty set F and the sum inequality ∑ x ∈ F, S ≤ ∑ x ∈ F, (k * f x) yields an element x ∈ F satisfying S ≤ k * f x, concluding the proof.

    lines 11–12

    uses Finset.exists_le_of_sum_le

      obtain ⟨x, hx, hle⟩ := Finset.exists_le_of_sum_le hne h_sum_le
      exact ⟨x, hx, hle⟩
Finset.card_pos
A finite set is nonempty if and only if its cardinality is strictly positive.
Finset.sum_const
The sum of a constant value over a finite set equals the cardinality of the set multiplied by that constant.
nsmul_eq_mul
Scalar multiplication by a natural number in a semiring equals multiplication by that natural number.
Finset.mul_sum
Multiplication distributes over a finite sum: multiplying a constant by a sum equals the sum of the constant multiplied by each term.
Nat.mul_le_mul_left
Multiplying both sides of an inequality of natural numbers on the left by a natural number preserves the inequality.
Finset.exists_le_of_sum_le
If the sum of one function over a nonempty finite set is at most the sum of another, then there exists an element of the set where the first function is at most the second.

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

/-- Averaging lemma: if a sum of nonnegative integers over a set of size k ≥ 1 is at least S, then some term is at least S/k. -/lemma exists_le_mul_of_le_sum {α : Type*} (F : Finset α) (f : α → ℕ) (k : ℕ) (hk : 1 ≤ k)    (hcard : F.card = k) (S : ℕ) (hsum : S ≤ ∑ x ∈ F, f x) :    ∃ x ∈ F, S ≤ k * f x := by  have hne : F.Nonempty := by    rw [← Finset.card_pos, hcard]    exact hk  have h_sum_le : ∑ x ∈ F, S ≤ ∑ x ∈ F, (k * f x) := by    rw [Finset.sum_const, nsmul_eq_mul, hcard, ← Finset.mul_sum]    exact Nat.mul_le_mul_left k hsum  obtain ⟨x, hx, hle⟩ := Finset.exists_le_of_sum_le hne h_sum_le  exact ⟨x, hx, hle⟩
See it in the graphDiscuss this resultChallenge it