Lemma 5.2 — initial value:
ProvedKServerConj.lemma_5_2competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , and with distinct . The potential of the initial columns (7) is
This is the starting value of the telescoping sum; it produces the additive constant in the main theorem.
Differences from the source:
- generalization: a metric space (M, d) → a pseudometric space (
PseudoMetricSpace M); reason: the paper, p.1: "our proof works also when d is a pseudometric"; every metric space is a pseudometric space - generalization: K, the fraction field of finite sums ∑ f_a z^a over F = ℚ(γ_{i,x}, ξ_{t,x} : t ∈ [T]), with ν the least exponent → K = HahnSeries ℝ F with F = ℚ(γ_{i,x}, ξ_{t,x} : t ∈ ℕ) (Var, F) and ν = HahnSeries.addVal; reason: the paper's K embeds in the Hahn series field as a subfield on which addVal is the paper's ν (both are multiplicative), so the statement over Hahn series specializes to the paper's K; the paper's F is the subfield of the Lean F generated by the variables with t ∈ [T] (the others never occur)
- encoding: k ≥ 2 (standing assumption of §2–5, p.5) → k = m + 1 with 1 ≤ m, first coordinate 0 : Fin (m+1); reason: the same values of k; coordinates 1, …, k become 0, …, m
- encoding: initial configuration C₀ = {s₁, …, s_k} → an injective tuple s : Fin (m+1) → M with C₀ = image s; reason: the variables γ_{i,x} are indexed by the initial server i; the points of a configuration are distinct
- encoding: µ(G) = min over increasing column choices, for spanning families → minorVal G : WithTop ℝ, the minimum over injections R ↪ ι, ⊤ when all maximal minors vanish; reason: column order only changes the sign of a determinant; on spanning families the two agree
- encoding: Q = [z^{−d(x,y)} q_x q_y]{x≤y} for a fixed total order on M, rows (e_ie_j){i≤j} in lexicographic order (and Q̂ its rows with 2 ≤ i ≤ j) → Qmat (and Qhat) with rows indexed by Sym2 (Fin k) (Sym2 (Fin m)) and columns by Sym2 M, diagonal pairs included; reason: the orders only enumerate the pairs; no minor valuation depends on the enumeration
Preamble
import Mathlib import Definitions.Def_KServerConj_cl import Definitions.Def_KServerConj_initCols import Definitions.Def_KServerConj_Psi
Formal statement
namespace KServerConj
/-- **Lemma 5.2 (Initial value).** Coester, Koutsoupias, Zbysiński, *The k-server conjecture is
true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), printed p.13 (PDF p.14): "The
initialization (7) satisfies Ψ₀ = −cl(C₀)."
**Formalization Note.** `k = m + 1` with `1 ≤ m` (printed p.5), `M` finite (printed p.1). The
initial configuration `C₀ = {s₁, …, s_k}` is the image of an injective `s`; `Ψ₀` is the potential
(17) of the initial columns (7). The value is a real number. -/
theorem lemma_5_2 {M : Type*} [PseudoMetricSpace M] [Fintype M] [DecidableEq M] {m : ℕ}
(hm : 1 ≤ m) (s : Fin (m + 1) → M) (hs : Function.Injective s) :
Psi (initCols s) = ((-(cl (Finset.univ.image s)) : ℝ) : WithTop ℝ) := by sorry
end KServerConj
Source
Coester, Koutsoupias, Zbysiński, The k-server conjecture is true, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), Lemma 5.2, p.13 (pdf p.14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.