Three Standard Deviations Suffice While One Does Not

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 $|Ax|_infty le 6sqrt{n}$. We show the upper bound $\sqrt{3\text{arsinh}(10)}\sqrt{n}+41.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.