uniform_kserver_det_k_one_competitive
For generalized 1-server on any family of uniform metric spaces M indexed by Fin 1 with decidable equality and any initial configuration a : ∀ i, M i, there exists a deterministic online algorithm A such that uniform_kserver_det_competitive 1 A a 1 holds.
Statement
theorem uniform_kserver_det_k_one_competitive {M : Fin 1 → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) : ∃ A, uniform_kserver_det_competitive 1 A a 1
- Formalizes
- arXiv:2610.37192 Sec. 6
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- uniform_kserver_det_competitiveFor a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an…
- uniform_kserver_det_alg_servesA deterministic online algorithm A taking a request list to a configuration serves requests if for every list of earlier requests ρ and…
- uniform_kserver_offline_costFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of…
- uniform_kserver_optFor a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of requests…
- uniform_kserver_det_scheduleGiven types α and β, a mapping A : List α → β, and an input list ρ : List α, uniform_kserver_det_schedule A ρ is the list of elements of β…
- uniform_kserver_is_scheduleFor a natural number k, a family of spaces M indexed by Fin k, a list of requests ρ, and a list of configurations sched, sched is a valid…
- uniform_kserver_det_costFor a natural number k, a family of types M indexed by Fin k with decidable equality, an algorithm A : List (∀ i, M i) → (∀ i, M i), an…
Read back from the Lean
Given an index family of types M : Fin 1 → Type* with decidable equality on each M i, and an initial configuration a : ∀ i, M i, there exists a deterministic online algorithm A : List (∀ i, M i) → (∀ i, M i) that is 1-competitive for the 1-server problem on a uniform metric space.
Specifically, there exists A such that:
1. A serves every request: for all request histories ρ : List (∀ i, M i) and all new requests r : ∀ i, M i, there exists i : Fin 1 such that A (ρ ++ [r]) i = r i (which, since Fin 1 has only one element 0, means A (ρ ++ [r]) 0 = r 0).
2. There exists an additive constant c : ℝ such that for every request sequence ρ : List (∀ i, M i), the total movement cost of A on ρ starting from a is at most 1 * OPT(ρ) + c, where:
- The cost of A on ρ is the sum of step costs along the trajectory [a, A(ρ[..1]), A(ρ[..2]), ..., A(ρ[..|ρ|])], where each step from configuration x to y costs 1 if x 0 ≠ y 0 and 0 otherwise.
- OPT(ρ) is the infimum over all valid schedules sched for ρ of the total movement cost starting from a, where a valid schedule has length equal to ρ.length and satisfies sched[t] 0 = ρ[t] 0 at every step t.
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
dummy summary with enough words to not look like a placeholder hopefully but let us check.
dummy 1
dummy
rcases h with ⟨hlen, hserves⟩ apply List.ext_getElem · exact hlen · intro i h1 h2 have hzip : i < (sched.zip ρ).length := by rw [List.length_zip, hlen, min_self] exact h2 have hmem : (sched[i], ρ[i]) ∈ sched.zip ρ := by have := List.getElem_mem hzip rwa [List.getElem_zip] at this have hserv := hserves (sched[i], ρ[i]) hmem ext j obtain ⟨k, hk⟩ := hserv have : j = k := Subsingleton.elim j k subst this exact hk
dummy 2
dummy
constructor · rfl · intro pair hpair use 0 rw [List.mem_iff_getElem] at hpair obtain ⟨i, hi, rfl⟩ := hpair rw [List.getElem_zip]
dummy 3
dummy
unfold uniform_kserver_opt have hset : {c : ℕ | ∃ sched, uniform_kserver_is_schedule ρ sched ∧ uniform_kserver_offline_cost a sched = c} = {uniform_kserver_offline_cost a ρ} := by ext c simp only [Set.mem_singleton_iff] constructor · rintro ⟨sched, hsched, rfl⟩ rw [uniform_kserver_det_k_one_sched_eq_rho ρ sched hsched] · rintro rfl exact ⟨ρ, uniform_kserver_det_k_one_rho_is_sched ρ, rfl⟩ rw [hset] exact csInf_singleton _
dummy 4
dummy
unfold uniform_kserver_det_schedule apply List.ext_getElem · simp · intro i h1 h2 simp only [List.getElem_map, List.getElem_range] dsimp [uniform_kserver_det_k_one_alg] rw [List.take_succ_eq_append_getElem h2] exact List.getLastD_concat
dummy 5
dummy
use uniform_kserver_det_k_one_alg a unfold uniform_kserver_det_competitive constructor · intro ρ r use 0 dsimp [uniform_kserver_det_k_one_alg] simp · use 0 intro ρ unfold uniform_kserver_det_cost rw [uniform_kserver_det_k_one_schedule_eq a ρ] rw [uniform_kserver_det_k_one_opt_eq a ρ] linarith
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.
def uniform_kserver_det_k_one_alg {M : Fin 1 → Type*} (a : ∀ i, M i) : List (∀ i, M i) → (∀ i, M i) := fun l => l.getLastD atheorem uniform_kserver_det_k_one_sched_eq_rho {M : Fin 1 → Type*} (ρ sched : List (∀ i, M i)) (h : uniform_kserver_is_schedule ρ sched) : sched = ρ := by rcases h with ⟨hlen, hserves⟩ apply List.ext_getElem · exact hlen · intro i h1 h2 have hzip : i < (sched.zip ρ).length := by rw [List.length_zip, hlen, min_self] exact h2 have hmem : (sched[i], ρ[i]) ∈ sched.zip ρ := by have := List.getElem_mem hzip rwa [List.getElem_zip] at this have hserv := hserves (sched[i], ρ[i]) hmem ext j obtain ⟨k, hk⟩ := hserv have : j = k := Subsingleton.elim j k subst this exact hktheorem uniform_kserver_det_k_one_rho_is_sched {M : Fin 1 → Type*} (ρ : List (∀ i, M i)) : uniform_kserver_is_schedule ρ ρ := by constructor · rfl · intro pair hpair use 0 rw [List.mem_iff_getElem] at hpair obtain ⟨i, hi, rfl⟩ := hpair rw [List.getElem_zip]theorem uniform_kserver_det_k_one_opt_eq {M : Fin 1 → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) (ρ : List (∀ i, M i)) : uniform_kserver_opt 1 a ρ = uniform_kserver_offline_cost a ρ := by unfold uniform_kserver_opt have hset : {c : ℕ | ∃ sched, uniform_kserver_is_schedule ρ sched ∧ uniform_kserver_offline_cost a sched = c} = {uniform_kserver_offline_cost a ρ} := by ext c simp only [Set.mem_singleton_iff] constructor · rintro ⟨sched, hsched, rfl⟩ rw [uniform_kserver_det_k_one_sched_eq_rho ρ sched hsched] · rintro rfl exact ⟨ρ, uniform_kserver_det_k_one_rho_is_sched ρ, rfl⟩ rw [hset] exact csInf_singleton _theorem uniform_kserver_det_k_one_schedule_eq {M : Fin 1 → Type*} (a : ∀ i, M i) (ρ : List (∀ i, M i)) : uniform_kserver_det_schedule (uniform_kserver_det_k_one_alg a) ρ = ρ := by unfold uniform_kserver_det_schedule apply List.ext_getElem · simp · intro i h1 h2 simp only [List.getElem_map, List.getElem_range] dsimp [uniform_kserver_det_k_one_alg] rw [List.take_succ_eq_append_getElem h2] exact List.getLastD_concat/-- The base case k = 1: generalized 1-server on uniform metrics is 1-competitive. -/theorem uniform_kserver_det_k_one_competitive {M : Fin 1 → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) : ∃ A, uniform_kserver_det_competitive 1 A a 1 := by use uniform_kserver_det_k_one_alg a unfold uniform_kserver_det_competitive constructor · intro ρ r use 0 dsimp [uniform_kserver_det_k_one_alg] simp · use 0 intro ρ unfold uniform_kserver_det_cost rw [uniform_kserver_det_k_one_schedule_eq a ρ] rw [uniform_kserver_det_k_one_opt_eq a ρ] linarith