The infinite-family lower-bound conjecture for Spencer discrepancy

About 1 year old · traced to

For a square ±1\pm1 matrix AA, let

disc⁡(A)=inf⁡x∈±1n∣Ax∣∞.\operatorname{disc}(A)=\inf_{x\in\\{\pm1\\}^n}\\|Ax\\|_\infty.

Spencer discrepancy lower-bound conjecture. The infinite-family normalized discrepancy satisfies

lim sup⁡n→∞sup⁡A∈±1n×ndisc⁡(A)n>1.\limsup_{n\to\infty}\sup_{A\in\\{\pm1\\}^{n\times n}}\frac{\operatorname{disc}(A)}{\sqrt n}>1.

No infinite family proving a bound strictly larger than 11 was known in the source, so the question remains open.

References

Primary source

Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard and Almut Rödder, “Randomstrasse101: Open Problems of 2024”, arXiv:2504.20539 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.