The Vector Balancing Constant for Zonotopes

The vector balancing constant $\operatorname{vb}(K, Q)$ of two symmetric convex bodies $K, Q$ is the minimum $r \geq 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 $\operatorname{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 $\operatorname{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 $\operatorname{vb}(K, Q) \lesssim \sqrt{d \log d}$. All the bounds are constructive and the corresponding colorings can be computed in polynomial time.

Authors

• Rainie Bozzai
• Victor Reis
• Thomas Rothvoss

Keywords

• Computer science
• Gaussian Measurement
• Conjecture
• Universal Constant
• discrepancy
• sparsification
• geometry