Optimal Vector Balancing for Zonotopes

A zonotope is a linear image of the cube $[-1,1{]}^m$ for some $m\in \mathbb{N}$. We show that there is a universal constant $C$ such that, for every zonotope $Z\subset {\mathbb{R}}^d$ and vectors $v_1,\dots ,v_n\in Z$, there are signs $x_1,\dots ,x_n\in \{-1,1\}$ with $$\sum _{i=1}^n{x}_i{v}_i\in C\sqrt{d}Z\mathrm{.}$$ This resolves a 2002 question of Schechtman and generalizes Spencer’s six standard deviations theorem, which corresponds to the case $Z=[-1,1{]}^d$.