The largest discrepancy of square ±1 matrices relative to √n
For an $n \times n$ matrix $A$ let $\operatorname{disc}(A) = \min_{x \in \{\pm1\}^n} \|Ax\|_\infty$. Spencer's "six standard deviations suffice" theorem gives $\operatorname{disc}(A) \le 6\sqrt n$ for every $A \in \{\pm1\}^{n \times n}$, and the constant has since been improved. The matrix $\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix}$ has discrepancy $2 = \sqrt2 \cdot \sqrt2$, so the quantity below is at least $\sqrt2$; Spielman mentioned a numerical construction, of one specific size, that achieves a slightly larger value. Bandeira knew of no lower bound above $2$.
Problem. What is the value of $$\sup_{n \in \mathbb{N}}\ \sup_{A \in \{\pm1\}^{n \times n}} \frac{1}{\sqrt n}\operatorname{disc}(A)?$$
Source: Bandeira, Open Problem 11 of Randomstrasse101, in “Did just a couple of deviations suffice all along?” (2024), from a discussion with Spielman, Schramm, Yehudayoff, Nizić-Nikolac and Kireeva; 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}
}
@article{kunisky2023komlos,
author = {Kunisky, Dmitriy},
title = {The discrepancy of unsatisfiable matrices and a lower bound for the {K}oml{\'o}s conjecture constant},
journal = {SIAM Journal on Discrete Mathematics},
volume = {37},
number = {2},
year = {2023}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00031, "The largest discrepancy of square ±1 matrices relative to √n", clopen.solutions.