OP-00064 Solution claimed

The Komlós conjecture

For an $n \times n$ matrix $A$ let $\operatorname{disc}(A) = \min_{x \in \{\pm1\}^n} \|Ax\|_\infty$. The conjecture would give $\operatorname{disc}(A) = O(\sqrt n)$ for every $A \in \{\pm1\}^{n \times n}$, Spencer's theorem up to the constant, since the columns of such a matrix have $\ell_2$ norm $\sqrt n$. Kunisky showed that $K$ must be at least $1 + \sqrt2$.

Problem. Prove or disprove that there is a universal constant $K$ such that, for all square matrices $A$ whose columns have unit $\ell_2$ norm, $\operatorname{disc}(A) \le K$.

Source: Komlós; see Spencer, Six standard deviations suffice (1985). Conjecture 10 of Randomstrasse101, in Bandeira's “Did just a couple of deviations suffice all along?” (2024); Entry 6 of arXiv:2504.20539. Also Open Problem 0.1 of his Forty-Two Open Problems.

The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.

Classification

Primary: CO — Combinatorics
Secondary: PR
Keywords: discrepancy theory, Komlós conjecture, Randomstrasse101, vector balancing
Literature checked: Oct. 2, 2026 by clemens-admin

References

@misc{randomstrasse2024,
  author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
  title = {{Randomstrasse101}: Open Problems of 2024},
  year = {2025},
  eprint = {2504.20539},
  archivePrefix = {arXiv}
}

@article{spencer1985,
  author = {Spencer, Joel},
  title = {Six standard deviations suffice},
  journal = {Transactions of the American Mathematical Society},
  volume = {289},
  number = {2},
  pages = {679--706},
  year = {1985}
}

@article{kunisky2023komlos,
  author = {Kunisky, Dmitriy},
  title = {The discrepancy of unsatisfiable matrices and a lower bound for the {K}oml{\'o}s conjecture constant},
  journal = {SIAM Journal on Discrete Mathematics},
  volume = {37},
  number = {2},
  year = {2023}
}

@misc{bandeira2016fortytwo,
  author = {Bandeira, Afonso S.},
  title = {Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science},
  year = {2016},
  url = {https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf}
}

Resolution claims

Vector Balancing via Directional Total Variation v1 arXiv ↗ AI-Verified

Shengtao Guo; Ethan X. Fang; Junwei Lu

Our main result is a $3\sqrt{2π}$ bound for the Komlós signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size. For any $κ\ge0$, if a bounded open convex set supports a probability density with directional total variation at …

Full resolution · not verified · fidelity not established · posted on arXiv 10 Sep 2026

Status history

When	Change	By	Reason
2026-10-04	Open → Solution claimed	The registry's curators	Vector Balancing via Directional Total Variation v1 recorded from arXiv:2609.11189v1.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00064, "The Komlós conjecture", clopen.solutions.