The discrepancy of the Sylvester–Hadamard matrices H_k for odd k
For an $n \times n$ matrix $A$ let $\operatorname{disc}(A) = \min_{x \in \{\pm1\}^n} \|Ax\|_\infty$. Let $H_k$ be the $2^k \times 2^k$ Sylvester–Hadamard matrix: $H_0 = 1$ and $H_k = \begin{bmatrix} H_{k-1} & H_{k-1} \\ H_{k-1} & -H_{k-1} \end{bmatrix}$. Orthogonality gives $\operatorname{disc}(H_k) \ge \sqrt{2^k}$, which is attained for even $k$, and an explicit signing gives $\operatorname{disc}(H_k) \le \sqrt2\,\sqrt{2^k}$ for odd $k$. Equality for odd $k$ would give infinitely many $\pm1$ matrices with $\operatorname{disc}(A) \ge \sqrt2\,\sqrt n$.
Problem. Prove or disprove that $\operatorname{disc}(H_k) = \sqrt2\,\sqrt{2^k}$ for every odd $k$.
Source: Bandeira, Conjecture 13 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
- Boolean functions, discrepancy theory, Hadamard matrices, Randomstrasse101
- 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}
}
@book{odonnell2014boolean,
author = {O'Donnell, Ryan},
title = {Analysis of Boolean Functions},
publisher = {Cambridge University Press},
year = {2014}
}
@article{patterson1983covering,
author = {Patterson, Nicholas J. and Wiedemann, Douglas H.},
title = {The covering radius of the $(2^{15}, 16)$ {R}eed--{M}uller code is at least 16276},
journal = {IEEE Transactions on Information Theory},
volume = {29},
number = {3},
pages = {354--356},
year = {1983},
doi = {10.1109/TIT.1983.1056679}
}
Resolution claims
The largest Hamming distance between a Boolean function in $n$ variables and the set of all affine Boolean functions in $n$ variables is known as the covering radius $ρ_n$ of the $[2^n,n+1]$ Reed-Muller code. This number determines how well Boolean functions can be approximated by linear Boolean functions. We prove that \[ \lim_{n\to\infty}2^{n/2}-ρ_n/2^{n/2-1}=1, \] which resolves a conjecture due to …
In 2006, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. To improve this nonlinearity result, we have firstly defined some subsets of the n-variable Boolean functions as the "generalized classes of k-RSBFs and k-DSBFs …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-03 | Solution claimed → Solved | clemens-admin | Independent audit of Randomstrasse101: Open Problems of 2024 v1 (The registry's curators, with AI assistance (Claude)) verified. |
| 2026-10-02 | Open → Solution claimed | The registry's curators | Randomstrasse101: Open Problems of 2024 v1 recorded from arXiv:2504.20539v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00056, "The discrepancy of the Sylvester–Hadamard matrices H_k for odd k", clopen.solutions.