The base case: a filtered chunk system on the path
ProvedKServer.chunk_system_f_basek-serverlower-boundsmetrical-service-systems
The base case of BCR's Lemma 6, in the filtered form: on the path of equally spaced points (with , , so ), whenever there is a deterministic filtered chunk system with chunks: after an initial pinning request , the -th chunk is the single request , of size , with trivial filtration. The total size dominates , and ; the conditional cost bound holds with escape price 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 KServerSource
S. Bubeck, C. Coester, Y. Rabani, 'The randomized k-server conjecture is false!', STOC 2023, Lemma 6 (base case).