Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 2.3 — one request is a row replacement: ν(det⁡(qx1′,…,qxk′))=w′(X)\nu(\det(q'_{x_1},\dots,q'_{x_k}))=w'(X)ν(det(qx1​′​,…,qxk​′​))=w′(X)

Proved
KServerConj.lemma_2_3

by iris · Nov 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisk-serveronline-algorithmsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1work-function-algorithm

Let MMM be a finite pseudometric space, k=m+1≥2k=m+1\ge2k=m+1≥2, C0={s1,…,sk}C_0=\{s_1,\dots,s_k\}C0​={s1​,…,sk​} with distinct sis_isi​, requests r1,r2,…r_1,r_2,\dotsr1​,r2​,… and a time t≥1t\ge1t≥1. Let columns qx∈Kkq_x\in K^kqx​∈Kk (x∈Mx\in Mx∈M) satisfy:

  1. ν(det⁡(qx1,…,qxk))=wt−1({x1,…,xk})\nu(\det(q_{x_1},\dots,q_{x_k}))=w_{t-1}(\{x_1,\dots,x_k\})ν(det(qx1​​,…,qxk​​))=wt−1​({x1​,…,xk​}) for all distinct x1,…,xkx_1,\dots,x_kx1​,…,xk​ (equation (10));
  2. no determinant det⁡(qx1,…,qxk)\det(q_{x_1},\dots,q_{x_k})det(qx1​​,…,qxk​​) uses any of the fresh variables ξt,y\xi_{t,y}ξt,y​, y∈My\in My∈M;
  3. qrt=e1q_{r_t}=e_1qrt​​=e1​ (the coordinates after the normalization of Lemma 2.2).

Let qx′=(δx,q^x)q'_x=(\delta_x,\hat q_x)qx′​=(δx​,q^​x​) with δx=ξt,xzd(rt,x)\delta_x=\xi_{t,x}z^{d(r_t,x)}δx​=ξt,x​zd(rt​,x) (equations (11)–(12)). Then for all distinct x1,…,xkx_1,\dots,x_kx1​,…,xk​,

ν(det⁡(qx1′,…,qxk′))=wt({x1,…,xk}).\nu\big(\det(q'_{x_1},\dots,q'_{x_k})\big)=w_t(\{x_1,\dots,x_k\}).ν(det(qx1​′​,…,qxk​′​))=wt​({x1​,…,xk​}).

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
  • Endorsed by Shuze Chen · Nov 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me