Komlós discrepancy constant

Description of constant

$C_{24}$ is the Komlós discrepancy constant (often denoted $K$).

For a real matrix $A\in\mathbb{R}^{m\times n}$, define its (sign) discrepancy by

\[\mathrm{disc}(A)\ :=\ \min_{x\in\{-1,1\}^{n}}\ \|Ax\|_{\infty}.\]

For each $n\ge 1$, define the dimension-$n$ Komlós discrepancy

\[K_{n}\ :=\ \sup\left\{\mathrm{disc}(A):\ A\in\mathbb{R}^{n\times n}\ \text{and}\ \|A_{\ast j}\|_{2}\le 1\ \text{for all columns }j\right\}.\]

Finally, define

\[C_{24}\ :=\ \sup_{n\ge 1} K_{n}\ \in [0,\infty].\]

The Komlós conjecture asserts that $C_{24}<\infty$ (i.e. $K_{n}=O(1)$ as $n\to\infty$).

Since it is not known whether $C_{24}$ is finite, results are typically stated as bounds on $K_{n}$.

Bound	Reference	Comments
$n$	Trivial	Since $\|\|A_{\ast j}\|\|{2}\le 1$ implies $\lvert a{ij}\rvert\le 1$, we have $\|\|Ax\|\|_{\infty}\le n$ for every $x\in{-1,1}^{n}$.
$O(\log n)$	[Bec1981], [Spe1985], [Glu1989]	Partial-coloring/entropy-method bounds yield $O(\log n)$ discrepancy for Komlós-type instances.
$O(\sqrt{\log n})$	[Ban1998]	Banaszczyk’s vector-balancing theorem (via Gaussian measure) gives the first $o(\log n)$ bound.
$O(\sqrt{\log n})$ (poly-time)	[BDG2019]	Polynomial-time algorithm matching Banaszczyk’s existential bound up to constants.
$\widetilde{O}(\log^{1/4} n)$	[BJ2025]	Current best published asymptotic bound (hides polylog factors, e.g. in $\log\log n$). First improvement over $O(\sqrt{\log n})$.

Bound	Reference	Comments
$1$	Trivial	Take $n=1$ and $A=[1]$, for which $\mathrm{disc}(A)=1$.
$1+\sqrt{2}$	[Kun2023]	Best known lower bound on $C_{24}$.

Status. The main open problem is whether $C_{24}$ is finite (Komlós conjecture). The best known bounds currently satisfy $1+\sqrt{2}\ \le\ C_{24}\ \le\ \infty,$ and, more quantitatively, $K_{n}\le \widetilde{O}(\log^{1/4} n)$ while $K_{n}\ge 1+\sqrt{2}$ for infinitely many $n$.
Vector discrepancy relaxation. Replacing signs $\varepsilon_{j}\in{-1,1}$ by unit vectors (an SDP relaxation) yields vector discrepancy. For Komlós instances, Nikolov proved this relaxation has optimum at most $1$, so any obstruction must be genuinely “integral.”
[Speculation] Sharp value. Given the lower bound $C_{24}\ge 1+\sqrt{2}$, it is natural to ask whether $C_{24}=1+\sqrt{2}$. No matching upper bound is known, and even finiteness remains open.
General background: Wikipedia page on geometric discrepancy theory.

[Ban1998] Banaszczyk, W. Balancing vectors and Gaussian measures of $n$-dimensional convex bodies. Random Structures & Algorithms 12(4) (1998), 351–360.
[Bec1981] Beck, J. Roth’s estimate of the discrepancy of integer sequences is nearly sharp. Combinatorica 1(4) (1981), 319–325.
[BF1981] Beck, J.; Fiala, T. Integer-making theorems. Discrete Appl. Math. 3(1) (1981), 1–8.
[BDG2019] Bansal, N.; Dadush, D.; Garg, S. An algorithm for Komlós conjecture matching Banaszczyk’s bound. SIAM J. Comput. 48(2) (2019), 534–553. arXiv:1605.02882.
[BJ2025] Bansal, N.; Jiang, S. Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk. arXiv:2508.03961 (2025).
[Glu1989] Gluskin, E. D. Extremal properties of orthogonal parallelepipeds and their applications to the theory of Banach spaces. Mat. Sb. (N.S.) 136(178)(1) (1988), 85–96; English transl.: Math. USSR-Sb. 64(1) (1989), 85–96.
[Kun2023] Kunisky, D. The discrepancy of unsatisfiable matrices and a lower bound for the Komlós conjecture constant. SIAM J. Discrete Math. 37(2) (2023), 586–603.
[Nik2013] Nikolov, A. The Komlós conjecture holds for vector colorings. arXiv:1301.4039 (2013).
[Spe1985] Spencer, J. Six standard deviations suffice. Trans. Amer. Math. Soc. 289(2) (1985), 679–706.

Prepared with assistance from ChatGPT 5.2 Pro.