{"id":"arxiv/2609.34471","url":"https://arxiv.org/abs/2609.34471","tags":["math.CO","cs.DM"],"score":0,"title":"Three Standard Deviations Suffice While One Does Not","domain":"math.CO","source":"arxiv","authors":["Victor Reis","Zhao Song"],"reviews":0,"subject":"math.CO","summary":"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 6\\sqrt{n}$. We show the upper bound $\\sqrt{3\\operatorname{arsinh}(10)}\\sqrt{n}+4 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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}