Lemma 4.1 — a useful minor of the old quadratic matrix:
ProvedKServerConj.lemma_4_1competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm
Let be a finite pseudometric space, , , and let columns satisfy (the coordinates after normalization at the request ). With the potential (17), (18) and the bottom block of (19),
This is the bound on the old potential in the comparison that pays for each 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 normalized columns of the algorithm before the request → every column family with q_r = e₁; reason: q_r = e₁ is the only property of the state the proof uses; the algorithm's normalized state has it
- 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
Formal statement
namespace KServerConj
/-- **Lemma 4.1 (A useful minor of the old quadratic matrix).** Coester, Koutsoupias, Zbysiński,
*The k-server conjecture is true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…),
printed p.10 (PDF p.11): "The old potential before the request satisfies Ψ ≤ µ(Q̂) + µ(H)."
The setting (§4, printed p.10): the columns have been normalized so that the request column is
`q_r = e₁`; `Ψ = µ(Q)` (17), `H = [z^{−d(r,x)} q_x]_x` (18) and `Q̂` is the bottom block of `Q` (19).
**Formalization Note.** `k = m + 1` with `1 ≤ m` (standing assumption `k ≥ 2`, printed p.5), `M`
finite (printed p.1). The statement is for every family of columns `q` with `q_r = e₁`, which
includes the normalized state of the algorithm before every request. -/
theorem lemma_4_1 {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) :
Psi q ≤ minorVal (Qhat q) + minorVal (Hmat 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.1, p.10 (pdf p.11)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.