OctoInformBeta

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

§1 (setting): signed prefixes and orderings: Constants CC such that suitable signs, or a suitable order of a zero-sum family, keep every prefix sum in ℝd\mathbb{R}^d within CdC\sqrt{d}

Signed and reordered prefix sums in the Euclidean unit ball.

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 the unit ball of ℝd\mathbb{R}^d and add them up one at a time: the partial sums trace a walk that starts at the origin. Two classical questions ask how close to the origin a good choice can keep this walk. In vector balancing each step may be turned around, and the choice is a sign εi∈{−1,1}\varepsilon_i \in \{-1, 1\} for each vector. When the vectors sum to zero, as in the Steinitz lemma, the choice is instead the order in which they are added. Both ask for a bound CdC\sqrt{d} on the norm of every prefix sum, with a constant CC that depends neither on the dimension dd nor on the number NN of vectors.

The Definition

Definition 1. For a natural number dd, the Euclidean space ℝd\mathbb{R}^d is the real vector space of tuples x=(x0,…,xd−1)x = (x_0, \dots, x_{d-1}) with the norm ∥x∥=(∑j=0d−1xj2)1/2.\|x\| = \Big( \sum_{j=0}^{d-1} x_j^2 \Big)^{1/2}.(1)✦ For a family v=(v0,…,vN−1)v = (v_0, \dots, v_{N-1}) of vectors in ℝd\mathbb{R}^d and a natural number kk, the kk-th prefix sum of the walk with steps viv_i is the vector Sk(v)=∑0≤i<Ni<kvi.S_k(v) = \sum_{\substack{0 \le i < N \\ i < k}} v_i .(2)✦ A real number CC is a signed prefix bound if, for all integers d≥1d \ge 1 and N≥1N \ge 1 and every family v=(v0,…,vN−1)v = (v_0, \dots, v_{N-1}) of vectors in ℝd\mathbb{R}^d with ∥vi∥≤1\|v_i\| \le 1 for all ii, there are signs ε0,…,εN−1∈{−1,1}\varepsilon_0, \dots, \varepsilon_{N-1} \in \{-1, 1\} such that the family εv=(ε0v0,…,εN−1vN−1)\varepsilon v = (\varepsilon_0 v_0, \dots, \varepsilon_{N-1} v_{N-1}) satisfies ∥Sk(εv)∥≤Cdfor k=0,1,…,N.\|S_k(\varepsilon v)\| \le C \sqrt{d} \qquad \text{for } k = 0, 1, \dots, N.(3)✦ A real number CC is an ordering prefix bound if, for all integers d≥1d \ge 1 and N≥1N \ge 1 and every family v=(v0,…,vN−1)v = (v_0, \dots, v_{N-1}) of vectors in ℝd\mathbb{R}^d with ∥vi∥≤1\|v_i\| \le 1 for all ii and v0+…+vN−1=0v_0 + \dots + v_{N-1} = 0, there is a permutation π\pi of {0,…,N−1}\{0, \dots, N-1\} such that the reordered family v∘π=(vπ(0),…,vπ(N−1))v \circ \pi = (v_{\pi(0)}, \dots, v_{\pi(N-1)}) satisfies ∥Sk(v∘π)∥≤Cdfor k=0,1,…,N.\|S_k(v \circ \pi)\| \le C \sqrt{d} \qquad \text{for } k = 0, 1, \dots, N.(4)✦

In the paper, the setting reads: vectors v1,…,vNv_1, \dots, v_N in the Euclidean unit ball of ℝd\mathbb{R}^d, their signed prefixes ∑i≤kεivi\sum_{i \le k} \varepsilon_i v_i and, for a family summing to zero, the prefixes ∑i≤kvπ(i)\sum_{i \le k} v_{\pi(i)} of a permutation π\pi, for 0≤k≤N0 \le k \le N; with the indices shifted down by one, its ∑i≤k\sum_{i \le k} is the page’s SkS_k.

What Is Checked

The signed and the ordering prefix bounds are stated over the Euclidean space (1), for every dimension d≥1d \ge 1 and length N≥1N \ge 1: over families v0,…,vN−1v_0, \dots, v_{N-1} of vectors of norm at most 11 with their prefix sums (2), signs εi∈{−1,1}\varepsilon_i \in \{-1, 1\}, and permutations π\pi of {0,…,N−1}\{0, \dots, N-1\}.