Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

Base case of BCR Lemma 12 at the tight escape price

Proved
KServer.bcr_tight_base

by Zexuan Liu · Sep 7, 2026 · Mathlib c5ea003 (Lean v4.30.0)

chunk-systemk-serveronline-algorithms

Let Mw\mathcal M_wMw​ be the level-www member of the recursive Bubeck--Coester--Rabani space family, with marked points sw,tws_w,t_wsw​,tw​ at distance dw=β 3wd_w=\beta\,3^wdw​=β3w, and let ChunksTight(α,β,w)\mathrm{ChunksTight}(\alpha,\beta,w)ChunksTight(α,β,w) be the level invariant of KServer.BCRInductiveChunksTight: a chunk system on Mw\mathcal M_wMw​ with sizes in [3w/2, 3⋅3w/2][3^w/2,\,3\cdot3^w/2][3w/2,3⋅3w/2], expected total at least αβw23w\alpha\beta w^2 3^wαβw23w, escape price dwd_wdw​, exactly M≥⌈αβw2⌉M\ge\lceil\alpha\beta w^2\rceilM≥⌈αβw2⌉ chunks, constant initial information and no empty chunk.

Statement. For every α≥0\alpha\ge0α≥0, every integer β≥2\beta\ge2β≥2 and every level www with

αw2  ≤  1,\alpha w^2\;\le\;1,αw2≤1,

the invariant ChunksTight(α,β,w)\mathrm{ChunksTight}(\alpha,\beta,w)ChunksTight(α,β,w) holds.

Why this is the easy half. When αw2≤1\alpha w^2\le1αw2≤1 the demanded expected total αβw23w\alpha\beta w^2 3^wαβw23w is at most β3w=dw\beta 3^w=d_wβ3w=dw​, so no randomness is needed: a deterministic single-file adversary suffices. Level www of the family contains a unit geodesic chain ggg with g(0)=swg(0)=s_wg(0)=sw​, g(β3w)=twg(\beta 3^w)=t_wg(β3w)=tw​ and d(g(i),g(j))=∣i−j∣d(g(i),g(j))=|i-j|d(g(i),g(j))=∣i−j∣; sampling it at the multiples of 3w3^w3w gives β+1\beta+1β+1 marked positions at spacing 3w3^w3w, and the singleton requests at those positions, one per chunk, form a chunk system of β\betaβ chunks of size 3w3^w3w. Each chunk forces the evader to advance one step of the chain, and bailing out is never cheaper because the escape price β3w\beta3^wβ3w is at least the chunk size 3w3^w3w.

Relation to the existing base case. This is KServer.bcr_induction_base with the escape price lowered from 2dw2d_w2dw​ to dwd_wdw​ and with the two structural clauses that the level steps additionally require: the exact chunk count and nonemptiness of the chunks. The lower price is what makes the invariant chainable, since KServer.level_step_sturdy assumes its input price is at most d(s,t)d(s,t)d(s,t), and it costs nothing here: the cost bound of the single-file system holds against any escape price at least the chunk size. The geodesic chain in the glued family and the single-file system along an arbitrary chain are the two ingredients of the existing proof and can be reused verbatim.

Preamble
import Definitions.Def_KServer_bcr_induction_tight
Formal statement
namespace KServer

theorem bcr_tight_base (α : ℝ) (hα : 0 ≤ α) (β : ℕ) (hβ : 0 < β) (hβ2 : 2 ≤ β)
    (w : ℕ) (hw : α * (w : ℝ) ^ 2 ≤ 1) :
    BCRInductiveChunksTight α β hβ w := by sorry

end KServer
Source
S. Bubeck, C. Coester, Y. Rabani, The randomized k-server conjecture is false!, STOC 2023, https://arxiv.org/abs/2211.05753: Lemma 12 (p. 14) with its base case (p. 15, the levels with alpha w^2 <= 1) and its induction step (Claim 13, p. 15-19, and Lemma 15, p. 19-21). Stated over the platform predicate KServer.BCRInductiveChunksTight, whose escape price d_w matches the hypotheses of KServer.level_step_sturdy.

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 paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me