Optimal Vector Balancing for Zonotopes
2026-05-22 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors studied a shape called a zonotope, which you can think of as a stretched and squished version of a cube in multiple dimensions. They proved that for any points inside this shape, you can assign positive or negative signs to each point so that when you add them up, the result stays inside a scaled-up version of the original shape, with the scaling depending on the dimension. This answers a question from 2002 by Schechtman and extends an earlier result known as Spencer's six standard deviations theorem, which handled the special case of normal cubes.
ZonotopeLinear imageCube [-1,1]^mSign assignmentVector sumScaling factorDimensionSpencer's six standard deviations theoremGeomtric functional analysisSchechtman's question
Authors
Victor Reis
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$.