Three Standard Deviations Suffice While One Does Not

Abstract

Spencer's 1985 ``six standard deviations suffice'' theorem shows that every A ∈ [−1,1]^{n × n} has a sign vector x ∈ {−1,1}ⁿ with |Ax|_∞ ≤ 6√n. We show the upper bound √(3arsinh(10))√n+4 < 2.9992 √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 ≥ 2⁵⁰, there exists a matrix A ∈ {−1,1}^{n × n} such that |Ax|_∞ >1.0000002√n for every choice of signs x ∈ {−1,1}ⁿ. The construction simply replaces a 2⁻²² fraction of the columns of a Hadamard matrix with independent random sign vectors. This is the first improvement over the √n lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.

Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense Input
Zhao Song, Lichen Zhang
arXiv21 Sep 2026PreprintCC BY-NC-ND 4.0Full textAnalysis & PDEs Optimisation & controlarXiv
Cost-Aware Stopping for Freeze-Thaw Bayesian Optimization: When Does One-Step Lookahead Suffice?
Long Vu, Jongseong Brad Choi, Binoy Ravindran +1
arXiv30 Oct 2026PreprintarXiv licenceFull textOptimisation & control StatisticsarXiv
Three Machines Suffice for Local Hardening of Electromechanical Oscillations
Kai Sun
arXiv17 Oct 2026PreprintarXiv licenceFull textDynamical systemsarXiv
When Weak Submodularity Meets Matroids: How Does Standard Greedy Behave?
Qixin Zhang, Shi Fu, Shengminjie Chen +2
arXiv21 Oct 2026PreprintCC BY 4.0Full textOptimisation & controlarXiv
What Does a Discrete Diffusion Model Learn? One Reverse Process in Three Coordinates
Rodrigo Casado Noguerales, Bernhard Schölkopf, Thomas Hofmann +1
arXiv14 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{reis2026three,
  title = {{Three Standard Deviations Suffice While One Does Not}},
  author = {Victor Reis and Zhao Song},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.34471},
  eprint = {2609.34471},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.34471},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Three Standard Deviations Suffice While One Does Not
AU  - Victor Reis
AU  - Zhao Song
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2609.34471
UR  - https://arxiv.org/abs/2609.34471
AB  - Spencer's 1985 ``six standard deviations suffice'' theorem shows that every A ∈ [−1,1]^n × n has a sign vector x ∈ {−1,1}^n with |Ax|_∞ ≤ 6√n. We show the upper bound √(3arsinh(10))√n+4 < 2.9992 √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 ≥ 2^50, there exists a matrix A ∈ {−1,1}^n × n such that |Ax|_∞ >1.0000002√n for every choice of signs x ∈ {−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 √n lower bound of Olson and Spencer (1978), which uses a Hadamard matrix.
ER  -

Abstract

Related

Cite