The Paley ETF restricted isometry conjecture
For a prime $p \equiv 1 \pmod 4$, the Paley equiangular tight frame consists of $p + 1$ vectors in $\mathbb{C}^{(p+1)/2}$, built from the rows of the $p \times p$ discrete Fourier transform matrix indexed by $0$ and the quadratic residues, rescaled, together with one standard basis vector (Definition 21.8 of Bandeira's lecture notes; Bandeira, Fickus, Mixon and Wong). Bandeira, Fickus, Mixon and Wong, and Bandeira, Mixon and Moreira, showed that the restricted isometry property of the Paley ETF would give upper bounds on the clique number of Paley graphs.
Problem. Prove or disprove that the Paley ETF has the restricted isometry property beyond the square-root bottleneck: there is $\varepsilon > 0$ such that, for $m \sim p^{1/2 + \varepsilon}$, every matrix formed by $m$ distinct vectors of the Paley ETF has condition number bounded by a constant independent of $p$.
Source: A weaker form of a conjecture of Bandeira, Fickus, Mixon and Wong (2013). Conjecture 29 of Randomstrasse101, in Bandeira's “On the clique number of the Paley Graph” (2025); Entry 12 of arXiv:2603.29571. Also Open Problem 6.4 of his Forty-Two Open Problems.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- FA — Functional Analysis
- Secondary
- CO, NT
- Keywords
- compressed sensing, equiangular tight frames, Paley graph, Randomstrasse101, restricted isometry property
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2025,
author = {Bandeira, Afonso S. and Dmitriev, Daniil and Lucca, Kevin and Nizi{\'c}-Nikolac, Petar and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2025},
year = {2026},
eprint = {2603.29571},
archivePrefix = {arXiv}
}
@article{bandeira2013rip,
author = {Bandeira, Afonso S. and Fickus, Matthew and Mixon, Dustin G. and Wong, Percy},
title = {The road to deterministic matrices with the restricted isometry property},
journal = {Journal of Fourier Analysis and Applications},
volume = {19},
number = {6},
pages = {1123--1149},
year = {2013}
}
@article{bandeira2017conditional,
author = {Bandeira, Afonso S. and Mixon, Dustin G. and Moreira, Joel},
title = {A conditional construction of restricted isometries},
journal = {International Mathematics Research Notices},
volume = {2017},
number = {2},
pages = {372--381},
year = {2017},
doi = {10.1093/imrn/rnv385},
eprint = {1410.6457},
archivePrefix = {arXiv}
}
@misc{bandeira2025snl,
author = {Bandeira, Afonso S.},
title = {A Tour Through the Mathematics of Signals, Networks, and Learning},
howpublished = {Lecture notes, ETH Z{\"u}rich},
year = {2025},
url = {https://people.math.ethz.ch/~abandeira/MathofSNLnotes2025.pdf}
}
@misc{bandeira2016fortytwo,
author = {Bandeira, Afonso S.},
title = {Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science},
year = {2016},
url = {https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00044, "The Paley ETF restricted isometry conjecture", clopen.solutions.