deadline_paging_lower_bound_k_plus_half
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.
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.
classical obtain ⟨hgen, hfeas, -⟩ := hρ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)`.
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]
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 ⊆ α.
uses
le_refllet 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 α))
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.
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_selfhave 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 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}.
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⟩
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.
uses
List.mem_append,Finset.mem_erase,Finset.mem_union.mplet 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⟩
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.
uses
List.mem_append.mpr,Or.inl,Or.inr,Finset.eq_of_subset_of_card_le,Nat.lt_or_gerefine ⟨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
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`.
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]
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.
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.
- The theorem is stated as a competitive ratio lower bound (ρ ≥ k + 1/2), but the proof actually establishes that no online clairvoyant schedule generator can produce a feasible schedule on all feasible request instances when |α| ≥ k + 2. The lower bound on ρ holds vacuously by contradiction (ex falso quodlibet) from k + 2 ≤ k.
- Linear arithmetic goals and case exclusions (such as establishing t = 1 given t ∈ [1, 3] and t ∉ {2, 3}, and the final contradiction k + 2 ≤ k) are closed automatically by the `omega` decision procedure.
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.
/-- 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