The Setting
Take vectors in the unit ball of , in a prescribed order. The task is to choose signs that keep every prefix sum , for , short in the Euclidean norm, with a bound that depends on the dimension alone and not on the length . The bound sought is , with an absolute constant.
The library states this signed problem with two companions. In the Steinitz problem the vectors sum to zero and are reordered instead of signed, and every prefix of the reordered sequence is to be short. In the scaled signed problem the vectors have small norm and coordinates indexed by an arbitrary nonempty finite set , and takes the place of .
Prefix Bounds
The space is the Euclidean space of real vectors with the norm .✦ For a finite set , the space is the Euclidean space of real vectors , and the mass of a vector is its squared norm .
For a real number , the signed prefix bound is the statement that for all integers and and all vectors with there are signs such that (1)✦
The ordering prefix bound of a real number is the statement that for all integers and and all vectors with and there is a permutation of such that (2)✦
The Constants
With the exponent , the gain constant , the epoch factor , the state rate , the body rate , the body scale , the increment constant , the moment constant , the survival radius , the state radius , the slab radius , the signing scale and the universal constant are the real numbers (3)
The Claim
Theorem 1 (Prescribed-order signed prefixes). (a) There is a real number such that (4)✦
(b) For the universal constant of (3), (5)✦
(c) Let be a nonempty finite set, let be a natural number, and let be vectors in , each of mass at most . Then there are signs such that (6)✦
What Is Checked
The three claims are stated over the Euclidean spaces and with the mass of a vector, the prefix bounds and of (1) and (2), and the constants of (3), from the exponent to the universal constant .