Let be vectors in the Euclidean unit ball of . The signing problem asks for one choice of signs for which every signed prefix sum , , has norm at most a bound depending only on . When , the ordering problem keeps the vectors unsigned and asks instead for an order in which every prefix sum is small. For such a zero-sum family, define , where is the set of permutations of . The Euclidean Steinitz constant is the supremum of over all finite zero-sum families in the unit ball of . The Euclidean Steinitz-Bergström conjecture asks whether .
The ordering problem goes back to Steinitz’s work on conditionally convergent vector series. Ambrus and Heck give a historical account of it. Grinberg and Sevast’yanov proved that, for an arbitrary norm on , every finite zero-sum family in the unit ball has an order whose partial sums stay within times the unit ball. Behrend discussed the expected growth on the smaller scale in Euclidean space. The modern formulation of the conjecture and its attribution to Bergström are recorded by Ambrus and Heck. For the signing problem, the question of a bound was stated explicitly by Bansal, Jiang, Meka, Singla and Sinha, following Banaszczyk. Their discussion records the bound of Banaszczyk, which grows with . Dutta, Jha and Jiang state an efficient signing bound . Chobanyan’s transference principle relates rearrangements to signed sums.
The preprint proves that there is an absolute constant such that, for all , every sequence in the unit ball of has signs with for every (Theorem 1.1). With the same constant, every zero-sum family in the unit ball of has a permutation with for every (Theorem 1.2). Theorem 1.2 resolves the Euclidean Steinitz-Bergström conjecture. The preprint also exhibits, in a -dimensional Euclidean space, unit vectors with pairwise inner products that sum to zero and have, in every order, a prefix sum of norm at least . The Lean library does not contain this example.
The Lean library Steinitz proves Theorem 1.1 and Theorem 1.2 as the preprint states them, without hypotheses. Lean has checked every result of the Lean library, so the Lean library is the reference. Each result on these pages is stated as the Lean library states it and linked to the Lean declaration behind it, with the preprint’s statement beside it where the two differ. The preprint is a guide only, which gives the results their order and their names. The Lean library proves the Gaussian correlation inequality of Royen for closed centrally symmetric convex sets under a centered Gaussian measure on a finite-dimensional space.
Steinitz is a Lean library: 26 items, in five groups. Each has a page written by OctoInform, listed below.
No item matches.