Vector Balancing in Lebesgue Spaces

Abstract

A tantalizing conjecture in discrete mathematics is the one of Komlós, suggesting that for any vectors ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n\in B_2^m$ there exist signs $x_1,\dots ,x_n\in \{-1,1\}$ so that $\Vert {\sum }_{i=1}^n{x}_i{\mathbf{a}}_i{\Vert }_{\infty }\le O(1)$. It is a natural extension to ask what ${\ell }_q$-norm bound to expect for ${\mathbf{a}}_1,\dots ,{\mathbf{a}}_n\in B_p^m$. We prove that, for $2\le p\le q\le \infty$, such vectors admit fractional colorings $x_1,\dots ,x_n\in [-1,1]$ with a linear number of $\pm 1$ coordinates so that $\Vert {\sum }_{i=1}^n{x}_i{\mathbf{a}}_i{\Vert }_q\le O(\sqrt{\min (p,\log (2m/n))})\cdot n^{1/2-1/p+1/q}$, and that one can obtain a full coloring at the expense of another factor of $\frac{1}{1/2-1/p+1/q}$. In particular, for $p\in (2,3]$ we can indeed find signs $\mathbf{x}\in \{-1,1{\}}^n$ with $\Vert {\sum }_{i=1}^n{x}_i{\mathbf{a}}_i{\Vert }_{\infty }\le O(n^{1/2-1/p}\cdot \frac{1}{p-2})$. Our result generalizes Spencer's theorem, for which $p=q=\infty$, and is tight for $m=n$. Additionally, we prove that for any fixed constant $\delta >0$, in a centrally symmetric body $K\subseteq {\mathbb{R}}^n$ with measure at least $e^{-\delta n}$ one can find such a fractional coloring in polynomial time. Previously this was known only for a small enough constant -- indeed in this regime classical nonconstructive arguments do not apply and partial colorings of the form $\mathbf{x}\in \{-1,0,1{\}}^n$ do not necessarily exist.

arXiv comment24 pages. Accepted to Random Structures and Algorithms