Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.4 — for every 2≤d≤n2\le d\le n2≤d≤n some ddd-dimensional geometric class forces Ω(dlog⁡n+dk)\Omega(d\log n+dk)Ω(dlogn+dk) expected queries

Open
SortingCounterexamples.Optimal.Supplement.theorem_5_4

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

geometric-rankingslearning-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexityrankingssorting

There is an absolute constant c>0c>0c>0 such that for all integers 2≤d≤n2\le d\le n2≤d≤n there are vectors v1,…,vn∈Rdv_1,\dots,v_n\in\mathbb R^dv1​,…,vn​∈Rd and a finite class HHH of rankings of the nnn items, each induced by some direction w∈Rdw\in\mathbb R^dw∈Rd, with the following property, where HHH is chosen before kkk and before the learner. For every k≥0k\ge0k≥0 and every randomized learner (Lω)ω∈Ω(L_\omega)_{\omega\in\Omega}(Lω​)ω∈Ω​ whose queries are linear orders (seed ω\omegaω from an arbitrary probability space (Ω,μ)(\Omega,\mu)(Ω,μ), each decision measurable in ω\omegaω; the learner may know kkk and HHH, and its queries need not lie in HHH) there are a target σ∈H\sigma\in Hσ∈H, fixed independently of the seed, and an oracle returning at most kkk untruthful counterexamples for σ\sigmaσ against every sequence of queries, such that

Eω∼μ[Q(Lω)] ≥ c (dlog⁡n+dk),\mathbb E_{\omega\sim\mu}\bigl[Q(L_\omega)\bigr]\ \ge\ c\,(d\log n+dk),Eω∼μ​[Q(Lω​)] ≥ c(dlogn+dk),

where Q∈{1,2,… }∪{∞}Q\in\{1,2,\dots\}\cup\{\infty\}Q∈{1,2,…}∪{∞} is the number of queries until approval.

This is the lower half of Theorem 1.2: the dependence on kkk of Theorem 5.1 is tight, and a factor ddd remains open in the noiseless term.

Formalization Note The expectation is a lower Lebesgue integral in [0,∞][0,\infty][0,∞], so a learner that fails to terminate with positive probability has infinite cost; it is not excluded by an assumption.

Differences from the source:

  • encoding: Ω(d log n + dk) worst-case expected query complexity → ∃ c > 0 before n, d, the class, k and the learner; ∃ σ ∈ H and an oracle with ofReal (c · (d log n + d k)) ≤ ∫⁻ Q dμ; reason: this is the meaning of an Ω bound on the worst case over targets in the class and oracles, uniform in all parameters; natural logarithm
  • encoding: possibly randomized learner whose queries are linear orders → a family of deterministic learners indexed by a seed of a probability space (Ω : Type), decisions measurable in the seed; reason: drawing all private randomness at the start covers every randomized learner; measurability is needed for the expectation to exist
  • encoding: in the presence of at most k untruthful counterexamples → a deterministic transcript-dependent oracle with at most k lies against every query sequence; reason: the source's hard oracles are of this kind; requiring validity against every query sequence only strengthens the existence claim
Preamble
import Mathlib
import Definitions.Def_SortingCounterexamples_Optimal_Protocol
import Definitions.Def_SortingCounterexamples_Optimal_Supplement_Geometric

open MeasureTheory
open scoped ENNReal
Formal statement
namespace SortingCounterexamples.Optimal.Supplement

open SortingCounterexamples.Optimal

/-- Theorem 5.4: there is an absolute `c > 0` such that for every `2 ≤ d ≤ n` there is a
`d`-dimensional geometric class `H` of rankings of `n` items (with a representation `v`),
chosen before `k` and the learner, such that for every `k` and every randomized learner whose
queries are linear orders there are a fixed target `σ ∈ H` and an oracle with at most `k`
untruthful counterexamples against every query sequence forcing expected number of queries at
least `c (d log n + d k)`. -/
theorem theorem_5_4 :
    ∃ c : ℝ, 0 < c ∧ ∀ (n d : ℕ), 2 ≤ d → d ≤ n →
      ∃ (v : Fin n → Fin d → ℝ) (H : Finset (Ranking n)), IsGeometricClass v H ∧
        ∀ k : ℕ, ∀ (Ω : Type) [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ]
          (L : Ω → DetLearner n), IsRandomizedLearner L →
          ∃ σ ∈ H, ∃ O : Oracle n, Admissible O σ k ∧
            ENNReal.ofReal (c * lowerRate n d k) ≤
              ∫⁻ ω, ((queries (L ω) O : ℕ∞) : ℝ≥0∞) ∂μ := by sorry

end SortingCounterexamples.Optimal.Supplement
Source
Noga Alon, Shay Moran, Shlomo Moran, STOC 2027 submission #549 (October 2026), printed p. 27 / PDF p. 28, Theorem 5.4 (proof to printed p. 29 / PDF p. 30); lower half of Theorem 1.2, printed p. 4 / PDF p. 5; model and randomized cost measure printed p. 1 / PDF p. 2

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