Complex sign selection bounds sums of vectors in any dimension
The Komlós conjecture for complex discrepancy
Discrete Mathematics
Summary
The Komlós conjecture asks if you can always pick plus or minus signs for a set of vectors so their sum never gets too large in any coordinate. The authors show that if instead of just ±1, you can choose any complex number with absolute value 1 as your sign, then you can guarantee the sum stays bounded by some fixed constant. This complex sign choice expands the possibilities and solves a version of the conjecture related to more flexible 'Gaussian discrepancy.' The work builds on recent advances using probability and harmonic analysis techniques.
What this means in practice
- •For signal processing engineers: Guarantee bounded component-wise sums when combining signals with complex weighting, improving stability in high-dimensional signal representations.
- •For quantum computing developers: Optimize phase selections in unitary transformations by applying complex sign bounds to maintain controlled system norms.
A theory result. No direct application yet.
Authors
Nestor Guillen, Vladimir A. Kobzar
Abstract
The Komlós conjecture is a classic problem in discrepancy theory; it asks whether an absolute constant $K$ exists such that given any $n$ vectors $a_1,\ldots,a_n$ inside the $m$-dimensional Euclidean ball, regardless of how large $m,n$ are, there is always a selection of signs $\varepsilon_1,\ldots,\varepsilon_n$ guaranteeing $$\|\varepsilon_1a_1+\ldots+\varepsilon_na_n\|_\infty \leq K.$$ We show that if the $\varepsilon_i$'s are allowed to take not just the values of $\pm 1$ but any unit modulus complex number, which we refer to as complex discrepancy, then the above inequality holds for a finite, explicit constant $K_{\mathbb{C}}$. Here, the $\ell^\infty$ norm of the resulting vector in $\mathbb{C}^m$ is the largest modulus of its entries, and thus the complex discrepancy of real vectors is equivalent to their rank-$2$ vector discrepancy. Therefore, our result resolves the Komlós problem for Gaussian discrepancy -- a discrepancy measure introduced by Chewi, Gerber, Rigollet and Turner. Our paper builds upon the recent work of Bansal and Jiang on the Beck-Fiala and Komlós conjectures, which we approach from the formalism of Burkholder and the Bellman function method from probability and harmonic analysis. Our work was in part motivated by the realization that the complex discrepancy of the columns of any unitary matrix is equal to 1, a fact that follows from a straightforward calculation based on Idel and Wolf's generalization of the Sinkhorn normal form for unitary matrices.