The Euclidean Steinitz–Bergström bound

One choice of signs keeps every running total of unit vectors within a constant times √d, at any length.

1 paper September 24, 2026 Explained by AI

Take a list of arrows, each at most one unit long, in a space with d directions. You may flip each arrow but must keep the order. This paper proves (Lean proof listed) that some flips keep every running total within a fixed multiple of √d. The bound does not grow with the length of the list. So arrows that add up to zero can be ordered to keep every running total within the same bound.

First step

1980

Grinberg and Sevast'yanov, a bound of d for every norm

Significance

Major

It removes the length term from known bounds and fixes the Euclidean Steinitz constant up to a constant factor.

Trust

Formal proof listed

Field

Convex and metric geometry

1 paper

The explanation

Take a list of arrows on a flat page, each at most one unit long. Here is one: right, up, right, up, and so on, eight arrows in all. Walk them in order and you drift away. After all eight you stand at the point (4, 4), about 5.66 units from the start. Now you may flip any arrow to point the opposite way. Flipping is the only move allowed; the order stays fixed. Choose plus, plus, minus, minus, and repeat. The walk visits (1, 0), (1, 1), (0, 1) and (0, 0), then loops. It never gets farther than √2, about 1.41, from the start. A search over all 256 sign choices finds nothing better.

The real question is how far you must stray in the worst case. The arrows may live in a space with any number of directions, called the dimension d. The list may have any length N. A prefix sum is the total of the first few signed arrows: one point along the walk. One choice of signs must keep every prefix sum close, not just the last one.

A simple rule shows why length is the enemy. At each step, pick the sign that leaves you nearer the start. Then your squared distance grows by at most 1 per step. That only guarantees a distance of √N after N steps. For 10,000 arrows the guarantee is 100 units, and it keeps growing. The paper names the difficulty plainly. One choice of signs must control every prefix, with a bound that does not depend on NSource 1.

The problem is old. It goes back to Steinitz's work on series of vectors whose order matters. In 1980, Grinberg and Sevast'yanov studied the ordering version for every way of measuring length. They kept the partial sums within d times the unit size. For ordinary straight-line length, called Euclidean length, a much smaller square-root scale was long expected. Behrend discussed it in 1954. For the signing problem, Banaszczyk's bound was of order √d + √(log N). In 2021, Bansal, Jiang, Meka, Singla and Sinha stated the pure √d question explicitly. A 2026 preprint by Dutta, Jha and Jiang states an efficient bound of order √d + d^(1/4)·(log N)^(7/4). Each of these bounds still grows with the length N, however slowly.

This paper proves (Lean proof listed) a bound with no length term at all. There is one fixed number C that works everywhere. Take any dimension d, any length N, and any list of arrows at most one unit long. Some signs keep every prefix sum within C√d. The same C serves every listSource 2. Repeated arrows and zero arrows are allowedSource 3. The proof shows the signs exist, and they may depend on the whole list. It gives no rule for picking signs as arrows arrive, and no efficient algorithmSource 4.

A second question follows. Suppose the arrows add up to zero. Now you may not flip any arrow, but you may change their order. The Steinitz constant is the worst-case distance you must accept in the best order. The paper turns good signs into a good order with a short trick. Put the plus-sign arrows first, in their original order. Then add the minus-sign arrows in reverse orderSource 5. Every point of the new walk is then controlled by the old bounds. So some order keeps every prefix sum within C√d. This settles the Euclidean Steinitz–Bergström conjecture, which asked for exactly this √d scaleSource 6.

The √d scale cannot be beaten. Take four arrows from the centre of a regular tetrahedron to its four corners, each one unit long. They live in three dimensions and add up to zero. Any two of them add up to about 1.155 units. So every order passes a point at least 1.155 from the start. The same shape in d dimensions forces a distance of at least half of √dSource 7. The Steinitz constant therefore lies between ½√d and C√dSource 8. The paper also derives versions for other ways of measuring lengthSource 9. Another covers grids of arrows whose rows are reordered separately.

How sure is this? A computer proof checker called Lean has checked a formal version of the main statements. It covers the signed bound with one constant C and the reordering bound for lists that sum to zero. The lower bound of ½√d and the other derived versions are outside the Lean scope note. No specialist review has been published.

What it doesn't show. This does not give an efficient algorithm or a rule that picks the signs as the vectors arrive.

Where it came from

This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026.

Hype check

Major if it holds. The main signed and reordering statements have a Lean proof listed with a Comparator statement. The ½√d lower bound and the other derived versions are outside the Lean scope note. No specialist review is published.

Words used

Dimension: The number of independent directions in a space; a flat page has 2.
Prefix sum: The total of the first few vectors in a list, one point along the walk.
Signing: A choice of plus or minus for each vector, flipping the minus ones.
Euclidean length: Ordinary straight-line length, found with Pythagoras' rule.
Steinitz constant: The worst-case distance that the best ordering of a zero-sum list must still reach.
Lean: A computer proof checker that confirms each step of a formal proof.

The original paper

The Euclidean Steinitz–Bergström theorem (PDF, opens in a new tab)
September 24, 2026 Formal proof listed

Lean notes

All quoted lines (9)

The difficulty in the first problem is to control every prefix by one choice of signs, with a bound independent of $N$ .
The Euclidean Steinitz–Bergström theorem Back to text
The same signs control all prefixes, and $C$ is independent of $d$ , $N$ and the sequence.
The Euclidean Steinitz–Bergström theorem Back to text
Both statements allow repetitions and zero vectors.
The Euclidean Steinitz–Bergström theorem Back to text
Its successive choice of signs does not supply an online rule or an efficient algorithm.
The Euclidean Steinitz–Bergström theorem Back to text
Place all positive-sign indices in their original order, followed by all negative-sign indices in reverse original order.
The Euclidean Steinitz–Bergström theorem Back to text
Theorem … gives its affirmative resolution.
The Euclidean Steinitz–Bergström theorem Back to text
These unit vectors sum to zero and satisfy $\langle u_i,u_j\rangle=-1/d$ for $i\ne j$ .
The Euclidean Steinitz–Bergström theorem Back to text
Thus $\tfrac12\sqrt d\le S_2(d)\le C\sqrt d\qquad(d\ge1).$
The Euclidean Steinitz–Bergström theorem Back to text
The signed-prefix bound also yields finite-dimensional $\ell_p$ estimates and a colorful row-permutation theorem.
The Euclidean Steinitz–Bergström theorem Back to text