AFTD Auto-Formalizing Theoretical Domains

deadline_paging_feasible_iff_exists_service_time

theoremverified

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.

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

    line 11

      constructor
  2. From 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.

    lines 12–17

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

    lines 18–20

        refine ⟨f, ?_, ?_, ?_⟩
        · intro i
          exact ⟨(hf i).1, (hf i).2.1⟩
  4. 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`.

    lines 21–29

    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)
  5. 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₀`.

    lines 30–35

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

    lines 36–39

      · 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, ?_, ?_, ?_⟩
  7. The schedule satisfies the initial cache condition `sched 0 = C₀`.

    By definition, `sched 0` evaluates directly to `C₀`.

    lines 40–41

        · show sched 0 = C₀
          dsimp [sched]
  8. 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`.

    lines 42–46

        · intro t
          dsimp [sched]
          split_ifs with ht
          · rw [hC₀]
          · exact hcap t ht
  9. 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`.

    lines 47–56

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

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

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