Vector Balancing via Directional Total Variation

Abstract

Our main result is a $3\sqrt{2\pi}$ bound for the Koml\'os signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size. For any $\kappa\ge0$, if a bounded open convex set supports a probability density with directional total variation at most $\kappa$ in every unit direction, then its open-set Banaszczyk transform supports another such density with the same $\kappa$, provided the translation vector $v$ satisfies $\kappa\|v\|_2\le1/3$. As a consequence, every finite set system in which each element belongs to at most $t$ sets, where $t\ge1$ is an integer, admits a two-coloring whose imbalance in each set is less than $3\sqrt{2\pi t}$. This gives the square-root dependence predicted by the Beck-Fiala conjecture. The proof was discovered by the Odin Automatic AI Research Agent.