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 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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.34471
curl -X POST /api/v1/records/arxiv/2609.34471/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.34471/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'