AFTD Auto-Formalizing Theoretical Domains

uniform_kserver_det_k_one_competitive

theoremverifiedformalization

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.

  1. dummy 1

    dummy

    lines 7–22

      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
  2. dummy 2

    dummy

    lines 26–32

      constructor
      · rfl
      · intro pair hpair
        use 0
        rw [List.mem_iff_getElem] at hpair
        obtain ⟨i, hi, rfl⟩ := hpair
        rw [List.getElem_zip]
  3. dummy 3

    dummy

    lines 37–48

      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 _
  4. dummy 4

    dummy

    lines 53–60

      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
  5. dummy 5

    dummy

    lines 66–78

      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

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
See it in the graphDiscuss this resultChallenge it