Theorem 2.1 — The asymptotic complete-information threshold
OpenRankingQueryCost.Joint.Supplement.theorem_2_1p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking
For every admissible sequence with and , the complete-information actual threshold and worst public radius satisfy
For every admissible sequence with and ,
For every fixed real , fixed-support estimation attains squared error with probability at least and hard budget , uniformly over all admissible including . One finite program has polynomial computation with constants depending only on the margin. A rational internal represents the real margin. The full-information quantities are finite on every admissible instance. This companion theorem establishes the information threshold; its acquisition clause is a separate operational guarantee.
Differences from the source:
- encoding: n labelled objects and ranks 0 through n−1 → Fin n labels and Rank n permutations; reason: a bijective encoding preserving every instance and the full continuous output space Q
- encoding: nonnegative real full-information thresholds and radii → extended nonnegative real operational extrema, with explicit finiteness before real-valued limits; reason: prevents empty or unbounded real infimum defaults; compact Q and finite tables recover the stated real extrema
- encoding: Oδ or Θδ query rates and polynomial computation → positive constants and finite word-RAM programs quantified before n, s and the precisions; reason: makes exactly the stated uniform dependence explicit and charges computation with the published Implements contracts
- encoding: o(1) and real relative margin δ → universal sequential ratio limits and rational internal δstar in [δ/2,δ]; reason: specifies every asymptotic quantifier and gives finite program input while retaining all real margins
Preamble
import Definitions.Def_RankingQueryCost_Joint_Supplement_PublicThreshold import Definitions.Def_RankingQueryCost_Joint_Supplement_ActualThreshold import Definitions.Def_RankingQueryCost_Joint_Supplement_Phi import Definitions.Def_RankingQueryCost_Joint_PublicGate set_option autoImplicit false
Formal statement
namespace RankingQueryCost.Joint.Supplement
/-- Theorem 2.1, printed p. 4 / PDF 5. Both threshold limits, the density
profile, and the uniform fixed-support acquisition contract are retained. -/
theorem theorem_2_1 :
(∀ n s : ℕ, Admissible n s →
actualThreshold n s ≠ ⊤ ∧ publicThreshold n s ≠ ⊤) ∧
(∀ n s : ℕ → ℕ, (∀ j, Admissible (n j) (s j) ∧ 1 ≤ s j) →
Filter.Tendsto (fun j => (s j : ℝ) / (n j : ℝ) ^ 2) Filter.atTop (nhds 0) →
Filter.Tendsto (fun j => (actualThreshold (n j) (s j)).toReal /
(errorScale (n j) (s j) : ℝ)) Filter.atTop (nhds 1) ∧
Filter.Tendsto (fun j => (publicThreshold (n j) (s j)).toReal /
(errorScale (n j) (s j) : ℝ)) Filter.atTop (nhds 1)) ∧
(∀ (n s : ℕ → ℕ) (c : ℝ), 0 < c →
(∀ j, Admissible (n j) (s j)) → Filter.Tendsto n Filter.atTop Filter.atTop →
Filter.Tendsto (fun j => (s j : ℝ) / (n j : ℝ)) Filter.atTop (nhds c) →
Filter.Tendsto (fun j => (errorScale (n j) (s j) : ℝ) / (n j : ℝ) ^ 2)
Filter.atTop (nhds (densityProfile c))) ∧
∀ δ : ℝ, 0 < δ → δ ≤ 1 →
∃ (C : ℝ) (Ctime degree : ℕ) (p : ComparisonProgram) (δstar : ℚ),
0 < C ∧ 0 < Ctime ∧ 0 < δstar ∧ δ / 2 ≤ (δstar : ℝ) ∧ (δstar : ℝ) ≤ δ ∧
∀ n s : ℕ, Admissible n s →
∃ (B : ℕ) (A : QueryPolicy n), HardBudget s 0 B A ∧ Actual s 0 (threshold n s δ) A ∧
(B : ℝ) ≤ C * resolutionCost n ((errorScale n s : ℝ) / (n : ℝ) ^ 3) ∧
PolyActual s 0 Ctime degree p δstar A := by sorry
end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), Theorem 2.1, p. 4, PDF p. 5