AFTD Auto-Formalizing Theoretical Domains

deadline_paging_lower_bound_k_plus_half

theoremverifiedformalization

For every cache capacity k ≥ 1, every finite page universe α with at least k + 2 pages, every initial cache C₀ of size k, every schedule generator Alg, and every real ρ, if Alg is ρ-competitive starting from C₀ in the sense of IsCompetitiveRatio, then ρ ≥ k + 1/2.

Statement

theorem deadline_paging_lower_bound_k_plus_half
    (k : ℕ) (hk : 1 ≤ k) {α : Type*} [Fintype α] [DecidableEq α] (hn : k + 2 ≤ Fintype.card α)
    (C₀ : Finset α) (hC₀ : C₀.card = k)
    (Alg : List (DeadlineRequest α) → (ℕ → Finset α))
    (ρ : ℝ) (hρ : IsCompetitiveRatio k C₀ Alg ρ) :
    (k : ℝ) + 1 / 2 ≤ ρ
Formalizes
arXiv:2610.18767 Theorem 1.3
Verified
18 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • DeadlineRequestA request in online paging with deadlines, specifying a requested page in α, an arrival time in ℕ, and a deadline in ℕ with arrival ≤…
  • IsCompetitiveRatioA schedule generator Alg is ρ-competitive for cache capacity k and initial cache C₀ if it is online, produces a feasible schedule whenever…
  • instanceHorizonThe finite time horizon of a list of deadline requests, defined as one more than the maximum deadline, or zero if empty.
  • 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.
  • IsOnlineClairvoyantScheduleGenA deterministic clairvoyant online schedule generator on lists of requests produces a cache configuration at time t that depends only on…
  • 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…

Read back from the Lean

