Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§5 — geometric ranking classes, weighted-majority weights, pair probabilities and the strong-majority graph

Definition
SortingCounterexamples_Optimal_Supplement_Geometric

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

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

This file adds the objects of §5 (Geometric Rankings) on top of the published interaction model (rankings of the items 0,…,n−10,\dots,n-10,…,n−1, counterexample pairs, transcripts, lie counts).

  1. Scores and induced rankings. A representation assigns to each item iii a vector vi∈Rdv_i\in\mathbb R^dvi​∈Rd. For a direction w∈Rdw\in\mathbb R^dw∈Rd the score of iii is ⟨vi,w⟩=∑l=1dvi,lwl\langle v_i,w\rangle=\sum_{l=1}^d v_{i,l}w_l⟨vi​,w⟩=∑l=1d​vi,l​wl​. The direction www induces the ranking π\piπ when, for all items i,ji,ji,j,
i≺πj  ⟺  ⟨vi,w⟩<⟨vj,w⟩.i\prec_\pi j\iff\langle v_i,w\rangle<\langle v_j,w\rangle .i≺π​j⟺⟨vi​,w⟩<⟨vj​,w⟩.

Such a direction gives pairwise distinct scores, so only directions inducing strict linear orders occur. 2. Geometric classes. A finite class HHH of rankings is ddd-dimensional geometric with representation vvv when every π∈H\pi\in Hπ∈H is induced by some direction w∈Rdw\in\mathbb R^dw∈Rd. HHH may be any such class; it need not contain all rankings induced by vvv. 3. Weights. After a transcript hhh (the chronological list of queries π^t\hat\pi_tπ^t​ with the returned pairs {i,j}\{i,j\}{i,j}), the weight of a ranking π\piπ is obtained from q0(π)=1q_0(\pi)=1q0​(π)=1 by halving it on every round in which π\piπ orders the returned pair as the query did, and leaving it unchanged otherwise (eq. (10)). These are exactly the rounds whose counterexample is untruthful for π\piπ, so qh(π)=2−ℓ(π,h)q_h(\pi)=2^{-\ell(\pi,h)}qh​(π)=2−ℓ(π,h) with ℓ(π,h)\ell(\pi,h)ℓ(π,h) the published lie count. 4. Pair probabilities. Qh=∑π∈Hqh(π)Q_h=\sum_{\pi\in H}q_h(\pi)Qh​=∑π∈H​qh​(π), Ph(π)=qh(π)/QhP_h(\pi)=q_h(\pi)/Q_hPh​(π)=qh​(π)/Qh​, and

ph(i,j)=∑π∈H, i≺πjPh(π),p_h(i,j)=\sum_{\pi\in H,\ i\prec_\pi j}P_h(\pi),ph​(i,j)=π∈H, i≺π​j∑​Ph​(π),

the probability that a ranking drawn from PhP_hPh​ places iii before jjj. 5. Strong-majority graph. GhG_hGh​ has an edge i→ji\to ji→j between distinct items exactly when ph(i,j)>1−1d+1p_h(i,j)>1-\frac1{d+1}ph​(i,j)>1−d+11​ (eq. (8)). A ranking is a linear extension of a relation when it places iii before jjj for every edge i→ji\to ji→j. 6. Rates. d2log⁡n+dkd^2\log n+dkd2logn+dk (Theorem 5.1) and dlog⁡n+dkd\log n+dkdlogn+dk (Theorem 5.4), with the natural logarithm.

These objects are used by Lemmas 5.2 and 5.3 and Theorems 5.1 and 5.4.

Formalization Note Vectors of Rd\mathbb R^dRd are functions Fin d → ℝ with the standard dot product. The weights depend only on the transcript, and are defined for every transcript, not only for those produced by a particular learner. When HHH is empty, Qh=0Q_h=0Qh​=0 and Lean's division gives ph≡0p_h\equiv0ph​≡0; the lemmas that normalize assume HHH nonempty.

Definition code
import Mathlib
import Definitions.Def_SortingCounterexamples_Optimal_Protocol

open scoped BigOperators

namespace SortingCounterexamples.Optimal.Supplement

open SortingCounterexamples.Optimal

