deadline_paging_feasible_iff_exists_service_time
An instance is feasible iff one can assign every request a service time inside its window so that each non-zero time slot sees at most k distinct pages and slot 0 sees only pages of the initial cache C₀.
Statement
theorem deadline_paging_feasible_iff_exists_service_time {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (hC₀ : C₀.card = k) (reqs : List (DeadlineRequest α)) : (∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) ↔ ∃ f : Fin reqs.length → ℕ, (∀ i, (reqs.get i).arrival ≤ f i ∧ f i ≤ (reqs.get i).deadline) ∧ (∀ t, t ≠ 0 → ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)).card ≤ k) ∧ ((Finset.univ.filter (fun i => f i = 0)).image (fun i => (reqs.get i).page)) ⊆ C₀
- Source
- step towards deadline_paging_optimal_competitive_ratio_two_holes
- Verified
- 18 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
The proof, explained
Feasibility of a deadline-paging instance is shown to be equivalent to the existence of an assignment of service times `f(i)` for each request `i` within its arrival-deadline window such that at most `k` distinct pages are served at any time slot `t > 0`, and only pages from the initial cache `C₀` are served at slot `0`. In the forward direction, given a feasible schedule, the axiom of choice extracts for each request a time slot in its window where its page is present in the cache; cache capacity bounds immediately transfer to the set of served pages. In the reverse direction, we simply set `sched 0 = C₀` and set `sched t` for `t > 0` to be exactly the set of pages assigned to `t`, which trivially satisfies the capacity bound and serves every request.
The equivalence between the existence of a feasible schedule and the existence of a valid service-time assignment splits into two implications.
The `constructor` tactic breaks the `↔` statement into the forward direction (extracting a service-time function from a feasible schedule) and the reverse direction (constructing a feasible schedule from a service-time function).
constructorFrom a feasible schedule, there exists a function `f` mapping each request index `i` to a time in its arrival-deadline window at which its requested page is in the cache.
Unpacking the assumption that the schedule is feasible gives the initial cache condition `sched 0 = C₀`, the capacity bound `|sched t| ≤ k` for all `t`, and the guarantee that every request in `reqs` is present in the cache at some time within its window. Applying this guarantee to the `i`-th request of the list (using `List.get_mem`) ensures such a time exists for each index `i`. By the axiom of choice (`choose`), we obtain a service-time function `f` selecting such a time `f(i)` for each request.
uses
List.get_mem· rintro ⟨sched, hsched⟩ rcases hsched with ⟨h0, hcard, hserve⟩ have h_each : ∀ i : Fin reqs.length, ∃ t, (reqs.get i).arrival ≤ t ∧ t ≤ (reqs.get i).deadline ∧ (reqs.get i).page ∈ sched t := by intro i exact hserve (reqs.get i) (List.get_mem reqs i) choose f hf using h_eachFor every request index `i`, the assigned service time `f(i)` lies in the window [arrival, deadline].
We provide `f` as the witness. The arrival lower bound and deadline upper bound hold immediately from the properties of `f` established during its selection.
refine ⟨f, ?_, ?_, ?_⟩ · intro i exact ⟨(hf i).1, (hf i).2.1⟩
For any time slot `t ≠ 0`, at most `k` distinct pages are served at time `t`.
Any page served at time `t` is requested by some index `i` with `f(i) = t`. By definition of `f`, this page belongs to `sched (f(i)) = sched t`. Thus the set of pages served at time `t` is a subset of `sched t`. Since `|sched t| ≤ k`, by monotonicity of cardinality (`Finset.card_le_card`) and transitivity of inequality (`le_trans`), the number of distinct pages served at time `t` is at most `k`.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_card,le_trans· intro t ht have hsub : ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)) ⊆ sched t := by intro p hp simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hp rcases hp with ⟨i, hi, rfl⟩ have := (hf i).2.2 rw [hi] at this exact this exact le_trans (Finset.card_le_card hsub) (hcard t)
All pages served at time `0` belong to the initial cache `C₀`.
If a page is served at time `0`, it is requested by some index `i` with `f(i) = 0`. By definition of `f`, the page belongs to `sched (f(i)) = sched 0`. Since `sched 0 = C₀`, the page belongs to `C₀`.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and· intro p hp simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hp rcases hp with ⟨i, hi, rfl⟩ have := (hf i).2.2 rw [hi, h0] at this exact this
Given a service-time assignment `f`, we define a candidate schedule `sched` where `sched 0 = C₀` and for `t ≠ 0`, `sched t` is the set of pages served at time `t`.
Assuming `f` satisfies the window, capacity, and initial cache conditions, we define `sched` by case distinction: `sched 0 = C₀`, and for `t ≠ 0`, `sched t` consists precisely of the pages requested with `f(i) = t`. It remains to show that `sched` satisfies the three feasibility conditions.
· rintro ⟨f, hwin, hcap, hC0_sub⟩ let sched : ℕ → Finset α := fun t => if t = 0 then C₀ else ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)) refine ⟨sched, ?_, ?_, ?_⟩The schedule satisfies the initial cache condition `sched 0 = C₀`.
By definition, `sched 0` evaluates directly to `C₀`.
· show sched 0 = C₀ dsimp [sched]
For every time `t`, the cache size satisfies `|sched t| ≤ k`.
For `t = 0`, `sched 0 = C₀`, which has cardinality `k` by the hypothesis `hC₀`. For `t ≠ 0`, `sched t` is the set of pages assigned to `t`, which has cardinality at most `k` by the capacity condition on `f`.
· intro t dsimp [sched] split_ifs with ht · rw [hC₀] · exact hcap t ht
Every request in `reqs` is served within its arrival-deadline window.
For any request `r ∈ reqs`, we express `r` as the `i`-th element of `reqs` using `List.mem_iff_get.mp`. We serve request `r` at time `f(i)`, which lies in its window by assumption. If `f(i) = 0`, the page is served at time 0 and therefore belongs to `C₀ = sched 0` by the initial condition on `f`. If `f(i) ≠ 0`, the page belongs to `sched (f(i))` by definition of `sched`.
uses
List.mem_iff_get.mp,Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and· intro r hr rcases List.mem_iff_get.mp hr with ⟨i, rfl⟩ refine ⟨f i, (hwin i).1, (hwin i).2, ?_⟩ dsimp [sched] split_ifs with ht · apply hC0_sub simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨i, ht, rfl⟩ · simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨i, rfl, rfl⟩
List.get_mem- For any list `l` and index `n : Fin l.length`, the element `l.get n` belongs to `l`.
Finset.mem_image- An element `b` belongs to the image of a finite set `s` under `f` if and only if there exists `a ∈ s` with `f a = b`.
Finset.mem_filter- An element `a` belongs to `s.filter p` if and only if `a ∈ s` and `p a` holds.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and- The conjunction `True ∧ p` is logically equivalent to `p`.
Finset.card_le_card- If `s ⊆ t` for finite sets `s` and `t`, then the cardinality of `s` is at most the cardinality of `t`.
le_trans- The inequality relation `≤` is transitive: if `a ≤ b` and `b ≤ c`, then `a ≤ c`.
List.mem_iff_get.mp- If an element belongs to a list `l`, then it equals `l.get n` for some index `n : Fin l.length`.
- Requests in the list `reqs` are formally indexed by `Fin reqs.length`, so service times are assigned via a function `f : Fin reqs.length → ℕ` rather than indexing by request objects directly.
- The schedule constructed in the reverse direction simply sets the cache at each non-zero slot `t` to be precisely the set of pages requested at slot `t`. It does not simulate cache retention across consecutive time steps because feasibility only requires that each requested page is present at its service time and that each slot does not exceed capacity `k` (cache persistence affects paging cost, but not feasibility).
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.
/-- Feasibility is equivalent to an assignment of service times with a per-slot capacity condition (≤ k distinct pages off slot 0, only C₀ at slot 0); caching is a cost matter, never a feasibility blocker. -/theorem deadline_paging_feasible_iff_exists_service_time {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (hC₀ : C₀.card = k) (reqs : List (DeadlineRequest α)) : (∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) ↔ ∃ f : Fin reqs.length → ℕ, (∀ i, (reqs.get i).arrival ≤ f i ∧ f i ≤ (reqs.get i).deadline) ∧ (∀ t, t ≠ 0 → ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)).card ≤ k) ∧ ((Finset.univ.filter (fun i => f i = 0)).image (fun i => (reqs.get i).page)) ⊆ C₀ := by constructor · rintro ⟨sched, hsched⟩ rcases hsched with ⟨h0, hcard, hserve⟩ have h_each : ∀ i : Fin reqs.length, ∃ t, (reqs.get i).arrival ≤ t ∧ t ≤ (reqs.get i).deadline ∧ (reqs.get i).page ∈ sched t := by intro i exact hserve (reqs.get i) (List.get_mem reqs i) choose f hf using h_each refine ⟨f, ?_, ?_, ?_⟩ · intro i exact ⟨(hf i).1, (hf i).2.1⟩ · intro t ht have hsub : ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)) ⊆ sched t := by intro p hp simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hp rcases hp with ⟨i, hi, rfl⟩ have := (hf i).2.2 rw [hi] at this exact this exact le_trans (Finset.card_le_card hsub) (hcard t) · intro p hp simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] at hp rcases hp with ⟨i, hi, rfl⟩ have := (hf i).2.2 rw [hi, h0] at this exact this · rintro ⟨f, hwin, hcap, hC0_sub⟩ let sched : ℕ → Finset α := fun t => if t = 0 then C₀ else ((Finset.univ.filter (fun i => f i = t)).image (fun i => (reqs.get i).page)) refine ⟨sched, ?_, ?_, ?_⟩ · show sched 0 = C₀ dsimp [sched] · intro t dsimp [sched] split_ifs with ht · rw [hC₀] · exact hcap t ht · intro r hr rcases List.mem_iff_get.mp hr with ⟨i, rfl⟩ refine ⟨f i, (hwin i).1, (hwin i).2, ?_⟩ dsimp [sched] split_ifs with ht · apply hC0_sub simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨i, ht, rfl⟩ · simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and] exact ⟨i, rfl, rfl⟩