Theorem 2.4 — maintained algebraic state: at every time
ProvedKServerConj.theorem_2_4competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , with distinct , and requests. Then:
- a run of the update exists: the initialization (7), followed at each request by a normalization with and and by the row replacement (12);
- in every run, at every time and for all distinct points ,
The work function is therefore represented at all times by valuations of minors of a matrix; the potential of §4 is built from these columns.
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 determinant-preserving normalization of Lemma 2.2 (Gaussian elimination, then scaling a row) → every matrix B with det B = 1 and B q_{r_t} = e₁ (IsRun), in clause 2; reason: no k-column determinant depends on the choice of B since det B = 1; the paper's B is one such matrix
- encoding: the procedure produces a matrix with the property → clause 1: a run exists (∃ q qn, IsRun …); clause 2: every run has the property; reason: "produce" asserts that the procedure can be carried out, which carries Lemma 2.2
- 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
- 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
Preamble
import Mathlib import Definitions.Def_KServerConj_workFn import Definitions.Def_KServerConj_colDet import Definitions.Def_KServerConj_IsRun
Formal statement
namespace KServerConj
/-- **Theorem 2.4 (Maintained algebraic state).** Coester, Koutsoupias, Zbysiński, *The k-server
conjecture is true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), printed p.8
(PDF p.9): "For every finite request sequence, the initialization (7) and the
determinant-preserving normalization followed by (12) produce a k × n matrix whose k-column
determinants have valuations exactly equal to the corresponding work function values at every
time."
Two clauses: a run of the update exists ("produce"; this carries Lemma 2.2, the existence of the
normalizing matrix `B` with `det B = 1`), and in every run, at every time `t ≤ T`, the valuation of
the determinant of the columns at any `k` distinct points `x₁, …, x_k` is `w_t({x₁, …, x_k})`.
**Formalization Note.** `k = m + 1` with `1 ≤ m` (standing assumption `k ≥ 2`, §2, printed p.5;
for `k = 1` the only `1 × 1` matrix with determinant one is the identity, so no normalization
exists). `M` is finite (printed p.1). `C₀ = image s` for injective `s`. Every normalizing matrix is
allowed (`IsRun`); requests are `r 1, …, r T`. -/
theorem theorem_2_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, IsRun s r T q qn) ∧
∀ q qn : ℕ → M → Fin (m + 1) → K (m + 1) M, IsRun s r T q qn →
∀ t, t ≤ T → ∀ x : Fin (m + 1) → M, Function.Injective x →
nu (colDet (q t) x) =
((workFn (m + 1) (Finset.univ.image s) r t (Finset.univ.image 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…), Theorem 2.4, p.8 (pdf p.9); Lemma 2.2, p.7 (pdf p.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.