AFTD Auto-Formalizing Theoretical Domains

deadline_paging_min_cost_schedule_exists

theoremverified

Every feasible deadline-paging instance admits a feasible schedule whose fetch cost over the instance horizon is minimal among all feasible schedules (the offline optimum, made concrete).

Statement

theorem deadline_paging_min_cost_schedule_exists
    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (reqs : List (DeadlineRequest α))
    (h : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) :
    ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧
      ∀ sched' : ℕ → Finset α, IsFeasibleSchedule k C₀ sched' reqs →
        scheduleCost sched (instanceHorizon reqs) ≤ 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 ≤…

The proof, explained

The theorem establishes the existence of a cost-minimizing feasible schedule using the well-ordering principle of the natural numbers. Because a feasible schedule exists by hypothesis, the set of costs achievable by feasible schedules over the instance horizon is a non-empty subset of ℕ. The schedule attaining the minimum element of this set is therefore an optimal feasible schedule.

  1. The set of fetch costs realized by feasible schedules over the horizon is non-empty.

    Under classical logic, we extract a witness feasible schedule $s_0$ from the feasibility hypothesis $h$. We define the predicate $P(n)$ stating that $n$ is the horizon schedule cost of some feasible schedule, and witness that $P$ is non-empty using the cost of $s_0$.

    lines 8–11

      classical
      obtain ⟨s₀, hs₀⟩ := h
      let P : ℕ → Prop := fun n => ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = n
      have h_ex : ∃ n, P n := ⟨scheduleCost s₀ (instanceHorizon reqs), s₀, hs₀, rfl⟩
  2. There exists a feasible schedule `sched` achieving the minimal cost `Nat.find h_ex`.

    By the well-ordering principle of the natural numbers (`Nat.find_spec`), the non-empty predicate $P$ has a least element $\operatorname{Nat.find}(h\_ex)$. We unpack the specification to obtain a concrete schedule `sched` that is feasible and achieves this minimal cost.

    line 12

    uses Nat.find_spec

      obtain ⟨sched, hsched_feas, hsched_cost⟩ := Nat.find_spec h_ex
  3. The schedule `sched` is feasible and its cost is at most the cost of any feasible schedule `sched'`.

    We propose `sched` as the desired schedule and provide its feasibility. For any other feasible schedule `sched'`, we rewrite the cost of `sched` to $\operatorname{Nat.find}(h\_ex)$, and conclude using `Nat.find_min'` since `sched'` demonstrates that its own cost satisfies $P$.

    lines 13–15

    uses Nat.find_min'

      refine ⟨sched, hsched_feas, fun sched' hsched' => ?_⟩
      rw [hsched_cost]
      exact Nat.find_min' h_ex ⟨sched', hsched', rfl⟩
Nat.find_spec
If a predicate on natural numbers is satisfied by some natural number, then `Nat.find` produces a witness that satisfies the predicate.
Nat.find_min'
The witness `Nat.find H` is less than or equal to any natural number that satisfies the predicate.

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

/-- A feasible instance has a feasible schedule of minimum fetch cost over its horizon; turns the offline optimum into a concrete schedule. -/theorem deadline_paging_min_cost_schedule_exists    {α : Type*} [DecidableEq α] (k : ℕ) (C₀ : Finset α) (reqs : List (DeadlineRequest α))    (h : ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs) :    ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧      ∀ sched' : ℕ → Finset α, IsFeasibleSchedule k C₀ sched' reqs →        scheduleCost sched (instanceHorizon reqs) ≤ scheduleCost sched' (instanceHorizon reqs) := by  classical  obtain ⟨s₀, hs₀⟩ := h  let P : ℕ → Prop := fun n => ∃ sched : ℕ → Finset α, IsFeasibleSchedule k C₀ sched reqs ∧ scheduleCost sched (instanceHorizon reqs) = n  have h_ex : ∃ n, P n := ⟨scheduleCost s₀ (instanceHorizon reqs), s₀, hs₀, rfl⟩  obtain ⟨sched, hsched_feas, hsched_cost⟩ := Nat.find_spec h_ex  refine ⟨sched, hsched_feas, fun sched' hsched' => ?_⟩  rw [hsched_cost]  exact Nat.find_min' h_ex ⟨sched', hsched', rfl⟩
See it in the graphDiscuss this resultChallenge it