AFTD Auto-Formalizing Theoretical Domains

rank_potential_offline_fetch_bound

theoremverifiedformalization

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

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

    lines 4–9

    uses Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase

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

    lines 10–15

    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_insert

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

    line 19

    uses rank_potential_offline_fetch_bound_aux

      have h1 := rank_potential_offline_fetch_bound_aux q cOpt p_in p_out
  4. The 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`.

    lines 20–27

    uses List.idxOf_lt_length_iff.mpr, Nat.zero_le

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

    line 28

      have h3 : rank_potential q (insert p_in (cOpt.erase p_out)) ≤ rank_potential q cOpt + k := by omega
  6. 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.

    lines 29–33

    uses Nat.cast_le

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

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