AFTD Auto-Formalizing Theoretical Domains

rank_potential_online_payment_bound

theoremverifiedformalization

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.

  1. 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.

    lines 3–7

    uses List.nodup_cons

      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.1
  2. 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.

    lines 11–25

    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_eq

      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]
      omega
  3. 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).

    lines 30–57

    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_mem

      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]
        omega
  4. 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.

    lines 62–67

    uses rank_potential_online_payment_bound_fetch_old, if_pos

      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
      omega
  5. 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.

    lines 71–72

    uses if_neg

      unfold fifo_rank
      rw [if_neg hx]
  6. 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.

    lines 77–87

    uses Finset.sdiff_subset_sdiff, subset_rfl, Finset.sum_subset, Finset.mem_sdiff, List.mem_toFinset, if_neg

      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]
  7. 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).

    lines 91–100

    uses List.mem_toFinset, Finset.mem_insert, List.mem_append, List.mem_singleton, List.mem_cons_of_mem

      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; rfl
  8. 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.

    lines 105–117

    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_toFinset

      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_in
  9. 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).

    lines 121–128

    uses Finset.mem_sdiff, Finset.mem_insert, False.elim, Or.inr

      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⟩
  10. 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).

    lines 132–140

    uses Finset.mem_sdiff, Finset.mem_insert, Or.inl, Or.inr

      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⟩
  11. 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.

    lines 144–151

    uses Finset.subset_insert, rank_potential_online_payment_bound_fetch_subset, rank_potential_online_payment_bound_eq_sum

      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'
  12. 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.

    lines 152–156

    uses Finset.sum_sub_distrib

      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]
  13. 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)|.

    lines 157–166

    uses Finset.mem_sdiff, List.mem_toFinset, rank_potential_online_payment_bound_diff_old, Finset.sum_congr, Finset.sum_const, nsmul_eq_mul

      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
  14. 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.

    lines 167–176

    uses rank_potential_online_payment_bound_insert_sdiff_mem, rank_potential_online_payment_bound_card_sdiff_ge_one

      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
  15. 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.

    lines 177–190

    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

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
See it in the graphDiscuss this resultChallenge it