The vector balancing constant $\mathrm{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 $\mathrm{vb}(K,K) \lesssim \sqrt{d}$. Intuitively, this asks whether a natural geometric generalization of Spencer's Theorem (for which $K = B^d_\infty$) 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.
翻译:向量平衡常值 $\ mathrm{ vb} (K, Q), 两个对称共方正方体 $K, Q$是最小值 $\ geq 0美元, 这样从 $K$ 中的任何矢量可以平衡成一个 $ 美元 的缩放。 Schechtman 提出的问题是, 对于任何 zonotope $ K\ substeq { mathb{ R\\ d$ 1 有 $ mathrm{vb} (K, K)\ smusm\ smissim\ slog\ sqrt{d} $。 直观而言, 询问斯潘塞理论的自然几何分化( $ = B= qd ⁇ infty $ ) 是否保持平衡。 我们证明, 对于任何 zonotope $ K\ subseqs {bbbbb} (K, liess\ sqrock lax a clas commax commaxal commax commotional commocal deal deal deal deal max a gres a gres a gres pal pral plals a mus mus mus