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. \] This resolves a 2002 question of Schechtman and generalizes Spencer's six standard deviations theorem, which corresponds to the case $Z=[-1,1]^d$.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.23866
curl -X POST /api/v1/records/arxiv/2605.23866/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.23866/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'