Lemma 5.1 — terminal bound:
ProvedKServerConj.lemma_5_1competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , with distinct , and requests. In every run of the algebraic update, at every time and for every configuration of points,
Applied at the final time to an optimal final configuration, it turns the telescoped potential into the bound up to clique weights.
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)
- generalization: the algorithm's state at every time → the state q t at every time t ≤ T of every run; reason: every run represents the work function (Theorem 2.4); the paper's run is one of them
- 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: a finite request sequence r₁, …, r_T → r : ℕ → M, with requests r 1, …, r T; reason: values of r outside 1, …, T enter no quantity of the statement
- 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_workFn import Definitions.Def_KServerConj_cl import Definitions.Def_KServerConj_Psi import Definitions.Def_KServerConj_IsRun
Formal statement
namespace KServerConj
/-- **Lemma 5.1 (Terminal bound).** Coester, Koutsoupias, Zbysiński, *The k-server conjecture is
true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), printed p.12 (PDF p.13): "At
every time and for every configuration X, we have Ψ ≤ (k + 1)w(X) − cl(X). (25)"
**Formalization Note.** `k = m + 1` with `1 ≤ m` (printed p.5), so `k + 1 = m + 2`; `M` finite
(printed p.1); `C₀ = image s` for injective `s`. "At every time" is every time `t ≤ T` of every
run of the update, with `Ψ` the potential of the columns `q t` and `w = w_t`; configurations are
the sets of `k` points. -/
theorem lemma_5_1 {M : Type*} [PseudoMetricSpace M] [Fintype M] [DecidableEq M] {m : ℕ}
(hm : 1 ≤ m) (s : Fin (m + 1) → M) (hs : Function.Injective s) (r : ℕ → M) (T : ℕ)
(q qn : ℕ → M → Fin (m + 1) → K (m + 1) M) (hrun : IsRun s r T q qn) :
∀ t, t ≤ T → ∀ X : Finset M, X.card = m + 1 →
Psi (q t) ≤
((((m + 2 : ℕ) : ℝ) * workFn (m + 1) (Finset.univ.image s) r t X - cl X : ℝ) : 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.1, p.12 (pdf p.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.