Euclidean vector balancing: signed prefixes and Steinitz orderings

Source and verification

This article explains family 097 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Signed prefixes and reordered prefixes

Let $v_1,\dots ,v_N$ lie in the Euclidean unit ball of ${\mathbb{R}}^d$. There are two related balancing problems.

In the first, the input order is fixed and signs can be chosen. One asks for a single sign sequence controlling every prefix: ${\sum }_{i\le k}{\epsilon }_i{v}_i$.

In the second, assume ${\sum }_i{v}_i=0$, keep every vector’s sign, and choose a permutation controlling the ordinary partial sums. The Euclidean Steinitz constant $S_2(d)$ is the worst, over all finite zero-sum unit-ball families, of the best possible maximum prefix norm.

The number of vectors $N$ is unrestricted. A bound growing with $\sqrt{N}$ would not solve the dimension-only problem.

🏷️ The two claimed estimates

Statements in the manuscript

There is an absolute $C$ such that every prescribed sequence has signs satisfying

$$\underset{0\le k\le N}{\max }\left|\sum _{i=1}^k{\epsilon }_i{v}_i\right|\le C\sqrt{d}.$$

For every zero-sum family, there is also a permutation $\pi$ with

$$\underset{0\le k\le N}{\max }\left|\sum _{i=1}^k{v}_{\pi (i)}\right|\le C\sqrt{d}.$$

The same constant suffices. (OpenAI, 2026)

The signing assertion needs no zero-sum condition. Both statements allow repeated and zero vectors. The construction may inspect the entire input and is existential; a successive choice in the proof is not automatically an online algorithm.

🏷️ A simplex lower bound

Take the $d+1$ vertices $u_i$ of a regular simplex centered at zero, normalized to unit length. Their inner products satisfy $⟨u_i,u_j⟩=-1/d$ for distinct indices. Every sum of $k$ distinct vertices has squared norm

$$\begin{array}{rl}{\left|\sum _{i\in I}{u}_i\right|}^2& =k+2\left(\genfrac{}{}{0ex}{}{k}{2}\right)\left(-\frac{1}{d}\right)\\ & =\frac{k(d+1-k)}{d}.\end{array}$$

This depends only on $k$, not on the chosen subset. At $k=\lfloor (d+1)/2\rfloor$ it is at least $d/4$. Thus every permutation has a prefix of norm at least $\sqrt{d}/2$:

$$S_2(d)\ge \frac{1}{2}\sqrt{d}.$$

Consequently the claimed upper estimate has the correct order in dimension, although the optimal constant is not determined.

🏷️ The exact transfer from signs to an order

The reduction is short enough to give in full. Fix a zero-sum family and choose an order minimizing its maximum prefix norm, denoted $\beta$. A minimizing order exists because there are finitely many permutations. Relabel in that order, and put

$$A_j=\sum _{i\le j}{v}_i,B_j=\sum _{i\le j}{\epsilon }_i{v}_i,$$

where the signs come from the claimed signing theorem. Then $|A_j|\le \beta$ and $|B_j|\le C\sqrt{d}$.

The positive-sign and negative-sign vectors from an original prefix sum respectively to

$$\begin{array}{rl}{P}_j& =\frac{A_j+B_j}{2},\\ M_j& =\frac{A_j-B_j}{2}.\end{array}$$

Now list the positive-sign indices in their original order, followed by the negative-sign indices in reverse original order. During the first block, each partial sum is some $P_j$. During the second, the unused indices are precisely the negative-sign indices of an original prefix. The total sum is zero, so the current partial sum is some $-M_j$.

Every new prefix has norm at most $(\beta +C\sqrt{d})/2$. Minimality of $\beta$ gives

$$\begin{array}{c}\beta \le \frac{\beta +C\sqrt{d}}{2},\\ \text{hence}\beta \le C\sqrt{d}.\end{array}$$

This includes the cases in which either sign block is empty. The source credits the underlying transference principle and proves this finite form explicitly. (OpenAI, 2026)

🏷️ The simultaneous signing mechanism

Controlling the final signed sum is weaker than controlling all prefixes with the same signs. The manuscript’s main work constructs a feasible region for coefficient states in which every filtered partial state remains bounded.

It places one square-root probability density on this region and controls its coordinate Dirichlet energies, that is, integrals of squared coordinate derivatives. A common density is important: separately favorable densities for different prefixes would not yield one compatible sign sequence.

A lifted geometric step produces a signed update subject to a scalar feasibility inequality. Filtered Ornstein–Uhlenbeck evolution then organizes how the density survives successive restrictions. Here Ornstein–Uhlenbeck evolution is Gaussian smoothing with a compensating contraction toward the origin.

The proof groups spectral scales dyadically and controls a trace budget for matrix variation. Matrices arising at different times need not commute, so a coordinatewise scalar estimate would lose information. The total budget is bounded independently of $N$, which is exactly what prevents a length-dependent loss.

Finally, a predictor shift cancels the contraction introduced by the smoothing evolution. The retained states are therefore actual partial sums of signed input vectors, rather than contracted substitutes that would satisfy an easier problem. These common-density, spectral-budget, and cancellation estimates are the substantive research input to the signing theorem.

🏷️ Key steps and proof outlines

