The Setting
Take vectors in the unit ball of and add them up one at a time: the partial sums trace a walk that starts at the origin. Two classical questions ask how close to the origin a good choice can keep this walk. In vector balancing each step may be turned around, and the choice is a sign for each vector. When the vectors sum to zero, as in the Steinitz lemma, the choice is instead the order in which they are added. Both ask for a bound on the norm of every prefix sum, with a constant that depends neither on the dimension nor on the number of vectors.
The Definition
Definition 1. For a natural number , the Euclidean space is the real vector space of tuples with the norm (1)✦ For a family of vectors in and a natural number , the -th prefix sum of the walk with steps is the vector (2)✦ A real number is a signed prefix bound if, for all integers and and every family of vectors in with for all , there are signs such that the family satisfies (3)✦ A real number is an ordering prefix bound if, for all integers and and every family of vectors in with for all and , there is a permutation of such that the reordered family satisfies (4)✦
In the paper, the setting reads: vectors in the Euclidean unit ball of , their signed prefixes and, for a family summing to zero, the prefixes of a permutation , for ; with the indices shifted down by one, its is the page’s .
What Is Checked
The signed and the ordering prefix bounds are stated over the Euclidean space (1), for every dimension and length : over families of vectors of norm at most with their prefix sums (2), signs , and permutations of .