Three Standard Deviations Suffice While One Does Not

Abstract

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every $A\in [-1,1{]}^{n\times n}$ has a sign vector $x\in \{-1,1{\}}^n$ with $\Vert Ax{\Vert }_{\infty }\le 6\sqrt{n}$. We show the upper bound $\sqrt{3\mathrm{arsinh}(10)}\sqrt{n}+4<2.9992\sqrt{n}+4$ by directly rounding the minimizer of a potential function to a vertex of the cube. We also show that, for every power of two $n\ge 2^{50}$, there exists a matrix $A\in \{-1,1{\}}^{n\times n}$ such that $\Vert Ax{\Vert }_{\infty }>1.0000002\sqrt{n}$ for every choice of signs $x\in \{-1,1{\}}^n$. The construction simply replaces a $2^{-22}$ fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the $\sqrt{n}$ lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

arXiv comment15 pages