OctoInformBeta

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

Theorem 1.1 [Prescribed-order signed prefixes]: An explicit constant for the signs, and one constant shared by the signs and the reordering of vectors summing to zero

Signing unit-ball vectors in order with prefix sums O(d)O(\sqrt{d})..

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, in a prescribed order. The task is to choose signs ε0,…,εN−1∈{−1,1}\varepsilon_0,\dots,\varepsilon_{N-1}\in\{-1,1\} that keep every prefix sum ∑i<kεivi\sum_{i<k}\varepsilon_i v_i, for k=0,1,…,Nk=0,1,\dots,N, short in the Euclidean norm, with a bound that depends on the dimension dd alone and not on the length NN. The bound sought is CdC\sqrt{d}, with CC an absolute constant.

The library states this signed problem with two companions. In the Steinitz problem the vectors sum to zero and are reordered instead of signed, and every prefix of the reordered sequence is to be short. In the scaled signed problem the vectors have small norm and coordinates indexed by an arbitrary nonempty finite set ι\iota, and |ι|\sqrt{|\iota|} takes the place of d\sqrt{d}.

Prefix Bounds

The space ℝd\mathbb{R}^d is the Euclidean space of real vectors x=(x0,…,xd−1)x=(x_0,\dots,x_{d-1}) with the norm ∥x∥=(∑j<dxj2)1/2\|x\|=\bigl(\sum_{j<d}x_j^2\bigr)^{1/2}.✦ For a finite set ι\iota, the space ℝι\mathbb{R}^\iota is the Euclidean space of real vectors b=(bj)j∈ιb=(b_j)_{j\in\iota}, and the mass of a vector b∈ℝιb\in\mathbb{R}^\iota is its squared norm ∥b∥2=∑j∈ιbj2\|b\|^2=\sum_{j\in\iota}b_j^2.

For a real number CC, the signed prefix bound SB(C)\mathrm{SB}(C) is the statement that for all integers d≥1d\ge 1 and N≥1N\ge 1 and all vectors v0,…,vN−1∈ℝdv_0,\dots,v_{N-1}\in\mathbb{R}^d with ∥vi∥≤1\|v_i\|\le 1 there are signs ε0,…,εN−1∈{−1,1}\varepsilon_0,\dots,\varepsilon_{N-1}\in\{-1,1\} such that ∥∑i<kεivi∥≤Cdfor k=0,1,…,N.\Bigl\|\sum_{i<k}\varepsilon_i v_i\Bigr\|\le C\sqrt{d}\qquad\text{for } k=0,1,\dots,N.(1)✦

The ordering prefix bound OB(C)\mathrm{OB}(C) of a real number CC is the statement that for all integers d≥1d\ge 1 and N≥1N\ge 1 and all vectors v0,…,vN−1∈ℝdv_0,\dots,v_{N-1}\in\mathbb{R}^d with ∥vi∥≤1\|v_i\|\le 1 and ∑i<Nvi=0\sum_{i<N}v_i=0 there is a permutation π\pi of {0,…,N−1}\{0,\dots,N-1\} such that ∥∑i<kvπ(i)∥≤Cdfor k=0,1,…,N.\Bigl\|\sum_{i<k}v_{\pi(i)}\Bigr\|\le C\sqrt{d}\qquad\text{for } k=0,1,\dots,N.(2)✦

The Constants

With the exponent p=3/2p=3/2, the gain constant γ\gamma, the epoch factor EE, the state rate α\alpha, the body rate β\beta, the body scale BB, the increment constant II, the moment constant MM, the survival radius ρ\rho, the state radius RR, the slab radius ss, the signing scale δ\delta and the universal constant C0C_0 are the real numbers γ=p2p,E=1+16γ,α=84E+2,β=2α+1,B=1000(2β+1),I=230400(1+16γ1/p),M=I+20,ρ=800(640M+2),R=4ρ,s=800(640+2),δ=18Bs,C0=2BRδ.\begin{aligned} \gamma&=p\,2^{p}, & E&=1+16\gamma, & \alpha&=84E+2,\\ \beta&=2\alpha+1, & B&=1000\,(2\beta+1), & I&=230400\,\bigl(1+16\,\gamma^{1/p}\bigr),\\ M&=I+20, & \rho&=800\,(640M+2), & R&=4\rho,\\ s&=800\,(640+2), & \delta&=\frac{1}{8Bs}, & C_0&=\frac{2BR}{\delta}. \end{aligned}(3)

The Claim

Theorem 1 (Prescribed-order signed prefixes). (a) There is a real number CC such that SB(C)andOB(C)hold.\mathrm{SB}(C)\quad\text{and}\quad\mathrm{OB}(C)\quad\text{hold.}(4)✦

(b) For the universal constant C0C_0 of (3), SB(C0)holds.\mathrm{SB}(C_0)\quad\text{holds.}(5)✦

(c) Let ι\iota be a nonempty finite set, let nn be a natural number, and let b0,…,bn−1b_0,\dots,b_{n-1} be vectors in ℝι\mathbb{R}^\iota, each of mass at most δ2\delta^2. Then there are signs ε0,…,εn−1∈{−1,1}\varepsilon_0,\dots,\varepsilon_{n-1}\in\{-1,1\} such that ∥∑i<kεibi∥≤2BR|ι|for k=0,1,…,n.\Bigl\|\sum_{i<k}\varepsilon_i b_i\Bigr\|\le 2BR\sqrt{|\iota|}\qquad\text{for } k=0,1,\dots,n.(6)✦

What Is Checked

The three claims are stated over the Euclidean spaces ℝd\mathbb{R}^d and ℝι\mathbb{R}^\iota with the mass of a vector, the prefix bounds SB\mathrm{SB} and OB\mathrm{OB} of (1) and (2), and the constants of (3), from the exponent pp to the universal constant C0C_0.