OP-12032OpenCombinatorics

Komlós discrepancy constant ( $C_{24}$ )

Komlós discrepancy constant: determine $C_{24}$ or improve its bounds; the repository records $1+\sqrt{2}$ (lower) and $\infty$ (upper).

MSC 11K38 · Irregularities of distribution, discrepancy

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

$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$ ).

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

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.

References (from the repository page)

[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.

Acknowledgements

Prepared with assistance from ChatGPT 5.2 Pro.

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound $1+\sqrt{2}$ ; best known upper bound $\infty$ . Values marked with an asterisk have minimal verification.

Known upper bounds

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})$ .

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}$ .

References

[1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Komlós discrepancy constant ($C_{24}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Source & evidence

https://teorth.github.io/optimizationproblems/constants/24a.html

Constant page from github.com/teorth/optimizationproblems at commit 2c1968c, Apache-2.0. The maintainers review submissions for plausibility and replicability but do not certify correctness; asterisked bounds have minimal verification.

Source date: Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differ
Imported: 2026-10-10

How we use sources ↗

Record

Difficulty: HardResisted sustained effort by specialists.
Posed by: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers) and contributors
Posed: 2026
Source: Curated problem listOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOriginal statement ↗
Citation: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — Komlós discrepancy constant ($C_{24}$)
Added: 5 Nov 2026
Views: 0

Fields

Combinatorics