rank_potential_offline_evict_hole_bound
At an offline fetch, if the evicted page is outside the online cache, the change in rank potential is at most 0 (Lemma 3.3(ii)).
Statement
theorem rank_potential_offline_evict_hole_bound {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (p_in p_out : α) (h_out : p_out ∉ q.pages) : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) - (rank_potential q cOpt : ℤ) ≤ 0
- Formalizes
- arXiv:2610.18767 Lemma 3.3(ii)
- 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
For any type α with decidable equality, any natural number k, any FIFO queue q : FifoQueue α k, any finite set cOpt : Finset α, and any elements p_in, p_out : α, if p_out is not in q.pages, then the difference between the rank potential of q with respect to the cache insert p_in (cOpt.erase p_out) and the rank potential of q with respect to cOpt (both cast to ℤ) is less than or equal to 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 of a FIFO queue with respect to an offline cache is defined as the sum of ranks of all online pages currently missing from that cache. When the offline algorithm evicts a page p_out that is not in the online queue (a 'hole') and fetches a page p_in, no page in the online queue is removed from the offline cache. Consequently, the set of online pages missing from the offline cache can only shrink, and since ranks are non-negative, the rank potential cannot increase.
The set of online pages missing from the updated offline cache is a subset of those missing from the original offline cache: q.pages.toFinset \ insert p_in (cOpt.erase p_out) ⊆ q.pages.toFinset \ cOpt.
To show this inclusion, take any page x in the difference. By definition of set difference (Finset.mem_sdiff), x is in the online queue (q.pages) and x is not in the updated offline cache insert p_in (cOpt.erase p_out). To show x ∉ cOpt, assume for contradiction that x ∈ cOpt. Because x is not in the updated cache, it is not equal to p_in and not in cOpt.erase p_out (by Finset.mem_insert and not_or). Furthermore, because x ∉ cOpt.erase p_out, any element of cOpt other than p_out is ruled out (by Finset.mem_erase and not_and), which forces x = p_out. But x ∈ q.pages (via List.mem_toFinset.mp), which would imply p_out ∈ q.pages, directly contradicting the hypothesis h_out that p_out is not in the queue. Thus x ∉ cOpt, establishing the subset inclusion.
uses
Finset.mem_sdiff,Finset.mem_insert,not_or,Finset.mem_erase,not_and,List.mem_toFinset.mphave h_sub : q.pages.toFinset \ insert p_in (cOpt.erase p_out) ⊆ q.pages.toFinset \ cOpt := by intro x hx rw [Finset.mem_sdiff] at hx ⊢ refine ⟨hx.1, ?_⟩ intro h_cOpt have h_not_in : x ∉ insert p_in (cOpt.erase p_out) := hx.2 rw [Finset.mem_insert, not_or] at h_not_in have h_not_erase : x ∉ cOpt.erase p_out := h_not_in.2 rw [Finset.mem_erase, not_and] at h_not_erase have h_x_eq : x = p_out := by by_contra h_ne exact h_not_erase h_ne h_cOpt have h_x_in : x ∈ q.pages := List.mem_toFinset.mp hx.1 rw [h_x_eq] at h_x_in exact h_out h_x_in
The rank potential under the updated offline cache is at most the rank potential under the original offline cache: rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt.
By definition, rank_potential q c is the sum of fifo_rank q x over all pages x in the online queue that are missing from the offline cache c. Since each fifo_rank is a non-negative integer and the set of missing pages for the new cache is a subset of the missing pages for the old cache, the sum can only decrease or stay the same (Finset.sum_le_sum_of_subset).
uses
Finset.sum_le_sum_of_subsethave h_le : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt := by unfold rank_potential exact Finset.sum_le_sum_of_subset h_sub
The change in rank potential, as an integer difference, is at most 0: (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) - (rank_potential q cOpt : ℤ) ≤ 0.
Linear integer arithmetic (omega) deduces that the difference of the integer casts is at most 0 from the inequality between natural numbers established in the previous step.
omega
Finset.mem_sdiff- An element belongs to the difference of two finite sets s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
not_or- The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
Finset.mem_erase- An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
not_and- The negation of a conjunction ¬(a ∧ b) is equivalent to the implication a → ¬b.
List.mem_toFinset.mp- If an element belongs to the finite set formed from a list, it belongs to the list.
Finset.sum_le_sum_of_subset- For a function taking values in a canonically ordered additive monoid (such as ℕ), the sum over a subset is at most the sum over the superset.
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.
/-- Potential change is at most 0 when offline evicts a hole of online cache. -/theorem rank_potential_offline_evict_hole_bound {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (p_in p_out : α) (h_out : p_out ∉ q.pages) : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) - (rank_potential q cOpt : ℤ) ≤ 0 := by have h_sub : q.pages.toFinset \ insert p_in (cOpt.erase p_out) ⊆ q.pages.toFinset \ cOpt := by intro x hx rw [Finset.mem_sdiff] at hx ⊢ refine ⟨hx.1, ?_⟩ intro h_cOpt have h_not_in : x ∉ insert p_in (cOpt.erase p_out) := hx.2 rw [Finset.mem_insert, not_or] at h_not_in have h_not_erase : x ∉ cOpt.erase p_out := h_not_in.2 rw [Finset.mem_erase, not_and] at h_not_erase have h_x_eq : x = p_out := by by_contra h_ne exact h_not_erase h_ne h_cOpt have h_x_in : x ∈ q.pages := List.mem_toFinset.mp hx.1 rw [h_x_eq] at h_x_in exact h_out h_x_in have h_le : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt := by unfold rank_potential exact Finset.sum_le_sum_of_subset h_sub omega