OP-00051 Solution claimed

The Group Spencer conjecture

The Matrix Spencer conjecture states that there is a positive universal constant $C$ such that, for all positive integers $n$ and all self-adjoint $A_1, \dots, A_n \in \mathbb{R}^{n \times n}$ with $\|A_i\| \le 1$ in the spectral norm, $\min_{\varepsilon \in \{\pm1\}^n} \|\sum_{i=1}^n \varepsilon_i A_i\| \le C\sqrt n$. Bandeira, Kunisky, Mixon and Zeng, who state the Matrix Spencer conjecture for arbitrary real square matrices, not only self-adjoint ones, proposed the special case below and proved it for simple groups; for commutative groups it follows from Spencer's theorem.

Problem. Let $G$ be a finite group of size $n$. Prove or disprove that the Matrix Spencer conjecture holds in the particular case in which $A_1, \dots, A_n$ are the $n \times n$ matrices of the regular representation of $G$.

Source: Bandeira, Kunisky, Mixon and Zeng (2022). Conjecture 2 of Randomstrasse101, in Bandeira's “Welcome, and Matrix Discrepancy” (2024); Entry 1 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: GR, PR
Keywords: discrepancy theory, Matrix Spencer, Randomstrasse101, regular representation
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{bandeira2024cayley,
  author = {Bandeira, Afonso S. and Kunisky, Dmitriy and Mixon, Dustin G. and Zeng, Xinmeng},
  title = {On the concentration of {G}aussian {C}ayley matrices},
  journal = {Applied and Computational Harmonic Analysis},
  volume = {73},
  pages = {101694},
  year = {2024},
  doi = {10.1016/j.acha.2024.101694},
  eprint = {2212.00066},
  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}
}

Resolution claims

Matrix Discrepancy for Representations of Finite Groups v1 arXiv ↗ AI-Verified

Afonso S. Bandeira; Helmut Bölcskei

We prove the group version of the Matrix Spencer conjecture. For every finite group $G$, there exist signs $\varepsilon\in\{\pm1\}^G$ such that $$\left\| \sum_{g\in G} \varepsilon_gρ(g) \right\|\leq C\, \sqrt{|G|},$$ where $ρ$ is the left regular representation of $G$ and $C$ is a universal constant. This conjecture was posed in [BKMZ24], which settled it for simple groups; we establish it for all …

Full resolution · not verified · fidelity not established · posted on arXiv 27 Jun 2026

Status history

When	Change	By	Reason
2026-10-02	Open → Solution claimed	The registry's curators	Matrix Discrepancy for Representations of Finite Groups v1 recorded from arXiv:2606.12181v2.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00051, "The Group Spencer conjecture", clopen.solutions.