AFTD Auto-Formalizing Theoretical Domains

rank_potential_zero_of_subset

theoremverified

If all pages in the online FIFO cache are present in the offline cache, the rank potential Φ is zero; in particular, the initial potential Φ₀ = 0.

Statement

theorem rank_potential_zero_of_subset {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (h : q.pages.toFinset ⊆ cOpt) : rank_potential q cOpt = 0
Source
arXiv:2610.18767 Section 3.2, line 414
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

Let α be a type with decidable equality and let k be a natural number. Let q be a FifoQueue α k (a structure with a duplicate-free list q.pages of length k) and let cOpt be a finite set of elements of α. If the set of elements in q.pages is a subset of cOpt (q.pages.toFinset ⊆ cOpt), then rank_potential q cOpt = 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 Φ(q, cOpt) is defined as the sum of the FIFO ranks of all pages in the online queue q that are not present in the offline cache cOpt. By assumption, the pages of the online queue form a subset of the offline cache, so this set difference is empty. Consequently, the sum is taken over the empty set and evaluates to zero.

  1. By definition, the rank potential is the sum of FIFO ranks over pages in the online cache not present in the offline cache: ∑ x ∈ q.pages.toFinset \ cOpt, fifo_rank q x = 0.

    Unfolding the definition of rank_potential expands the goal into showing that the sum of fifo_rank q x over the set difference q.pages.toFinset \ cOpt equals zero.

    line 3

      unfold rank_potential
  2. The set difference is empty, so the sum evaluates to 0.

    Because the online cache is a subset of the offline cache (q.pages.toFinset ⊆ cOpt by hypothesis h), the set difference q.pages.toFinset \ cOpt is empty by Finset.sdiff_eq_empty_iff_subset.mpr. Rewriting with this fact and Finset.sum_empty shows that the sum over the empty set is 0.

    line 4

    uses Finset.sdiff_eq_empty_iff_subset.mpr, Finset.sum_empty

      rw [Finset.sdiff_eq_empty_iff_subset.mpr h, Finset.sum_empty]
Finset.sdiff_eq_empty_iff_subset.mpr
If a finite set s is a subset of t, then their set difference s \ t is empty.
Finset.sum_empty
The sum of any function over the empty finite set is 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

/-- Rank potential is zero when online cache is a subset of offline cache. -/theorem rank_potential_zero_of_subset {α : Type*} [DecidableEq α] {k : ℕ} (q : FifoQueue α k) (cOpt : Finset α) (h : q.pages.toFinset ⊆ cOpt) : rank_potential q cOpt = 0 := by  unfold rank_potential  rw [Finset.sdiff_eq_empty_iff_subset.mpr h, Finset.sum_empty]
See it in the graphDiscuss this resultChallenge it