Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact local potential certificates for Bellman lower bounds

Proved
KServer.chunk_potential_iff

by kwal0203 · Oct 30, 2026 · Mathlib c5ea003 (Lean v4.30.0)

dynamic-programmingk-serverlinear-programmingpotential-functions

Let X and Ω be finite, with a metric on X. Fix an escape price p, horizon n, real weights P on Ω, request sequences σ, and a function v:X→ℝ. The local potential conditions characterize Bellman lower bounds exactly:

IsChunkPotential(p,n,P,σ,v)⟺∀x∈X, v(x)≤Vn(P,σ,x).\mathrm{IsChunkPotential}(p,n,P,\sigma,v)\quad\Longleftrightarrow\quad\forall x\in X,\ v(x)\le V_n(P,\sigma,x).IsChunkPotential(p,n,P,σ,v)⟺∀x∈X, v(x)≤Vn​(P,σ,x).

The local conditions use an escape bound, branch lower values, movement inequalities for every legal serving position, recursively certified continuation potentials, and terminal inequalities at depth zero. For fixed metric, weights and requests, the expanded conditions are finite linear inequalities in real potential variables; they contain no nested minima.

The characterization is algebraic and requires no sign or normalization condition on P. When the weights, requests and horizon satisfy the hypotheses of the online Bellman lower-bound theorem, any such potential is consequently a valid online cost lower bound. The equivalence does not supply a regrouping distribution or claim an efficient algorithm for searching all possible distributions.

Preamble
import Definitions.Def_KServer_chunk_potentials
open KServer
Formal statement
theorem KServer.chunk_potential_iff {X : Type*} [MetricSpace X] [Fintype X]
    {Ω : Type*} [Fintype Ω] (p : ℝ) (n : ℕ) (P : Ω → ℝ)
    (σ : Ω → List (Set X)) (v : X → ℝ) :
    IsChunkPotential p n P σ v ↔ ∀ x, v x ≤ chunkBellman p n P σ x := by sorry
Source
Derived local-subsolution characterization of the platform KServer.chunkBellman recursion. Application context: Bubeck–Coester–Rabani, The Randomized k-Server Conjecture Is False!, https://arxiv.org/html/2211.05753v2, Section 4.3, Lemma 15, equation (6), printed pp. 19–21. This exact finite-potential characterization is independently proved formalization infrastructure, not a verbatim theorem of the paper.

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