One level of BCR Lemma 12 at the tight escape price
OpenKServer.bcr_tight_stepLet be the level invariant of KServer.BCRInductiveChunksTight: on the level- space of the recursive Bubeck--Coester--Rabani family, a chunk system between the marked points (at distance ) with sizes in , expected total at least , escape price , exactly chunks, constant initial information and no empty chunk.
Statement. There are constants and an integer , chosen once and for all, such that for every level with ,
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- 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 to while the distance triples, so the race has to contribute chunk masses beyond the three copies supplied by stages 1, 2b and 3; this is what forces 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 . The exact chunk count and the nonemptiness of the chunks are carried by the invariant. And, decisively, the escape price is rather than , 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 is reachable.
What remains for a prover. The choice of the parameter schedule: the number of coin steps , the tie-break scale , 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.
import Definitions.Def_KServer_bcr_induction_tight
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