rank_potential_offline_fetch_bound
At an offline fetch, the increase in rank potential is at most k (Lemma 3.3(i)).
Statement
theorem rank_potential_offline_fetch_bound {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (p_in p_out : α) : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) - (rank_potential q cOpt : ℤ) ≤ (k : ℤ)
- Formalizes
- arXiv:2610.18767 Lemma 3.3(i)
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
Read back from the Lean
For any type α with decidable equality, any natural number k, any FIFO queue q over α of length k (consisting of a duplicate-free list of pages of length k), any finite set cOpt of elements of α, and any elements p_in, p_out : α: the integer difference between the rank potential of q with respect to the set obtained by erasing p_out from cOpt and inserting p_in (i.e., insert p_in (cOpt.erase p_out)) and the rank potential of q with respect to cOpt is at most k.
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 proof establishes that an offline cache fetch increases the rank potential Φ(q, cOpt) = ∑_{x ∈ q \ cOpt} fifo_rank(q, x) by at most k. An auxiliary lemma first shows that evicting p_out and inserting p_in can only add p_out to the set of queue pages missing from the cache, so the potential increases by at most fifo_rank(q, p_out). Since the queue contains k pages, the FIFO rank of any page is at most k, and casting this bound to ℤ yields the result.
The set of queue pages not in the updated cache (cOpt \ {p_out}) ∪ {p_in} is a subset of {p_out} ∪ (q.pages \ cOpt).
We unfold the definition of `rank_potential`. To show the subset relation, we take an arbitrary page x and simplify the membership conditions for set difference, insertion, and erasure using `Finset.mem_sdiff`, `Finset.mem_insert`, and `Finset.mem_erase`. The remaining propositional logic is verified by `tauto`.
uses
Finset.mem_sdiff,Finset.mem_insert,Finset.mem_eraseunfold rank_potential have hsub : q.pages.toFinset \ insert p_in (cOpt.erase p_out) ⊆ insert p_out (q.pages.toFinset \ cOpt) := by intro x hx simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] at hx ⊢ tauto
The rank potential after updating the cache is at most the original potential plus the FIFO rank of p_out.
Using `Finset.sum_le_sum_of_subset_of_nonneg` with the subset inclusion from the previous step and the fact that FIFO ranks are non-negative (`Nat.zero_le`), we bound the sum over the new difference by the sum over insert p_out (q.pages \ cOpt) using `le_trans`. We then split into cases on whether p_out ∈ q.pages \ cOpt: if it is, the insertion does not change the set (`Finset.insert_eq_of_mem`), and the bound follows by `Nat.le_add_right`; if it is not, `Finset.sum_insert` extracts the term `fifo_rank q p_out`, and the two sides match (`omega`).
uses
le_trans,Finset.sum_le_sum_of_subset_of_nonneg,Nat.zero_le,Finset.insert_eq_of_mem,Nat.le_add_right,Finset.sum_insertrefine le_trans (Finset.sum_le_sum_of_subset_of_nonneg hsub (fun i _ _ => Nat.zero_le _)) ?_ by_cases h : p_out ∈ q.pages.toFinset \ cOpt · rw [Finset.insert_eq_of_mem h] exact Nat.le_add_right _ _ · rw [Finset.sum_insert h] omega
The new potential is bounded by the current potential plus the FIFO rank of p_out.
We apply the auxiliary lemma `rank_potential_offline_fetch_bound_aux` directly to q, cOpt, p_in, and p_out.
uses
rank_potential_offline_fetch_bound_auxhave h1 := rank_potential_offline_fetch_bound_aux q cOpt p_in p_outThe FIFO rank of any page p_out in the queue q is at most k.
We unfold `fifo_rank` and split on whether p_out is in q.pages. If p_out ∈ q.pages, its index is strictly less than q.pages.length by `List.idxOf_lt_length_iff.mpr`; since q.pages has length k (from q.length_eq), the 1-based rank idxOf + 1 is at most k (verified by `omega`). If p_out ∉ q.pages, the rank is 0, which is at most k by `Nat.zero_le`.
uses
List.idxOf_lt_length_iff.mpr,Nat.zero_lehave h2 : fifo_rank q p_out ≤ k := by unfold fifo_rank split next h => have h1 := List.idxOf_lt_length_iff.mpr h have h2 := q.length_eq omega next h => exact Nat.zero_le _
The updated potential is at most the original potential plus k in the natural numbers.
Linear arithmetic (`omega`) combines the auxiliary bound (increase at most fifo_rank q p_out) with the bound that fifo_rank q p_out ≤ k.
have h3 : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt + k := by omega
In the integers, the increase in rank potential is at most k.
We cast the natural inequality to ℤ using `Nat.cast_le`, push the integer cast over the addition using `push_cast`, and use linear arithmetic (`linarith`) to rearrange the terms into the final form (rank_potential_new : ℤ) - (rank_potential_old : ℤ) ≤ k.
uses
Nat.cast_lehave h4 : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) ≤ (rank_potential q cOpt : ℤ) + (k : ℤ) := by have := Nat.cast_le (α := ℤ).mpr h3 push_cast at this linarith linarith
Finset.mem_sdiff- An element belongs to a set difference 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.
Finset.mem_erase- An element belongs to s.erase b if and only if it is not equal to b and belongs to s.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and the summands are non-negative on t \ s, then the sum over s is at most the sum over t.
Nat.zero_le- Every natural number is greater than or equal to zero.
Finset.insert_eq_of_mem- Inserting an element that is already in a finite set leaves the set unchanged.
Nat.le_add_right- Any natural number n is less than or equal to n + k.
Finset.sum_insert- If an element is not in a finite set s, the sum over insert a s equals the value at a plus the sum over s.
rank_potential_offline_fetch_bound_aux- The rank potential after an offline cache modification (evicting p_out and inserting p_in) is at most the original potential plus the FIFO rank of p_out.
List.idxOf_lt_length_iff.mpr- If an element is present in a list, its first index of occurrence is strictly less than the list's length.
Nat.cast_le- For natural numbers m and n, their casts to an ordered ring satisfy ↑m ≤ ↑n if and only if m ≤ n.
- The potential function `rank_potential` takes values in ℕ; the theorem statement casts these potentials to ℤ before subtracting to prevent saturating (truncated) natural subtraction.
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.
lemma rank_potential_offline_fetch_bound_aux {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (p_in p_out : α) : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt + fifo_rank q p_out := by unfold rank_potential have hsub : q.pages.toFinset \ insert p_in (cOpt.erase p_out) ⊆ insert p_out (q.pages.toFinset \ cOpt) := by intro x hx simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase] at hx ⊢ tauto refine le_trans (Finset.sum_le_sum_of_subset_of_nonneg hsub (fun i _ _ => Nat.zero_le _)) ?_ by_cases h : p_out ∈ q.pages.toFinset \ cOpt · rw [Finset.insert_eq_of_mem h] exact Nat.le_add_right _ _ · rw [Finset.sum_insert h] omega/-- Potential increase at an offline fetch is at most k. -/theorem rank_potential_offline_fetch_bound {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (p_in p_out : α) : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) - (rank_potential q cOpt : ℤ) ≤ (k : ℤ) := by have h1 := rank_potential_offline_fetch_bound_aux q cOpt p_in p_out have h2 : fifo_rank q p_out ≤ k := by unfold fifo_rank split next h => have h1 := List.idxOf_lt_length_iff.mpr h have h2 := q.length_eq omega next h => exact Nat.zero_le _ have h3 : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt + k := by omega have h4 : (rank_potential q (insert p_in (cOpt.erase p_out)) : ℤ) ≤ (rank_potential q cOpt : ℤ) + (k : ℤ) := by have := Nat.cast_le (α := ℤ).mpr h3 push_cast at this linarith linarith