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$). This was proved in [GFL2026a].
Known upper bounds
Before [GFL2026a], results were 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] | Best asymptotic bound prior to [GFL2026a] (hides polylog factors, e.g. in $\log\log n$). First improvement over $O(\sqrt{\log n})$. |
| $3\sqrt{2\pi} \approx 7.5199$* | [GFL2026a] | Proof of the conjecture. An algorithmic version is given in [GFL2026b]. |
| $36$ | [KL2026] | Elementary proof based on [GFL2026a], with a Lean4 check [Dah2026]. |
| $6.9013$* | [AS2026] | Refines [GFL2026a]. The constant is the root $C \approx 6.9012574$ of $\frac{3\sqrt{2\pi}}{C}\int_0^3 (1-r/3)^2 \exp(-\pi^2 r^2/(2C^2)) dr = 1$ (Theorem 2.4 of v2). |
Known lower bounds
| 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}$. |
Additional comments and links
-
Status. The Komlós conjecture is now a theorem, and the verified bounds are \(1+\sqrt{2}\ \le\ C_{24}\ \le\ 36.\)
-
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}$.
-
General background: Wikipedia page on geometric discrepancy theory.
References
- [AS2026] Akbas, E.; Sra, S. Tighter bounds on Komlós discrepancy: existence and algorithmic results. arXiv:2609.27172v2 (29 Sep 2026). Version 1 (23 Sep 2026) was titled An exposition of the proof of the Komlós conjecture. Certificates: suvrit/komlos.
- [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).
- [Dah2026] Dahia, G. Komlós conjecture. Lean 4 formalization of [KL2026], gdahia/Komlos at commit
d802857. Palomar entry PALOMAR-2026-09-18-000003, version 1, registered 18 Sep 2026. Written with AI coding agents; see the repository’sformalization.yaml. - [GFL2026a] Guo, S.; Fang, E. X.; Lu, J. Vector balancing via directional total variation. arXiv:2609.11189 (10 Sep 2026).
- [GFL2026b] Guo, S.; Fang, E. X.; Lu, J. Vector balancing in polynomial time. arXiv:2609.23540 (20 Sep 2026).
- [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.
- [KL2026] Karingula, S. R.; Lovett, S. An elementary proof of the Komlós conjecture. arXiv:2609.20979 (v1 17 Sep 2026, v2 22 Sep 2026); also ECCC TR26-188 (17 Sep 2026).
- [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.
Contribution notes
Prepared with assistance from ChatGPT 5.2 Pro.
The 2026 update on the resolution of the Komlós conjecture was drafted with Claude Code (Claude Opus 5.5) and reviewed by a human contributor.