Work functions are preserved by injective isometries
ProvedKServerConj.workFn_map_compatisometryk-serverpseudometricwork-function
Let be an injective distance-preserving map between pseudometric spaces, let , and let have cardinality . Suppose the request histories agree under through time . Then for every and every -point configuration ,
Thus passing to a larger pseudometric space creates no cheaper work-function value for a configuration and request history lying in the original space. In particular, the work function can be computed in a finite subspace containing the initial configuration, the request prefix, and the target configuration. Explicit injectivity is required because distance preservation alone need not imply injectivity in a pseudometric space.
Preamble
import Definitions.Def_KServerConj_confDist import Definitions.Def_KServerConj_workFn
Formal statement
theorem KServerConj.workFn_map_compat {N M : Type*} [PseudoMetricSpace N] [PseudoMetricSpace M]
(f : N ↪ M) (hd : ∀ x y, dist (f x) (f y) = dist x y)
(k : ℕ) (hk : 1 ≤ k) (C₀ : Finset N) (hC₀ : C₀.card = k)
(rN : ℕ → N) (rM : ℕ → M) (T : ℕ)
(hreq : ∀ t, 1 ≤ t → t ≤ T → f (rN t) = rM t) :
∀ t, t ≤ T → ∀ X : Finset N, X.card = k →
KServerConj.workFn k (C₀.map f) rM t (X.map f) = KServerConj.workFn k C₀ rN t X := by sorrySource
Finite-space reduction for Coester–Koutsoupias–Zbysiński, The k-server conjecture is true, arXiv:2609.15979, Theorem 1.3.