Let k be a natural number such that 1 ≤ k. Let α be a finite type with decidable equality such that the cardinality of α is at least k + 2. Let C₀ be a finite subset of α of cardinality k. Let Alg be a function mapping any list of deadline requests to a cache schedule ℕ → Finset α. Let ρ be a real number. If Alg has competitive ratio ρ (with respect to capacity k and initial cache C₀), then k + 1/2 ≤ ρ.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem is proven by contradiction: no online clairvoyant algorithm can produce a feasible schedule on all feasible instances when the page universe has size at least k + 2. A fixed prefix of k + 2 requests for distinct pages T with window [1, 3] is introduced; for each page x ∈ T, future tight requests at times 2 and 3 force any feasible algorithm to fill its cache with T \\ {x}, leaving time 1 as the only available slot to serve x. Because the algorithm is online clairvoyant, its time-1 cache must be identical across all these instances, forcing this single cache of capacity k to contain all k + 2 pages of T. This gives the arithmetic contradiction k + 2 ≤ k, from which the competitive ratio lower bound follows vacuously.

  1. Extract the online clairvoyance and feasibility hypotheses from the competitive ratio assumption.

    The assumption `IsCompetitiveRatio k C₀ Alg ρ` bundles three conditions: `Alg` is an online clairvoyant schedule generator (its cache at time t depends only on requests arriving at or before time t), it outputs a feasible schedule whenever an offline feasible schedule exists, and its total cost is bounded relative to the optimal cost. We unpack the first two properties as `hgen` and `hfeas` and discard the cost inequality, as feasibility alone will suffice.

    lines 8–9

      classical
      obtain ⟨hgen, hfeas, -⟩ := hρ
  2. Construct a subset T ⊆ α of k + 2 distinct pages.

    Because the universe α has cardinality at least k + 2 (`hn`), we embed `Fin (k + 2)` into α via an injective map e. Defining T as the image of e yields a finset of size exactly k + 2, using injectivity of the embedding and the standard cardinality of `Fin (k + 2)`.

    lines 10–18

    uses Fin.castLE_injective, Finset.card_image_of_injective, Finset.card_univ, Fintype.card_fin

      -- an enumeration of k+2 distinct pages
      let e : Fin (k + 2) → α := fun i => (Fintype.equivFin α).symm (Fin.castLE hn i)
      have he_inj : Function.Injective e := by
        intro i j hij
        exact Fin.castLE_injective hn ((Fintype.equivFin α).symm.injective hij)
      let T : Finset α := Finset.univ.image e
      have hTcard : T.card = k + 2 := by
        show (Finset.univ.image e).card = k + 2
        rw [Finset.card_image_of_injective _ he_inj, Finset.card_univ, Fintype.card_fin]
  3. Define the common prefix `pre` on T and the tight request constructor `tight`.

    We define `pre` as a list of k + 2 requests, one for each page in T, all arriving at time 1 with deadline 3. We also define a helper `tight S t` that creates zero-slack requests (arriving and expiring at time t) for every page in a subset S ⊆ α.

    lines 19–25

    uses le_refl

      let h13 : 1 ≤ 3 := by norm_num
      -- the common prefix: every page of `T` is requested with window [1,3]
      let pre : List (DeadlineRequest α) :=
        List.ofFn (fun i : Fin (k+2) => (⟨e i, 1, 3, h13⟩ : DeadlineRequest α))
      -- tight requests for all pages of `S` at time `t`
      let tight : Finset α → ℕ → List (DeadlineRequest α) :=
        fun S t => S.val.toList.map (fun p => (⟨p, t, t, le_refl t⟩ : DeadlineRequest α))
  4. Establish membership and arrival-filtering lemmas for `pre` and `tight`.

    We prove characterizations of `pre` (it contains exactly requests for pages in T with window [1, 3]) and `tight S t` (it contains exactly requests for pages in S with window [t, t]). We also verify that filtering for requests with arrival time ≤ 1 leaves `pre` unchanged, but reduces `tight S t` to the empty list whenever t > 1.

    lines 26–64

    uses List.mem_ofFn.mp, Finset.mem_image.mpr, Finset.mem_univ, Finset.mem_image.mp, List.mem_ofFn.mpr, List.mem_map.mp, Finset.mem_val, Multiset.mem_toList, List.mem_map.mpr, Multiset.mem_toList.mpr, List.filter_eq_nil_iff, List.filter_eq_self

      have hpre_mem : ∀ r ∈ pre, r.page ∈ T ∧ r.arrival = 1 ∧ r.deadline = 3 := by
        intro r hr
        obtain ⟨i, hi⟩ := List.mem_ofFn.mp hr
        rw [← hi]
        exact ⟨Finset.mem_image.mpr ⟨i, Finset.mem_univ i, rfl⟩, rfl, rfl⟩
      have hpre_exists : ∀ p ∈ T, ∃ r ∈ pre, r.page = p ∧ r.arrival = 1 ∧ r.deadline = 3 := by
        intro p hp
        obtain ⟨i, -, hi⟩ := Finset.mem_image.mp hp
        exact ⟨⟨e i, 1, 3, h13⟩, List.mem_ofFn.mpr ⟨i, rfl⟩, hi, rfl, rfl⟩
      have htight_mem : ∀ (S : Finset α) (t : ℕ) {r : DeadlineRequest α}, r ∈ tight S t →
          r.page ∈ S ∧ r.arrival = t ∧ r.deadline = t := by
        intro S t r hr
        obtain ⟨p, hp, hpr⟩ := List.mem_map.mp hr
        have hpS : p ∈ S := by
          rw [← Finset.mem_val, ← Multiset.mem_toList]
          exact hp
        rw [← hpr]
        exact ⟨hpS, rfl, rfl⟩
      have htight_exists : ∀ (S : Finset α) (t : ℕ), ∀ p ∈ S,
          ∃ r ∈ tight S t, r.page = p ∧ r.arrival = t ∧ r.deadline = t := by
        intro S t p hp
        exact ⟨⟨p, t, t, le_refl t⟩,
          List.mem_map.mpr ⟨p, Multiset.mem_toList.mpr (by rwa [Finset.mem_val]), rfl⟩, rfl, rfl, rfl⟩
      have htight_filter : ∀ (S : Finset α) (t : ℕ), 1 < t →
          List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) (tight S t) = [] := by
        intro S t ht
        rw [List.filter_eq_nil_iff]
        intro r hr
        obtain ⟨-, h1, -⟩ := htight_mem S t hr
        rw [h1]
        simp
        omega
      have hpre_filter :
          List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) pre = pre := by
        rw [List.filter_eq_self]
        intro r hr
        obtain ⟨-, h1, -⟩ := hpre_mem r hr
        rw [h1]
        simp
  5. For each page x ∈ T, construct two k-element sets A, B ⊆ T \\ {x} whose union covers T \\ {x}.

    Erasing x from T leaves k + 1 pages. Since k ≥ 1, this set has cardinality at least 2, so it contains two distinct pages y ≠ z. Removing y yields a set A of size k, and removing z yields a set B of size k. Neither set contains x, and their union A ∪ B covers all of T \\ {x}.

    lines 65–100

    uses Finset.card_erase_of_mem, Finset.one_lt_card.mp, Finset.mem_erase, Finset.mem_union, Or.inr, Or.inl

      -- for each x in T: a feasible instance whose time-1 cache (after the common prefix) holds x
      have key : ∀ x ∈ T, ∃ (L : List (DeadlineRequest α)) (sched : ℕ → Finset α),
          IsFeasibleSchedule k C₀ sched L ∧ x ∈ Alg L 1 ∧
            List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) L = pre := by
        intro x hx
        have hexcard : (T.erase x).card = k + 1 := by
          rw [Finset.card_erase_of_mem hx, hTcard]
          omega
        obtain ⟨y, hy, z, hz, hyz⟩ := Finset.one_lt_card.mp (by omega : 1 < (T.erase x).card)
        let A : Finset α := (T.erase x).erase y
        let B : Finset α := (T.erase x).erase z
        have hAcard : A.card = k := by
          rw [Finset.card_erase_of_mem hy, hexcard]
          omega
        have hBcard : B.card = k := by
          rw [Finset.card_erase_of_mem hz, hexcard]
          omega
        have hxA : x ∉ A := by
          simp only [A, Finset.mem_erase]
          tauto
        have hxB : x ∉ B := by
          simp only [B, Finset.mem_erase]
          tauto
        have hAB : A ∪ B = T.erase x := by
          ext w
          simp only [Finset.mem_union, A, B, Finset.mem_erase]
          constructor
          · rintro (⟨-, hwx, hwT⟩ | ⟨-, hwx, hwT⟩)
            · exact ⟨hwx, hwT⟩
            · exact ⟨hwx, hwT⟩
          · rintro ⟨hwx, hwT⟩
            by_cases hwy : w = y
            · refine Or.inr ⟨?_, hwx, hwT⟩
              intro h
              exact hyz (hwy.symm.trans h)
            · exact Or.inl ⟨hwy, hwx, hwT⟩
  6. Construct the request sequence L and prove that an offline schedule feasible for L exists.

    For a chosen x ∈ T, set L = pre ++ tight A 2 ++ tight B 3. We define an explicit schedule that starts at C₀, caches {x} at time 1, A at time 2, B at time 3, and empty thereafter. This schedule never exceeds cache capacity k. Moreover, every request in L is served within its window: x is served at time 1, any other page of T lies in A ∪ B and is served at time 2 or 3, and the tight requests for A and B are served at times 2 and 3 respectively.

    lines 101–131

    uses List.mem_append, Finset.mem_erase, Finset.mem_union.mp

        let L : List (DeadlineRequest α) := pre ++ tight A 2 ++ tight B 3
        let sched : ℕ → Finset α := fun t =>
          if t = 0 then C₀ else if t = 1 then {x} else if t = 2 then A else if t = 3 then B else ∅
        have hsched0 : sched 0 = C₀ := by simp [sched]
        have hschcard : ∀ t, (sched t).card ≤ k := by
          intro t
          simp only [sched]
          split_ifs with h0 h1 h2 h3
          · rw [hC₀]
          · simp; omega
          · rw [hAcard]
          · rw [hBcard]
          · simp
        have hserve : ∀ r ∈ L, ∃ t, r.arrival ≤ t ∧ t ≤ r.deadline ∧ r.page ∈ sched t := by
          intro r hr
          simp only [L, List.mem_append] at hr
          rcases hr with (hr | hr) | hr
          · obtain ⟨hpT, h1, h3⟩ := hpre_mem r hr
            by_cases hpx : r.page = x
            · exact ⟨1, by omega, by omega, by simp [sched, hpx]⟩
            · have hmem : r.page ∈ A ∪ B := by
                rw [hAB]
                simp only [Finset.mem_erase]
                exact ⟨hpx, hpT⟩
              rcases Finset.mem_union.mp hmem with hA | hB
              · exact ⟨2, by omega, by omega, by simpa [sched] using hA⟩
              · exact ⟨3, by omega, by omega, by simpa [sched] using hB⟩
          · obtain ⟨hpA, h1, h3⟩ := htight_mem A 2 hr
            exact ⟨2, by omega, by omega, by simpa [sched] using hpA⟩
          · obtain ⟨hpB, h1, h3⟩ := htight_mem B 3 hr
            exact ⟨3, by omega, by omega, by simpa [sched] using hpB⟩
  7. Any feasible algorithm must cache page x at time 1: x ∈ Alg L 1.

    Because L admits a feasible schedule, `Alg L` must be feasible by `hfeas`. At time 2, the k tight requests for A force the algorithm's cache of size ≤ k to equal A exactly (`Alg L 2 = A`). Similarly, at time 3, tight requests force `Alg L 3 = B`. The request for x arriving at time 1 with deadline 3 must be served at some time t ∈ {1, 2, 3}. But x ∉ A and x ∉ B, so x cannot be served at time 2 or 3; therefore it must be served at time 1, meaning x ∈ Alg L 1.

    lines 132–177

    uses List.mem_append.mpr, Or.inl, Or.inr, Finset.eq_of_subset_of_card_le, Nat.lt_or_ge

        refine ⟨L, sched, ⟨hsched0, hschcard, hserve⟩, ?_, ?_⟩
        · have hAlg := hfeas L ⟨sched, ⟨hsched0, hschcard, hserve⟩⟩
          obtain ⟨-, hAlgcard, hAlgserve⟩ := hAlg
          have hA2 : Alg L 2 = A := by
            have hsub : A ⊆ Alg L 2 := by
              intro p hp
              obtain ⟨r, hr, hpage, h1, h3⟩ := htight_exists A 2 p hp
              have hrL : r ∈ L := by
                simp only [L]
                exact List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inr hr)))
              obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL
              rw [hpage] at htmem
              have ht : t = 2 := by omega
              rwa [ht] at htmem
            symm
            exact Finset.eq_of_subset_of_card_le hsub (by rw [hAcard]; exact hAlgcard 2)
          have hB3 : Alg L 3 = B := by
            have hsub : B ⊆ Alg L 3 := by
              intro p hp
              obtain ⟨r, hr, hpage, h1, h3⟩ := htight_exists B 3 p hp
              have hrL : r ∈ L := by
                simp only [L]
                exact List.mem_append.mpr (Or.inr hr)
              obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL
              rw [hpage] at htmem
              have ht : t = 3 := by omega
              rwa [ht] at htmem
            symm
            exact Finset.eq_of_subset_of_card_le hsub (by rw [hBcard]; exact hAlgcard 3)
          obtain ⟨r, hr, hpage, h1, h3⟩ := hpre_exists x hx
          have hrL : r ∈ L := by
            simp only [L]
            exact List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inl hr)))
          obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL
          rw [hpage] at htmem
          have ht : t = 1 := by
            rcases Nat.lt_or_ge t 2 with h | h
            · omega
            rcases Nat.lt_or_ge t 3 with h' | h'
            · exfalso
              rw [show t = 2 by omega, hA2] at htmem
              exact hxA htmem
            · exfalso
              rw [show t = 3 by omega, hB3] at htmem
              exact hxB htmem
          rwa [ht] at htmem
  8. The sublist of requests in L arriving by time 1 is exactly `pre`.

    Filtering the concatenated list L for requests with arrival time ≤ 1 discards the requests from `tight A 2` and `tight B 3` (which arrive at times 2 and 3), leaving only `pre`.

    lines 178–179

    uses List.filter_append, List.append_nil

        · simp only [L, List.filter_append, htight_filter A 2 (by omega), htight_filter B 3 (by omega),
            List.append_nil, hpre_filter]
  9. All k + 2 pages of T must belong to the algorithm's time-1 cache, yielding k + 2 ≤ k and completing the proof. automation

    Pick x₀ ∈ T (as T is nonempty) and its corresponding instance L₀. Because Alg is online clairvoyant (`hgen`) and every instance L constructed for x ∈ T shares the exact same arrival-time ≤ 1 prefix `pre` as L₀, Alg L 1 = Alg L₀ 1 for all x. Since x ∈ Alg L 1, every x ∈ T must be present in the single cache Alg L₀ 1. Thus T ⊆ Alg L₀ 1, which implies k + 2 = |T| ≤ |Alg L₀ 1| ≤ k. This contradiction (k + 2 ≤ k) is impossible, and `omega` closes the goal.

    lines 180–194

    uses Finset.card_pos.mp, Finset.card_le_card

      -- all instances have the same time-1 cache, so it holds all of `T`
      have hTne : T.Nonempty := Finset.card_pos.mp (by rw [hTcard]; omega)
      obtain ⟨x₀, hx₀⟩ := hTne
      obtain ⟨L₀, sched₀, feas₀, hmem₀, hfilt₀⟩ := key x₀ hx₀
      have hAlgL₀ := hfeas L₀ ⟨sched₀, feas₀⟩
      have hsub : ∀ x ∈ T, x ∈ Alg L₀ 1 := by
        intro x hx
        obtain ⟨L, sched, feas, hmem, hfilt⟩ := key x hx
        have heq : Alg L 1 = Alg L₀ 1 := hgen L L₀ 1 (by rw [hfilt, hfilt₀])
        rw [heq] at hmem
        exact hmem
      have hcardT : T.card ≤ (Alg L₀ 1).card := Finset.card_le_card hsub
      have hkle := hAlgL₀.2.1 1
      have : k + 2 ≤ k := by omega
      omega
