Skip to content
All apps

Steinitz walk — short partial sums at any length (3D)

About this app

Many short arrows, each may be flipped: does the walk of partial sums stay in a ball of radius √d, however long it is? Random signs run off like √n, the greedy choice fails against an adversarial sequence, a search over the whole sequence stays inside. Sliders for steps (up to 2000) and dimension (2–12), charts over n and over d. Euclidean Steinitz–Bergström theorem, openai/math family 097 (formalised in Lean). Exhibit-ready.

What it is about

You have many arrows of length at most 1 in a fixed order and may flip each one. Can the signs be chosen so that the walk of accumulated arrows never strays far from the start, however long it gets? The question goes back to Ernst Steinitz (1913). Bounds proportional to d (Grinberg and Sevast’yanov 1980) and √(d·log n) (Banaszczyk 2012) were known; √d was conjectured. An AI-generated preprint in github.com/openai/math (family 097) claims a bound C·√d for every dimension and every sequence. The catalogue lists the main theorem as formalised in Lean; the preprint is not peer-reviewed.

What the app shows

A ball of radius √d surrounds the starting point, and three walks run through the same sequence of arrows. Random signs drift away like √n. The greedy choice only sees the past and fails against an adversarial sequence whose arrows stand perpendicular to the current sum. A balanced choice searches over the whole sequence and stays inside. Sliders set up to 2000 steps and dimension 2 to 12; charts show the distances against n and against d. For d > 3 you see a projection, and the colour shows the true length.

What to look for

Make the walk longer: the random one keeps drifting outwards, while the balanced one stays inside the ball regardless of the number of steps. Raise the dimension and watch the required bound grow with √d. You cannot do better: with the basis vectors, the partial sum after d steps always has length √d. The proof is existential; it gives no algorithm and no value for C, and the search in the app is a heuristic. The app can run as an exhibit.

Frequently asked questions

What does the Steinitz lemma say?
The Steinitz lemma states that if finitely many vectors of length at most 1 in d-dimensional space sum to zero, they can be reordered so that every partial sum is bounded by a constant depending only on d. The number of vectors does not matter. How this constant depends on d was open.
What is discrepancy for signed sums?
In a signing problem you give each vector of a sequence a + or − and look at the length of the partial sums. The discrepancy is the smallest achievable maximum partial sum. Random signs typically give partial sums of size √n, while a clever choice can keep them independent of n.
Has the √d bound for partial sums been proved?
An AI-generated preprint in the catalogue github.com/openai/math (family 097) claims there is a fixed constant C such that, for every dimension and every sequence, all partial sums stay within C·√d; the Steinitz version follows. The catalogue lists the main theorem as formalised in Lean. The preprint has not yet been peer-reviewed.
What can I try out in this app?
You set the number of steps and the dimension and compare three signing strategies: random, greedy and a search over the whole sequence. The ball of radius √d shows which one stays inside. Charts plot the distances against n and against d.

Subject: Open problems, solved by AI

More from Open problems, solved by AI

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps