Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem A.1 — Factor two after every prefix on non-decreasing profiles

Open
ChangingCache.UpperBound.Supplement.theorem_A_1

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

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

Let mmm be any positive growth-limited memory profile satisfying m(j)≤m(j+1)m(j)\le m(j+1)m(j)≤m(j+1) for every natural jjj, and let σ\sigmaσ be any finite request sequence. Under (2,2)(2,2)(2,2) augmentation, starting with empty caches, after every prefix of length 0≤r≤∣σ∣0\le r\le |\sigma|0≤r≤∣σ∣,

FLRU(σ<r)≤2FOPT(σ<r).F_{\mathrm{LRU}}(\sigma_{<r})\le 2F_{\mathrm{OPT}}(\sigma_{<r}).FLRU​(σ<r​)≤2FOPT​(σ<r​).

The optimum on the right is computed for that same prefix and profile. Pages may belong to any type with decidable equality. There is no initial-capacity-one, normal-form, greedy-request or bank-invariant hypothesis and no additive term.

This companion theorem isolates the upper bound for non-decreasing profiles; it is not a step in the proof of the published Theorem 1.1 goal.

Differences from the source:

  • encoding: every prefix of a finite request sequence → every natural r ≤ σ.length, with σ.take r for the prefix optimum and the published prefix LRU count; reason: zero-based lists include the empty prefix and leave all finite sequences and all allowed initial capacities arbitrary
Preamble
import Mathlib
import Definitions.Def_ChangingCache_UpperBound_NormalForm
Formal statement
namespace ChangingCache.UpperBound.Supplement

/-- Theorem A.1, pp. 23–24: every prefix, with no normalization or initial-capacity restriction. -/
theorem theorem_A_1 {α : Type*} [DecidableEq α] (m : ℕ → ℕ) (σ : List α)
    (hm : IsMemoryProfile m) (hmono : ∀ j, m j ≤ m (j + 1)) :
    ∀ r ≤ σ.length, lruMissCount (augCap 2 2 m) σ r ≤ 2 * optMisses m (σ.take r) := 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. 23, Theorem A.1; proof pp. 23–24

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