Keeping every partial sum of a vector sequence under control

← All digests

Family 097 · Convex and metric geometry
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-14

1. The question

Imagine following a sequence of short steps in $\mathbb R^d$. You may reverse the direction of each step, but must keep their prescribed order. Can you choose the reversals so that the entire walk stays near the origin, however long the sequence is?

A related problem starts with steps whose total is zero. This time the directions are fixed, but you may reorder the steps. Can every intermediate position remain close to the origin?

Family 097 contains one manuscript claiming a bound of order $\sqrt d$ for both problems when every step has Euclidean length at most one. The same signs or permutation must control all prefixes simultaneously. The total number of steps does not appear in the bound.

The rearrangement statement resolves the Euclidean Steinitz–Bergström growth question as formulated in the source. A regular simplex shows that the square-root dependence on dimension cannot be improved in order.

2. Background and essential definitions

For vectors $v_1,\ldots,v_N$, a prefix sum uses the first $k$ terms for some $0\leq k\leq N$. The empty prefix is zero.

In the signed problem, choose $\varepsilon_i\in\{-1,1\}$ and control

$$\max_{0\leq k\leq N}\left|\sum_{i=1}^k\varepsilon_iv_i\right|_2.$$

There is no zero-total assumption here. Each vector is either kept or reversed, and the order stays fixed.

In the rearrangement problem, assume $\sum_i v_i=0$, choose a permutation $\pi$, and control

$$\max_{0\leq k\leq N}\left|\sum_{i=1}^kv_{\pi(i)}\right|_2.$$

The Euclidean Steinitz constant $S_2(d)$ is the worst, over all finite zero-sum families in the unit ball, of the smallest possible maximum prefix norm. Indexed families are used so that repetitions count as distinct entries to be permuted.

A terminal balancing theorem controls only the final signed sum. It is weaker in its quantifiers: choosing a good signing separately for every prefix may give incompatible choices. The present question asks for one signing that works for every stopping time along the prescribed list.

The theorem is also offline. The signs may be chosen using the complete sequence. An online rule would have to choose a sign before seeing later vectors and is a different requirement.

3. Development history and previous partial results

Steinitz’s rearrangement theory grew from questions about conditionally convergent vector series. For general norms in dimension $d$, Grinberg and Sevast’yanov proved a bound of $d$ times the unit ball. Euclidean geometry suggests a smaller square-root scale, discussed in classical work including Behrend’s 1954 account and recorded in modern form by Ambrus and Heck.

Prescribed-order signing has its own history. Banaszczyk’s work on signed vector series gave a bound with a dimension term and an additional dependence on sequence length. Bansal, Jiang, Meka, Singla and Sinha’s prefix-discrepancy paper explicitly formulates the square-root-dimensional conjecture.

A 2026 preprint by Dutta, Jha and Jiang gives an efficient bound of the form

$$O\left(\sqrt d+d^{1/4}\log^{7/4}N\right)$$

for signing, with a corresponding ordering result. M1 claims to remove the length term entirely, while making no efficient-algorithm assertion.

Chobanyan’s transference principle links signing and rearrangement. The finite form used here places positively signed vectors in their original order and negatively signed vectors in reverse order. This established principle turns a signed-prefix theorem into the zero-sum ordering theorem.

The analytic construction draws on Gaussian vector balancing and more recent directional-density and symmetrization methods. The manuscript credits Guo, Fang and Lu’s directional total-variation approach, related Dirichlet-energy formulations, and Gaussian correlation. These methods concern finding a compatible set of signs, not merely applying a final-sum theorem separately at each prefix.

4. What the new manuscripts claim

M1 states that an absolute constant $C$ exists such that, for every $d,N\geq1$ and every sequence with $|v_i|_2\leq1$, there are signs satisfying

$$\max_{0\leq k\leq N}\left|\sum_{i=1}^k\varepsilon_i v_i\right|_2 \leq C\sqrt d.$$

The same constant gives, for every zero-sum family, a permutation with

$$\max_{0\leq k\leq N}\left|\sum_{i=1}^kv_{\pi(i)}\right|_2 \leq C\sqrt d.$$

Consequently the source states

$$\frac12\sqrt d\leq S_2(d)\leq C\sqrt d.$$

The lower example uses the $d+1$ unit vertices of a regular simplex centered at the origin. Distinct vertices have inner product $-1/d$, so any sum of $k$ of them has squared norm $k(d+1-k)/d$, independently of their order. A prefix containing about half the vertices must therefore have square-root-dimensional size.

Norm comparison gives a further consequence for $\ell_p^d$, $1\leq p\leq\infty$: unit-ball inputs admit signed prefixes, and zero-sum inputs admit reordered prefixes, bounded by

$$C d^{\max\{1/p,\,1-1/p\}}.$$

The source claims sharp dimensional order for $1\leq p\leq2$, not throughout the entire range above two.

