BCR Lemma 15: regrouping tame subchunks into the next level
ProvedKServer.bcr_lemma15_regroup_levels_tameIn Bubeck-Coester-Rabani's randomized lower bound the induction over levels alternates two steps. Claim 13 refines a level- chunk system into small subchunks on level , of maximal size , escape price and expected total , the extra being reserved to pay for the next step. Lemma 15 then regroups these subchunks into chunks of the size the induction hypothesis wants on level : sizes in , expected total , escape price , and at least chunks.
Theorem. For , an integer and a level with : if a tame subchunk system on level exists - one whose conditional expected remaining size is branchwise slowly-decreasing and surprise-bounded with parameter - then the level- induction hypothesis holds.
The regrouping cuts the subchunk sequence at the stopping times at which the conditional expected remaining size first drops below with , so the resulting window is exactly the required ; the reserved surplus is exactly what makes super-chunks affordable; and the price increase fits inside precisely because .
Formalization note. Tameness is a hypothesis here rather than a consequence of Claim 13 as currently formalized: the abstract statement that a subchunk system with the stated parameters exists does not by itself record how its conditional remaining mass behaves along individual branches, whereas the regrouping is a branchwise stopping-time argument. Closing the gap means strengthening the output of Claim 13 to a tame system.
import Mathlib import Definitions.Def_KServer_bcr_induction import Definitions.Def_KServer_bcr_subchunks_tame
theorem KServer.bcr_lemma15_regroup_levels_tame (α : ℝ) (hα : 0 < α) (β : ℕ) (hβ : 0 < β)
(hβ2 : 2 ≤ β) (w : ℕ) (hw : 1 < α * ((w + 1 : ℕ) : ℝ) ^ 2)
(h : KServer.BCRInductiveSubchunksTame α β hβ w) :
KServer.BCRInductiveChunks α β hβ (w + 1) := by sorry