The Komlós conjecture for complex discrepancy
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 a1,…,an inside the m-dimensional Euclidean ball, regardless of how large m,n are, there is always a selection of signs ε1,…,εn guaranteeing |ε1a1+…+εnan|∞ ≤ K. We show that if the εi's are allowed to take not just the values of ± 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ℂ. Here, the ℓ∞ norm of the resulting vector in ℂm is the largest modulus of its entries, and thus the complex discrepancy of real vectors is equivalent to their rank-$2$ vector discrepancy. This quantity provides an upper bound (modulo uniform constant prefactor) on Gaussian discrepancy -- a discrepancy measure introduced by Chewi, Gerber, Rigollet and Turner. Thus, we also resolve the Komlós conjecture for Gaussian discrepancy. 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.
Related
- Tighter bounds on Komlós discrepancy: existence and algorithmic results
- An elementary proof of the Komlós conjecture
- Proving the Komlós conjecture slowly
- Proof of a conjecture of Johnston on binary matrices with low discrepancy
- A Walk From Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer Conjecture
BibTeX
@misc{guillen2026komlós,
title = {{The Komlós conjecture for complex discrepancy}},
author = {Nestor Guillen and Vladimir A. Kobzar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.15071},
eprint = {2609.15071},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.15071},
}
RIS
TY - UNPB
TI - The Komlós conjecture for complex discrepancy
AU - Nestor Guillen
AU - Vladimir A. Kobzar
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2609.15071
UR - https://arxiv.org/abs/2609.15071
AB - 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,…,a_n inside the m-dimensional Euclidean ball, regardless of how large m,n are, there is always a selection of signs ε_1,…,ε_n guaranteeing |ε_1a_1+…+ε_na_n|_∞ ≤ K. We show that if the ε_i's are allowed to take not just the values of ± 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_ℂ. Here, the ℓ^∞ norm of the resulting vector in ℂ^m is the largest modulus of its entries, and thus the complex discrepancy of real vectors is equivalent to their rank-$2$ vector discrepancy. This quantity provides an upper bound (modulo uniform constant prefactor) on Gaussian discrepancy -- a discrepancy measure introduced by Chewi, Gerber, Rigollet and Turner. Thus, we also resolve the Komlós conjecture for Gaussian discrepancy. 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.
ER -