Theorem 8 — large regular-degree values, gap scale, and optimizer convergence
OpenRankingCertGap.Supplement.theorem_8asymptotic-analysisonline-matchingp2o-gran-per-chapterp2o-plan-paperp2o-v1randomized-primal-dualranking-algorithm
For every integer ,
As through the integers,
Moreover, every sequence satisfying obeys
The result separates the scale of the certifiable regularity improvement from the larger certifying gap and identifies the only possible limiting profile of asymptotically optimal certificates.
Formalization Note The sharp capacity expansion is the equivalent normalized limit. The norm is the Lebesgue integral on .
Differences from the source:
- encoding: in the expansion of → an explicit absolute constant and integer threshold; reason: this is the definition of the remainder bound
- encoding: → the normalized limit ; reason: the forms are equivalent for integer
- encoding: , , and convergence → filter limits, an eventual lower bound for every positive error, and the Lebesgue integral of the absolute difference; reason: these are their standard literal meanings and the eventual form avoids a junk real
liminfon an unbounded sequence - encoding: profiles on → total real profiles compared only in ; reason: the extension changes no source value
- encoding: a sequence over positive integer degrees → a zero-based natural-number sequence with every term in ; reason: adding the unused finite initial term does not affect either limit and every source sequence has such an extension
Preamble
import Mathlib import Definitions.Def_RankingCertGap_Supplement_Objects set_option autoImplicit false open Filter Topology
Formal statement
namespace RankingCertGap.Supplement
/-- **Theorem 8 (Large regular degree).** Xu, arXiv:2610.17545 (held file sha256 75896dd9…),
Theorem 8, pp.10–11, eqs. (28)–(32). This includes the finite-degree lower bound and its
second-order expansion, the sharp normalized capacity asymptotic, convergence of competitiveness
and the gap, the `lim inf` lower bound, and `L¹` convergence of every asymptotically optimal profile
sequence.
**Formalization Note.** Equation (29) is represented by the normalized limit
`(Γ̃(d) - (1-1/e)) d²/(log d)² → 1/(2e)`, exactly equivalent to its printed
`(1/(2e)+o(1))(log d)²/d²` form. The `O(d⁻²)` in (28) is an explicit absolute constant and
threshold. Equation (32) quantifies over the entire sequence before assuming asymptotic optimality. -/
theorem theorem_8 :
(∀ d : ℕ, 2 ≤ d →
1 - (1 - 1 / (d : ℝ)) ^ d ≤ gammaC (regular d)) ∧
(∃ C : ℝ, 0 ≤ C ∧ ∃ N : ℕ, ∀ d : ℕ, N ≤ d →
|(1 - (1 - 1 / (d : ℝ)) ^ d) -
(1 - 1 / Real.exp 1 + 1 / (2 * Real.exp 1 * d))| ≤ C / (d : ℝ) ^ 2) ∧
Tendsto
(fun d : ℕ =>
(GammaC classF (regular d) - (1 - 1 / Real.exp 1)) * (d : ℝ) ^ 2 /
(Real.log d) ^ 2)
atTop (nhds (1 / (2 * Real.exp 1))) ∧
Tendsto (fun d : ℕ => gammaC (regular d)) atTop (nhds (1 - 1 / Real.exp 1)) ∧
Tendsto (fun d : ℕ => gapC classF (regular d)) atTop (nhds 0) ∧
(∀ epsilon : ℝ, 0 < epsilon →
∀ᶠ d : ℕ in atTop,
1 / (2 * Real.exp 1) - epsilon ≤ (d : ℝ) * gapC classF (regular d)) ∧
(∀ f : ℕ → ℝ → ℝ, (∀ d, f d ∈ classF) →
Tendsto
(fun d : ℕ => GammaC classF (regular d) - chiC (f d) (regular d))
atTop (nhds 0) →
Tendsto (fun d : ℕ => l1Dist (f d) expProfile) atTop (nhds 0)) := 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 8, pp.10–11, eqs. (28)–(32)