Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Infinite prefixes, real-speed banks and unbounded makespan ratios

Definition
ChangingCache_UpperBound_Supplement_Streams

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

cachingchanging-cachep2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1resource-augmentation

For an infinite request stream σ:N→P\sigma:\mathbb N\to Pσ:N→P, let σ<r\sigma_{<r}σ<r​ be its first rrr requests. A single family SrS_rSr​ of cache snapshots is legal on the stream if it is legal, in the published finite-cache model, on every prefix, with the same snapshots throughout.

For real speed sss, profile mmm, and a designated policy SSS, the bank is

Bs(r)=sFS(r)−FLRU(r).B_s(r)=sF_S(r)-F_{\mathrm{LRU}}(r).Bs​(r)=sFS​(r)−FLRU​(r).

The predicate for an unbounded makespan ratio means

∀R>0  ∃m,σ:FOPT(σ)>0,FLRU(σ)>R s FOPT(σ).\forall R>0\;\exists m,\sigma:\quad F_{\mathrm{OPT}}(\sigma)>0,\qquad F_{\mathrm{LRU}}(\sigma)>R\,s\,F_{\mathrm{OPT}}(\sigma).∀R>0∃m,σ:FOPT​(σ)>0,FLRU​(σ)>RsFOPT​(σ).

Here mmm is a positive growth-limited memory profile and σ\sigmaσ is a nonempty finite list. LRU has memory factor two and the published capacity 2m(⌊k/s⌋)2m(\lfloor k/s\rfloor)2m(⌊k/s⌋) after kkk misses. Natural page names permit arbitrarily many distinct pages. The ratio condition uses multiplication, so it does not depend on a convention for division by zero.

These definitions extend the published finite model and supply the common language of the two lower bounds; they impose no new restriction on a policy or profile.

Definition code
import Mathlib
import Definitions.Def_ChangingCache_UpperBound_NormalForm

namespace ChangingCache.UpperBound.Supplement

/-- The first `r` requests of one infinite stream; includes the empty prefix. -/
def streamPrefix {α : Type*} (σ : ℕ → α) (r : ℕ) : List α :=
  (List.range r).map σ

/-- One policy, with the same snapshots on every finite prefix. -/
def IsStreamLegal {α : Type*} [DecidableEq α] (m : ℕ → ℕ)
    (σ : ℕ → α) (S : ℕ → Finset α) : Prop :=
  ∀ r, IsLegal m (streamPrefix σ r) S

/-- Definition 3.2 (= Definition 6.1), with real speed and signed real subtraction. -/
noncomputable def bank {α : Type*} [DecidableEq α] (s : ℝ) (m : ℕ → ℕ)
    (σ : List α) (S : ℕ → Finset α) (r : ℕ) : ℝ :=
  s * (policyMisses σ S r : ℝ) - (lruMissCount (augCap 2 s m) σ r : ℝ)

/-- Unbounded multiplicative makespan ratio, not an additive gap. Natural page names impose
no finite bound on the universe. OPT's denominator is strictly positive. -/
def UnboundedMakespanRatio (s : ℝ) : Prop :=
  ∀ R : ℝ, 0 < R → ∃ (m : ℕ → ℕ) (σ : List ℕ),
    IsMemoryProfile m ∧ σ ≠ [] ∧ 0 < optMisses m σ ∧
    R * s * (optMisses m σ : ℝ) < ((lruRun (augCap 2 s m) σ).misses : ℝ)

end ChangingCache.UpperBound.Supplement
Source
Michael A. Bender, Daniel DeLayo, Pritom Kundu, Charlie McGuffey, Zofia Stefankovic, Zhonglue Wang, STOC 2027 submission #93 (October 2026), pp. 2, 7 (Definition 3.2), 16–17 (Definition 6.1), 24 (Theorem B.1)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me