Randomstrasse101 Open Problems (2024) — Conjecture 12

Definitions and mathematical statement

For each integer $k\geq 0$, define the Sylvester Hadamard matrix recursively by \[ H_0=(1),\qquad H_{k+1}=\begin{pmatrix}H_k&H_k\\H_k&-H_k\end{pmatrix}. \] Thus $H_k\in\{-1,1\}^{2^k\times 2^k}$. For a real $m\times n$ matrix $A=(a_{ij})$, interpret its discrepancy as the unnormalized sign discrepancy \[ \operatorname{disc}(A):=\min_{x\in\{-1,1\}^n}\|Ax\|_\infty =\min_{x\in\{-1,1\}^n}\max_{1\leq i\leq m}\left|\sum_{j=1}^n a_{ij}x_j\right|. \] The supplied excerpt does not define $\operatorname{disc}$ and refers to preceding material for the Sylvester construction. Consequently, the following is a conditional formalization using the explicitly stated conventions; their agreement with the full source requires review.

The supplied Conjecture 12 asserts that, for every odd integer $k\geq 1$, \[ \operatorname{disc}(H_k)=\sqrt{2}\sqrt{2^k}. \] Equivalently, for each such $k$, there exists $x\in\{-1,1\}^{2^k}$ such that every coordinate of $H_kx$ has absolute value at most $\sqrt{2}\sqrt{2^k}$, and every $x\in\{-1,1\}^{2^k}$ has at least one coordinate of $H_kx$ with absolute value at least $\sqrt{2}\sqrt{2^k}$.

Short English statement

Under the stated discrepancy convention, the conjecture says that for every positive odd $k$, the smallest possible largest absolute row sum of the Sylvester matrix after assigning signs to its columns is exactly $\sqrt{2}\sqrt{2^k}$. The supplied registry labels the problem open; that status and the discrepancy convention have not been independently verified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $800846$, source problem code catalogue entry, titled "Randomstrasse101 Open Problems (2024) --- Conjecture 12." The record attributes the problem to Bandeira et al., gives proposed year 2025, and labels its status as open.
• Bandeira et al., Randomstrasse101: Open Problems of 2024 (2025), Conjecture 12. Supplied source URL: https://arxiv.org/abs/2504.20539. The record reports access on 2026-10-16 and extraction by arxiv_latex; these are supplied provenance details, not an independent verification or a claim of access here.
• Supplied upstream revision: d371ee917ac9647fbb06cd6fc529deec6f3dda82.