Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.3 — every comparison of a linear extension of GtG_tGt​ has weight at least 1/(d+1)1/(d+1)1/(d+1)

Proved
SortingCounterexamples.Optimal.Supplement.lemma_5_3

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

geometric-rankingslearning-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1rankingssorting

Let v1,…,vn∈Rdv_1,\dots,v_n\in\mathbb R^dv1​,…,vn​∈Rd and let HHH be a nonempty finite ddd-dimensional geometric class of rankings with this representation. For any transcript, let p(i,j)p(i,j)p(i,j) be the probability that a ranking drawn from HHH with the normalized weighted-majority weights places iii before jjj, and let GGG be the strong-majority graph with an edge i→ji\to ji→j for distinct i,ji,ji,j whenever p(i,j)>1−1d+1p(i,j)>1-\frac1{d+1}p(i,j)>1−d+11​. If a ranking π^\hat\piπ^ is a linear extension of GGG (it places iii before jjj for every edge i→ji\to ji→j) and π^\hat\piπ^ places iii before jjj, then

p(i,j) ≥ 1d+1.p(i,j)\ \ge\ \frac1{d+1}.p(i,j) ≥ d+11​.

This is the progress guarantee of the upper bound: whichever pair the oracle returns, the rankings that agree with the query on it carry at least a 1/(d+1)1/(d+1)1/(d+1) fraction of the weight, so the total weight drops by a factor 1−12(d+1)1-\frac1{2(d+1)}1−2(d+1)1​ (eq. (11)).

Differences from the source:

  • generalization: π̂_t, the linear extension of G_t queried by the learner at time t → every linear extension π̂ of G for the weights after any transcript; reason: the learner's query is one such extension of the graph of its own transcript, so the source's statement is a special case
  • encoding: P_t is a probability distribution on H → H nonempty; reason: normalization by Q_t is defined only for nonempty H; for empty H Lean's division by zero would give p = 0
Preamble
import Mathlib
import Definitions.Def_SortingCounterexamples_Optimal_Protocol
import Definitions.Def_SortingCounterexamples_Optimal_Supplement_Geometric
Formal statement
namespace SortingCounterexamples.Optimal.Supplement

open SortingCounterexamples.Optimal

/-- Lemma 5.3: for a nonempty `d`-dimensional geometric class `H` and the weights after any
transcript `h`, every linear extension `π̂` of the strong-majority graph `G_t` orients only
pairs with support at least `1/(d+1)`: if `π̂` places `i` before `j`, then
`p_t(i, j) ≥ 1/(d+1)`. -/
theorem lemma_5_3 {n d : ℕ} (v : Fin n → Fin d → ℝ) (H : Finset (Ranking n))
    (hH : IsGeometricClass v H) (hne : H.Nonempty) (h : Transcript n) (πhat : Ranking n)
    (hext : IsLinearExtension πhat (MajorityEdge d H h)) :
    ∀ i j : Fin n, πhat.Before i j → 1 / ((d : ℝ) + 1) ≤ pairProb H h i j := by sorry

end SortingCounterexamples.Optimal.Supplement
Source
Noga Alon, Shay Moran, Shlomo Moran, STOC 2027 submission #549 (October 2026), printed p. 24 / PDF p. 25, Lemma 5.3; graph G_t from eq. (8), printed p. 23 / PDF p. 24; setting printed p. 22 / PDF p. 23

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