Lemma 4.3 — the extended cost is exactly
ProvedKServerConj.lemma_4_3competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , with distinct , requests and . Let columns represent the work function , i.e. for distinct points, and satisfy . With and as in (18) for the request , both and are finite, and
This is the algebraic form of the duality lemma (Lemma 1.2); together with Lemmas 4.1 and 4.2 it shows that the potential pays every request.
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 normalized columns at request t → every column family representing w_{t−1} (10) with q_{r_t} = e₁; reason: the proof uses only (10) and q_{r_t} = e₁
- encoding: the difference µ(Ĥ) − µ(H) of two minimum valuations → ∃ reals a, b with µ(H) = a, µ(Ĥ) = b and ExtCost_t = b − a; reason: µ takes values in WithTop ℝ, which has no subtraction; the paper notes both quantities are finite (p.10)
- encoding: ν(u(X)) = w(X) for all X ∈ M^k, with w = ∞ when X has a repeated point → ν(colDet q x) = w(image x) for injective tuples x; reason: for a repeated point the determinant is 0 and both sides are ∞ (p.7: "Equation (10) holds even if x_i = x_j")
- 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
Preamble
import Mathlib import Definitions.Def_KServerConj_extCost import Definitions.Def_KServerConj_colDet import Definitions.Def_KServerConj_minorVal import Definitions.Def_KServerConj_Hmat
Formal statement
namespace KServerConj
/-- **Lemma 4.3 (Why the potential change pays the extended cost).** 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); algebraic proof in Appendix A, printed pp.14–15: "The
extended cost of the request is exactly max_X {w′(X) − w(X)} = µ(Ĥ) − µ(H)."
The setting: normalized columns `q` representing the work function `w = w_{t−1}` (10), with
`q_{r_t} = e₁`; `w′ = w_t`; `H`, `Ĥ` as in (18) for the request `r = r_t`.
**Formalization Note.** `k = m + 1` with `1 ≤ m` (printed p.5), `M` finite (printed p.1),
`C₀ = image s` for injective `s`. The difference `µ(Ĥ) − µ(H)` is read in `ℝ`: the conclusion
asserts that both minimum valuations are finite reals `a = µ(H)` and `b = µ(Ĥ)` and that the
extended cost equals `b − a`. -/
theorem lemma_4_3 {M : Type*} [PseudoMetricSpace M] [Fintype M] [DecidableEq M] {m : ℕ}
(hm : 1 ≤ m) (s : Fin (m + 1) → M) (hs : Function.Injective s) (r : ℕ → M) (t : ℕ)
(ht : 1 ≤ t) (q : M → Fin (m + 1) → K (m + 1) M)
(hrep : ∀ x : Fin (m + 1) → M, Function.Injective x →
nu (colDet q x) = ((workFn (m + 1) (Finset.univ.image s) r (t - 1) (Finset.univ.image x) : ℝ) :
WithTop ℝ))
(hr : q (r t) = Pi.single 0 1) :
∃ a b : ℝ, minorVal (Hmat q (r t)) = (a : WithTop ℝ) ∧ minorVal (Hhat q (r t)) = (b : WithTop ℝ) ∧
extCost (m + 1) (Finset.univ.image s) r t = b - a := 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 4.3, p.12 (pdf p.13); algebraic proof in Appendix A, pp.14–15 (pdf pp.15–16)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.