OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction · §1

Theorem 1.2 [Euclidean Steinitz-Bergström bound]: An absolute CC gives every zero-sum family in the unit ball of ℝd\mathbb{R}^d an ordering with all prefix sums at most CdC\sqrt{d}

Signed prefix bounds give ordering bounds with the same constant.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take vectors v0,…,vN−1v_0, \dots, v_{N-1} in Euclidean space ℝd\mathbb{R}^d, each of norm at most 11. If they sum to zero, how small can a reordering π\pi of the indices make all the prefix sums ∑i<kvπ(i)\sum_{i<k} v_{\pi(i)}, 0≤k≤N0 \le k \le N, uniformly in NN? This is the question of the Steinitz lemma. Its signed counterpart drops the condition on the sum and keeps the order: it asks for signs εi∈{−1,1}\varepsilon_i \in \{-1, 1\} that make every signed prefix sum ∑i<kεivi\sum_{i<k} \varepsilon_i v_i short.

Theorem 1.2, the Euclidean Steinitz-Bergström bound, asks for orderings with every prefix sum of norm at most CdC\sqrt{d}, with CC an absolute constant for which the signed prefix bound, defined below, holds.

The Two Prefix Bounds

For a real number CC, the signed prefix bound with constant CC, written 𝖲(C)\mathsf{S}(C), is the property that for all integers d,N≥1d, N \ge 1 and all vectors v0,…,vN−1v_0, \dots, v_{N-1} in ℝd\mathbb{R}^d of norm at most 11 there are signs ε0,…,εN−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{N-1} \in \{-1, 1\} with ∥∑i<kεivi∥≤Cdfor k=0,1,…,N.\Big\| \sum_{i<k} \varepsilon_i v_i \Big\| \le C\sqrt{d} \qquad \text{for } k = 0, 1, \dots, N.(1)✦

For a real number CC, the ordering prefix bound with constant CC, written 𝖮(C)\mathsf{O}(C), is the property that whenever d,N≥1d, N \ge 1 and v0,…,vN−1v_0, \dots, v_{N-1} are vectors in ℝd\mathbb{R}^d of norm at most 11 with v0+…+vN−1=0v_0 + \dots + v_{N-1} = 0, some permutation π\pi of {0,…,N−1}\{0, \dots, N-1\} gives ∥∑i<kvπ(i)∥≤Cdfor k=0,1,…,N.\Big\| \sum_{i<k} v_{\pi(i)} \Big\| \le C\sqrt{d} \qquad \text{for } k = 0, 1, \dots, N.(2)✦

The Claim

Theorem 1. There is a real number CC for which both prefix bounds hold: 𝖲(C)and𝖮(C).\mathsf{S}(C) \quad \text{and} \quad \mathsf{O}(C).(3)✦ For every real number CC, if the signed prefix bound holds with constant CC, then the ordering prefix bound holds with the same constant: 𝖲(C)⇒𝖮(C).\mathsf{S}(C) \;\Longrightarrow\; \mathsf{O}(C).(4)✦

What Is Checked

The claim is stated over Euclidean space ℝd\mathbb{R}^d and over the signed and ordering prefix bounds 𝖲(C)\mathsf{S}(C) and 𝖮(C)\mathsf{O}(C) of a real number CC, which quantify over every family of N≥1N \ge 1 vectors of norm at most 11 in ℝd\mathbb{R}^d, d≥1d \ge 1, the ordering bound over those summing to zero.