exists_le_mul_of_le_sum
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.
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.
uses
Finset.card_poshave hne : F.Nonempty := by rw [← Finset.card_pos, hcard] exact hk
∑ 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.
uses
Finset.sum_const,nsmul_eq_mul,Finset.mul_sum,Nat.mul_le_mul_lefthave 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
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.
uses
Finset.exists_le_of_sum_leobtain ⟨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
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.
/-- 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⟩