Theorem 5 — exact online-degree-two values, gap, unique optimizer, and Stieltjes measure
OpenRankingCertGap.Supplement.theorem_5asymptotic-analysisonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-primal-dualranking-algorithm
Let be the unique root in of . Then
Writing , the unique optimizer is below , on , and at . Its Stieltjes measure is
This gives the complete exact result at online degree at most two, including both the optimized certificate and RANKING's larger worst-case value.
Formalization Note The series is the published cStar, whose index is shifted to start at zero without changing the exponent. Optimizer equality is on .
Differences from the source:
- encoding: as the unique root in → the infimum of the root set together with explicit membership, roothood, and uniqueness clauses; reason: the clauses identify the same unique root and prevent the empty-infimum convention from surviving
- encoding: → ; reason: an index shift removes natural-number subtraction and is term-for-term identical
- encoding: profiles and Stieltjes measures on → total real profiles and probability measures on identified by their lower-interval values on ; reason: the extensions and ambient carrier change no source instance
- encoding: unique optimizer on → equality at every point of ; reason: values outside the source domain are irrelevant
Preamble
import Mathlib import Definitions.Def_RankingCertGap_Supplement_Objects import Definitions.Def_RankingCertGap_SafetyState set_option autoImplicit false open MeasureTheory
Formal statement
namespace RankingCertGap.Supplement
/-- **Theorem 5 (Online degree at most two: exact values and gap).** Xu, arXiv:2610.17545
(held file sha256 75896dd9…), Theorem 5, pp.8–9, eqs. (18)–(22). The unique root `s★`, the
exact capacity, competitiveness and gap, the unique step-profile optimizer, and its Stieltjes
measure are all included.
**Formalization Note.** `cStar` is definitionally
`1 - ∑' k : ℕ, (1/2)^(2^(k+1)+k)`, the source series after shifting its index from `k ≥ 1`.
Optimizer equality is pointwise on `[0,1]`. The Stieltjes-measure coefficients use `ENNReal.ofReal`;
the root and optimizer clauses imply they are the printed nonnegative weights. -/
theorem theorem_5 :
sStar ∈ Set.Ioo (0 : ℝ) 1 ∧
rootPoly sStar = 0 ∧
(∀ s ∈ Set.Ioo (0 : ℝ) 1, rootPoly s = 0 → s = sStar) ∧
GammaC classF (onDegLE 2) = 2 / (3 - sStar) ∧
gammaC (onDegLE 2) = cStar ∧
gapC classF (onDegLE 2) = cStar - 2 / (3 - sStar) ∧
fStar ∈ classF ∧
chiC fStar (onDegLE 2) = GammaC classF (onDegLE 2) ∧
(∀ f : ℝ → ℝ, f ∈ classF →
chiC f (onDegLE 2) = GammaC classF (onDegLE 2) →
∀ y ∈ Set.Icc (0 : ℝ) 1, f y = fStar y) ∧
HasStieltjesMeasure fStar
(ENNReal.ofReal wStar • Measure.dirac sStar +
ENNReal.ofReal (1 - wStar) • Measure.dirac (1 : ℝ)) := by sorry
end RankingCertGap.Supplement
Source
Xu, Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking, arXiv:2610.17545 (held file sha256 75896dd9…), Theorem 5, pp.8–9, eqs. (18)–(22)