Theorem B.1 — Unbounded makespan ratio for every real speed from 2 to 2.18
OpenChangingCache.UpperBound.Supplement.theorem_B_1cachingchanging-cachep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1resource-augmentation
For every real speed in the closed interval , LRU under augmentation has an unbounded makespan competitive ratio:
The witness is a legal positive growth-limited memory profile and a nonempty finite request sequence. LRU's capacity after misses is exactly , with an arbitrary real number. Both endpoints are included.
This companion theorem extends the speed-two lower bound. The O-estimates in Appendix B concern its proof, not the statement; no finite grid of tested speeds or illustrative value substitutes for its real interval.
Differences from the source:
- encoding: the printed decimal endpoint 2.18 → the exact real number 109/50; reason: 2.18 is exactly 109/50; no endpoint is changed and the speed variable remains real
- encoding: unbounded makespan competitive ratio → UnboundedMakespanRatio s with every positive real target and cross-multiplied strict inequality; reason: positive OPT counts make this equivalent to the makespan ratio, without a division-by-zero convention
- encoding: existential page identifiers → natural page identifiers without a finite universe bound; reason: pages can be renamed by order of first request, preserving every finite-run hit, miss and capacity
Preamble
import Mathlib import Definitions.Def_ChangingCache_UpperBound_Supplement_Streams
Formal statement
namespace ChangingCache.UpperBound.Supplement
/-- Theorem B.1, pp. 24–25: the printed endpoint 2.18 is exactly 109/50. -/
theorem theorem_B_1 (s : ℝ) (hlo : 2 ≤ s) (hhi : s ≤ 109 / 50) :
UnboundedMakespanRatio s := by sorry
end ChangingCache.UpperBound.Supplement
Source
Michael A. Bender, Daniel DeLayo, Pritom Kundu, Charlie McGuffey, Zofia Stefankovic, Zhonglue Wang, STOC 2027 submission #93 (October 2026), p. 24, Theorem B.1; proof pp. 24–25