Sharp total work-function growth at the antipodal coalesced configurations
ProvedKServer.antipodal_coalesced_growth_sum_sharpLet , let be a finite metric space, let bound all distances of , and let . Write for the antipodal extension of at scale (KServer.antipodalExtension): carries a copy of (via Sum.inl) and a second copy (via Sum.inr), with , so that every point has an antipode at distance exactly from it, and for every .
Start all servers of at the point (regarded in the left copy) and let be a request sequence drawn from , mapped into by Sum.inl. Write
for the unordered work function of after the first requests, and let be the antipode of the -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 times the offline optimum in the base space:
Why this is the right formulation, and where the difficulty sits. On an antipodal space the increment is maximised, over all target configurations , 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 , and via the isometric embedding KServer.workFnU_antipodal_extension_restrict it dominates the corresponding total growth in itself.
So this statement is a concrete form of the sharp 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 (equivalently, in the Extended Cost Lemma, giving competitive ratio ) is the -server conjecture; Koutsoupias--Papadimitriou obtain by this route (KServer.workFnU_growth_2k_inj), and the sharp is known only for and for spaces of at most 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 -th request (the default p is irrelevant, since the sum ranges over ). 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 ; since Sum.inl is an isometric embedding, the offline optimum in over Sum.inl-requests is at most this, so the statement as written is the weaker (and hence the correct, usable) form.
import Mathlib import Definitions.Def_KServer_workfunctionU import Definitions.Def_KServer_antipodal_extension open KServer
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