AFTD Auto-Formalizing Theoretical Domains

deadline_paging_cost_zero_iff_pages_subset_cache

theoremverified

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.

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

    lines 8–11

    uses deadline_paging_opt_cost_ge_pages_outside_cache

      constructor
      · rintro ⟨sched, hfeas, hcost⟩
        have hle := deadline_paging_opt_cost_ge_pages_outside_cache k C₀ sched reqs hfeas
        rw [hcost] at hle
  2. 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.

    lines 12–14

    uses Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset

        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
  3. 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₀.

    lines 15–17

      · intro hsub
        use fun _ => C₀
        refine ⟨⟨rfl, fun t => by rw [hC₀], fun r hr => ?_⟩, ?_⟩
  4. 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.

    lines 18–21

    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⟩
  5. 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.

    lines 22–23

        · 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

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