Base case of BCR Lemma 12 at the tight escape price
ProvedKServer.bcr_tight_baseLet be the level- member of the recursive Bubeck--Coester--Rabani space family, with marked points at distance , and let be the level invariant of KServer.BCRInductiveChunksTight: a chunk system on with sizes in , expected total at least , escape price , exactly chunks, constant initial information and no empty chunk.
Statement. For every , every integer and every level with
the invariant holds.
Why this is the easy half. When the demanded expected total is at most , so no randomness is needed: a deterministic single-file adversary suffices. Level of the family contains a unit geodesic chain with , and ; sampling it at the multiples of gives marked positions at spacing , and the singleton requests at those positions, one per chunk, form a chunk system of chunks of size . Each chunk forces the evader to advance one step of the chain, and bailing out is never cheaper because the escape price is at least the chunk size .
Relation to the existing base case. This is KServer.bcr_induction_base with the escape price lowered from to 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 , 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.
import Definitions.Def_KServer_bcr_induction_tight
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