Infinitely many square ±1 matrices with discrepancy a constant factor above √n
For an $n \times n$ matrix $A$ let $\operatorname{disc}(A) = \min_{x \in \{\pm1\}^n} \|Ax\|_\infty$. By Spencer's theorem $\operatorname{disc}(A) \le 6\sqrt n$ for every $A \in \{\pm1\}^{n \times n}$. Bandeira knew of no infinite family of $\pm1$ matrices, constructed or shown to exist, whose discrepancy is at least $c\sqrt n$ for some $c > 1$.
Problem. Prove or disprove that $$\limsup_{n \to \infty}\ \sup_{A \in \{\pm1\}^{n \times n}} \frac{\operatorname{disc}(A)}{\sqrt n} > 1.$$
Source: Bandeira, Conjecture 12 of Randomstrasse101, in “Did just a couple of deviations suffice all along?” (2024); Entry 6 of arXiv:2504.20539.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- CO — Combinatorics
- Secondary
- PR
- Keywords
- discrepancy theory, Randomstrasse101, sign matrices, Spencer's theorem
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2024,
author = {Bandeira, Afonso S. and Kireeva, Anastasia and Maillard, Antoine and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2024},
year = {2025},
eprint = {2504.20539},
archivePrefix = {arXiv}
}
@article{spencer1985,
author = {Spencer, Joel},
title = {Six standard deviations suffice},
journal = {Transactions of the American Mathematical Society},
volume = {289},
number = {2},
pages = {679--706},
year = {1985}
}
Resolution claims
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 < 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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-02 | Open → Solution claimed | The registry's curators | Three Standard Deviations Suffice While One Does Not v1 recorded from arXiv:2609.34471v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00055, "Infinitely many square ±1 matrices with discrepancy a constant factor above √n", clopen.solutions.