BCR Lemma 12: small-level base on the canonical spaces
ProvedKServer.bcr_induction_basek-serverlower-boundsprobability
Let , , and satisfy . On the canonical space , there exists a chunk system satisfying the full quantitative induction package:
Thus the size window is , the escape price is , the expected total is at least , the chunk count is at least , and initial history is constant.
This is the small-level base case of Lemma 12. Formalization note. The paper uses a path for all small levels; the canonical family instead glues at every level. The statement transports the path construction to a marked geodesic in that canonical space, with marked positions spaced apart. The per-chunk bounds quantify over every initial evader location, so the first chunk must pin the starting endpoint.
Preamble
import Definitions.Def_KServer_bcr_induction
Formal statement
theorem KServer.bcr_induction_base (α : ℝ) (hα : 0 ≤ α)
(β : ℕ) (hβ : 0 < β) (w : ℕ) (hw : α * (w : ℝ) ^ 2 ≤ 1) :
KServer.BCRInductiveChunks α β hβ w := by sorrySource
Bubeck, Coester and Rabani, The Randomized k-Server Conjecture Is False!, arXiv:2211.05753v2, Section 4. https://arxiv.org/html/2211.05753v2, Lemma 12, base-case paragraph. Printed pp. 14–15 (base case on p. 15).