AFTD Auto-Formalizing Theoretical Domains

deadline_paging_opt_cost_ge_pages_outside_cache

theoremverified

Every feasible schedule must fetch each requested page outside the initial cache at least once, so its fetch cost is at least the number of distinct requested pages outside C₀.

Statement

theorem deadline_paging_opt_cost_ge_pages_outside_cache
    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α)
    (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α))
    (h : IsFeasibleSchedule k C₀ sched reqs) :
    ((reqs.map (fun r => r.page)).toFinset \ C₀).card ≤ scheduleCost sched (instanceHorizon reqs)
Source
step towards deadline_paging_optimal_competitive_ratio_two_holes
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • IsFeasibleScheduleA schedule of cache configurations of size at most k is feasible for a list of deadline requests starting from initial cache C₀ if it…
  • scheduleCostThe total fetch cost of a cache schedule up to time T, defined as the sum over time steps of the number of newly fetched pages.
  • instanceHorizonThe finite time horizon of a list of deadline requests, defined as one more than the maximum deadline, or zero if empty.
  • DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
Used by 1

The proof, explained

The theorem is proved by a counting argument that maps each requested page outside the initial cache to the time step immediately before its first appearance in the schedule. For each page outside C₀, feasibility ensures that the page appears in the schedule at or before its request deadline, which strictly precedes the instance horizon. We define f(p) = t_min - 1, where t_min ≥ 1 is the first time step p appears in the cache. By partitioning these missing pages into the fibers of f, each fiber f⁻¹(b) is shown to be a subset of the pages fetched at transition b → b + 1, namely sched(b + 1) \ sched(b). Summing the fiber cardinalities over all time steps up to the horizon bounds the number of distinct requested pages outside C₀ by the total schedule cost.

  1. Every request in `reqs` has its deadline strictly less than `instanceHorizon reqs`.

    We prove the helper lemma by induction on the list of requests `reqs`. For the empty list, the hypothesis that `r ∈ []` is contradictory. For `hd :: tl`, the definition of `instanceHorizon` expands via `List.foldr_cons` to `max (hd.deadline + 1) (instanceHorizon tl)`. If `r = hd`, then `r.deadline < r.deadline + 1 ≤ max (r.deadline + 1) ...` by `le_max_left` and `Nat.lt_of_lt_of_le`. If `r ∈ tl`, the inductive hypothesis gives `r.deadline < instanceHorizon tl`, which is at most `max (hd.deadline + 1) (instanceHorizon tl)` by `le_max_right`, completing the inductive step by transitivity.

    lines 4–16

    uses List.foldr_cons, List.mem_cons.mp, le_max_left, Nat.lt_of_lt_of_le, Nat.lt_succ_self, le_max_right

      induction reqs with
      | nil => contradiction
      | cons hd tl ih =>
        simp only [instanceHorizon, List.foldr_cons]
        rcases List.mem_cons.mp hr with rfl | htl
        · have : r.deadline + 1 ≤ max (r.deadline + 1) (List.foldr (fun r m => max (r.deadline + 1) m) 0 tl) :=
            le_max_left _ _
          exact Nat.lt_of_lt_of_le (Nat.lt_succ_self _) this
        · have ih' := ih htl
          have : List.foldr (fun r m => max (r.deadline + 1) m) 0 tl ≤
            max (hd.deadline + 1) (List.foldr (fun r m => max (r.deadline + 1) m) 0 tl) :=
            le_max_right _ _
          exact Nat.lt_of_lt_of_le ih' this
  2. Define the set `s` of requested pages outside the initial cache `C₀`, and the map `f` assigning each page the time step preceding its first appearance in the schedule.

    We work classically. We define `s` as the finset of all pages requested in `reqs` that are not in the initial cache `C₀`. For any page `p`, if `p` appears in the schedule at some time (witnessed by `hex`), we set `f(p) = Nat.find hex - 1`, which is one step before its earliest appearance; otherwise, we set `f(p) = 0`.

    lines 24–27

      classical
      let s := (reqs.map (fun r => r.page)).toFinset \ C₀
      let f : α → ℕ := fun p =>
        if hex : ∃ t, p ∈ sched t then Nat.find hex - 1 else 0
  3. `f` maps every page in `s` into `Finset.range (instanceHorizon reqs)`.

    Let `p ∈ s`. Unfolding the definition of `s = (reqs.map (·.page)).toFinset \ C₀`, there is a request `r ∈ reqs` for `p` such that `p ∉ C₀`. By feasibility of the schedule, `p` appears in the cache at some time `t` satisfying `r.arrival ≤ t ≤ r.deadline`, providing the witness `hex`. The earliest time `Nat.find hex` is at most `t ≤ r.deadline` by `Nat.find_min'`. Since `r.deadline < instanceHorizon reqs` by the helper lemma, and `Nat.find hex - 1 ≤ Nat.find hex`, chaining inequalities shows that `f(p) < instanceHorizon reqs`, meaning `f(p) ∈ Finset.range (instanceHorizon reqs)`.

    lines 28–40

    uses Finset.mem_coe, Finset.mem_sdiff, List.mem_toFinset, List.mem_map, Finset.mem_range, dif_pos, Nat.find_min', deadline_paging_opt_cost_ge_pages_outside_cache_deadline_lt_instanceHorizon, Nat.sub_le, lt_of_le_of_lt, le_trans

      have h_maps : Set.MapsTo f ↑s ↑(Finset.range (instanceHorizon reqs)) := by
        intro p hp
        rw [Finset.mem_coe, Finset.mem_sdiff, List.mem_toFinset, List.mem_map] at hp
        rcases hp with ⟨⟨r, hr, rfl⟩, hpC0⟩
        rcases h.2.2 r hr with ⟨t, ht_arr, ht_dead, ht_mem⟩
        have hex : ∃ t, r.page ∈ sched t := ⟨t, ht_mem⟩
        simp only [Finset.mem_coe, Finset.mem_range]
        dsimp [f]
        rw [dif_pos hex]
        have hfind_le : Nat.find hex ≤ t := Nat.find_min' hex ht_mem
        have hdead := deadline_paging_opt_cost_ge_pages_outside_cache_deadline_lt_instanceHorizon hr
        have : Nat.find hex - 1 ≤ Nat.find hex := Nat.sub_le _ _
        exact lt_of_le_of_lt (le_trans this (le_trans hfind_le ht_dead)) hdead
  4. It suffices to show that for each time step `b < instanceHorizon reqs`, the fiber `{p ∈ s | f(p) = b}` is a subset of `sched (b + 1) \ sched b`.

    By `Finset.card_eq_sum_card_fiberwise`, the cardinality of `s` equals the sum of the cardinalities of its fibers `{p ∈ s | f(p) = b}` over all `b < instanceHorizon reqs`. By definition, `scheduleCost` is the sum of `(sched (b + 1) \ sched b).card`. By `Finset.sum_le_sum`, it suffices to show that each fiber has cardinality at most `(sched (b + 1) \ sched b).card`. In turn, by `Finset.card_le_card`, it suffices to show that every element in the fiber `{p ∈ s | f(p) = b}` belongs to `sched (b + 1) \ sched b`.

    lines 41–46

    uses Finset.card_eq_sum_card_fiberwise, Finset.sum_le_sum, Finset.card_le_card

      rw [Finset.card_eq_sum_card_fiberwise h_maps]
      unfold scheduleCost
      apply Finset.sum_le_sum
      intro b hb
      apply Finset.card_le_card
      intro p hp
  5. For any `p ∈ s` with `f(p) = b`, the earliest time `p` appears in the schedule is exactly `b + 1`.

    Let `p ∈ {a ∈ s | f(a) = b}`, so `p ∈ s` and `f(p) = b`. Since `p ∈ s`, `p ∉ C₀` and `p` is requested, so feasibility provides a time when `p` is in the cache, yielding the witness `hex`. Thus `f(p) = Nat.find hex - 1 = b`. The minimal time cannot be 0, because if `Nat.find hex = 0`, then `p ∈ sched 0 = C₀` by `Nat.find_spec`, contradicting `p ∉ C₀`. Since `Nat.find hex ≠ 0` and `Nat.find hex - 1 = b`, linear arithmetic (`omega`) gives `Nat.find hex = b + 1`.

    lines 47–62

    uses Finset.mem_filter, Finset.mem_sdiff, List.mem_toFinset, List.mem_map, dif_pos, Nat.find_spec

      simp only [Finset.mem_filter] at hp
      rcases hp with ⟨hps, hfp⟩
      have hp_sdiff := hps
      rw [Finset.mem_sdiff, List.mem_toFinset, List.mem_map] at hp_sdiff
      rcases hp_sdiff with ⟨⟨r, hr, rfl⟩, hpC0⟩
      rcases h.2.2 r hr with ⟨t, ht_arr, ht_dead, ht_mem⟩
      have hex : ∃ t, r.page ∈ sched t := ⟨t, ht_mem⟩
      dsimp [f] at hfp
      rw [dif_pos hex] at hfp
      have hpos : Nat.find hex ≠ 0 := by
        intro hzero
        have hspec := Nat.find_spec hex
        rw [hzero, h.1] at hspec
        exact hpC0 hspec
      have heq : Nat.find hex = b + 1 := by
        omega
  6. `p ∈ sched (b + 1) \ sched b`, which completes the proof.

    We need `p ∈ sched (b + 1)` and `p ∉ sched b`. By `Nat.find_spec`, `p ∈ sched (Nat.find hex)`, and since `Nat.find hex = b + 1`, we have `p ∈ sched (b + 1)`. If `p ∈ sched b`, since `b < b + 1 = Nat.find hex`, this would contradict the minimality of `Nat.find hex` (`Nat.find_min`). Hence `p ∉ sched b`, showing `p ∈ sched (b + 1) \ sched b`.

    lines 63–69

    uses Finset.mem_sdiff, Nat.find_spec, Nat.find_min

      rw [Finset.mem_sdiff]
      constructor
      · have hspec := Nat.find_spec hex
        rwa [heq] at hspec
      · intro hbad
        have hlt : b < Nat.find hex := by omega
        exact Nat.find_min hex hlt hbad
