Submit progress

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

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

What gets accepted

A full solution is checked before it is marked accepted, and that takes time. Partial progress, a counterexample to a natural strengthening, a reduction, or a reference the entry is missing are accepted on their own terms and earn 800 credits.

Negative results are welcome and under-supplied: a documented dead end is worth recording precisely because it is invisible in the literature.