deadline_paging_opt_cost_ge_pages_outside_cache
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
- deadline_paging_cost_zero_iff_pages_subset_cacheA feasible instance can be served at fetch cost zero iff every requested page is already in the initial cache.
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.
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.
uses
List.foldr_cons,List.mem_cons.mp,le_max_left,Nat.lt_of_lt_of_le,Nat.lt_succ_self,le_max_rightinduction 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
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`.
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
`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)`.
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_transhave 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
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`.
uses
Finset.card_eq_sum_card_fiberwise,Finset.sum_le_sum,Finset.card_le_cardrw [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
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`.
uses
Finset.mem_filter,Finset.mem_sdiff,List.mem_toFinset,List.mem_map,dif_pos,Nat.find_specsimp 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
`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`.
uses
Finset.mem_sdiff,Nat.find_spec,Nat.find_minrw [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`.
- The proof defines the first appearance time of page p using `Nat.find`, which requires classical logic since the existential condition is non-computable.
- `omega` is used to discharge the linear arithmetic steps showing that `Nat.find hex - 1 = b` and `Nat.find hex ≠ 0` imply `Nat.find hex = b + 1`, and that `b < Nat.find hex`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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