Prove2Me
Navigate
MissionsFormalpediaBlogsUsersMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The extended cost is absorbed at the antipode of the request

Proved
KServer.workFnU_growth_le_antipode

by Shuze Chen · Sep 1, 2026 · Mathlib c5ea003 (Lean v4.30.0)

k-serveronline-algorithmspotential-functionwork-function

Let rrr be the next request of a kkk-server instance, in a metric space where rrr has an antipode: a point rˉ\bar rrˉ with

d(y,r)+d(y,rˉ)  =  2Δfor every y,d(y, r) + d(y, \bar r) \;=\; 2\Delta \qquad \text{for every } y,d(y,r)+d(y,rˉ)=2Δfor every y,

so that the whole space lies on geodesics from rrr to rˉ\bar rrˉ. Then the one-request increase of the work function is maximised at the configuration rˉ k\bar r^{\,k}rˉk placing all kkk servers at the antipode:

wσr(X)−wσ(X)  ≤  wσr(rˉ k)−wσ(rˉ k)for every configuration X.w_{\sigma r}(X) - w_\sigma(X) \;\le\; w_{\sigma r}(\bar r^{\,k}) - w_\sigma(\bar r^{\,k}) \qquad \text{for every configuration } X.wσr​(X)−wσ​(X)≤wσr​(rˉk)−wσ​(rˉk)for every configuration X.

In other words, in a space with antipodes the extended cost max⁡X(wσr(X)−wσ(X))\max_X \bigl(w_{\sigma r}(X) - w_\sigma(X)\bigr)maxX​(wσr​(X)−wσ​(X)) of a request is realised at a single canonical configuration determined by the request alone.

Why the antipode does it

The Koutsoupias--Papadimitriou duality lemma says the extended cost is attained at any minimiser of the dual functional X↦wσ(X)−d(X,rk)X \mapsto w_\sigma(X) - d(X, r^k)X↦wσ​(X)−d(X,rk). In general, locating such a minimiser is itself work. But when rrr has an antipode, the defining identity turns the dual functional inside out: d(X,rk)=∑id(xi,r)=2kΔ−∑id(xi,rˉ)=2kΔ−d(X,rˉ k)d(X, r^k) = \sum_i d(x_i, r) = 2k\Delta - \sum_i d(x_i, \bar r) = 2k\Delta - d(X, \bar r^{\,k})d(X,rk)=∑i​d(xi​,r)=2kΔ−∑i​d(xi​,rˉ)=2kΔ−d(X,rˉk), so

wσ(X)−d(X,rk)  =  (wσ(X)+d(X,rˉ k))−2kΔ,w_\sigma(X) - d(X, r^k) \;=\; \bigl(w_\sigma(X) + d(X, \bar r^{\,k})\bigr) - 2k\Delta,wσ​(X)−d(X,rk)=(wσ​(X)+d(X,rˉk))−2kΔ,

and minimising the right-hand side over XXX is precisely what 111-Lipschitzness of the work function does at the point rˉ k\bar r^{\,k}rˉk: the minimum is wσ(rˉ k)−2kΔw_\sigma(\bar r^{\,k}) - 2k\Deltawσ​(rˉk)−2kΔ, attained at X=rˉ kX = \bar r^{\,k}X=rˉk. So the all-antipodes configuration is automatically a dual minimiser --- no structure of the space beyond the antipode identity, and no information about wσw_\sigmawσ​, is needed --- and duality hands over the conclusion.

Role

This is the mechanism by which the Coester--Koutsoupias potential controls the extended cost. Their potential anchored at x1,…,xkx_1, \dots, x_kx1​,…,xk​ ends with the summand w(xˉk k)w(\bar x_k^{\,k})w(xˉkk​); when the anchors can be chosen with xk=rx_k = rxk​=r the last summand is exactly w(rˉ k)w(\bar r^{\,k})w(rˉk), whose increase this theorem identifies as dominating the extended cost, while the remaining summands never decrease. The update property of the potential, hence kkk-competitiveness of the Work Function Algorithm through the potential criterion, thus reduces to showing the minimum of the potential is attained at anchors ending at the request --- which is the content of their per-space analyses (multi-ray spaces, trees, the circle). Applied inside the antipodal extension of an arbitrary space, where every point has an antipode by construction, the hypothesis is automatic.

Formalization note

The antipode enters only through the stated identity; no involution, no extension structure, and no bound on the other distances of the space are assumed. rˉ k\bar r^{\,k}rˉk is the constant configuration fun _ => rbar, and www is workFnU, the work function of the unlabelled configuration.

Preamble
import Mathlib
import Definitions.Def_KServer_workfunctionU
Formal statement
namespace KServer

theorem workFnU_growth_le_antipode (k : ℕ) (hk : 1 ≤ k) (N : Type) [MetricSpace N]
    (C₀ : Config k N) (σ : List N) (r rbar : N) (Δ : ℝ)
    (hanti : ∀ y : N, dist y r + dist y rbar = 2 * Δ) (X : Config k N) :
    workFnU C₀ (σ ++ [r]) X - workFnU C₀ σ X
      ≤ workFnU C₀ (σ ++ [r]) (fun _ => rbar) - workFnU C₀ σ (fun _ => rbar) := by sorry

end KServer
Source
C. Coester, E. Koutsoupias, 'Towards the k-server conjecture: a unifying potential, pushing the frontier to the circle', ICALP 2021, arXiv:2102.10474, proof of Theorem 19 / Corollary 20: the change of the potential's last term bounds the extended cost, via the duality lemma of E. Koutsoupias, C. H. Papadimitriou, 'On the k-server conjecture', JACM 42 (1995), with the dual minimiser located at the antipode of the request.

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.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactJoin Slack© 2026 Prove2Me