Submit progress

on Spencer discrepancy constant (“six standard deviations suffice”) ($C_{10c}$)

The statement

$C_{10c}$ is the least constant $K$ for which one has

\mathrm{disc}(A) \le K\sqrt{n} \qquad\text{for all }n\text{ and all }A\in[-1,1]^{n\times n}.

Here the discrepancy $\mathrm{disc}(A)$ is defined as

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

Equivalently, if the linear forms are

L_i(x_1,\dots,x_n)=\sum_{j=1}^n a_{ij}x_j,

then

\mathrm{disc}((a_{ij})_{i,j=1}^n)= \min_{\varepsilon\in\{\pm 1\}^n} \max_{1\le i\le n}\lvert L_i(\varepsilon)\rvert.

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.