rank_potential_zero_of_subset
If all pages in the online FIFO cache are present in the offline cache, the rank potential Φ is zero; in particular, the initial potential Φ₀ = 0.
Statement
theorem rank_potential_zero_of_subset {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (h : q.pages.toFinset ⊆ cOpt) : rank_potential q cOpt = 0
- Source
- arXiv:2610.18767 Section 3.2, line 414
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- FifoQueueA first-in first-out (FIFO) cache queue of capacity k over page type α, represented as a duplicate-free list of length k.
- fifo_rankThe rank of a page in a FIFO queue of size k, ranging from 1 for the oldest page (next to be evicted) to k for the most recently fetched…
- rank_potentialThe rank potential function Φ for FIFO paging, defined as the sum of ranks of all pages currently in the online FIFO cache but absent from…
Read back from the Lean
Let α be a type with decidable equality and let k be a natural number. Let q be a FifoQueue α k (a structure with a duplicate-free list q.pages of length k) and let cOpt be a finite set of elements of α. If the set of elements in q.pages is a subset of cOpt (q.pages.toFinset ⊆ cOpt), then rank_potential q cOpt = 0.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The rank potential Φ(q, cOpt) is defined as the sum of the FIFO ranks of all pages in the online queue q that are not present in the offline cache cOpt. By assumption, the pages of the online queue form a subset of the offline cache, so this set difference is empty. Consequently, the sum is taken over the empty set and evaluates to zero.
By definition, the rank potential is the sum of FIFO ranks over pages in the online cache not present in the offline cache: ∑ x ∈ q.pages.toFinset \ cOpt, fifo_rank q x = 0.
Unfolding the definition of rank_potential expands the goal into showing that the sum of fifo_rank q x over the set difference q.pages.toFinset \ cOpt equals zero.
unfold rank_potentialThe set difference is empty, so the sum evaluates to 0.
Because the online cache is a subset of the offline cache (q.pages.toFinset ⊆ cOpt by hypothesis h), the set difference q.pages.toFinset \ cOpt is empty by Finset.sdiff_eq_empty_iff_subset.mpr. Rewriting with this fact and Finset.sum_empty shows that the sum over the empty set is 0.
uses
Finset.sdiff_eq_empty_iff_subset.mpr,Finset.sum_emptyrw [Finset.sdiff_eq_empty_iff_subset.mpr h, Finset.sum_empty]
Finset.sdiff_eq_empty_iff_subset.mpr- If a finite set s is a subset of t, then their set difference s \ t is empty.
Finset.sum_empty- The sum of any function over the empty finite set is 0.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Rank potential is zero when online cache is a subset of offline cache. -/theorem rank_potential_zero_of_subset {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (h : q.pages.toFinset ⊆ cOpt) : rank_potential q cOpt = 0 := by unfold rank_potential rw [Finset.sdiff_eq_empty_iff_subset.mpr h, Finset.sum_empty]