Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

One level of BCR Lemma 12 at the tight escape price

Open
KServer.bcr_tight_step

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

chunk-systemk-serveronline-algorithms

Let ChunksTight(α,β,w)\mathrm{ChunksTight}(\alpha,\beta,w)ChunksTight(α,β,w) be the level invariant of KServer.BCRInductiveChunksTight: on the level-www space Mw\mathcal M_wMw​ of the recursive Bubeck--Coester--Rabani family, a chunk system between the marked points sw,tws_w,t_wsw​,tw​ (at distance dw=β3wd_w=\beta 3^wdw​=β3w) 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. There are constants 0<α≤10<\alpha\le10<α≤1 and an integer β≥2\beta\ge2β≥2, chosen once and for all, such that for every level www with α(w+1)2>1\alpha(w+1)^2>1α(w+1)2>1,

ChunksTight(α,β,w) ⟹ ChunksTight(α,β,w+1).\mathrm{ChunksTight}(\alpha,\beta,w)\ \Longrightarrow\ \mathrm{ChunksTight}(\alpha,\beta,w+1).ChunksTight(α,β,w) ⟹ ChunksTight(α,β,w+1).

Content. This is one full level of the induction of BCR's Lemma 12: Claim 13, which builds subchunks on the six-copy next-level space out of the level-www system in three stages and extracts the anti-concentration gain of the stage-2a race, followed by the regrouping of Lemma 15, which merges the subchunks into chunks of the next scale and restores the size window and the chunk count. The competitive ratio must rise from αβw2\alpha\beta w^2αβw2 to αβ(w+1)2\alpha\beta(w+1)^2αβ(w+1)2 while the distance triples, so the race has to contribute Θ(αβw)\Theta(\alpha\beta w)Θ(αβw) chunk masses beyond the three copies supplied by stages 1, 2b and 3; this is what forces αβ≲1\sqrt{\alpha\beta}\lesssim1αβ​≲1 and fixes the relation between the two constants.

Why this formulation. Every hypothesis of the proved level step KServer.level_step_sturdy is available from the invariant. Its taut-space hypothesis is KServer.bcrLevel2_taut. Its variance, sturdiness, Doob-jump and below-floor-count hypotheses follow from the two-sided size window through KServer.chunk_window_variance and KServer.chunk_window_invariants, with the below-floor count equal to zero for any floor at most 3w/23^w/23w/2. The exact chunk count and the nonemptiness of the chunks are carried by the invariant. And, decisively, the escape price is dwd_wdw​ rather than 2dw2d_w2dw​, which is what the step's hypothesis p ≤ dist s t demands; the older predicate KServer.BCRInductiveChunks fails this, and no adjustment can repair it, because the cost bound of a chunk system is stated against its escape price and KServer.ChunkSystemB.adjust can only raise it. The step's output price may be any value at least the input's, so the invariant's price dw+1=3dwd_{w+1}=3d_wdw+1​=3dw​ is reachable.

What remains for a prover. The choice of the parameter schedule: the number of coin steps κ\kappaκ, the tie-break scale ε\varepsilonε, the floor used in the anti-concentration bound, and the block length of the regrouping, subject to the gain of KServer.level_step_sturdy exceeding the losses it charges. The regrouping is KServer.chunk_combining_strong, which returns exactly the three structural clauses of the invariant.

Preamble
import Definitions.Def_KServer_bcr_induction_tight
Formal statement
namespace KServer

theorem bcr_tight_step :
    ∃ α : ℝ, 0 < α ∧ α ≤ 1 ∧ ∃ β : ℕ, ∃ hβ : 0 < β, 2 ≤ β ∧
      ∀ w : ℕ, 1 < α * ((w + 1 : ℕ) : ℝ) ^ 2 →
        BCRInductiveChunksTight α β hβ w →
        BCRInductiveChunksTight α β hβ (w + 1) := 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