direct_sum_alpha_star_le_one
For positive weights W_j > 0 and parameters 0 < r_j ≤ 1 on a nonempty finite index set M, the direct-sum calibration ratio α* = (∑_{j ∈ M} W_j) / (∑_{j ∈ M} W_j / r_j) satisfies α* ≤ 1.
Statement
theorem direct_sum_alpha_star_le_one {M : Type*} [DecidableEq M] [Fintype M] (W : M → ℝ) (r : M → ℝ) (hM : (Finset.univ : Finset M).Nonempty) (hW : ∀ j, 0 < W j) (hr : ∀ j, 0 < r j ∧ r j ≤ 1) : let W_bar := Finset.univ.sum W let denom := Finset.univ.sum (fun j => W j / r j) W_bar / denom ≤ 1
- Source
- scout/2610-29731-computing-the-nucleon-of-matching-games.md:1163
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
Let $M$ be a finite, nonempty type with decidable equality. Let $W, r : M \to \mathbb{R}$ be functions such that for all $j \in M$, $W(j) > 0$ and $0 < r(j) \le 1$. Then $$\frac{\sum_{j \in M} W(j)}{\sum_{j \in M} \frac{W(j)}{r(j)}} \le 1.$$
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 goal W_bar / denom ≤ 1 is equivalent to W_bar ≤ denom once the denominator is known to be strictly positive. For each index j ∈ M, the guarantee r j ∈ (0, 1] implies W j ≤ W j / r j, so summing over M gives W_bar ≤ denom. Since M is nonempty and each term W j / r j is strictly positive, the denominator is strictly positive, which completes the proof.
Let W_bar = ∑_{j ∈ M} W j and denom = ∑_{j ∈ M} (W j / r j).
Introduce the local definitions for the total weight W_bar and the weighted denominator denom into the context.
intro W_bar denomFor each j ∈ M, W j ≤ W j / r j.
Fix an index j. We are given 0 < r j ≤ 1 and W j > 0. Since r j > 0, multiplying both sides by r j shows that W j ≤ W j / r j is equivalent to W j * r j ≤ W j, which holds because r j ≤ 1 and W j > 0.
uses
le_div_iff₀have h_le : ∀ j ∈ Finset.univ, W j ≤ W j / r j := by intro j _ have hrpos : 0 < r j := (hr j).1 have hrle : r j ≤ 1 := (hr j).2 have hWpos : 0 < W j := hW j rw [le_div_iff₀ hrpos] nlinarith
W_bar ≤ denom
Sum the pointwise inequality W j ≤ W j / r j over all j ∈ M to obtain ∑_{j ∈ M} W j ≤ ∑_{j ∈ M} (W j / r j).
uses
Finset.sum_le_sumhave h_sum_le : W_bar ≤ denom := Finset.sum_le_sum h_le0 < denom
Because M is nonempty, there is at least one element j0 ∈ M. Each summand W j / r j is non-negative since W j > 0 and r j > 0, and the term at j0 is strictly positive. A finite sum of non-negative terms with at least one strictly positive term is strictly positive.
uses
Finset.sum_pos',div_nonneg,le_of_lt,div_poshave h_denom_pos : 0 < denom := by obtain ⟨j0, hj0⟩ := hM apply Finset.sum_pos' · intro j _ exact div_nonneg (le_of_lt (hW j)) (le_of_lt (hr j).1) · exact ⟨j0, hj0, div_pos (hW j0) (hr j0).1⟩
W_bar / denom ≤ 1
Because denom > 0, dividing W_bar ≤ denom by denom yields W_bar / denom ≤ 1.
uses
div_le_one₀exact (div_le_one₀ h_denom_pos).mpr h_sum_le
le_div_iff₀- For a positive divisor c > 0, a ≤ b / c holds if and only if a * c ≤ b.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set, then ∑ i, f(i) ≤ ∑ i, g(i).
Finset.sum_pos'- A sum over a finite set is strictly positive if all summands are non-negative and at least one summand is strictly positive.
div_nonneg- The quotient of two non-negative elements is non-negative.
le_of_lt- A strict inequality a < b implies the non-strict inequality a ≤ b.
div_pos- The quotient of two strictly positive elements is strictly positive.
div_le_one₀- For a strictly positive denominator b > 0, a / b ≤ 1 holds if and only if a ≤ 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
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.
/-- The direct-sum calibration optimum is at most 1 when guarantees are in (0, 1]. -/theorem direct_sum_alpha_star_le_one {M : Type*} [DecidableEq M] [Fintype M] (W : M → ℝ) (r : M → ℝ) (hM : (Finset.univ : Finset M).Nonempty) (hW : ∀ j, 0 < W j) (hr : ∀ j, 0 < r j ∧ r j ≤ 1) : let W_bar := Finset.univ.sum W let denom := Finset.univ.sum (fun j => W j / r j) W_bar / denom ≤ 1 := by intro W_bar denom have h_le : ∀ j ∈ Finset.univ, W j ≤ W j / r j := by intro j _ have hrpos : 0 < r j := (hr j).1 have hrle : r j ≤ 1 := (hr j).2 have hWpos : 0 < W j := hW j rw [le_div_iff₀ hrpos] nlinarith have h_sum_le : W_bar ≤ denom := Finset.sum_le_sum h_le have h_denom_pos : 0 < denom := by obtain ⟨j0, hj0⟩ := hM apply Finset.sum_pos' · intro j _ exact div_nonneg (le_of_lt (hW j)) (le_of_lt (hr j).1) · exact ⟨j0, hj0, div_pos (hW j0) (hr j0).1⟩ exact (div_le_one₀ h_denom_pos).mpr h_sum_le