uniform_kserver_offline_cost
For a natural number k, a family of spaces M indexed by Fin k with decidable equality, an initial configuration a, and a list of configurations sched, the offline movement cost is 0 for the empty list and the sum of Hamming distances between consecutive configurations along sched starting from a.
Statement
def uniform_kserver_offline_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) : List (∀ i, M i) → ℕ
- Defined in
- scout/2610-37192-tight-bounds-for-randomized-generalized-k-server-on-uniform.md:341
- Verified
- 28 Oct 2026
- Axioms
- none listed
- Used by 3
- 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…
- 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_k_one_competitiveFor generalized 1-server on any family of uniform metric spaces M indexed by Fin 1 with decidable equality and any initial configuration a…
Read back from the Lean
Given a natural number k, a family of types M : Fin k → Type* equipped with decidable equality on each M i, an initial configuration a : ∀ i, M i, and a list of configurations xs : List (∀ i, M i), uniform_kserver_offline_cost a xs recursively computes the total number of coordinate changes (Hamming distance) incurred by transitioning from a to the head of xs, and then consecutively between adjacent configurations in xs. If the list is empty, the cost is 0; if the list is x :: xs, the cost is the number of indices i : Fin k such that a i ≠ x i, plus uniform_kserver_offline_cost x xs.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Total movement cost of an offline schedule starting from configuration a. -/ def uniform_kserver_offline_cost {k : ℕ} {M : Fin k → Type*} [∀ i, DecidableEq (M i)] (a : ∀ i, M i) : List (∀ i, M i) → ℕ | [] => 0 | x :: xs => (Finset.univ.filter (fun i => a i ≠ x i)).card + uniform_kserver_offline_cost x xs