Prove2Me
Navigate
MissionsFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The base case: a filtered chunk system on the path

Proved
KServer.chunk_system_f_base

by Shuze Chen · Sep 1, 2026 · Mathlib c5ea003 (Lean v4.30.0)

k-serverlower-boundsmetrical-service-systems

The base case of BCR's Lemma 6, in the filtered form: on the path of β+1\beta + 1β+1 equally spaced points (with s=0s = 0s=0, t=βt = \betat=β, so d(s,t)=βd(s,t) = \betad(s,t)=β), whenever αw2≤1\alpha w^2 \le 1αw2≤1 there is a deterministic filtered chunk system with m=βm = \betam=β chunks: after an initial pinning request {0}\{0\}{0}, the iii-th chunk is the single request {i}\{i\}{i}, of size 1∈[12,32]1 \in [\tfrac12, \tfrac32]1∈[21​,23​], with trivial filtration. The total size β\betaβ dominates αw2β\alpha w^2\betaαw2β, and m=β≥⌈αβw2⌉m = \beta \ge \lceil \alpha\beta w^2\rceilm=β≥⌈αβw2⌉; the conditional cost bound holds with escape price 2β2\beta2β because the previous singleton request pins the evader one step away.

This is the same statement as chunk_system_base transported to the filtered package KServer_chunk_system_f, which is the form consumed by the combining and subchunk steps of the induction.

Formalization note

The filtration is constant (hist ≡ 0): the system is deterministic.

Preamble
import Mathlib
import Definitions.Def_KServer_evader
import Definitions.Def_KServer_chunk_system
import Definitions.Def_KServer_chunk_system_f
Formal statement
namespace KServer

theorem chunk_system_f_base (β : ℕ) (hβ : 1 ≤ β) (α : ℝ) (hα0 : 0 ≤ α) (w : ℕ)
    (hw : α * (w : ℝ) ^ 2 ≤ 1) :
    letI := pathMetric β
    dist (0 : Fin (β + 1)) (Fin.last β) = β ∧
    Nonempty (ChunkSystemF (Fin (β + 1)) 0 (Fin.last β)
      (1 / 2) (3 / 2) (α * (w : ℝ) ^ 2 * β) (2 * β) ⌈α * β * (w : ℝ) ^ 2⌉₊) := by sorry

end KServer
Source
S. Bubeck, C. Coester, Y. Rabani, 'The randomized k-server conjecture is false!', STOC 2023, Lemma 6 (base case).

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.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me