One density must control all coordinate energies

The signing problem can be encoded by a convex symmetric region $K$ of coefficient states. A square-root density is a nonnegative function $f\in H^1({\mathbb{R}}^m)$, supported in $K$, with $\int f^2=1$. Its coordinate energies are $E_i(f)=\int |{\partial }_{i}f{|}^2$. Low energy means the probability density $f^2$ can be shifted slightly in coordinate $i$ without becoming too different.

The source considers the set of simultaneous upper bounds for the vector $(E_i(f))$. A separation argument reduces existence of one density with all required bounds to estimates for arbitrary nonnegative weighted sums of the energies. Convexity follows by mixing densities: if $f,g$ are admissible and $0\le t\le 1$, then $h=\sqrt{t{f}^2+(1-t)g^2}$ is admissible and $E_i(h)\le t{E}_i(f)+(1-t)E_i(g)$. The pointwise derivative estimate follows from Cauchy–Schwarz, with approximation at common zeros. Thus the set of attainable upper-bound vectors is convex, permitting the dual formulation. Proving a separate bound for each $i$ with a different $f$ would not select one compatible signed walk. (OpenAI, 2026)

Survival probabilities control weighted Dirichlet energy

For a positive covariance matrix $Q$, Brownian motion with generator $\mathrm{tr}(Q{\nabla }^2)$ killed on exiting a region has a self-adjoint Dirichlet semigroup. Its leading spectral value is governed by the Rayleigh quotient

$$\frac{\int ⟨Q\nabla f,\nabla f⟩}{\int f^2}.$$

The source estimates the probability that the process survives inside the slab-defined feasible region. Semigroup decay then bounds the lowest Dirichlet energy. The analogous Ornstein–Uhlenbeck argument uses Gaussian measure and the drift toward the origin. On bounded regions, Gaussian and Lebesgue Sobolev form domains agree because the Gaussian density is bounded above and below there.

These survival estimates provide the weighted energy inequalities required by the common-density separation argument. They must be uniform in the number of coefficient coordinates, since that number grows with the input length.

A shifted-sign lemma converts analytic room into a discrete choice

The low-energy density supplies overlap between nearby translated feasible sets. A lifted geometric argument uses that overlap to choose one of two signed updates while allowing a controlled predictor shift. The conclusion is a genuine feasibility statement for the next coefficient state, not merely a small expected increment.

Iterating this lemma keeps every filtered partial state in the region. The filter is a sequence of symmetric contractions built from the input vectors. Its purpose is to make the analytic survival argument possible. But a contracted partial state is not the original signed sum, so the predictor shifts must later be identified exactly.

Matrix variation is paid by trace rather than by time

As the filter changes, its covariance matrices need not commute. The source groups their spectra into dyadic scales and estimates variation using trace quantities. A scalar comparison for the weight on one spectral interval is integrated over the interval; the resulting matrix estimate controls transitions without selecting one eigenbasis for the whole process.

The total trace budget depends on the ambient dimension $d$, not on the number $N$ of updates. This is the analytic source of a dimension-only radius. If one instead bounded each step by an absolute constant and summed, the radius would grow with $N$. If one diagonalized each matrix separately and ignored basis rotation, the omitted terms could accumulate just as badly.

Predictor cancellation returns to the actual walk

In the assembly, the update of the filtered state contains a contraction term and a predictor shift. Write $b_i=\sigma v_i$ with a fixed small $\sigma >0$, choose ${\eta }_i$ so that $C_i=(I-b_i{b}_i^T{)}^{1/2}$, and initialize $R_{0}x=0$. The precise recurrence uses $C_i=I-{\eta }_i{b}_i{b}_i^T$ and $x_{d+i}={\eta }_i{b}_i^T{R}_{i-1}x+{\epsilon }_i$. Substitution into $R_{i}x=C_i{R}_{i-1}x+x_{d+i}{b}_i$ gives $R_{i}x=R_{i-1}x+{\epsilon }_i{b}_i$. The predictor depends only on earlier coordinates, and final membership in the prescribed slabs ensures that the clipping used in constructing the predictor is inactive. What remains is

$$s_k=\sum _{i=1}^k{\epsilon }_i{v}_i$$

with the original vectors, while the feasible-region radius is $O(\sqrt{d})$. The proof checks all prefixes with the same signs. This exact cancellation is the final interface between the continuous smoothing method and the discrete theorem.

The ordering statement then follows from the finite transference argument already given: minimize the maximum ordinary prefix norm, apply the signing theorem in that order, and place positive-sign vectors forward and negative-sign vectors backward. The inequality $\beta \le (\beta +C\sqrt{d})/2$ closes without any further analytic input. The simplex example supplies the matching lower order. Thus the main research burden is the common density, survival, matrix budget, and predictor cancellation needed for simultaneous signing.

See Also

The Gaussian propeller bound uses first moments of a Gaussian partition to constrain vector configurations. Dimension reduction in Lp contrasts exact and approximate preservation of finite Euclidean-type data.

🏷️ Manuscripts and verification scope

• The Euclidean Steinitz–Bergström theorem — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope describes both the prescribed-order signing theorem and the zero-sum rearrangement theorem. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. The Euclidean Steinitz–Bergström theorem.