Lemma 4.2 — the new potential:
ProvedKServerConj.lemma_4_2competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , , and let columns satisfy . Let be a row with for every , and let be the replaced columns (12), with potential . With (18) and (19) built from the old columns,
Both inequalities are asserted; the paper notes that only is needed for the main theorem.
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 normalized columns and the fresh row δ_x = ξ_{t,x} z^{d(r,x)} (11) → every column family with q_r = e₁ and every row δ with ν(δ_x) = d(r, x); reason: the proof uses only q_r = e₁ and the valuations ν(δ_x) = d(r, x) ("Notice that ν(δ_x) = d(r, x) for every x", p.7); the paper's row is one such row
- 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: µ(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_Psi import Definitions.Def_KServerConj_Hmat import Definitions.Def_KServerConj_rowReplace
Formal statement
namespace KServerConj
/-- **Lemma 4.2 (The minimum minor valuation of the new quadratic matrix).** Coester, Koutsoupias,
Zbysiński, *The k-server conjecture is true*, arXiv:2609.15979 (version of 2026-11-03, sha256
7ca0380a…), printed p.11 (PDF p.12): "The new potential after the request satisfies
Ψ′ = µ(Q̂) + µ(Ĥ)."
The setting: normalized columns with `q_r = e₁`; the new columns `q′_x = (δ_x, q̂_x)` (12), where
`ν(δ_x) = d(r, x)` for every `x` ("Notice that ν(δ_x) = d(r, x) for every x", printed p.7);
`Ψ′ = µ(Q′)` is the potential of the new columns, and `Q̂`, `Ĥ` are built from the old ones (18)–(19).
**Formalization Note.** `k = m + 1` with `1 ≤ m` (printed p.5), `M` finite (printed p.1). The
statement holds for every family `q` with `q_r = e₁` and every first row `δ` with
`ν(δ_x) = d(r, x)`; the paper's `δ_x = ξ_{t,x} z^{d(r,x)}` (11) is one such row. Both directions of
the equality are asserted. -/
theorem lemma_4_2 {M : Type*} [PseudoMetricSpace M] [Fintype M] [DecidableEq M] {m : ℕ}
(hm : 1 ≤ m) (q : M → Fin (m + 1) → K (m + 1) M) (r : M) (hr : q r = Pi.single 0 1)
(δ : M → K (m + 1) M) (hδ : ∀ x, nu (δ x) = ((dist r x : ℝ) : WithTop ℝ)) :
Psi (rowReplace q δ) = minorVal (Qhat q) + minorVal (Hhat q r) := 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.2, p.11 (pdf p.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.