direct_sum_alpha_star_eq_one_iff
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) equals 1 if and only if r_j = 1 for all j ∈ M.
Statement
theorem direct_sum_alpha_star_eq_one_iff {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 ↔ ∀ j : M, r j = 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$. Let $\bar{W} = \sum_{j \in M} W(j)$ and $\mathrm{denom} = \sum_{j \in M} \frac{W(j)}{r(j)}$. Then $\bar{W} / \mathrm{denom} = 1$ if and only if $r(j) = 1$ for all $j \in M$.
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 direct-sum calibration ratio α* = W_bar / denom equals 1 if and only if the numerator W_bar = ∑_{j ∈ M} W j equals the denominator denom = ∑_{j ∈ M} W j / r j, since denom is strictly positive. Because 0 < r j ≤ 1 and W j > 0, each term satisfies W j ≤ W j / r j. For two sums whose terms are pointwise ordered, equality of the sums is equivalent to pointwise equality of every summand, W j = W j / r j. Finally, because W j > 0 and r j > 0, this termwise equality holds if and only if r j = 1 for all j ∈ M.
For every component j ∈ M, W j ≤ W j / r j.
Introduce the abbreviations W_bar for the numerator ∑_{j ∈ M} W j and denom for the denominator ∑_{j ∈ M} W j / r j. Since r j > 0, clearing the denominator via le_div_iff₀ transforms W j ≤ W j / r j into W j * r j ≤ W j. This inequality holds because W j > 0 and r j ≤ 1.
uses
le_div_iff₀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
The denominator denom = ∑_{j ∈ M} W j / r j is strictly positive.
Since M is nonempty, choose an element j0 ∈ M. For each j ∈ M, W j / r j is non-negative by div_nonneg because W j ≥ 0 and r j ≥ 0 (from le_of_lt). At j0, both W j0 > 0 and r j0 > 0, so W j0 / r j0 > 0 by div_pos. Therefore, by Finset.sum_pos', the sum denom 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⟩
The ratio W_bar / denom equals 1 if and only if W_bar = denom.
Since denom > 0, it is nonzero by ne_of_gt. By div_eq_one_iff_eq, W_bar / denom = 1 is equivalent to W_bar = denom, which unfolds to ∑_{j ∈ M} W j = ∑_{j ∈ M} W j / r j.
uses
div_eq_one_iff_eq,ne_of_gthave h_div_eq : W_bar / denom = 1 ↔ W_bar = denom := div_eq_one_iff_eq (ne_of_gt h_denom_pos) rw [h_div_eq] dsimp [W_bar, denom]
The sum equality W_bar = denom holds if and only if W j = W j / r j for all j ∈ M.
Applying Finset.sum_eq_sum_iff_of_le to the pointwise inequality W j ≤ W j / r j shows that the two sums are equal if and only if the terms are equal pointwise. Simplifying the membership condition j ∈ Finset.univ via Finset.mem_univ and true_implies yields the universal condition ∀ j : M, W j = W j / r j.
uses
Finset.sum_eq_sum_iff_of_le,Finset.mem_univ,true_impliesrw [Finset.sum_eq_sum_iff_of_le h_le] simp only [Finset.mem_univ, true_implies]
For all j ∈ M, W j = W j / r j holds if and only if r j = 1 for all j ∈ M.
By forall_congr', it suffices to verify the equivalence for an arbitrary j ∈ M. Since r j > 0 and W j > 0, both are nonzero by ne_of_gt. Clearing the fraction with div_eq_iff transforms W j = W j / r j into W j * r j = W j. By mul_right_eq_self₀, this holds if and only if r j = 1 or W j = 0. Since W j ≠ 0, this simplifies to r j = 1.
uses
forall_congr',ne_of_gt,eq_comm,div_eq_iff,mul_right_eq_self₀apply forall_congr' intro j have hr0 : r j ≠ 0 := ne_of_gt (hr j).1 have hw0 : W j ≠ 0 := ne_of_gt (hW j) rw [eq_comm, div_eq_iff hr0, eq_comm] rw [mul_right_eq_self₀] simp [hw0]
le_div_iff₀- For positive c, a ≤ b / c if and only if a * c ≤ b.
Finset.sum_pos'- A finite sum of non-negative terms is strictly positive if at least one term is strictly positive.
div_nonneg- The quotient of two non-negative numbers 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 numbers is strictly positive.
div_eq_one_iff_eq- For a nonzero denominator b, the ratio a / b equals 1 if and only if a = b.
ne_of_gt- If b < a, then a ≠ b.
Finset.sum_eq_sum_iff_of_le- If f(i) ≤ g(i) for all elements in a finite set, their sums are equal if and only if f(i) = g(i) pointwise.
Finset.mem_univ- Every element of a finite type belongs to its universal set Finset.univ.
true_implies- The proposition (True → p) simplifies to p.
forall_congr'- Universal quantifiers preserve equivalence: if p(x) ↔ q(x) for all x, then (∀ x, p(x)) ↔ (∀ x, q(x)).
eq_comm- Equality is symmetric: a = b is equivalent to b = a.
div_eq_iff- For b ≠ 0, a / b = c is equivalent to a = c * b.
mul_right_eq_self₀- For elements in a structure with zero-cancellation, a * b = a holds if and only if b = 1 or a = 0.
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 equals 1 iff all component guarantees equal 1. -/theorem direct_sum_alpha_star_eq_one_iff {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 ↔ ∀ j : M, r j = 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_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⟩ have h_div_eq : W_bar / denom = 1 ↔ W_bar = denom := div_eq_one_iff_eq (ne_of_gt h_denom_pos) rw [h_div_eq] dsimp [W_bar, denom] rw [Finset.sum_eq_sum_iff_of_le h_le] simp only [Finset.mem_univ, true_implies] apply forall_congr' intro j have hr0 : r j ≠ 0 := ne_of_gt (hr j).1 have hw0 : W j ≠ 0 := ne_of_gt (hW j) rw [eq_comm, div_eq_iff hr0, eq_comm] rw [mul_right_eq_self₀] simp [hw0]