There is also a colorful array version. If unit vectors are arranged in equally long rows and their global total is zero, each row can be permuted so that the aggregate of the first $m$ entries of every row has norm at most $2C\sqrt d$, simultaneously for all $m$. Individual rows need not sum to zero, and the bound concerns their combined synchronous prefixes.

5. Why the advance matters

Importance: 4/5. The result would settle the optimal dimensional order of a classical Euclidean rearrangement problem and the stronger prescribed-order signing question. The improvement is uniform in sequence length, including sequences much longer than any fixed function of dimension.

Uniform control of all prefixes is useful whenever a cumulative process may be stopped at an arbitrary stage. A small final total does not prevent a large excursion in the middle. The claimed theorem prevents those excursions through one globally coordinated choice.

The transference also clarifies the relationship between two kinds of freedom. Reversing steps in a fixed order and reordering zero-sum steps are different operations, yet the signed estimate is strong enough to control the ordering problem with the same constant.

The score reflects a substantial classical resolution and its balancing consequences. It does not imply an optimal numerical constant, an online strategy, or a polynomial-time implementation. The constructive length-dependent predecessors retain algorithmic advantages not asserted by this existence theorem.

6. The main idea

Encode all prefixes in one convex body

The proof introduces a coefficient space with one coordinate for each incoming vector, together with initial-state coordinates. Linear maps turn these coefficients into a sequence of states in $\mathbb R^d$.

Each update contracts the old state and injects a multiple of the next vector. Requiring every state to remain in a prescribed ball defines a symmetric convex body in the larger coefficient space. One point of that body will encode a signing controlling the whole walk.

The contractions initially change the desired partial sums. A carefully chosen scalar shift in each incoming coefficient compensates for the lost part of the previous state. When the coefficients are finally selected in the allowed shifted-sign form, the resulting states become the actual signed prefix sums.

Turn low energy into compatible signed steps

The first analytic ingredient concerns Dirichlet energy, an integral of squared derivatives. If the coefficient body has sufficiently small energy in every positively weighted coordinate direction, the manuscript constructs one square root of a probability density whose coordinate derivatives are all controlled.

A lifted Steiner symmetrization preserves those estimates. It then permits a coordinate choice of the form $q+\varepsilon$, where $|q|\leq1/4$ and $\varepsilon\in\{-1,1\}$. The shift may depend on earlier choices and is designed to cancel the state contraction.

This produces one compatible sequence of choices. It is stronger than showing that each individual coordinate can be selected successfully in isolation.

Bound energy without paying for the number of states

The second ingredient estimates survival of a stationary Ornstein–Uhlenbeck process in coefficient space. This is a Gaussian diffusion with a restoring drift, so its stationary distribution is Gaussian. Survival probabilities in a region are related to its Dirichlet-energy scale.

The states are organized by dyadic spectral scales of their covariance matrices. A matrix-variation estimate controls changes by an additive trace budget, even when the contractions do not commute. At each scale, groups with bounded accumulated energy retain a uniform positive probability of satisfying all their constraints over a matched time interval.

Gaussian correlation combines the groups and scales. The resulting exponential survival rate gives an energy bound independent of how many filters or prefixes occur. That independence is what removes the sequence-length term.

For the final transfer to rearrangement, start from an ordering with optimal maximum $\beta$. If $A_j$ and $B_j$ are its ordinary and signed prefix sums, the positive and negative selections have sums $(A_j+B_j)/2$ and $(A_j-B_j)/2$. Positive-forward, negative-reverse ordering therefore gives maximum at most $(\beta+C\sqrt d)/2$. Minimality of $\beta$ yields $\beta\leq C\sqrt d$.

7. Scope, limitations, and open questions

The signing theorem allows arbitrary finite sequences of Euclidean unit-ball vectors, with no zero-total assumption. The permutation theorem requires total zero and changes no vector signs. Repetitions and zero vectors are allowed in both.

The existence choices can depend on the full input. A proof that selects signs successively after global preparation does not automatically yield an online rule. The source also makes no efficient-algorithm claim.

The Euclidean square-root bound is not a constant $\ell_\infty$ bound for all prefixes. The stated norm-comparison consequence gives order $d$ at $p=\infty$. Similarly, the colorful statement controls the aggregate across rows, not each row individually.

The sharp numerical constant and the strongest algorithmic or other-norm variants remain separate questions. The digest follows the source’s Gaussian-energy strategy and dependencies without checking the analytic estimates.

8. Sources and further reading

M1 states the signing and ordering theorems, gives the simplex lower example, and proves the transference immediately in its introduction. Its final section records the $\ell_p$ and colorful consequences with their precise quantifiers.

The linked prefix-discrepancy and 2026 constructive papers explain earlier sequence-length dependence. Chobanyan’s rearrangement principle and Bárány’s A matrix version of the Steinitz lemma (2024), cited in M1, supply the earlier transference mechanisms used for the ordering and array consequences.

Source manuscripts

• M1. OpenAI, The Euclidean Steinitz–Bergström theorem (September 24, 2026).

Sources consulted on 14 October 2026 at repository revision 1581d4c. Download the manuscript citations.