Lemma 2.3 — one request is a row replacement:
ProvedKServerConj.lemma_2_3competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , with distinct , requests and a time . Let columns () satisfy:
- for all distinct (equation (10));
- no determinant uses any of the fresh variables , ;
- (the coordinates after the normalization of Lemma 2.2).
Let with (equations (11)–(12)). Then for all distinct ,
A request thus acts on the representation by a single row replacement, and the representation of the work function is maintained.
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 columns after the normalization at request t → every column family satisfying (10) for w_{t−1}, q_{r_t} = e₁, and whose k-column determinants use no ξ_{t,y}; reason: these are the facts the paper's setting provides and its proof uses; the algorithm's columns satisfy them (Theorem 2.4, 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
Preamble
import Mathlib import Definitions.Def_KServerConj_workFn import Definitions.Def_KServerConj_colDet import Definitions.Def_KServerConj_rowReplace
Formal statement
namespace KServerConj
/-- **Lemma 2.3 (one request is a row replacement).** Coester, Koutsoupias, Zbysiński, *The k-server
conjecture is true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…), printed p.7
(PDF p.8): "The new columns satisfy ν(det(q′_{x₁}, …, q′_{x_k})) = w′(X) for all
X = (x₁, …, x_k) ∈ M^k."
The setting (p.7): columns `q_x` represent the work function `w = w_{t−1}` (10), have been
normalized so that `q_{r_t} = e₁` (Lemma 2.2), and their determinants use none of the fresh
variables `ξ_{t,x}` ("the old determinants contain none of them"); `q′` replaces the first
coordinate of every column by `δ_x = ξ_{t,x} z^{d(r_t,x)}` (11)–(12), and `w′ = w_t`.
**Formalization Note.** `k = m + 1` with `1 ≤ m` (the paper's standing assumption `k ≥ 2`, §2,
printed p.5). `M` is finite (standing assumption, printed p.1). The initial configuration is
`C₀ = image s` for injective `s`. Representations are asserted on tuples of distinct points; for a
repeated point the determinant is `0` and the paper's value is `∞` by convention. -/
theorem lemma_2_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 ℝ))
(hfree : ∀ x : Fin (m + 1) → M,
FreeOf (Set.range fun y : M => (Sum.inr (t, y) : Var (m + 1) M)) (colDet q x))
(hr : q (r t) = Pi.single 0 1) :
∀ x : Fin (m + 1) → M, Function.Injective x →
nu (colDet (rowReplace q (freshRow r 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…), Lemma 2.3, p.7 (pdf p.8)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.