Vector balancing in Lebesgue spaces. Issue 3 (26th August 2022) - Reis, Victor; Rothvoss, Thomas
Abstract: The Komlós conjecture suggests that for any vectors a 1, …, a n ∈ B 2 m a_1, …, a_nB_2^m there exist x 1, …, x n ∈ − 1, 1 x_1, …, x_n{-1, 1} so that ‖ ∑ i = 1 n x i a i ‖ ∞ ≤ O ( 1 ) _i=1^nx_ia_i_∞O(1) . It is a natural extension to ask what ℓ q _q ‐norm bound to expect for a 1, …, a n ∈ B p m a_1, …, a_nB_p^m . We prove a tight partial coloring result for such vectors, implying a nearly tight full coloring bound. As a corollary, this implies a special case of Beck–Fiala's conjecture. We achieve this by showing that, for any δ > 0 δ >0 , a symmetric convex body K ⊆ ℝ n KR^n with Gaussian measure at least e − δ n e^-δ n admits a partial coloring. Previously this was known only for a small enough δ δ . Additionally, we show that a hereditary volume bound suffices to provide such Gaussian measure lower bounds.