Lemma 2.1 — fresh coefficients prevent cancellation:
ProvedKServerConj.lemma_2_1competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1valuationswork-function-algorithm
Let be distinct coefficient variables, and let use none of them: every coefficient of each lies in the subfield of generated by the other variables. For all real numbers , if at least one is nonzero, then
In general of a sum can exceed the minimum of the valuations (cancellation); independent fresh coefficients rule this out, which is how the algebraic update reproduces the min-plus recurrence exactly.
Differences from the source:
- 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)
- encoding: f₁, …, f_m use none of the variables η₁, …, η_m → every Hahn coefficient of each f_i lies in Subfield.closure of the variables outside {η_i} (FreeOf); reason: a rational expression in the other variables has all its coefficients in that subfield
- encoding: indices 1, …, m and independent variables η_i → Fin N and η_i = coef (v i) for an injective v into the variables; reason: m is used for k − 1 elsewhere in the mission; the η_i are distinct variables of F
- generalization: M finite and k ≥ 2 (standing assumptions, p.1 and p.5) → any k and any type M indexing the variables γ_{i,x}, ξ_{t,x}; reason: the lemma concerns elements of K only and its proof uses neither; the finite case is a special case
Preamble
import Mathlib import Definitions.Def_KServerConj_K
Formal statement
namespace KServerConj
/-- **Lemma 2.1 (Fresh coefficients prevent cancellation).** Coester, Koutsoupias, Zbysiński,
*The k-server conjecture is true*, arXiv:2609.15979 (version of 2026-11-03, sha256 7ca0380a…),
printed p.6 (PDF p.7): "Suppose f₁, …, f_m ∈ K use none of the independent coefficient variables
η₁, …, η_m. For real numbers a₁, …, a_m, if at least one f_i is nonzero, then
ν(∑_{i=1}^m η_i z^{a_i} f_i) = min_i (a_i + ν(f_i))."
**Formalization Note.** The count `m` of the lemma is `N` here (`m` is used for `k − 1` elsewhere
in the mission). The independent variables are `η_i = coef (v i)` for an injective
`v : Fin N → Var k M`; "uses none of the variables" is `FreeOf (range v)`. Terms with `f_i = 0`
contribute `⊤` to the minimum, as in the paper. -/
theorem lemma_2_1 {k : ℕ} {M : Type*} {N : ℕ} (v : Fin N → Var k M) (hv : Function.Injective v)
(f : Fin N → K k M) (hf : ∀ i, FreeOf (Set.range v) (f i)) (a : Fin N → ℝ)
(hne : ∃ i, f i ≠ 0) :
nu (∑ i, coef (v i) * zp (a i) * f i) =
Finset.univ.inf fun i => ((a i : ℝ) : WithTop ℝ) + nu (f i) := 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.1, p.6 (pdf p.7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.