Vector Balancing in Lebesgue Spaces
A tantalizing conjecture in discrete mathematics is the one of Komlós, suggesting that for any vectors a1,…,an∈B2m there exist signs x1,…,xn∈{−1,1} so that ∥∑i=1nxiai∥∞≤O(1). It is a natural extension to ask what ℓq-norm bound to expect for a1,…,an∈Bpm. We prove that, for 2≤p≤q≤∞, such vectors admit fractional colorings x1,…,xn∈[−1,1] with a linear number of ±1 coordinates so that ∥∑i=1nxiai∥q≤O(min(p,log(2m/n)))⋅n1/2−1/p+1/q, and that one can obtain a full coloring at the expense of another factor of 1/2−1/p+1/q1. In particular, for p∈(2,3] we can indeed find signs x∈{−1,1}n with ∥∑i=1nxiai∥∞≤O(n1/2−1/p⋅p−21). Our result generalizes Spencer's theorem, for which p=q=∞, and is tight for m=n. Additionally, we prove that for any fixed constant δ>0, in a centrally symmetric body K⊆Rn with measure at least e−δ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 x∈{−1,0,1}n do not necessarily exist.
