The Vector Balancing Constant for Zonotopes

The vector balancing constant vb(K,Q) of two symmetric convex bodies K,Q is the minimum r ≥ 0 so that any number of vectors from K can be balanced into an r-scaling of Q. A question raised by Schechtman is whether for any zonotope K subseteq ℝd one has vb(K,K) lesssim √d. Intuitively, this asks whether a natural geometric generalization of Spencer's Theorem (for which K = Bd_∞) holds. We prove that for any zonotope K subseteq ℝd one has vb(K,K) lesssim √d log log log d. Our main technical contribution is a tight lower bound on the Gaussian measure of any section of a normalized zonotope, generalizing Vaaler's Theorem for cubes. We also prove that for two different normalized zonotopes K and Q one has vb(K,Q) lesssim √d log d. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.