Randomstrasse101 Open Problems (2024) — Conjecture 11

Definitions and mathematical statement

The supplied excerpt refers to preceding definitions that are not included, so its meaning of $\mathrm{disc}(A)$ cannot be confirmed. The following is a conditional reconstruction using the usual matrix discrepancy convention.

For a positive integer $n$, let $\{\pm1\}^{n\times n}$ denote the set of real $n\times n$ matrices whose entries are $-1$ or $1$. For $A=(a_{ij})$ in this set, define \[ \mathrm{disc}(A):=\min_{x\in\{\pm1\}^{n}}\|Ax\|_{\infty} =\min_{x\in\{\pm1\}^{n}}\max_{1\le i\le n}\left|\sum_{j=1}^{n}a_{ij}x_j\right|. \] Under this convention, the supplied Conjecture 11 asserts \[ \limsup_{n\to\infty}\ \sup_{A\in\{\pm1\}^{n\times n}}\frac{\mathrm{disc}(A)}{\sqrt n}>1. \] Equivalently, there exist a real number $\delta>0$, a strictly increasing sequence of positive integers $(n_k)_{k\ge1}$, and matrices $A_k\in\{\pm1\}^{n_k\times n_k}$ such that \[ \mathrm{disc}(A_k)\ge(1+\delta)\sqrt{n_k}\qquad\text{for every }k\ge1. \] The identification of the displayed definition with the source's omitted definition remains unresolved. The excerpt's author additionally states, with the qualification "to the best of my knowledge," that no construction or existence proof of such an infinite family with normalized lower bound strictly greater than one was known. This is a supplied source assessment, not an independently verified literature conclusion.

Short English statement

Under the usual matrix discrepancy convention, the conjecture asks whether some fixed constant greater than $1$ is a lower bound for the normalized discrepancy of suitable square sign matrices in infinitely many dimensions. The source's preceding definitions are missing, so this interpretation requires confirmation. The registry labels the problem open; that label has not been independently verified.

Sources

• Local supplied UnsolvedMath registry record: permanent ID $800845$, exact source problem code catalogue entry, titled Randomstrasse101 Open Problems (2024) --- Conjecture 11. The record attributes the problem to Bandeira et al., gives proposed year 2025, and labels it open.
• Supplied source reference: Bandeira et al., Randomstrasse101: Open Problems of 2024 (2025), Conjecture 11, https://arxiv.org/abs/2504.20539. The record reports access on 2026-10-16 and extraction by arxiv_latex. These are supplied provenance details; the source was not independently accessed or verified for this draft.