The Vector Balancing Constant for Zonotopes

Abstract

The vector balancing constant $\mathrm{vb}(K,Q)$ of two symmetric convex bodies $K,Q$ is the minimum $r\ge 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 {\mathbb{R}}^d$ one has $\mathrm{vb}(K,K)\lesssim \sqrt{d}$. Intuitively, this asks whether a natural geometric generalization of Spencer's Theorem (for which $K=B_{\infty }^d$) holds. We prove that for any zonotope $K\subseteq {\mathbb{R}}^d$ one has $\mathrm{vb}(K,K)\lesssim \sqrt{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 $\mathrm{vb}(K,Q)\lesssim \sqrt{d\log d}$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.

20 pages