Theorem 1 — in every -dimensional normed space, every online algorithm for convex body chasing has competitive ratio
ProvedCBCLowerBound.EveryNorm.theorem_1There 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:
- 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
import Mathlib import Definitions.Def_CBCLowerBound_EveryNorm_Chasing
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.