Math Conjectures

Komlos Discrepancy Conjecture

OPENLandmarkConjectureProposed c. 1970 · Full conjecture

Canonical statement

There is a universal constant CC such that, for every finite sequence v1,…,vn∈Rmv_1,\ldots,v_n\in\mathbb R^m with ∥vj∥2≤1\lVert v_j\rVert_2\le1, there are signs εj∈{−1,+1}\varepsilon_j\in\{-1,+1\} for which ∥∑jεjvj∥∞≤C\left\lVert\sum_j\varepsilon_jv_j\right\rVert_\infty\le C.
View source LaTeX
There is a universal constant \(C\) such that, for every finite sequence \(v_1,\ldots,v_n\in\mathbb R^m\) with \(\lVert v_j\rVert_2\le1\), there are signs \(\varepsilon_j\in\{-1,+1\}\) for which \(\left\lVert\sum_j\varepsilon_jv_j\right\rVert_\infty\le C\).
COMB-DISC-016:[Spencer1994TenLectures][Banaszczyk1998Balancing][BansalDadushGarg2016Komlos][BansalJiang2025Decoupling]
CombinatoricsTheoretical computer science

Notes

The Komlós conjecture asks for a universal constant CC such that vectors v1,…,vn∈Rmv_1,\ldots,v_n\in\mathbb R^m with ∥vj∥2≤1\|v_j\|_2\le1 can always be signed so that ∥∑jεjvj∥∞≤C\|\sum_j\varepsilon_jv_j\|_\infty\le C. Spencer's discrepancy lectures give an early standard formulation [Spencer1994TenLectures], while Banaszczyk proved the benchmark O(log⁡n)O(\sqrt{\log n}) bound [Banaszczyk1998Balancing].

Bansal, Dadush, and Garg made this vector-discrepancy method algorithmic [BansalDadushGarg2016Komlos], and Bansal and Jiang later improved the general dependence to roughly a fourth root of a logarithm [BansalJiang2025Decoupling]. A bound independent of both mm and nn is still missing; special sparsity assumptions, random inputs, or dimension-dependent bounds do not settle the conjecture.

References (4)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.