Optimal Vector Balancing for Zonotopes

Abstract

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$.

24 pages