List.foldr_cons
Folding a function `f` over a non-empty list `a :: l` with accumulator `b` evaluates to `f a (List.foldr f b l)`.
List.mem_cons.mp
An element belongs to `a :: l` only if it is equal to `a` or belongs to `l`.
le_max_left
For any elements `a` and `b`, `a ≤ max a b`.
le_max_right
For any elements `a` and `b`, `b ≤ max a b`.
Nat.lt_of_lt_of_le
If `n < m` and `m ≤ k`, then `n < k`.
Nat.lt_succ_self
For any natural number `n`, `n < n + 1`.
Finset.mem_coe
An element belongs to the set coercion of a finset `s` if and only if it belongs to `s`.
Finset.mem_sdiff
An element belongs to the finset difference `s \ t` if and only if it belongs to `s` and does not belong to `t`.
List.mem_toFinset
An element belongs to the finset converted from a list if and only if it belongs to the list.
List.mem_map
An element `b` belongs to `List.map f l` if and only if `b = f a` for some `a` in `l`.
Finset.mem_range
A natural number `m` belongs to `Finset.range n` if and only if `m < n`.
dif_pos
Given a proof of the condition `c`, the dependent if-then-else evaluates to the `then` branch.
Nat.find_min'
If `p m` holds, the minimal index `Nat.find H` satisfying `p` is at most `m`.
deadline_paging_opt_cost_ge_pages_outside_cache_deadline_lt_instanceHorizon
If a request `r` belongs to the list `reqs`, then `r.deadline < instanceHorizon reqs`.
Nat.sub_le
For any natural numbers `n` and `m`, `n - m ≤ n`.
lt_of_le_of_lt
If `a ≤ b` and `b < c`, then `a < c`.
le_trans
Inequality is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
Finset.card_eq_sum_card_fiberwise
If `f` maps a finset `s` into a finset `t`, the cardinality of `s` is the sum over `b ∈ t` of the cardinalities of the fibers `{a ∈ s | f a = b}`.
Finset.sum_le_sum
If `f i ≤ g i` for all `i ∈ s`, then `∑ i ∈ s, f i ≤ ∑ i ∈ s, g i`.
Finset.card_le_card
If a finset `s` is a subset of `t`, then the cardinality of `s` is at most the cardinality of `t`.
Finset.mem_filter
An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Nat.find_spec
The index returned by `Nat.find H` satisfies the underlying predicate `p`.
Nat.find_min
No natural number strictly smaller than `Nat.find H` satisfies the underlying predicate `p`.

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 deadline_paging_opt_cost_ge_pages_outside_cache_deadline_lt_instanceHorizon    {α : Type*} {reqs : List (DeadlineRequest α)} {r : DeadlineRequest α} (hr : r ∈ reqs) :    r.deadline < instanceHorizon reqs := by  induction reqs with  | nil => contradiction  | cons hd tl ih =>    simp only [instanceHorizon, List.foldr_cons]    rcases List.mem_cons.mp hr with rfl | htl    · have : r.deadline + 1 ≤ max (r.deadline + 1) (List.foldr (fun r m => max (r.deadline + 1) m) 0 tl) :=        le_max_left _ _      exact Nat.lt_of_lt_of_le (Nat.lt_succ_self _) this    · have ih' := ih htl      have : List.foldr (fun r m => max (r.deadline + 1) m) 0 tl ≤        max (hd.deadline + 1) (List.foldr (fun r m => max (r.deadline + 1) m) 0 tl) :=        le_max_right _ _      exact Nat.lt_of_lt_of_le ih' this/-- The fetch cost of any feasible schedule is at least the number of distinct requested pages outside the initial cache. -/theorem deadline_paging_opt_cost_ge_pages_outside_cache    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α)    (sched : ℕ → Finset α) (reqs : List (DeadlineRequest α))    (h : IsFeasibleSchedule k C₀ sched reqs) :    ((reqs.map (fun r => r.page)).toFinset \ C₀).card ≤ scheduleCost sched (instanceHorizon reqs) := by  classical  let s := (reqs.map (fun r => r.page)).toFinset \ C₀  let f : α → ℕ := fun p =>    if hex : ∃ t, p ∈ sched t then Nat.find hex - 1 else 0  have h_maps : Set.MapsTo f ↑s ↑(Finset.range (instanceHorizon reqs)) := by    intro p hp    rw [Finset.mem_coe, Finset.mem_sdiff, List.mem_toFinset, List.mem_map] at hp    rcases hp with ⟨⟨r, hr, rfl⟩, hpC0⟩    rcases h.2.2 r hr with ⟨t, ht_arr, ht_dead, ht_mem⟩    have hex : ∃ t, r.page ∈ sched t := ⟨t, ht_mem⟩    simp only [Finset.mem_coe, Finset.mem_range]    dsimp [f]    rw [dif_pos hex]    have hfind_le : Nat.find hex ≤ t := Nat.find_min' hex ht_mem    have hdead := deadline_paging_opt_cost_ge_pages_outside_cache_deadline_lt_instanceHorizon hr    have : Nat.find hex - 1 ≤ Nat.find hex := Nat.sub_le _ _    exact lt_of_le_of_lt (le_trans this (le_trans hfind_le ht_dead)) hdead  rw [Finset.card_eq_sum_card_fiberwise h_maps]  unfold scheduleCost  apply Finset.sum_le_sum  intro b hb  apply Finset.card_le_card  intro p hp  simp only [Finset.mem_filter] at hp  rcases hp with ⟨hps, hfp⟩  have hp_sdiff := hps  rw [Finset.mem_sdiff, List.mem_toFinset, List.mem_map] at hp_sdiff  rcases hp_sdiff with ⟨⟨r, hr, rfl⟩, hpC0⟩  rcases h.2.2 r hr with ⟨t, ht_arr, ht_dead, ht_mem⟩  have hex : ∃ t, r.page ∈ sched t := ⟨t, ht_mem⟩  dsimp [f] at hfp  rw [dif_pos hex] at hfp  have hpos : Nat.find hex ≠ 0 := by    intro hzero    have hspec := Nat.find_spec hex    rw [hzero, h.1] at hspec    exact hpC0 hspec  have heq : Nat.find hex = b + 1 := by    omega  rw [Finset.mem_sdiff]  constructor  · have hspec := Nat.find_spec hex    rwa [heq] at hspec  · intro hbad    have hlt : b < Nat.find hex := by omega    exact Nat.find_min hex hlt hbad
See it in the graphDiscuss this resultChallenge it