Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.1 — Obtuse rank displacements

Open
RankingQueryCost.Joint.Supplement.lemma_5_1

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

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

Let k≥1k\ge1k≥1 fixed-support worlds share one complete table T0T_0T0​ and have compatible ranks rj=p+djr^j=p+d^jrj=p+dj. Assume ⟨di,dj⟩≤0\langle d^i,d^j\rangle\le0⟨di,dj⟩≤0 for i≠ji\ne ji=j and ∥dj∥2≥S\|d^j\|^2\ge S∥dj∥2≥S for every jjj. Put m=⌈3k/4⌉m=\lceil3k/4\rceilm=⌈3k/4⌉. Then

Mact(n,s)≥(1−1/m)S,ρs(T0)≥(1−1/k)S.M_{\rm act}(n,s)\ge(1-1/m)S,\qquad\rho_s(T_0)\ge(1-1/k)S.Mact​(n,s)≥(1−1/m)S,ρs​(T0​)≥(1−1/k)S.

The center ppp is an arbitrary real vector. The statement applies to every finite nnn and budget sss, without the main theorems' admissibility restriction. It controls actual randomized estimation as well as the public radius. Compatibility with the complete table exactly expresses existence of the fixed-support worlds.

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: k worlds and m=ceil(3k/4) → k≥1 and m=(3*k+3)/4 in natural arithmetic; reason: k≥1 is the implicit nondegeneracy of both reciprocals, and the integer formula is exactly the ceiling
  • generalization: the standing admissible comparison domain of §2.1 → every finite ambient n and natural budget s, without Admissible n s; reason: the common-table packing argument depends only on compatibility and the displacement hypotheses; restricting to admissible instances recovers the complete source claim
Preamble
import Definitions.Def_RankingQueryCost_Joint_Supplement_Radius
import Definitions.Def_RankingQueryCost_Joint_Supplement_ActualThreshold

set_option autoImplicit false
Formal statement
namespace RankingQueryCost.Joint.Supplement

/-- Lemma 5.1, printed p. 25 / PDF 26. The nonempty candidate family is
implicit in the paper's divisions by k and ceil(3k/4). No admissible-domain
restriction is imposed on n or s in this pure packing result. -/
theorem lemma_5_1 (n s k : ℕ) (hk : 1 ≤ k) (T : Tournament n)
    (r : Fin k → Rank n) (p : Fin n → ℝ) (d : Fin k → Fin n → ℝ) (S : ℝ)
    (hworlds : ∀ j, r j ∈ compatible s (completeTranscript T))
    (hranks : ∀ j i, rankVector (r j) i = p i + d j i)
    (hobtuse : ∀ i j, i ≠ j → ∑ v, d i v * d j v ≤ 0)
    (hnorm : ∀ j, S ≤ ∑ v, (d j v) ^ 2) :
    let m : ℕ := (3 * k + 3) / 4
    ENNReal.ofReal ((1 - 1 / (m : ℝ)) * S) ≤ actualThreshold n s ∧
    ENNReal.ofReal ((1 - 1 / (k : ℝ)) * S) ≤ radius s T := by sorry

end RankingQueryCost.Joint.Supplement
Source
Chaoqiang Fu, Yifan Su, Daofeng Li, STOC 2027 submission #812 (October 2026), Lemma 5.1, p. 25, PDF p. 26

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