Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 6.3 — First drop and exact negative bank

Open
ChangingCache.UpperBound.Supplement.lemma_6_3

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

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

Let mmm follow the Section 6 staircase through stage NNN, and let the integer drop height hhh satisfy

2bN+4≤h≤(KN+1+bN)/2.2b_N+4\le h\le (K_{N+1}+b_N)/2.2bN​+4≤h≤(KN+1​+bN​)/2.

Assume the profile has height hhh at entries TN+1,…,TN+⌈h/2⌉T_N+1,\ldots,T_N+\lceil h/2\rceilTN​+1,…,TN​+⌈h/2⌉. For any greedy tie rule, the first-drop construction retains the h−1h-1h−1 least recently requested old useful pages. At request

rf=rN+bN+h+1r_f=r_N+b_N+h+1rf​=rN​+bN​+h+1

it has

B2(rf)=2bN+3−h<0,∣U(rf)∣=h−1,U(rf)⊆PLRU(rf).B_2(r_f)=2b_N+3-h<0,\qquad |U(r_f)|=h-1,\qquad U(r_f)\subseteq P_{\mathrm{LRU}}(r_f).B2​(rf​)=2bN​+3−h<0,∣U(rf​)∣=h−1,U(rf​)⊆PLRU​(rf​).

The constructed policy is legal, all its misses are cold, and all requests miss in LRU. Entries beyond the stated plateau are unrestricted, subject to being a legal memory profile.

This first-drop lemma supplies the exact negative bank and useful-page configuration needed by the second drop.

Differences from the source:

  • encoding: the Section 6 greedy adversary and its useful-page policy → the recursive greedyRun and greedyPolicy with an arbitrary valid finite-set picker and request-position names for fresh pages; reason: this implements every greedy tie choice; renaming fresh pages changes no cache event
  • encoding: useful pages immediately after a request, with discards at the next miss → greedyRun.useful before advance discards, and greedyPolicy after discards before the next request; temporary non-useful incoming pages are discarded immediately; reason: the temporary page is in LRU and is never selected again; earlier voluntary discards preserve all hits, misses and capacity checks in the published snapshot convention
  • encoding: integer heights, signed banks, one-based request names and profile entries starting at zero → signed integer stage arithmetic followed by natural indices, lists indexed from zero and a real-valued bank; reason: positive source lengths and request positions make the conversions exact; no negative bank is truncated
  • encoding: the constructed legal OPT policy has only cold misses and every request misses in LRU → IsLegal, AllMissesCold and LRUAlwaysMisses are explicit conclusions about the constructed histories; reason: OPT and the Section 6 run conventions are certified rather than assumed as invariant hypotheses
  • encoding: h ≤ (K_{N+1}+b_N)/2 with integer h → 2*h ≤ K_{N+1}+b_N in integer arithmetic; reason: cross multiplication by positive two preserves the entire interval, including both endpoints
Preamble
import Mathlib
import Definitions.Def_ChangingCache_UpperBound_Supplement_Adversary
Formal statement
namespace ChangingCache.UpperBound.Supplement

/-- Lemma 6.3, pp. 19–20. Later unread entries of the profile remain unrestricted. -/
theorem lemma_6_3 (m : ℕ → ℕ) (pick : Finset ℕ → ℕ) (N : ℕ) (h : ℤ)
    (hm : IsMemoryProfile m) (hpick : IsPicker pick) (hstairs : StaircaseThrough m N)
    (hlo : 2 * stageB N + 4 ≤ h) (hhi : 2 * h ≤ stageK (N + 1) + stageB N)
    (hplateau : ∀ j : ℕ, stageT N < (j : ℤ) →
      (j : ℤ) ≤ stageT N + halfCeil h → (m j : ℤ) = h) :
    let rf := (stageRequest N + stageB N + h + 1).toNat
    let st := greedyRun m pick rf
    let σ := st.history
    let S := greedyPolicy m pick
    IsLegal m σ S ∧ AllMissesCold σ S ∧ LRUAlwaysMisses (augCap 2 2 m) σ ∧
    bank 2 m σ S rf = ((2 * stageB N + 3 - h : ℤ) : ℝ) ∧
    bank 2 m σ S rf < 0 ∧
    (st.useful.length : ℤ) = h - 1 ∧
    st.useful.toFinset ⊆ (lruRun (augCap 2 2 m) σ).cache.toFinset := 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. 19, Lemma 6.3; proof pp. 19–20

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