not_deadline_paging_upper_bound_k_plus_one
The statement deadline_paging_upper_bound_k_plus_one is false: The statement (for every k≥1, every finite α with card ≥ k+1, every C₀ of size k, there is an online Alg that is feasible on every feasible instance and (k+1)-competitive) is FALSE already for k=1, |α|=3, |C₀|=1. The failure is not about the ratio at all: the *feasibility* conjunct of IsCompetitiveRatio is unsatisfiable, because IsOnlineClairvoyantScheduleGen forces the algorithm to commit to the same cache at time 1 on two different feasible instances whose feasibility requires contradictory contents at time 1.
Concretely take α = 3 pages {q0,q1,q2}, C₀={q0}, k=1, and consider two request lists (written (page,arrival,deadline)):
reqsB = [(q0,0,0),(q2,0,2),(q1,0,2),(q1,2,2)]
reqsC = [(q0,0,0),(q2,0,2),(q1,0,2),(q2,2,2)]
Both are feasible (k=1):
reqsB served by cache sequence q0 (t=0), q2 (t=1), q1 (t=2);
reqsC served by q0 (t=0), q1 (t=1), q2 (t=2).
Their arrival-≤-1 filters are identical (the last request of each has arrival 2), so IsOnlineClairvoyantScheduleGen forces Alg reqsB 1 = Alg reqsC 1.
On the one hand, feasibility of Alg reqsB for reqsB: the request (q1,2,2) forces q1 ∈ Alg reqsB 2, hence (card ≤ 1) Alg reqsB 2 = {q1}; then (q2,0,2) forces q2 ∈ Alg reqsB t for some t∈{0,1,2}, and since Alg reqsB 0 = {q0} and Alg reqsB 2 = {q1}, we get q2 ∈ Alg reqsB 1.
On the other hand, feasibility of Alg reqsC for reqsC: (q2,2,2) forces Alg reqsC 2 = {q2}; then (q1,0,2) forces q1 ∈ Alg reqsC t for some t∈{0,1,2}, and since Alg reqsC 0={q0} and Alg reqsC 2={q2}, we get q1 ∈ Alg reqsC 1 = Alg reqsB 1.
Thus both q1 and q2 lie in Alg reqsB 1, contradicting card(Alg reqsB 1) ≤ 1. So no Alg satisfies the feasibility conjunct, hence none is (ρ)-competitive for any ρ.
This is a genuine contradiction in the Lean definitions (fetch-only cost, hard deadlines), independent of the (k+1) bound; it likely stems from the combination of IsOnlineClairvoyantScheduleGen (which filters only by arrival) with the requirement of feasibility on all feasible instances. A verified Lean proof of the negation is provided; it instantiates the counterexample using ULift(Fin 3) so it holds at an arbitrary universe level.
Statement
theorem not_deadline_paging_upper_bound_k_plus_one : ¬ (∀ (k : ℕ) (hk : 1 ≤ k) {α : Type*} [Fintype α] [DecidableEq α] (hn : k + 1 ≤ Fintype.card α) (C₀ : Finset α) (hC₀ : C₀.card = k), ∃ (Alg : List (DeadlineRequest α) → (ℕ → Finset α)), IsCompetitiveRatio k C₀ Alg (k + 1 : ℝ))
- Related work
- refutes `deadline_paging_upper_bound_k_plus_one`
- 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…
The proof, explained
We prove by contradiction that no online algorithm can satisfy the deadline paging competitiveness specification. Assuming such an algorithm exists, we specialize to cache capacity k = 1 and three pages {q0, q1, q2} with initial cache {q0}, and construct two feasible request sequences that are identical up to time 1 but diverge at time 2. Feasibility forces the algorithm's cache at time 1 to contain q2 on the first sequence and q1 on the second, yet the online clairvoyant condition requires the cache at time 1 to be identical in both runs, forcing two distinct pages into a cache of size 1 and giving a contradiction.
Assuming the upper bound holds, there is an online clairvoyant algorithm Alg that produces feasible schedules of size k = 1 starting from initial cache {q0} for all feasible instances on a 3-element page set.
We assume the universal statement for contradiction. We instantiate it with cache capacity k = 1, page universe α = ULift (Fin 3), and initial cache C₀ = {q0}. Verifying 1 ≤ k, k + 1 ≤ |α|, and |C₀| = k yields an algorithm Alg satisfying the competitive ratio predicate: it is online clairvoyant, feasible on every feasible instance, and cost-bounded.
uses
le_reflclassical intro h let q0 : ULift (Fin 3) := ULift.up 0 let q1 : ULift (Fin 3) := ULift.up 1 let q2 : ULift (Fin 3) := ULift.up 2 obtain ⟨Alg, hgen, hfeas, hcost⟩ := h 1 (le_refl 1) (α := ULift (Fin 3)) (by simp) ({q0} : Finset (ULift (Fin 3))) (by simp [q0])
Two request sequences, reqsB and reqsC, and candidate schedules, schedB and schedC, are defined.
We define five requests: a = (q0, 0, 0), b = (q2, 0, 2), c = (q1, 0, 2), dB = (q1, 2, 2), and dC = (q2, 2, 2). From these we form two sequences reqsB = [a, b, c, dB] and reqsC = [a, b, c, dC], which differ only in the final request arriving at time 2. We also define two candidate schedules: schedB (holding {q0} at t = 0, {q2} at t = 1, and {q1} at t ≥ 2) and schedC (holding {q0} at t = 0, {q1} at t = 1, and {q2} at t ≥ 2).
uses
le_refllet a : DeadlineRequest (ULift (Fin 3)) := ⟨q0, 0, 0, le_refl 0⟩ let b : DeadlineRequest (ULift (Fin 3)) := ⟨q2, 0, 2, by decide⟩ let c : DeadlineRequest (ULift (Fin 3)) := ⟨q1, 0, 2, by decide⟩ let dB : DeadlineRequest (ULift (Fin 3)) := ⟨q1, 2, 2, by decide⟩ let dC : DeadlineRequest (ULift (Fin 3)) := ⟨q2, 2, 2, by decide⟩ let reqsB : List (DeadlineRequest (ULift (Fin 3))) := [a, b, c, dB] let reqsC : List (DeadlineRequest (ULift (Fin 3))) := [a, b, c, dC] let schedB : ℕ → Finset (ULift (Fin 3)) := fun t => if t = 0 then {q0} else if t = 1 then {q2} else {q1} let schedC : ℕ → Finset (ULift (Fin 3)) := fun t => if t = 0 then {q0} else if t = 1 then {q1} else {q2}
The request sequence reqsB has a feasible schedule of cache size 1 starting from {q0}.
The candidate schedule schedB witnesses feasibility for reqsB: its initial cache is {q0}, its cardinality is 1 at every time step, and it serves each of the four requests in reqsB within its arrival-to-deadline window (a at t = 0, b at t = 1, c at t = 2, and dB at t = 2).
uses
List.mem_cons,List.not_mem_nil,or_falsehave feasB : ∃ opt, IsFeasibleSchedule 1 ({q0} : Finset (ULift (Fin 3))) opt reqsB := by refine ⟨schedB, ?_, ?_, ?_⟩ · simp [schedB] · intro t; dsimp only [schedB]; split_ifs <;> simp · intro r hr simp only [reqsB, List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl · exact ⟨0, by simp [a], by simp [a], by simp [a, schedB]⟩ · exact ⟨1, by simp [b], by simp [b], by simp [b, schedB]⟩ · exact ⟨2, by simp [c], by simp [c], by simp [c, schedB]⟩ · exact ⟨2, by simp [dB], by simp [dB], by simp [dB, schedB]⟩
The request sequence reqsC has a feasible schedule of cache size 1 starting from {q0}.
Similarly, schedC witnesses feasibility for reqsC: it starts at {q0}, has cache size 1 at every time step, and serves each request in its valid window (a at t = 0, b at t = 2, c at t = 1, and dC at t = 2).
uses
List.mem_cons,List.not_mem_nil,or_falsehave feasC : ∃ opt, IsFeasibleSchedule 1 ({q0} : Finset (ULift (Fin 3))) opt reqsC := by refine ⟨schedC, ?_, ?_, ?_⟩ · simp [schedC] · intro t; dsimp only [schedC]; split_ifs <;> simp · intro r hr simp only [reqsC, List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl · exact ⟨0, by simp [a], by simp [a], by simp [a, schedC]⟩ · exact ⟨2, by simp [b], by simp [b], by simp [b, schedC]⟩ · exact ⟨1, by simp [c], by simp [c], by simp [c, schedC]⟩ · exact ⟨2, by simp [dC], by simp [dC], by simp [dC, schedC]⟩
Alg produces feasible schedules on both reqsB and reqsC.
Because both instances admit feasible schedules, the feasibility guarantee of Alg implies that Alg reqsB and Alg reqsC are both feasible schedules: each starts with cache {q0}, has size at most 1 at all times, and serves every request by its deadline.
have hFB := hfeas reqsB feasB have hFC := hfeas reqsC feasC obtain ⟨h0B, hcardB, hserveB⟩ := hFB obtain ⟨h0C, hcardC, hserveC⟩ := hFC
On reqsB, the algorithm's cache at time 2 is precisely {q1}.
The request dB = (q1, 2, 2) has arrival 2 and deadline 2, so it must be served at time t = 2, forcing q1 ∈ Alg reqsB 2. Since the cache has size at most 1, containing q1 forces the entire cache at time 2 to equal the singleton {q1}.
uses
Finset.eq_singleton_iff_unique_mem,Finset.card_le_one.mphave hmem1 : q1 ∈ Alg reqsB 2 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveB dB (by simp [reqsB]) simp only [dB] at ht1 ht2 hmem have ht : t = 2 := by omega simpa [ht] using hmem have hEq1 : Alg reqsB 2 = {q1} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hmem1, fun x hx => Finset.card_le_one.mp (hcardB 2) x hx q1 hmem1⟩
On reqsC, the algorithm's cache at time 2 is precisely {q2}.
The request dC = (q2, 2, 2) must be served at time 2, forcing q2 ∈ Alg reqsC 2. Because the cache capacity is at most 1, the cache at time 2 must equal {q2}.
uses
Finset.eq_singleton_iff_unique_mem,Finset.card_le_one.mphave hmem2C : q2 ∈ Alg reqsC 2 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveC dC (by simp [reqsC]) simp only [dC] at ht1 ht2 hmem have ht : t = 2 := by omega simpa [ht] using hmem have hEq2 : Alg reqsC 2 = {q2} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hmem2C, fun x hx => Finset.card_le_one.mp (hcardC 2) x hx q2 hmem2C⟩
On reqsB, the algorithm's cache at time 1 must contain q2.
The request b = (q2, 0, 2) must be served at some integer time t ∈ [0, 2]. We check each case: at t = 0 the cache is {q0} (which does not contain q2), and at t = 2 the cache is {q1} (which does not contain q2). Thus the request must be served at t = 1, giving q2 ∈ Alg reqsB 1.
have hB1 : q2 ∈ Alg reqsB 1 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveB b (by simp [reqsB]) simp only [b] at ht1 ht2 hmem interval_cases t · rw [h0B] at hmem; simp [q0, q2] at hmem · exact hmem · rw [hEq1] at hmem; simp [q1, q2] at hmem
On reqsC, the algorithm's cache at time 1 must contain q1.
The request c = (q1, 0, 2) must be served at some time t ∈ [0, 2]. At t = 0 the cache is {q0} and at t = 2 the cache is {q2}, neither of which contains q1. Therefore, it must be served at t = 1, so q1 ∈ Alg reqsC 1.
have hC1 : q1 ∈ Alg reqsC 1 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveC c (by simp [reqsC]) simp only [c] at ht1 ht2 hmem interval_cases t · rw [h0C] at hmem; simp [q0, q1] at hmem · exact hmem · rw [hEq2] at hmem; simp [q1, q2] at hmem
The algorithm's cache at time 1 on reqsB must also contain q1.
Filtering each request list to arrivals at or before time 1 gives the identical sublist [a, b, c], since dB and dC only arrive at time 2. By the online clairvoyant property IsOnlineClairvoyantScheduleGen, Alg reqsB 1 = Alg reqsC 1. Since q1 ∈ Alg reqsC 1, we obtain q1 ∈ Alg reqsB 1.
have hfilt : List.filter (fun r => decide (r.arrival ≤ 1)) reqsB = List.filter (fun r => decide (r.arrival ≤ 1)) reqsC := by simp [reqsB, reqsC, a, b, c, dB, dC] have heq := hgen reqsB reqsC 1 hfilt have hC1' : q1 ∈ Alg reqsB 1 := by rw [heq]; exact hC1
Contradiction: the algorithm cannot exist.
The cache Alg reqsB 1 has capacity at most 1, yet it contains both q1 and q2. By Finset.card_le_one.mp, this implies q1 = q2, which is impossible since q1 and q2 correspond to distinct elements 1 and 2 in Fin 3.
uses
Finset.card_le_one.mphave huniq : q1 = q2 := Finset.card_le_one.mp (hcardB 1) q1 hC1' q2 hB1 exact absurd huniq (by simp [q1, q2])
le_refl- Every element in a preorder is less than or equal to itself: a ≤ a.
List.mem_cons- An element belongs to a prepended list b :: l if and only if it equals the head b or belongs to the tail l.
List.not_mem_nil- The empty list contains no elements.
or_false- Disjunction with false simplifies to the proposition itself: (P ∨ False) = P.
Finset.eq_singleton_iff_unique_mem- A finite set equals the singleton {a} if and only if a belongs to the set and every element in the set equals a.
Finset.card_le_one.mp- If a finite set has cardinality at most 1, any two elements in it are equal.
- The competitive ratio factor k + 1 and the cost function play no role in the refutation; the contradiction arises solely from the combination of the feasibility requirement on all feasible instances with the online condition IsOnlineClairvoyantScheduleGen.
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.
theorem not_deadline_paging_upper_bound_k_plus_one : ¬ (∀ (k : ℕ) (hk : 1 ≤ k) {α : Type*} [Fintype α] [DecidableEq α] (hn : k + 1 ≤ Fintype.card α) (C₀ : Finset α) (hC₀ : C₀.card = k), ∃ (Alg : List (DeadlineRequest α) → (ℕ → Finset α)), IsCompetitiveRatio k C₀ Alg (k + 1 : ℝ)) := by classical intro h let q0 : ULift (Fin 3) := ULift.up 0 let q1 : ULift (Fin 3) := ULift.up 1 let q2 : ULift (Fin 3) := ULift.up 2 obtain ⟨Alg, hgen, hfeas, hcost⟩ := h 1 (le_refl 1) (α := ULift (Fin 3)) (by simp) ({q0} : Finset (ULift (Fin 3))) (by simp [q0]) let a : DeadlineRequest (ULift (Fin 3)) := ⟨q0, 0, 0, le_refl 0⟩ let b : DeadlineRequest (ULift (Fin 3)) := ⟨q2, 0, 2, by decide⟩ let c : DeadlineRequest (ULift (Fin 3)) := ⟨q1, 0, 2, by decide⟩ let dB : DeadlineRequest (ULift (Fin 3)) := ⟨q1, 2, 2, by decide⟩ let dC : DeadlineRequest (ULift (Fin 3)) := ⟨q2, 2, 2, by decide⟩ let reqsB : List (DeadlineRequest (ULift (Fin 3))) := [a, b, c, dB] let reqsC : List (DeadlineRequest (ULift (Fin 3))) := [a, b, c, dC] let schedB : ℕ → Finset (ULift (Fin 3)) := fun t => if t = 0 then {q0} else if t = 1 then {q2} else {q1} let schedC : ℕ → Finset (ULift (Fin 3)) := fun t => if t = 0 then {q0} else if t = 1 then {q1} else {q2} have feasB : ∃ opt, IsFeasibleSchedule 1 ({q0} : Finset (ULift (Fin 3))) opt reqsB := by refine ⟨schedB, ?_, ?_, ?_⟩ · simp [schedB] · intro t; dsimp only [schedB]; split_ifs <;> simp · intro r hr simp only [reqsB, List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl · exact ⟨0, by simp [a], by simp [a], by simp [a, schedB]⟩ · exact ⟨1, by simp [b], by simp [b], by simp [b, schedB]⟩ · exact ⟨2, by simp [c], by simp [c], by simp [c, schedB]⟩ · exact ⟨2, by simp [dB], by simp [dB], by simp [dB, schedB]⟩ have feasC : ∃ opt, IsFeasibleSchedule 1 ({q0} : Finset (ULift (Fin 3))) opt reqsC := by refine ⟨schedC, ?_, ?_, ?_⟩ · simp [schedC] · intro t; dsimp only [schedC]; split_ifs <;> simp · intro r hr simp only [reqsC, List.mem_cons, List.not_mem_nil, or_false] at hr rcases hr with rfl | rfl | rfl | rfl · exact ⟨0, by simp [a], by simp [a], by simp [a, schedC]⟩ · exact ⟨2, by simp [b], by simp [b], by simp [b, schedC]⟩ · exact ⟨1, by simp [c], by simp [c], by simp [c, schedC]⟩ · exact ⟨2, by simp [dC], by simp [dC], by simp [dC, schedC]⟩ have hFB := hfeas reqsB feasB have hFC := hfeas reqsC feasC obtain ⟨h0B, hcardB, hserveB⟩ := hFB obtain ⟨h0C, hcardC, hserveC⟩ := hFC have hmem1 : q1 ∈ Alg reqsB 2 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveB dB (by simp [reqsB]) simp only [dB] at ht1 ht2 hmem have ht : t = 2 := by omega simpa [ht] using hmem have hEq1 : Alg reqsB 2 = {q1} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hmem1, fun x hx => Finset.card_le_one.mp (hcardB 2) x hx q1 hmem1⟩ have hmem2C : q2 ∈ Alg reqsC 2 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveC dC (by simp [reqsC]) simp only [dC] at ht1 ht2 hmem have ht : t = 2 := by omega simpa [ht] using hmem have hEq2 : Alg reqsC 2 = {q2} := by rw [Finset.eq_singleton_iff_unique_mem] exact ⟨hmem2C, fun x hx => Finset.card_le_one.mp (hcardC 2) x hx q2 hmem2C⟩ have hB1 : q2 ∈ Alg reqsB 1 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveB b (by simp [reqsB]) simp only [b] at ht1 ht2 hmem interval_cases t · rw [h0B] at hmem; simp [q0, q2] at hmem · exact hmem · rw [hEq1] at hmem; simp [q1, q2] at hmem have hC1 : q1 ∈ Alg reqsC 1 := by obtain ⟨t, ht1, ht2, hmem⟩ := hserveC c (by simp [reqsC]) simp only [c] at ht1 ht2 hmem interval_cases t · rw [h0C] at hmem; simp [q0, q1] at hmem · exact hmem · rw [hEq2] at hmem; simp [q1, q2] at hmem have hfilt : List.filter (fun r => decide (r.arrival ≤ 1)) reqsB = List.filter (fun r => decide (r.arrival ≤ 1)) reqsC := by simp [reqsB, reqsC, a, b, c, dB, dC] have heq := hgen reqsB reqsC 1 hfilt have hC1' : q1 ∈ Alg reqsB 1 := by rw [heq]; exact hC1 have huniq : q1 = q2 := Finset.card_le_one.mp (hcardB 1) q1 hC1' q2 hB1 exact absurd huniq (by simp [q1, q2])