Corollary 4.4 — the potential pays every request:
ProvedKServerConj.corollary_4_4competitive-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, with the potential of the columns at time , for each
Summing over , the total extended cost telescopes to , which Lemmas 5.1 and 5.2 bound.
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 run, with the normalization of Lemma 2.2 → every run (every normalizing matrix B with det B = 1 and B q_{r_t} = e₁); reason: Ψ and all k-column determinants are unchanged by any such B; the paper's run is one of them
- encoding: ExtCost_t ≤ Ψ_t − Ψ_{t−1} → ExtCost_t + Ψ_{t−1} ≤ Ψ_t in WithTop ℝ; reason: WithTop ℝ has no subtraction; the potentials are finite reals (Lemmas 5.1, 5.2), where the two forms are equivalent
- 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: 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
- 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
Preamble
import Mathlib import Definitions.Def_KServerConj_extCost import Definitions.Def_KServerConj_Psi import Definitions.Def_KServerConj_IsRun
Formal statement
namespace KServerConj
/-- **Corollary 4.4 (The potential pays every request).** 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): "For each time t, ExtCost_t ≤ Ψ_t − Ψ_{t−1}."
`Ψ_t = µ(Q)` (17) is the potential of the columns `q t` at time `t` of a run of the update
(initialization (7), normalization, row replacement (12)).
**Formalization Note.** `k = m + 1` with `1 ≤ m` (printed p.5), `M` finite (printed p.1),
`C₀ = image s` for injective `s`. The statement holds in every run (every choice of normalizing
matrices). The difference of potentials, which take values in `WithTop ℝ`, is written additively:
`ExtCost_t + Ψ_{t−1} ≤ Ψ_t`. -/
theorem corollary_4_4 {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, 1 ≤ t → t ≤ T →
((extCost (m + 1) (Finset.univ.image s) r t : ℝ) : WithTop ℝ) + Psi (q (t - 1)) ≤
Psi (q t) := 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…), Corollary 4.4, p.12 (pdf p.13)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.