AFTD Auto-Formalizing Theoretical Domains

direct_sum_alpha_star_le_one

theoremverified

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.

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

    line 11

      intro W_bar denom
  2. For 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.

    lines 12–18

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

    line 19

    uses Finset.sum_le_sum

      have h_sum_le : W_bar ≤ denom := Finset.sum_le_sum h_le
  4. 0 < 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.

    lines 20–25

    uses Finset.sum_pos', div_nonneg, le_of_lt, div_pos

      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⟩
  5. W_bar / denom ≤ 1

    Because denom > 0, dividing W_bar ≤ denom by denom yields W_bar / denom ≤ 1.

    line 26

    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

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