Fin.castLE_injective
The canonical embedding Fin.castLE of Fin m into Fin n (for m ≤ n) is injective.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the domain set.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of the type.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
le_refl
The ordering relation ≤ is reflexive: a ≤ a for every a.
List.mem_ofFn.mp
An element of List.ofFn f is in the range of f: there exists an index i such that f i = a.
Finset.mem_image.mpr
If y = f x for some x in a finite set s, then y belongs to the image Finset.image f s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_image.mp
If an element belongs to Finset.image f s, it equals f x for some x ∈ s.
List.mem_ofFn.mpr
If an element is in the range of f : Fin n → α, it belongs to List.ofFn f.
List.mem_map.mp
If an element belongs to List.map f l, it equals f a for some a ∈ l.
Finset.mem_val
An element belongs to a finset s if and only if it belongs to its underlying multiset s.val.
Multiset.mem_toList
An element belongs to the list representation of a multiset if and only if it belongs to the multiset.
List.mem_map.mpr
If a ∈ l, then f a belongs to List.map f l.
Multiset.mem_toList.mpr
If an element belongs to a multiset, it belongs to the multiset's list representation.
List.filter_eq_nil_iff
Filtering a list by a boolean predicate yields the empty list if and only if no element in the list satisfies the predicate.
List.filter_eq_self
Filtering a list by a boolean predicate yields the list itself if and only if every element in the list satisfies the predicate.
Finset.card_erase_of_mem
Erasing an element from a finite set that contains it decreases the set's cardinality by 1.
Finset.one_lt_card.mp
A finite set with cardinality strictly greater than 1 contains at least two distinct elements.
Finset.mem_erase
An element belongs to s.erase a if and only if it is not equal to a and belongs to s.
Finset.mem_union
An element belongs to s ∪ t if and only if it belongs to s or to t.
Or.inr
Constructs a proof of A ∨ B from a proof of the right disjunct B.
Or.inl
Constructs a proof of A ∨ B from a proof of the left disjunct A.
List.mem_append
An element belongs to the concatenation s ++ t if and only if it belongs to s or to t.
Finset.mem_union.mp
If an element belongs to the union s ∪ t, then it belongs to s or to t.
List.mem_append.mpr
If an element belongs to s or to t, it belongs to the concatenation s ++ t.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.
Nat.lt_or_ge
For any two natural numbers n and m, either n < m or n ≥ m.
List.filter_append
Filtering a concatenated list distributes over the concatenation: filter p (l₁ ++ l₂) = filter p l₁ ++ filter p l₂.
List.append_nil
Appending the empty list to any list returns the list unchanged.
Finset.card_pos.mp
If a finite set has strictly positive cardinality, then it is nonempty.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is less than or equal to the other's cardinality.

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

