Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — in every ddd-dimensional normed space, every online algorithm for convex body chasing has competitive ratio ≥c d\ge c\,d≥cd

Proved
CBCLowerBound.EveryNorm.theorem_1

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

competitive-analysisconvex-body-chasinglower-boundsnormed-spacesp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1

There is a universal constant c>0c>0c>0 such that, for every d≥2d\ge2d≥2 and every norm ∥⋅∥\|\cdot\|∥⋅∥ on Rd\mathbb R^dRd, any algorithm for convex body chasing in (Rd,∥⋅∥)(\mathbb R^d,\|\cdot\|)(Rd,∥⋅∥) has competitive ratio at least c dc\,dcd.

Precisely: let XXX be a real normed space of dimension d≥2d\ge2d≥2, let x0∈Xx_0\in Xx0​∈X, and let Alg\mathrm{Alg}Alg be a deterministic or randomized online algorithm for chasing nonempty closed convex sets K1,…,KT⊆XK_1,\dots,K_T\subseteq XK1​,…,KT​⊆X starting at x0x_0x0​, where TTT is unknown in advance. If for some R∈RR\in\mathbb RR∈R

E[Alg(K1,…,KT)]≤R⋅Opt(K1,…,KT)\mathbb E\big[\mathrm{Alg}(K_1,\dots,K_T)\big]\le R\cdot\mathrm{Opt}(K_1,\dots,K_T)E[Alg(K1​,…,KT​)]≤R⋅Opt(K1​,…,KT​)

for every finite sequence of nonempty closed convex sets, then R≥c dR\ge c\,dR≥cd. The constant ccc does not depend on ddd, on the norm, on x0x_0x0​ or on the algorithm.

The bound matches the O(d)O(d)O(d) competitive ratio of Sellke's functional Steiner point algorithm in every norm, so it is optimal up to the constant; in particular no norm, the Euclidean one included, admits a sublinear competitive ratio.

Formalization Note The chasing model (bodies, algorithms, expected cost, Opt\mathrm{Opt}Opt, competitiveness) is the definition Chasing of this mission. A randomized algorithm is a probability space of seeds with a deterministic online algorithm per seed and measurable decisions. "CR≥cd\mathrm{CR}\ge cdCR≥cd" is stated as "every RRR for which the algorithm is RRR-competitive satisfies cd≤Rcd\le Rcd≤R", which also covers an infinite competitive ratio and avoids a ratio with Opt=0\mathrm{Opt}=0Opt=0.

Differences from the source:

  • encoding: every norm on ℝ^d → every real normed space X with FiniteDimensional ℝ X and finrank ℝ X = d; reason: every norm on ℝ^d gives such an X and every such X is linearly isometric to ℝ^d with a norm
  • encoding: competitive ratio CR(Alg) = sup Alg/Opt ≥ c·d → every R with E[Alg(σ)] ≤ R·Opt(σ) for all finite sequences of bodies satisfies c·d ≤ R; reason: CR(Alg) is the infimum of such R
  • encoding: randomized algorithm and its expected cost → a probability space of seeds, a deterministic online algorithm per seed with measurable decisions, and the lower Lebesgue integral of the movement; reason: measurability of the decisions is what makes "expected cost" meaningful; deterministic algorithms are the one-point case
  • encoding: the starting point x₀ → universally quantified x₀ ∈ X; reason: the paper fixes an arbitrary starting point
Preamble
import Mathlib
import Definitions.Def_CBCLowerBound_EveryNorm_Chasing
Formal statement
namespace CBCLowerBound.EveryNorm

/-- **Theorem 1** (Christianson, STOC 2027 #674, p.2). There is a universal constant `c > 0`
such that, for every `d ≥ 2` and every norm on `ℝ^d` (every `d`-dimensional real normed space
`X`), every start point `x₀` and every (deterministic or randomized) online algorithm for convex
body chasing in `X`, the competitive ratio is at least `c·d`: every `R` for which the algorithm
is `R`-competitive satisfies `c·d ≤ R`. -/
theorem theorem_1 : ∃ c : ℝ, 0 < c ∧ ∀ d : ℕ, 2 ≤ d →
    ∀ (X : Type) [NormedAddCommGroup X] [NormedSpace ℝ X] [FiniteDimensional ℝ X],
      Module.finrank ℝ X = d →
      ∀ (x₀ : X) (A : RandomizedAlgorithm X x₀) (R : ℝ), A.IsCompetitive R → c * d ≤ R := by sorry

end CBCLowerBound.EveryNorm
Source
Nicolas Christianson, A Linear Lower Bound for Convex Body Chasing in Every Norm, STOC 2027 submission #674 (October 2026), p.2, Theorem 1 (proof pp.16–17), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/674.pdf
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 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