Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Sharp total work-function growth at the antipodal coalesced configurations

Proved
KServer.antipodal_coalesced_growth_sum_sharp

by carlok · Sep 7, 2026 · Mathlib c5ea003 (Lean v4.30.0)

competitive-analysisk-servermetric-spacesonline-algorithmswork-function

Let k≥3k \ge 3k≥3, let MMM be a finite metric space, let Δ>0\Delta > 0Δ>0 bound all distances of MMM, and let p∈Mp \in Mp∈M. Write N=M⊔MˉN = M \sqcup \bar MN=M⊔Mˉ for the antipodal extension of MMM at scale Δ\DeltaΔ (KServer.antipodalExtension): NNN carries a copy of MMM (via Sum.inl) and a second copy Mˉ\bar MMˉ (via Sum.inr), with d(x,yˉ)=2Δ−d(x,y)d(x, \bar y) = 2\Delta - d(x,y)d(x,yˉ​)=2Δ−d(x,y), so that every point q∈Nq \in Nq∈N has an antipode qˉ\bar qqˉ​ at distance exactly 2Δ2\Delta2Δ from it, and d(y,q)+d(y,qˉ)=2Δd(y,q) + d(y,\bar q) = 2\Deltad(y,q)+d(y,qˉ​)=2Δ for every y∈Ny \in Ny∈N.

Start all kkk servers of NNN at the point ppp (regarded in the left copy) and let σ=r0,…,rm−1\sigma = r_0, \dots, r_{m-1}σ=r0​,…,rm−1​ be a request sequence drawn from MMM, mapped into NNN by Sum.inl. Write

w^t  =  w^(pk;  r0,…,rt−1;  ⋅)\widehat w_t \;=\; \widehat w\bigl(p^k;\; r_0,\dots,r_{t-1};\; \cdot\bigr)wt​=w(pk;r0​,…,rt−1​;⋅)

for the unordered work function of NNN after the first ttt requests, and let rˉt∈Mˉ⊆N\bar r_t \in \bar M \subseteq Nrˉt​∈Mˉ⊆N be the antipode of the ttt-th request.

Statement. The total growth of the work function, measured only at the coalesced configuration sitting on the antipode of the current request, is at most (k+1)(k+1)(k+1) times the offline optimum in the base space:

∑t=0m−1(w^t+1(rˉt k)−w^t(rˉt k))  ≤  (k+1) OPTM(pk,σ).\sum_{t=0}^{m-1} \Bigl( \widehat w_{t+1}\bigl(\bar r_t^{\,k}\bigr) - \widehat w_{t}\bigl(\bar r_t^{\,k}\bigr) \Bigr) \;\le\; (k+1)\,\mathrm{OPT}_M\bigl(p^k, \sigma\bigr).t=0∑m−1​(wt+1​(rˉtk​)−wt​(rˉtk​))≤(k+1)OPTM​(pk,σ).

Why this is the right formulation, and where the difficulty sits. On an antipodal space the increment w^t+1(X)−w^t(X)\widehat w_{t+1}(X) - \widehat w_t(X)wt+1​(X)−wt​(X) is maximised, over all target configurations XXX, at the coalesced configuration on the antipode of the request just served — this is KServer.workFnU_growth_le_antipode, already proved. Consequently the single sum above dominates the total growth ∑tmax⁡X{w^t+1(X)−w^t(X)}\sum_t \max_X\{\widehat w_{t+1}(X) - \widehat w_t(X)\}∑t​maxX​{wt+1​(X)−wt​(X)}, and via the isometric embedding KServer.workFnU_antipodal_extension_restrict it dominates the corresponding total growth in MMM itself.

So this statement is a concrete form of the sharp (k+1)(k+1)(k+1) work-function growth bound: it carries no existential over potential functions and no quantifier over target configurations. One explicit real number is attached to each step, and the assertion is a single inequality between two explicit reals. That is exactly what is needed to feed KServer.growth_of_potential_sharp and hence KServer.workFnU_growth_sharp_coalesced_finite.

The mathematical content is genuinely the open part. The coefficient k+1k+1k+1 (equivalently, λ=k+1\lambda = k+1λ=k+1 in the Extended Cost Lemma, giving competitive ratio kkk) is the kkk-server conjecture; Koutsoupias--Papadimitriou obtain λ=2k\lambda = 2kλ=2k by this route (KServer.workFnU_growth_2k_inj), and the sharp λ=k+1\lambda = k+1λ=k+1 is known only for k≤2k \le 2k≤2 and for spaces of at most k+2k+2k+2 points (KServer.workFnU_sharp_potential_known_cases). Nothing here is bookkeeping: the antipodal reduction, which is bookkeeping, has been performed already, and what remains is the inequality itself.

Formalization note. σ.getD t p is the ttt-th request (the default p is irrelevant, since the sum ranges over t<∣σ∣t < |\sigma|t<∣σ∣). The prefixes appear as σ.take t, mapped into the extension by List.map Sum.inl. The right-hand side uses offlineCost in the base space MMM; since Sum.inl is an isometric embedding, the offline optimum in NNN over Sum.inl-requests is at most this, so the statement as written is the weaker (and hence the correct, usable) form.

Preamble
import Mathlib
import Definitions.Def_KServer_workfunctionU
import Definitions.Def_KServer_antipodal_extension
open KServer
Formal statement
theorem KServer.antipodal_coalesced_growth_sum_sharp
    (k : ℕ) (hk : 3 ≤ k) (M : Type) [MetricSpace M] [Fintype M]
    (Δ : ℝ) (hΔ0 : 0 < Δ) (hΔ : ∀ x y : M, dist x y ≤ Δ)
    (p : M) (σ : List M) :
    ∑ t ∈ Finset.range σ.length,
        (@workFnU k (M ⊕ M) (antipodalExtension M Δ hΔ0 hΔ) (fun _ => Sum.inl p)
            ((σ.take (t + 1)).map Sum.inl) (fun _ => Sum.inr (σ.getD t p))
          - @workFnU k (M ⊕ M) (antipodalExtension M Δ hΔ0 hΔ) (fun _ => Sum.inl p)
            ((σ.take t).map Sum.inl) (fun _ => Sum.inr (σ.getD t p)))
      ≤ ((k : ℝ) + 1) * offlineCost (fun _ : Fin k => p) σ := by sorry
Source
E. Koutsoupias, The k-server problem (survey), Computer Science Review 3 (2009) 105-118, https://doi.org/10.1016/j.cosrev.2009.04.002, Section 3.4; E. Koutsoupias, C. Papadimitriou, On the k-server conjecture, J. ACM 42(5) (1995) 971-983, https://doi.org/10.1145/210118.210128 (the antipodal/quasiconvexity argument and the lambda = 2k bound).

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