/-- Deterministic lower bound of k + 1/2 on at least two holes. -/theorem deadline_paging_lower_bound_k_plus_half    (k : ℕ) (hk : 1 ≤ k) {α : Type*} [Fintype α] [DecidableEq α] (hn : k + 2 ≤ Fintype.card α)    (C₀ : Finset α) (hC₀ : C₀.card = k)    (Alg : List (DeadlineRequest α) → (ℕ → Finset α))    (ρ : ℝ) (hρ : IsCompetitiveRatio k C₀ Alg ρ) :    (k : ℝ) + 1 / 2 ≤ ρ := by  classical  obtain ⟨hgen, hfeas, -⟩ := hρ  -- an enumeration of k+2 distinct pages  let e : Fin (k + 2) → α := fun i => (Fintype.equivFin α).symm (Fin.castLE hn i)  have he_inj : Function.Injective e := by    intro i j hij    exact Fin.castLE_injective hn ((Fintype.equivFin α).symm.injective hij)  let T : Finset α := Finset.univ.image e  have hTcard : T.card = k + 2 := by    show (Finset.univ.image e).card = k + 2    rw [Finset.card_image_of_injective _ he_inj, Finset.card_univ, Fintype.card_fin]  let h13 : 1 ≤ 3 := by norm_num  -- the common prefix: every page of `T` is requested with window [1,3]  let pre : List (DeadlineRequest α) :=    List.ofFn (fun i : Fin (k+2) => (⟨e i, 1, 3, h13⟩ : DeadlineRequest α))  -- tight requests for all pages of `S` at time `t`  let tight : Finset α → ℕ → List (DeadlineRequest α) :=    fun S t => S.val.toList.map (fun p => (⟨p, t, t, le_refl t⟩ : DeadlineRequest α))  have hpre_mem : ∀ r ∈ pre, r.page ∈ T ∧ r.arrival = 1 ∧ r.deadline = 3 := by    intro r hr    obtain ⟨i, hi⟩ := List.mem_ofFn.mp hr    rw [← hi]    exact ⟨Finset.mem_image.mpr ⟨i, Finset.mem_univ i, rfl⟩, rfl, rfl⟩  have hpre_exists : ∀ p ∈ T, ∃ r ∈ pre, r.page = p ∧ r.arrival = 1 ∧ r.deadline = 3 := by    intro p hp    obtain ⟨i, -, hi⟩ := Finset.mem_image.mp hp    exact ⟨⟨e i, 1, 3, h13⟩, List.mem_ofFn.mpr ⟨i, rfl⟩, hi, rfl, rfl⟩  have htight_mem : ∀ (S : Finset α) (t : ℕ) {r : DeadlineRequest α}, r ∈ tight S t →      r.page ∈ S ∧ r.arrival = t ∧ r.deadline = t := by    intro S t r hr    obtain ⟨p, hp, hpr⟩ := List.mem_map.mp hr    have hpS : p ∈ S := by      rw [← Finset.mem_val, ← Multiset.mem_toList]      exact hp    rw [← hpr]    exact ⟨hpS, rfl, rfl⟩  have htight_exists : ∀ (S : Finset α) (t : ℕ), ∀ p ∈ S,      ∃ r ∈ tight S t, r.page = p ∧ r.arrival = t ∧ r.deadline = t := by    intro S t p hp    exact ⟨⟨p, t, t, le_refl t⟩,      List.mem_map.mpr ⟨p, Multiset.mem_toList.mpr (by rwa [Finset.mem_val]), rfl⟩, rfl, rfl, rfl⟩  have htight_filter : ∀ (S : Finset α) (t : ℕ), 1 < t →      List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) (tight S t) = [] := by    intro S t ht    rw [List.filter_eq_nil_iff]    intro r hr    obtain ⟨-, h1, -⟩ := htight_mem S t hr    rw [h1]    simp    omega  have hpre_filter :      List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) pre = pre := by    rw [List.filter_eq_self]    intro r hr    obtain ⟨-, h1, -⟩ := hpre_mem r hr    rw [h1]    simp  -- for each x in T: a feasible instance whose time-1 cache (after the common prefix) holds x  have key : ∀ x ∈ T, ∃ (L : List (DeadlineRequest α)) (sched : ℕ → Finset α),      IsFeasibleSchedule k C₀ sched L ∧ x ∈ Alg L 1 ∧        List.filter (fun r : DeadlineRequest α => decide (r.arrival ≤ 1)) L = pre := by    intro x hx    have hexcard : (T.erase x).card = k + 1 := by      rw [Finset.card_erase_of_mem hx, hTcard]      omega    obtain ⟨y, hy, z, hz, hyz⟩ := Finset.one_lt_card.mp (by omega : 1 < (T.erase x).card)    let A : Finset α := (T.erase x).erase y    let B : Finset α := (T.erase x).erase z    have hAcard : A.card = k := by      rw [Finset.card_erase_of_mem hy, hexcard]      omega    have hBcard : B.card = k := by      rw [Finset.card_erase_of_mem hz, hexcard]      omega    have hxA : x ∉ A := by      simp only [A, Finset.mem_erase]      tauto    have hxB : x ∉ B := by      simp only [B, Finset.mem_erase]      tauto    have hAB : A ∪ B = T.erase x := by      ext w      simp only [Finset.mem_union, A, B, Finset.mem_erase]      constructor      · rintro (⟨-, hwx, hwT⟩ | ⟨-, hwx, hwT⟩)        · exact ⟨hwx, hwT⟩        · exact ⟨hwx, hwT⟩      · rintro ⟨hwx, hwT⟩        by_cases hwy : w = y        · refine Or.inr ⟨?_, hwx, hwT⟩          intro h          exact hyz (hwy.symm.trans h)        · exact Or.inl ⟨hwy, hwx, hwT⟩    let L : List (DeadlineRequest α) := pre ++ tight A 2 ++ tight B 3    let sched : ℕ → Finset α := fun t =>      if t = 0 then C₀ else if t = 1 then {x} else if t = 2 then A else if t = 3 then B else ∅    have hsched0 : sched 0 = C₀ := by simp [sched]    have hschcard : ∀ t, (sched t).card ≤ k := by      intro t      simp only [sched]      split_ifs with h0 h1 h2 h3      · rw [hC₀]      · simp; omega      · rw [hAcard]      · rw [hBcard]      · simp    have hserve : ∀ r ∈ L, ∃ t, r.arrival ≤ t ∧ t ≤ r.deadline ∧ r.page ∈ sched t := by      intro r hr      simp only [L, List.mem_append] at hr      rcases hr with (hr | hr) | hr      · obtain ⟨hpT, h1, h3⟩ := hpre_mem r hr        by_cases hpx : r.page = x        · exact ⟨1, by omega, by omega, by simp [sched, hpx]⟩        · have hmem : r.page ∈ A ∪ B := by            rw [hAB]            simp only [Finset.mem_erase]            exact ⟨hpx, hpT⟩          rcases Finset.mem_union.mp hmem with hA | hB          · exact ⟨2, by omega, by omega, by simpa [sched] using hA⟩          · exact ⟨3, by omega, by omega, by simpa [sched] using hB⟩      · obtain ⟨hpA, h1, h3⟩ := htight_mem A 2 hr        exact ⟨2, by omega, by omega, by simpa [sched] using hpA⟩      · obtain ⟨hpB, h1, h3⟩ := htight_mem B 3 hr        exact ⟨3, by omega, by omega, by simpa [sched] using hpB⟩    refine ⟨L, sched, ⟨hsched0, hschcard, hserve⟩, ?_, ?_⟩    · have hAlg := hfeas L ⟨sched, ⟨hsched0, hschcard, hserve⟩⟩      obtain ⟨-, hAlgcard, hAlgserve⟩ := hAlg      have hA2 : Alg L 2 = A := by        have hsub : A ⊆ Alg L 2 := by          intro p hp          obtain ⟨r, hr, hpage, h1, h3⟩ := htight_exists A 2 p hp          have hrL : r ∈ L := by            simp only [L]            exact List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inr hr)))          obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL          rw [hpage] at htmem          have ht : t = 2 := by omega          rwa [ht] at htmem        symm        exact Finset.eq_of_subset_of_card_le hsub (by rw [hAcard]; exact hAlgcard 2)      have hB3 : Alg L 3 = B := by        have hsub : B ⊆ Alg L 3 := by          intro p hp          obtain ⟨r, hr, hpage, h1, h3⟩ := htight_exists B 3 p hp          have hrL : r ∈ L := by            simp only [L]            exact List.mem_append.mpr (Or.inr hr)          obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL          rw [hpage] at htmem          have ht : t = 3 := by omega          rwa [ht] at htmem        symm        exact Finset.eq_of_subset_of_card_le hsub (by rw [hBcard]; exact hAlgcard 3)      obtain ⟨r, hr, hpage, h1, h3⟩ := hpre_exists x hx      have hrL : r ∈ L := by        simp only [L]        exact List.mem_append.mpr (Or.inl (List.mem_append.mpr (Or.inl hr)))      obtain ⟨t, ht1, ht2, htmem⟩ := hAlgserve r hrL      rw [hpage] at htmem      have ht : t = 1 := by        rcases Nat.lt_or_ge t 2 with h | h        · omega        rcases Nat.lt_or_ge t 3 with h' | h'        · exfalso          rw [show t = 2 by omega, hA2] at htmem          exact hxA htmem        · exfalso          rw [show t = 3 by omega, hB3] at htmem          exact hxB htmem      rwa [ht] at htmem    · simp only [L, List.filter_append, htight_filter A 2 (by omega), htight_filter B 3 (by omega),        List.append_nil, hpre_filter]  -- all instances have the same time-1 cache, so it holds all of `T`  have hTne : T.Nonempty := Finset.card_pos.mp (by rw [hTcard]; omega)  obtain ⟨x₀, hx₀⟩ := hTne  obtain ⟨L₀, sched₀, feas₀, hmem₀, hfilt₀⟩ := key x₀ hx₀  have hAlgL₀ := hfeas L₀ ⟨sched₀, feas₀⟩  have hsub : ∀ x ∈ T, x ∈ Alg L₀ 1 := by    intro x hx    obtain ⟨L, sched, feas, hmem, hfilt⟩ := key x hx    have heq : Alg L 1 = Alg L₀ 1 := hgen L L₀ 1 (by rw [hfilt, hfilt₀])    rw [heq] at hmem    exact hmem  have hcardT : T.card ≤ (Alg L₀ 1).card := Finset.card_le_card hsub  have hkle := hAlgL₀.2.1 1  have : k + 2 ≤ k := by omega  omega
See it in the graphDiscuss this resultChallenge it