Optimal Vector Balancing for Zonotopes
This resolves an open problem in geometric discrepancy theory, providing a tight bound for vector balancing in zonotopes.
The authors prove that for any zonotope Z in R^d and any vectors inside it, there exists a signed sum of the vectors that lies in C√d Z, resolving a 2002 question by Schechtman and generalizing Spencer's six standard deviations theorem.
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. \] This resolves a 2002 question of Schechtman and generalizes Spencer's six standard deviations theorem, which corresponds to the case $Z=[-1,1]^d$.