/-- The score `⟨v i, w⟩` of item `i` in direction `w`, for a representation `v` of the items
by vectors of `ℝ^d` (standard inner product). -/
def score {n d : ℕ} (v : Fin n → Fin d → ℝ) (w : Fin d → ℝ) (i : Fin n) : ℝ :=
  ∑ l : Fin d, v i l * w l

/-- The direction `w` induces the ranking `π` in the representation `v`: for all items,
`i` comes before `j` in `π` exactly when `⟨v i, w⟩ < ⟨v j, w⟩`. Such a `w` gives pairwise
distinct scores, so only directions inducing strict linear orders are used. -/
def InducedBy {n d : ℕ} (v : Fin n → Fin d → ℝ) (w : Fin d → ℝ) (π : Ranking n) : Prop :=
  ∀ i j : Fin n, π.Before i j ↔ score v w i < score v w j

/-- `H` is a `d`-dimensional geometric class of rankings with representation `v`: every
ranking of `H` is induced by some direction `w ∈ ℝ^d`. `H` may be any such class, not
necessarily all rankings induced by `v`. -/
def IsGeometricClass {n d : ℕ} (v : Fin n → Fin d → ℝ) (H : Finset (Ranking n)) : Prop :=
  ∀ π ∈ H, ∃ w : Fin d → ℝ, InducedBy v w π

/-- The weight `q_t(π)` after the transcript `h`: starting from `1`, it is halved on every
round whose returned pair `{i, j}` is ordered by `π` as by that round's query (eq. (10)).
Those are exactly the rounds whose counterexample is untruthful for `π`, so
`q_h(π) = (1/2)^(lieCount π h)`. -/
noncomputable def weight {n : ℕ} (h : Transcript n) (π : Ranking n) : ℝ :=
  (1 / 2 : ℝ) ^ lieCount π h

/-- The total weight `Q_t = ∑_{π ∈ H} q_t(π)`. -/
noncomputable def totalWeight {n : ℕ} (H : Finset (Ranking n)) (h : Transcript n) : ℝ :=
  ∑ π ∈ H, weight h π

/-- `p_t(i, j)`: the probability that a ranking drawn from `H` with the normalized weights
`P_t(π) = q_t(π) / Q_t` places `i` before `j`. -/
noncomputable def pairProb {n : ℕ} (H : Finset (Ranking n)) (h : Transcript n) (i j : Fin n) :
    ℝ :=
  (∑ π ∈ H.filter (fun π => π.Before i j), weight h π) / totalWeight H h

/-- The strong-majority graph `G_t` (eq. (8)): an edge `i → j` between distinct items
whenever `p_t(i, j) > 1 - 1/(d+1)`. -/
def MajorityEdge {n : ℕ} (d : ℕ) (H : Finset (Ranking n)) (h : Transcript n) (i j : Fin n) :
    Prop :=
  i ≠ j ∧ 1 - 1 / ((d : ℝ) + 1) < pairProb H h i j

/-- `π` is a linear extension of the relation `E`: every edge `i → j` of `E` is respected,
`i` before `j` in `π`. -/
def IsLinearExtension {n : ℕ} (π : Ranking n) (E : Fin n → Fin n → Prop) : Prop :=
  ∀ i j : Fin n, E i j → π.Before i j

/-- The upper rate `d² log n + d k` of Theorem 5.1 (natural logarithm). -/
noncomputable def upperRate (n d k : ℕ) : ℝ := (d : ℝ) ^ 2 * Real.log n + d * k

/-- The lower rate `d log n + d k` of Theorem 5.4 (natural logarithm). -/
noncomputable def lowerRate (n d k : ℕ) : ℝ := (d : ℝ) * Real.log n + d * k

end SortingCounterexamples.Optimal.Supplement
Source
Noga Alon, Shay Moran, Shlomo Moran, STOC 2027 submission #549 (October 2026), printed p. 22 / PDF p. 23, §5 (geometric classes, directions inducing strict linear orders) and proof of Theorem 5.1 (weights q_t, Q_t, P_t, p_t); printed p. 23 / PDF p. 24, eq. (8); printed p. 24 / PDF p. 25, eq. (10); printed p. 3–4 / PDF p. 4–5 (geometric rankings, Figure 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