Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Worst complete-table compatible-set radius

Definition
RankingQueryCost_Joint_Supplement_PublicThreshold

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1persistent-faultsquery-complexityranking

For each complete comparison table TTT with nonempty compatible set Cs(T)C_s(T)Cs​(T), let ρs(T)\rho_s(T)ρs​(T) be its squared radius with continuous centers in QQQ. Define

Mpub(n,s)=sup⁡T:Cs(T)≠∅ρs(T).M_{\rm pub}(n,s)=\sup_{T:C_s(T)\ne\varnothing}\rho_s(T).Mpub​(n,s)=T:Cs​(T)=∅sup​ρs​(T).

The finite table space makes this supremum a maximum. The definition uses extended nonnegative reals; a clean table always supplies a nonempty compatible set. This quantity measures full-information public uncertainty, rather than an acquisition budget.

Definition code
import Definitions.Def_RankingQueryCost_Joint_Supplement_Radius

set_option autoImplicit false

noncomputable section

namespace RankingQueryCost.Joint.Supplement

/-- §2.2: maximum complete-table radius, ranging only over nonempty version spaces.
There are finitely many tables; no asymptotic rate is built into this definition. -/
def publicThreshold (n s : ℕ) : ENNReal :=
  ⨆ T : {T : Tournament n // (compatible s (completeTranscript T)).Nonempty}, radius s T.val

end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), §2.2, p. 4, PDF p. 5

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me