rank_potential_online_payment_bound
For any type α with decidable equality, any k ≥ 1, any FIFO queue q of capacity k, any offline cache cOpt of cardinality k, and any page v ∉ q.pages: if v ∈ cOpt then the integer change in rank potential after fetching v, (rank_potential (fifo_fetch hk q v hv) cOpt : ℤ) - (rank_potential q cOpt : ℤ), is at most -1; and unconditionally, this rank potential change is at most k.
Statement
theorem rank_potential_online_payment_bound {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (cOpt : Finset α) (v : α) (hv : v ∉ q.pages) (hc : cOpt.card = k) : ((v ∈ cOpt → (rank_potential (fifo_fetch hk q v hv) cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ -1) ∧ ((rank_potential (fifo_fetch hk q v hv) cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ (k : ℤ)))
- Formalizes
- arXiv:2610.18767 Lemma 3.3(iii)
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- fifo_fetchUpdating a FIFO queue of size k ≥ 1 upon fetching a new page v: the oldest page (front of the queue) is evicted and v is appended to the…
Read back from the Lean
For any type α with decidable equality, any natural number k such that 1 ≤ k, any FIFO queue q over α of size k (consisting of a duplicate-free list q.pages of length k), any finite set cOpt : Finset α of cardinality k, and any element v : α not in q.pages:
Let q' be the updated queue fifo_fetch hk q v hv obtained by removing the head of q.pages and appending v to the tail.
Then both of the following hold:
1. If v ∈ cOpt, then the integer difference between the rank potential of q' with respect to cOpt and the rank potential of q with respect to cOpt is at most -1:
(rank_potential q' cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ -1.
2. The integer difference between the rank potential of q' with respect to cOpt and the rank potential of q with respect to cOpt is at most k:
(rank_potential q' cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ 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 bounds the change in rank potential ΔΦ after fetching a missing page v into a FIFO queue q of capacity k. First, helper lemmas establish that fetching v evicts the head and shifts all other pages, decreasing each existing page's rank by 1 while assigning the newly fetched page rank k. By embedding the page sets of q and the updated queue q' into the common universe S = {v} ∪ q.pages, the potential difference decomposes into a sum of individual rank changes over S \ cOpt. If v ∈ cOpt, the new page does not appear in S \ cOpt, yielding a potential decrease of at least 1 since q.pages and cOpt cannot coincide; if v ∉ cOpt, v contributes +k while existing pages contribute a non-positive sum, bounding the increase by k.
The queue's pages can be decomposed as head :: tail, and fetching v yields pages tail ++ [v], with tail.length + 1 = k and head ∉ tail.
Deconstruct q into its page list, length hypothesis hlen, and distinctness proof hnodup. Since k ≥ 1, the empty list case is ruled out by omega. In the non-empty case head :: tail, tail.length + 1 = k follows by simplifying the length, and head ∉ tail follows from List.nodup_cons.
uses
List.nodup_consrcases q with ⟨_ | ⟨head, tail⟩, hlen, hnodup⟩ · simp at hlen; omega · refine ⟨head, tail, rfl, rfl, ?_, ?_⟩ · simp at hlen; exact hlen · rw [List.nodup_cons] at hnodup; exact hnodup.1
The rank of the newly fetched page v in fifo_fetch hk q v hv is k.
Decompose the queue using rank_potential_online_payment_bound_fetch_pages_eq. The fetched page v appears at the end of tail ++ [v] (List.mem_append_right, List.mem_singleton), so fifo_rank evaluates using if_pos. Since v ∉ q.pages, v cannot belong to tail (List.mem_cons_of_mem). Hence its index in tail ++ [v] is tail.length + List.idxOf v [v] (List.idxOf_append_of_notMem), which equals tail.length (List.idxOf_cons_eq). Adding 1 gives tail.length + 1 = k by omega.
uses
rank_potential_online_payment_bound_fetch_pages_eq,List.mem_append_right,List.mem_singleton,if_pos,List.mem_cons_of_mem,List.idxOf_append_of_notMem,List.idxOf_cons_eqobtain ⟨head, tail, hq, hq', hlen, hhd⟩ := rank_potential_online_payment_bound_fetch_pages_eq hk q v hv unfold fifo_rank have hv_mem : v ∈ (fifo_fetch hk q v hv).pages := by rw [hq'] exact List.mem_append_right tail (List.mem_singleton.mpr rfl) rw [if_pos hv_mem] rw [hq'] have hv_not_tail : v ∉ tail := by intro h have : v ∈ q.pages := by rw [hq]; exact List.mem_cons_of_mem head h exact hv this rw [List.idxOf_append_of_notMem hv_not_tail] have : List.idxOf v [v] = 0 := List.idxOf_cons_eq [] rfl rw [this] omega
For any page x present in q, its rank in the updated queue is fifo_rank q x - 1.
Decompose q.pages into head :: tail via rank_potential_online_payment_bound_fetch_pages_eq. Any x ∈ q.pages is either head or in tail. If x = head, it is evicted and not in tail ++ [v] (List.mem_append, List.mem_singleton, not_or), giving rank 0 via if_neg, while its original rank was 1 (if_pos, List.idxOf_cons_eq). If x ∈ tail, it remains in tail ++ [v] (List.mem_append_left), distinct from head, and its 0-based index shifts from idxOf x tail + 1 in q (List.idxOf_cons_ne) to idxOf x tail in the fetched queue (List.idxOf_append_of_mem), so its rank decreases by 1 (omega).
uses
rank_potential_online_payment_bound_fetch_pages_eq,List.mem_append,List.mem_singleton,not_or,if_neg,if_pos,List.idxOf_cons_eq,List.mem_append_left,List.idxOf_cons_ne,List.idxOf_append_of_memobtain ⟨head, tail, hq, hq', hlen, hhd⟩ := rank_potential_online_payment_bound_fetch_pages_eq hk q v hv have hx_cases : x = head ∨ x ∈ tail := by rw [hq] at hx cases hx with | head => left; rfl | tail _ h => right; exact h rcases hx_cases with rfl | hx_tail · have h_not_in : x ∉ (fifo_fetch hk q v hv).pages := by rw [hq'] simp only [List.mem_append, List.mem_singleton, not_or] refine ⟨hhd, ?_⟩ rintro rfl exact hv hx unfold fifo_rank rw [if_neg h_not_in] rw [if_pos hx] rw [hq, List.idxOf_cons_eq tail rfl] · have h_in_q' : x ∈ (fifo_fetch hk q v hv).pages := by rw [hq'] exact List.mem_append_left [v] hx_tail have h_x_ne_hd : head ≠ x := by rintro rfl exact hhd hx_tail unfold fifo_rank rw [if_pos h_in_q', if_pos hx] rw [hq, List.idxOf_cons_ne tail h_x_ne_hd] rw [hq', List.idxOf_append_of_mem hx_tail] omega
For any page x ∈ q.pages, the integer change in rank (fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ) equals -1.
By rank_potential_online_payment_bound_fetch_old, fifo_rank q' x = fifo_rank q x - 1. Since x ∈ q.pages, fifo_rank q x ≥ 1 via if_pos. Linear arithmetic (omega) then shows that the difference in integers is exactly -1.
uses
rank_potential_online_payment_bound_fetch_old,if_poshave h_fetch := rank_potential_online_payment_bound_fetch_old hk q v hv x hx have h_pos : 1 ≤ fifo_rank q x := by unfold fifo_rank rw [if_pos hx] omega omega
Any page not present in a queue has rank 0.
Unfolding fifo_rank, since x ∉ q.pages, the if condition fails, and if_neg evaluates the rank to 0.
uses
if_negunfold fifo_rank rw [if_neg hx]
For any superset S ⊇ q.pages, rank_potential q cOpt equals ∑ x ∈ S \ cOpt, fifo_rank q x.
Unfold rank_potential. Since q.pages.toFinset ⊆ S, we have q.pages.toFinset \ cOpt ⊆ S \ cOpt by Finset.sdiff_subset_sdiff and subset_rfl. By Finset.sum_subset, it suffices to check that any x ∈ S \ cOpt outside q.pages.toFinset \ cOpt has rank 0. Indeed, such an x cannot belong to q.pages (Finset.mem_sdiff, List.mem_toFinset), so if_neg shows its rank is 0.
uses
Finset.sdiff_subset_sdiff,subset_rfl,Finset.sum_subset,Finset.mem_sdiff,List.mem_toFinset,if_negunfold rank_potential have h_sub : q.pages.toFinset \ cOpt ⊆ S \ cOpt := Finset.sdiff_subset_sdiff hS subset_rfl rw [← Finset.sum_subset h_sub] intro x hx hnot rw [Finset.mem_sdiff] at hx hnot have h_not_q : x ∉ q.pages.toFinset := by intro h exact hnot ⟨h, hx.2⟩ rw [List.mem_toFinset] at h_not_q unfold fifo_rank rw [if_neg h_not_q]
The pages of fifo_fetch hk q v hv are contained in insert v q.pages.toFinset.
Deconstruct q; the empty case is ruled out by omega. In the cons case head :: tail, the fetched queue has pages tail ++ [v]. Any page in this list (List.mem_toFinset) is either in tail (hence in head :: tail by List.mem_append and List.mem_cons_of_mem) or equals v (List.mem_singleton), so it belongs to insert v q.pages.toFinset (Finset.mem_insert).
uses
List.mem_toFinset,Finset.mem_insert,List.mem_append,List.mem_singleton,List.mem_cons_of_memrcases q with ⟨_ | ⟨head, tail⟩, hlen, hnodup⟩ · simp at hlen; omega · intro x hx simp only [List.mem_toFinset, Finset.mem_insert] at hx ⊢ have : (fifo_fetch hk ⟨head :: tail, hlen, hnodup⟩ v hv).pages = tail ++ [v] := rfl rw [this] at hx simp only [List.mem_append, List.mem_singleton] at hx rcases hx with hx_tail | rfl · right; exact List.mem_cons_of_mem head hx_tail · left; rfl
If cOpt has size k and contains v ∉ q.pages, then (q.pages.toFinset \ cOpt).card ≥ 1.
Since q.pages has length k and no duplicates, |q.pages.toFinset| = k by List.toFinset_card_of_nodup. By contradiction (by_contra), if |q.pages.toFinset \ cOpt| < 1, then the difference has size 0 (omega) and is empty, meaning q.pages.toFinset ⊆ cOpt (Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset). Since both sets have size k, they must be equal (Finset.eq_of_subset_of_card_le). But then v ∈ cOpt would imply v ∈ q.pages.toFinset (List.mem_toFinset), contradicting v ∉ q.pages.
uses
List.toFinset_card_of_nodup,Finset.card_eq_zero,Finset.sdiff_eq_empty_iff_subset,Finset.eq_of_subset_of_card_le,List.mem_toFinsethave hq_card : q.pages.toFinset.card = k := by rw [List.toFinset_card_of_nodup q.nodup, q.length_eq] by_contra h have h0 : (q.pages.toFinset \ cOpt).card = 0 := by omega rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at h0 have heq : q.pages.toFinset = cOpt := by apply Finset.eq_of_subset_of_card_le h0 omega have hv_in : v ∈ q.pages.toFinset := by rw [heq] exact hv_c rw [List.mem_toFinset] at hv_in exact hv hv_in
If x ∈ t, then (insert x s) \ t = s \ t.
By extensionality (ext), an element y belongs to (insert x s) \ t iff (y = x ∨ y ∈ s) ∧ y ∉ t (Finset.mem_sdiff, Finset.mem_insert). If y = x, then y ∉ t contradicts x ∈ t (False.elim). Thus y ∈ s ∧ y ∉ t, which means y ∈ s \ t (Or.inr).
uses
Finset.mem_sdiff,Finset.mem_insert,False.elim,Or.inrext y simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨rfl | hy, hyt⟩ · exact (hyt hx).elim · exact ⟨hy, hyt⟩ · rintro ⟨hy, hyt⟩ exact ⟨Or.inr hy, hyt⟩
If x ∉ t, then (insert x s) \ t = insert x (s \ t).
By extensionality (ext), y ∈ (insert x s) \ t iff (y = x ∨ y ∈ s) ∧ y ∉ t (Finset.mem_sdiff, Finset.mem_insert). Because x ∉ t, the condition y = x automatically satisfies y ∉ t, so this is equivalent to y = x ∨ (y ∈ s ∧ y ∉ t), which characterizes y ∈ insert x (s \ t) (Or.inl, Or.inr).
uses
Finset.mem_sdiff,Finset.mem_insert,Or.inl,Or.inrext y simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨rfl | hy, hyt⟩ · exact Or.inl rfl · exact Or.inr ⟨hy, hyt⟩ · rintro (rfl | ⟨hy, hyt⟩) · exact ⟨Or.inl rfl, hx⟩ · exact ⟨Or.inr hy, hyt⟩
Both rank_potential q cOpt and rank_potential q' cOpt can be expressed as sums of ranks over the common set S \ cOpt, where S = insert v q.pages.toFinset.
Let q' be the queue after fetching v, and let S be the union of q.pages with {v}. Both q.pages and q'.pages are subsets of S (by Finset.subset_insert and rank_potential_online_payment_bound_fetch_subset). Because any page outside a queue's pages has rank 0, rank_potential_online_payment_bound_eq_sum allows extending the sum defining the rank potential from each queue's own pages to the common superset S \ cOpt.
uses
Finset.subset_insert,rank_potential_online_payment_bound_fetch_subset,rank_potential_online_payment_bound_eq_sumset q' := fifo_fetch hk q v hv set S := insert v q.pages.toFinset have hS_q : q.pages.toFinset ⊆ S := Finset.subset_insert v q.pages.toFinset have hS_q' : q'.pages.toFinset ⊆ S := rank_potential_online_payment_bound_fetch_subset hk q v hv have h_sum_q : rank_potential q cOpt = ∑ x ∈ S \ cOpt, fifo_rank q x := rank_potential_online_payment_bound_eq_sum q cOpt S hS_q have h_sum_q' : rank_potential q' cOpt = ∑ x ∈ S \ cOpt, fifo_rank q' x := rank_potential_online_payment_bound_eq_sum q' cOpt S hS_q'
The change in rank potential equals the sum over S \ cOpt of the pointwise rank differences fifo_rank q' x - fifo_rank q x.
Subtracting the sum for q from the sum for q' and distributing the difference across the sum using Finset.sum_sub_distrib expresses the potential difference as a single sum over S \ cOpt of the pointwise differences in rank.
uses
Finset.sum_sub_distribhave h_diff : (rank_potential q' cOpt : ℤ) - (rank_potential q cOpt : ℤ) = ∑ x ∈ S \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) := by rw [h_sum_q, h_sum_q'] push_cast rw [← Finset.sum_sub_distrib]
The sum of rank differences over the old pages q.pages \ cOpt equals -|(q.pages.toFinset \ cOpt)|.
For each old page x in q.pages, its rank decreases by exactly 1 after fetching v (rank_potential_online_payment_bound_diff_old). Summing this constant value -1 over q.pages.toFinset \ cOpt via Finset.sum_congr, Finset.sum_const, and nsmul_eq_mul gives -|(q.pages.toFinset \ cOpt)|.
uses
Finset.mem_sdiff,List.mem_toFinset,rank_potential_online_payment_bound_diff_old,Finset.sum_congr,Finset.sum_const,nsmul_eq_mulhave h_q_term : ∀ x ∈ q.pages.toFinset \ cOpt, (fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ) = -1 := by intro x hx rw [Finset.mem_sdiff, List.mem_toFinset] at hx exact rank_potential_online_payment_bound_diff_old hk q v hv x hx.1 have h_sum_q_terms : ∑ x ∈ q.pages.toFinset \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) = - ((q.pages.toFinset \ cOpt).card : ℤ) := by have : ∑ x ∈ q.pages.toFinset \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) = ∑ x ∈ q.pages.toFinset \ cOpt, (-1 : ℤ) := Finset.sum_congr rfl h_q_term rw [this, Finset.sum_const, nsmul_eq_mul] ring
If v ∈ cOpt, the rank potential change is at most -1 and at most k.
When v ∈ cOpt, inserting v does not alter the set difference with cOpt (rank_potential_online_payment_bound_insert_sdiff_mem), so S \ cOpt is simply q.pages.toFinset \ cOpt, and the total potential difference is -|(q.pages.toFinset \ cOpt)|. Because cOpt has size k and contains v ∉ q.pages, the two size-k sets cannot be identical, so |q.pages.toFinset \ cOpt| ≥ 1 (rank_potential_online_payment_bound_card_sdiff_ge_one). Linear arithmetic (omega) then proves that -|(q.pages.toFinset \ cOpt)| is at most -1 and at most k.
uses
rank_potential_online_payment_bound_insert_sdiff_mem,rank_potential_online_payment_bound_card_sdiff_ge_oneby_cases hvc : v ∈ cOpt · have hS_sdiff : S \ cOpt = q.pages.toFinset \ cOpt := rank_potential_online_payment_bound_insert_sdiff_mem q.pages.toFinset cOpt v hvc rw [hS_sdiff, h_sum_q_terms] at h_diff have h_card_ge : 1 ≤ (q.pages.toFinset \ cOpt).card := rank_potential_online_payment_bound_card_sdiff_ge_one q cOpt v hv hc hvc constructor · intro _ omega · omega
If v ∉ cOpt, the rank potential change is at most k, and the implication holds vacuously.
When v ∉ cOpt, S \ cOpt equals {v} ∪ (q.pages.toFinset \ cOpt) (rank_potential_online_payment_bound_insert_sdiff_not_mem). Separating the v term using Finset.sum_insert, page v has rank k in q' (rank_potential_online_payment_bound_fetch_v) and rank 0 in q (rank_potential_online_payment_bound_rank_not_mem), contributing k - 0 = k, while the remaining terms sum to -|(q.pages.toFinset \ cOpt)|. The total difference is k - |(q.pages.toFinset \ cOpt)| ≤ k. The first goal holds vacuously because v ∈ cOpt is false, and linear arithmetic (omega) closes the second inequality.
uses
rank_potential_online_payment_bound_insert_sdiff_not_mem,Finset.mem_sdiff,List.mem_toFinset,Finset.sum_insert,rank_potential_online_payment_bound_fetch_v,rank_potential_online_payment_bound_rank_not_mem· have hS_sdiff : S \ cOpt = insert v (q.pages.toFinset \ cOpt) := rank_potential_online_payment_bound_insert_sdiff_not_mem q.pages.toFinset cOpt v hvc have hv_not_sdiff : v ∉ q.pages.toFinset \ cOpt := by intro h rw [Finset.mem_sdiff, List.mem_toFinset] at h exact hv h.1 rw [hS_sdiff, Finset.sum_insert hv_not_sdiff, h_sum_q_terms] at h_diff have hv_q' : fifo_rank q' v = k := rank_potential_online_payment_bound_fetch_v hk q v hv have hv_q : fifo_rank q v = 0 := rank_potential_online_payment_bound_rank_not_mem q v hv rw [hv_q', hv_q] at h_diff constructor · intro h exact (hvc h).elim · omega
List.nodup_cons- A list with prepended head has no duplicates iff the head is not in the tail and the tail has no duplicates.
rank_potential_online_payment_bound_fetch_pages_eq- A FIFO queue of capacity k ≥ 1 has pages head :: tail, and fetching a missing page v produces tail ++ [v] with tail.length + 1 = k and head ∉ tail.
List.mem_append_right- An element belonging to the second list belongs to the concatenation of two lists.
List.mem_singleton- An element belongs to a singleton list [b] if and only if it equals b.
if_pos- An if-then-else expression evaluates to its then branch when the condition is true.
List.mem_cons_of_mem- An element belonging to a list also belongs to any list formed by prepending a head.
List.idxOf_append_of_notMem- The index of an element in l₁ ++ l₂ is l₁.length + idxOf a l₂ if the element does not belong to l₁.
List.idxOf_cons_eq- The index of an element at the head of a list is 0.
List.mem_append- An element belongs to the concatenation of two lists if and only if it belongs to either list.
not_or- The negation of a disjunction ¬(p ∨ q) is equivalent to ¬p ∧ ¬q.
if_neg- An if-then-else expression evaluates to its else branch when the condition is false.
List.mem_append_left- An element belonging to the first list belongs to the concatenation of two lists.
List.idxOf_cons_ne- The index of an element in b :: l is the successor of its index in l when b is not equal to that element.
List.idxOf_append_of_mem- The index of an element in l₁ ++ l₂ equals its index in l₁ if it already belongs to l₁.
rank_potential_online_payment_bound_fetch_old- For any page x present in the queue, fetching a new page decreases the rank of x by 1.
Finset.sdiff_subset_sdiff- Set difference preserves inclusion: if s ⊆ t and v ⊆ u, then s \ u ⊆ t \ v.
subset_rfl- Every set is a subset of itself.
Finset.sum_subset- A sum over a subset equals the sum over the superset if the summand vanishes outside the subset.
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.
List.mem_toFinset- An element is in the finset of a list if and only if it belongs to the list.
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
List.toFinset_card_of_nodup- The cardinality of the finset of a duplicate-free list equals the length of the list.
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.sdiff_eq_empty_iff_subset- The set difference s \ t is empty if and only if s is a subset of t.
Finset.eq_of_subset_of_card_le- A subset of a finite set equals the set if its cardinality is at least that of the superset.
False.elim- From False, any proposition follows.
Or.inr- Proof of a disjunction from a proof of its right disjunct.
Or.inl- Proof of a disjunction from a proof of its left disjunct.
Finset.subset_insert- A finite set is a subset of the result of inserting any element into it.
rank_potential_online_payment_bound_fetch_subset- The set of pages in a queue after fetching a missing page v is contained in the original pages union {v}.
rank_potential_online_payment_bound_eq_sum- The rank potential of a queue with respect to cOpt can be computed by summing ranks over S \ cOpt for any superset S of the queue's pages.
Finset.sum_sub_distrib- The sum of a difference of functions equals the difference of the sums.
rank_potential_online_payment_bound_diff_old- For any page already present in the queue, its rank after fetching v minus its original rank equals -1 in ℤ.
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree on every element.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set times the constant.
nsmul_eq_mul- Scalar multiplication of an integer by a natural number equals ordinary multiplication by the integer cast of that number.
rank_potential_online_payment_bound_insert_sdiff_mem- Inserting an element into s that already belongs to t does not change the set difference s \ t.
rank_potential_online_payment_bound_card_sdiff_ge_one- If cOpt has size k and contains a page v not present in the k-page queue q, then q.pages \ cOpt has cardinality at least 1.
rank_potential_online_payment_bound_insert_sdiff_not_mem- Inserting an element not in t into s adds that element to the set difference s \ t.
Finset.sum_insert- Inserting a new element into a finite set pulls that element's term out of the sum.
rank_potential_online_payment_bound_fetch_v- A newly fetched page in a FIFO queue of capacity k has rank k.
rank_potential_online_payment_bound_rank_not_mem- Any page not present in a queue has rank 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.
lemma rank_potential_online_payment_bound_fetch_pages_eq {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : ∃ head tail, q.pages = head :: tail ∧ (fifo_fetch hk q v hv).pages = tail ++ [v] ∧ tail.length + 1 = k ∧ head ∉ tail := by rcases q with ⟨_ | ⟨head, tail⟩, hlen, hnodup⟩ · simp at hlen; omega · refine ⟨head, tail, rfl, rfl, ?_, ?_⟩ · simp at hlen; exact hlen · rw [List.nodup_cons] at hnodup; exact hnodup.1lemma rank_potential_online_payment_bound_fetch_v {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : fifo_rank (fifo_fetch hk q v hv) v = k := by obtain ⟨head, tail, hq, hq', hlen, hhd⟩ := rank_potential_online_payment_bound_fetch_pages_eq hk q v hv unfold fifo_rank have hv_mem : v ∈ (fifo_fetch hk q v hv).pages := by rw [hq'] exact List.mem_append_right tail (List.mem_singleton.mpr rfl) rw [if_pos hv_mem] rw [hq'] have hv_not_tail : v ∉ tail := by intro h have : v ∈ q.pages := by rw [hq]; exact List.mem_cons_of_mem head h exact hv this rw [List.idxOf_append_of_notMem hv_not_tail] have : List.idxOf v [v] = 0 := List.idxOf_cons_eq [] rfl rw [this] omegalemma rank_potential_online_payment_bound_fetch_old {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) (x : α) (hx : x ∈ q.pages) : fifo_rank (fifo_fetch hk q v hv) x = fifo_rank q x - 1 := by obtain ⟨head, tail, hq, hq', hlen, hhd⟩ := rank_potential_online_payment_bound_fetch_pages_eq hk q v hv have hx_cases : x = head ∨ x ∈ tail := by rw [hq] at hx cases hx with | head => left; rfl | tail _ h => right; exact h rcases hx_cases with rfl | hx_tail · have h_not_in : x ∉ (fifo_fetch hk q v hv).pages := by rw [hq'] simp only [List.mem_append, List.mem_singleton, not_or] refine ⟨hhd, ?_⟩ rintro rfl exact hv hx unfold fifo_rank rw [if_neg h_not_in] rw [if_pos hx] rw [hq, List.idxOf_cons_eq tail rfl] · have h_in_q' : x ∈ (fifo_fetch hk q v hv).pages := by rw [hq'] exact List.mem_append_left [v] hx_tail have h_x_ne_hd : head ≠ x := by rintro rfl exact hhd hx_tail unfold fifo_rank rw [if_pos h_in_q', if_pos hx] rw [hq, List.idxOf_cons_ne tail h_x_ne_hd] rw [hq', List.idxOf_append_of_mem hx_tail] omegalemma rank_potential_online_payment_bound_diff_old {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) (x : α) (hx : x ∈ q.pages) : (fifo_rank (fifo_fetch hk q v hv) x : ℤ) - (fifo_rank q x : ℤ) = -1 := by have h_fetch := rank_potential_online_payment_bound_fetch_old hk q v hv x hx have h_pos : 1 ≤ fifo_rank q x := by unfold fifo_rank rw [if_pos hx] omega omegalemma rank_potential_online_payment_bound_rank_not_mem {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (x : α) (hx : x ∉ q.pages) : fifo_rank q x = 0 := by unfold fifo_rank rw [if_neg hx]lemma rank_potential_online_payment_bound_eq_sum {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (S : Finset α) (hS : q.pages.toFinset ⊆ S) : rank_potential q cOpt = ∑ x ∈ S \ cOpt, fifo_rank q x := by unfold rank_potential have h_sub : q.pages.toFinset \ cOpt ⊆ S \ cOpt := Finset.sdiff_subset_sdiff hS subset_rfl rw [← Finset.sum_subset h_sub] intro x hx hnot rw [Finset.mem_sdiff] at hx hnot have h_not_q : x ∉ q.pages.toFinset := by intro h exact hnot ⟨h, hx.2⟩ rw [List.mem_toFinset] at h_not_q unfold fifo_rank rw [if_neg h_not_q]lemma rank_potential_online_payment_bound_fetch_subset {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (v : α) (hv : v ∉ q.pages) : (fifo_fetch hk q v hv).pages.toFinset ⊆ insert v q.pages.toFinset := by rcases q with ⟨_ | ⟨head, tail⟩, hlen, hnodup⟩ · simp at hlen; omega · intro x hx simp only [List.mem_toFinset, Finset.mem_insert] at hx ⊢ have : (fifo_fetch hk ⟨head :: tail, hlen, hnodup⟩ v hv).pages = tail ++ [v] := rfl rw [this] at hx simp only [List.mem_append, List.mem_singleton] at hx rcases hx with hx_tail | rfl · right; exact List.mem_cons_of_mem head hx_tail · left; rfllemma rank_potential_online_payment_bound_card_sdiff_ge_one {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (v : α) (hv : v ∉ q.pages) (hc : cOpt.card = k) (hv_c : v ∈ cOpt) : 1 ≤ (q.pages.toFinset \ cOpt).card := by have hq_card : q.pages.toFinset.card = k := by rw [List.toFinset_card_of_nodup q.nodup, q.length_eq] by_contra h have h0 : (q.pages.toFinset \ cOpt).card = 0 := by omega rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at h0 have heq : q.pages.toFinset = cOpt := by apply Finset.eq_of_subset_of_card_le h0 omega have hv_in : v ∈ q.pages.toFinset := by rw [heq] exact hv_c rw [List.mem_toFinset] at hv_in exact hv hv_inlemma rank_potential_online_payment_bound_insert_sdiff_mem {α : Type*} [DecidableEq α] (s t : Finset α) (x : α) (hx : x ∈ t) : insert x s \ t = s \ t := by ext y simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨rfl | hy, hyt⟩ · exact (hyt hx).elim · exact ⟨hy, hyt⟩ · rintro ⟨hy, hyt⟩ exact ⟨Or.inr hy, hyt⟩lemma rank_potential_online_payment_bound_insert_sdiff_not_mem {α : Type*} [DecidableEq α] (s t : Finset α) (x : α) (hx : x ∉ t) : insert x s \ t = insert x (s \ t) := by ext y simp only [Finset.mem_sdiff, Finset.mem_insert] constructor · rintro ⟨rfl | hy, hyt⟩ · exact Or.inl rfl · exact Or.inr ⟨hy, hyt⟩ · rintro (rfl | ⟨hy, hyt⟩) · exact ⟨Or.inl rfl, hx⟩ · exact ⟨Or.inr hy, hyt⟩/-- Potential change at an online payment: at most -1 if v in Opt, at most k always. -/theorem rank_potential_online_payment_bound {α : Type*} [DecidableEq α] {k : ℕ} (hk : 1 ≤ k) (q : FifoQueue α k) (cOpt : Finset α) (v : α) (hv : v ∉ q.pages) (hc : cOpt.card = k) : ((v ∈ cOpt → (rank_potential (fifo_fetch hk q v hv) cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ -1) ∧ ((rank_potential (fifo_fetch hk q v hv) cOpt : ℤ) - (rank_potential q cOpt : ℤ) ≤ (k : ℤ))) := by set q' := fifo_fetch hk q v hv set S := insert v q.pages.toFinset have hS_q : q.pages.toFinset ⊆ S := Finset.subset_insert v q.pages.toFinset have hS_q' : q'.pages.toFinset ⊆ S := rank_potential_online_payment_bound_fetch_subset hk q v hv have h_sum_q : rank_potential q cOpt = ∑ x ∈ S \ cOpt, fifo_rank q x := rank_potential_online_payment_bound_eq_sum q cOpt S hS_q have h_sum_q' : rank_potential q' cOpt = ∑ x ∈ S \ cOpt, fifo_rank q' x := rank_potential_online_payment_bound_eq_sum q' cOpt S hS_q' have h_diff : (rank_potential q' cOpt : ℤ) - (rank_potential q cOpt : ℤ) = ∑ x ∈ S \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) := by rw [h_sum_q, h_sum_q'] push_cast rw [← Finset.sum_sub_distrib] have h_q_term : ∀ x ∈ q.pages.toFinset \ cOpt, (fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ) = -1 := by intro x hx rw [Finset.mem_sdiff, List.mem_toFinset] at hx exact rank_potential_online_payment_bound_diff_old hk q v hv x hx.1 have h_sum_q_terms : ∑ x ∈ q.pages.toFinset \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) = - ((q.pages.toFinset \ cOpt).card : ℤ) := by have : ∑ x ∈ q.pages.toFinset \ cOpt, ((fifo_rank q' x : ℤ) - (fifo_rank q x : ℤ)) = ∑ x ∈ q.pages.toFinset \ cOpt, (-1 : ℤ) := Finset.sum_congr rfl h_q_term rw [this, Finset.sum_const, nsmul_eq_mul] ring by_cases hvc : v ∈ cOpt · have hS_sdiff : S \ cOpt = q.pages.toFinset \ cOpt := rank_potential_online_payment_bound_insert_sdiff_mem q.pages.toFinset cOpt v hvc rw [hS_sdiff, h_sum_q_terms] at h_diff have h_card_ge : 1 ≤ (q.pages.toFinset \ cOpt).card := rank_potential_online_payment_bound_card_sdiff_ge_one q cOpt v hv hc hvc constructor · intro _ omega · omega · have hS_sdiff : S \ cOpt = insert v (q.pages.toFinset \ cOpt) := rank_potential_online_payment_bound_insert_sdiff_not_mem q.pages.toFinset cOpt v hvc have hv_not_sdiff : v ∉ q.pages.toFinset \ cOpt := by intro h rw [Finset.mem_sdiff, List.mem_toFinset] at h exact hv h.1 rw [hS_sdiff, Finset.sum_insert hv_not_sdiff, h_sum_q_terms] at h_diff have hv_q' : fifo_rank q' v = k := rank_potential_online_payment_bound_fetch_v hk q v hv have hv_q : fifo_rank q v = 0 := rank_potential_online_payment_bound_rank_not_mem q v hv rw [hv_q', hv_q] at h_diff constructor · intro h exact (hvc h).elim · omega