Convex body chasing is a basic online problem in metric geometry and online algorithms: an algorithm must stay inside a sequence of convex constraints revealed one at a time while moving as little as possible. It was introduced by Friedman and Linial (FL93, Discrete Comput. Geom. 1993) and is the geometric core of online convex optimization with switching costs and of convex function chasing (Antoniadis et al., LATIN 2016; BLLS19). The central quantity is the best possible competitive ratio as a function of the dimension and of the norm that measures movement.
Timeline of the bounds:
Let be a real normed space of dimension and . An adversary reveals bodies (nonempty closed convex sets) , with unknown in advance. After seeing , an online algorithm picks using only , and pays . Its cost is , or its expectation for a randomized algorithm, whose seed is independent of the requests. The offline optimum is the infimum of over , . The competitive ratio is
The milestones use the recursive construction of Bubeck, Coester and Rabani (BCR23, §3.6). For parameters and with , , the graph is one edge and joins a source to a target by two branches, each an entrance edge of length followed by copies of scaled to length and copies scaled to length . The metric is the shortest-path distance and . A random request sequence of vertex sets advances through the copies (alternately, then by fair coins), keeping the other branch's current vertex as a waiting vertex, and finally drops the branch that advanced more. The map records the depth and, for each level and branch , the aggregate branch function : the distance of to the nearer endpoint of the level- copy containing it if is on branch of that copy, and otherwise.
There is a universal such that for every , every -dimensional real normed space , every start point and every deterministic or randomized online algorithm,
The result. Combined with Sellke's algorithm, Theorem 1 determines the competitive ratio of convex body chasing up to a constant factor in every norm: . It closes the polynomial gaps that remained for general norms ( versus ) and for , ( versus ), and answers negatively whether any norm, the Euclidean one included, admits a sublinear ratio. Since nested chasing has sublinear ratio in every with (BKL+19), general chasing is strictly harder than nested chasing. Proposition 9 alone is the first linear lower bound for with .
Formalizing it. The result is proved on paper, in a recent submission; none of it has a machine-checked proof. A complete development checks the reduction from metrical service systems to convex body chasing (Lemmas 4–8, Proposition 9) and the transfer to arbitrary norms, and it would contain the first formal statements and proofs of two cited results the argument rests on: the Bubeck–Coester–Rabani lower bound (Lemma 3) and Milman's quotient-of-a-subspace theorem (Lemma 10).
Convexity gives the online algorithm more freedom than the discrete instance: a point of is a weighted average of mapped vertices, and a small movement of the average need not correspond to a cheap transport of the weights. Any embedding of into dimensions that only approximately preserves distances therefore fails to transfer the discrete lower bound; the comparison has to hold for distributions on consecutive requests specifically (Lemma 8), which requires an exact description of what consecutive requests look like (Lemmas 5, 7, Corollary 6).
The discrete lower bound (Lemma 3) itself needs the strengthened induction of BCR §3.5, since an algorithm may switch branches after seeing part of a recursive call. Milman's theorem (Lemma 10) is a deep result of asymptotic geometric analysis, absent from Mathlib. The general-norm step cannot simply apply John's theorem: a Banach–Mazur distortion would destroy the linear bound.
The chasing model is a normed space X with FiniteDimensional ℝ X and Module.finrank ℝ X = d; request sequences are List (Set X). Online algorithms are maps from request prefixes to points, feasible along sequences of bodies, with the start point on the empty prefix. A randomized algorithm is a probability space of seeds with a deterministic algorithm per seed and measurable decisions; its expected cost is a lower Lebesgue integral in . "" means: every with on all finite sequences of bodies has . There is no additive constant, as in the source's definition.
The graphs are encoded with an explicit finite vertex type (branch, copy index, inner vertex), copies by address paths, and as an infimum over walks. is a probability mass function on annotated request sequences that record the active calls and the retained waiting vertices; algorithms see only the plain vertex sets. Statements hold for both tie rules of Stage 3. Randomized algorithms on the discrete requests are in the distributional form of the source (p.4): a probability vector after each prefix, paying between consecutive ones. is PiLp p, with written (p⁻¹).toReal so that is included. The goal, Lemma 3, Proposition 9 and Lemma 10 carry their constants , , as single existentials before every other quantifier.
Trivializations ruled out: algorithm feasibility is required only for bodies, so algorithms exist (a sanity file constructs one, and a Dirac randomized one); the parameter structure contains only the source's conditions and is satisfiable; the annotation ties "the call to " and the waiting set of Lemma 5 to the construction instead of letting them be chosen freely.
Reusable infrastructure: the chasing model, finite , shortest-path metrics of weighted graphs, and the BCR graphs and request distribution, which also underlie the randomized -server lower bound. Welcome contributions: proofs of the structural Lemmas 4, 5, 7 and Corollary 6, the transport inequality of Lemma 8, and any of the three deep inputs.
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
There is a universal constant such that, for every and every norm on , any algorithm for convex body chasing in has competitive ratio at least .
Precisely: let be a real normed space of dimension , let , and let be a deterministic or randomized online algorithm for chasing nonempty closed convex sets starting at , where is unknown in advance. If for some
for every finite sequence of nonempty closed convex sets, then . The constant does not depend on , on the norm, on or on the algorithm.
The bound matches the 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, , 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. "" is stated as "every for which the algorithm is -competitive satisfies ", which also covers an infinite competitive ratio and avoids a ratio with .
Differences from the source:
No open leaves. Every sub-goal is proved or awaiting decomposition.