deadline_paging_cost_zero_iff_pages_subset_cache
A feasible instance can be served at fetch cost zero iff every requested page is already in the initial cache.
Statement
theorem deadline_paging_cost_zero_iff_pages_subset_cache {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (hC₀ : C₀.card = k) (reqs : List (DeadlineRequest α)) : (∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = 0) ↔ (reqs.map (fun r => r.page)).toFinset ⊆ C₀
- Source
- step towards deadline_paging_optimal_competitive_ratio_two_holes
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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 ≤…
- deadline_paging_opt_cost_ge_pages_outside_cacheEvery feasible schedule must fetch each requested page outside the initial cache at least once, so its fetch cost is at least the number…
The proof, explained
The equivalence is proven in two directions. In the forward direction, any feasible schedule incurs a fetch cost of at least the number of requested pages outside the initial cache C₀; since the cost is zero, this count is zero, which means every requested page must already be in C₀. Conversely, if all requested pages already belong to C₀, the static schedule that keeps the cache fixed at C₀ for all time is feasible—each request is served immediately upon its arrival—and incurs zero cost because no page replacements ever occur.
In the forward direction, assuming a feasible schedule with cost zero, the number of requested pages outside the initial cache is at most zero: |P \ C₀| ≤ 0.
We split the equivalence into both directions. In the forward direction, let sched be a feasible schedule with cost zero (hcost). By deadline_paging_opt_cost_ge_pages_outside_cache, the fetch cost of any feasible schedule is bounded below by the number of distinct requested pages outside C₀, so |P \ C₀| ≤ scheduleCost. Substituting scheduleCost = 0 yields |P \ C₀| ≤ 0.
uses
deadline_paging_opt_cost_ge_pages_outside_cacheconstructor · rintro ⟨sched, hfeas, hcost⟩ have hle := deadline_paging_opt_cost_ge_pages_outside_cache k C₀ sched reqs hfeas rw [hcost] at hle
All requested pages are contained in the initial cache: P ⊆ C₀.
Since the cardinality |P \ C₀| is a natural number and |P \ C₀| ≤ 0, it must equal 0 (verified by linear arithmetic via omega). By Finset.card_eq_zero, a finite set of size zero is empty, so P \ C₀ = ∅. By Finset.sdiff_eq_empty_iff_subset, P \ C₀ = ∅ is equivalent to P ⊆ C₀, concluding the forward direction.
uses
Finset.card_eq_zero,Finset.sdiff_eq_empty_iff_subsethave hcard : ((reqs.map (fun r => r.page)).toFinset \ C₀).card = 0 := by omega rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hcard exact hcard
In the reverse direction, assuming P ⊆ C₀, the constant schedule that keeps the cache at C₀ for all time satisfies the initial state and cache capacity constraints.
For the converse, assume all requested pages are in C₀. We propose the static candidate schedule sched(t) = C₀ for all t ≥ 0. The initial state sched(0) = C₀ holds by definition, and at every time step t, the cache capacity constraint |sched(t)| ≤ k is satisfied because |C₀| = k ≤ k using the hypothesis hC₀.
· intro hsub use fun _ => C₀ refine ⟨⟨rfl, fun t => by rw [hC₀], fun r hr => ?_⟩, ?_⟩
The constant schedule serves every deadline request.
For each request r in reqs, we choose to serve it at its arrival time t = r.arrival. This time is valid because r.arrival ≤ r.arrival by reflexivity (le_rfl) and r.arrival ≤ r.deadline by definition of a deadline request. The requested page r.page is in C₀ because r.page belongs to the set of requested pages P (via List.mem_toFinset and List.mem_map), and P ⊆ C₀ by assumption.
uses
le_rfl,List.mem_toFinset,List.mem_map· refine ⟨r.arrival, le_rfl, r.h_deadline, ?_⟩ apply hsub rw [List.mem_toFinset, List.mem_map] exact ⟨r, hr, rfl⟩
The constant schedule incurs zero total fetch cost. automation
Unfolding scheduleCost, the total cost is the sum over time of the number of newly fetched pages |sched(t + 1) \ sched(t)|. Since the cache never changes, sched(t + 1) \ sched(t) = C₀ \ C₀ = ∅, which has size 0. The sum of zeros simplifies to 0.
· unfold scheduleCost simp
deadline_paging_opt_cost_ge_pages_outside_cache- The fetch cost of any feasible schedule over the instance horizon is at least the number of requested pages not present in the initial cache.
Finset.card_eq_zero- A finite set has cardinality zero if and only if it is the empty set.
Finset.sdiff_eq_empty_iff_subset- The set difference s \ t is empty if and only if s is a subset of t.
le_rfl- The inequality relation ≤ is reflexive (a ≤ a for all a).
List.mem_toFinset- An element belongs to the set conversion of a list if and only if it is a member of the list.
List.mem_map- An element y is in List.map f l if and only if y = f x for some x in l.
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.
/-- Zero-cost feasibility is equivalent to all requested pages already being cached. -/theorem deadline_paging_cost_zero_iff_pages_subset_cache {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (hC₀ : C₀.card = k) (reqs : List (DeadlineRequest α)) : (∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = 0) ↔ (reqs.map (fun r => r.page)).toFinset ⊆ C₀ := by constructor · rintro ⟨sched, hfeas, hcost⟩ have hle := deadline_paging_opt_cost_ge_pages_outside_cache k C₀ sched reqs hfeas rw [hcost] at hle have hcard : ((reqs.map (fun r => r.page)).toFinset \ C₀).card = 0 := by omega rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hcard exact hcard · intro hsub use fun _ => C₀ refine ⟨⟨rfl, fun t => by rw [hC₀], fun r hr => ?_⟩, ?_⟩ · refine ⟨r.arrival, le_rfl, r.h_deadline, ?_⟩ apply hsub rw [List.mem_toFinset, List.mem_map] exact ⟨r, hr, rfl⟩ · unfold scheduleCost simp