AFTD Auto-Formalizing Theoretical Domains

rank_potential_offline_evict_hole_bound

theoremverifiedformalization

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.

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

    lines 3–17

    uses Finset.mem_sdiff, Finset.mem_insert, not_or, Finset.mem_erase, not_and, List.mem_toFinset.mp

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

    lines 18–20

    uses Finset.sum_le_sum_of_subset

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

    line 21

      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

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