10 Lectures and 42 Open Problems — The Paley ETF Conjecture

Paley RIP: an exact clique obstruction to beyond-coherence arguments

Definitions and mathematical statement

Let $p\equiv1\pmod4$ be prime and let $Q\subset\mathbb F_p^*$ be the nonzero quadratic residues. Form a matrix $A_p$ with rows $\{0\}\cup Q$ and columns $\mathbb F_p\cup\{\infty\}$ by \[ (A_p)_{0j}=p^{-1/2},\quad (A_p)_{rj}=(2/p)^{1/2}e^{2\pi i rj/p}\quad(r\in Q,j\in\mathbb F_p), \qquad (A_p)_{\cdot,\infty}=e_0. \] The vector $e_0$ is one in row zero and zero elsewhere. This is the unit-column-norm Paley equiangular tight frame, of size $(p+1)/2$ by $p+1$. Distinct columns have inner-product magnitude $p^{-1/2}$.

For $s\ge1$, set \[ \delta_s(A_p)=\max_{|J|\le s} \|(A_p)_J^*(A_p)_J-I_{|J|}\|_{\mathrm{op}}, \] where $J$ is a column subset and the norm is the largest singular value. Does there exist a fixed $\delta<1$ and an integer function $s(p)$ with $s(p)/\sqrt p\to\infty$ such that $\delta_{s(p)}(A_p)\le\delta$ for all sufficiently large such primes?

Even an unbounded logarithmic improvement over $\sqrt p$ is sought; a fixed constant multiple of $\sqrt p$ does not suffice. Equivalently, all coefficient vectors on each permissible column set must have their squared norm preserved within factors $1\pm\delta$. The question is unconditional for this specific arithmetic frame, not a random choice of Fourier rows or a conclusion assuming an unproved distribution property of quadratic residues.

Short English statement

Does the Paley frame preserve sparse-vector norms for sparsity growing faster than the square root of its size?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 2800604 (AMR-027-0604), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Bandeira - 42 Open Problems in Data Science $2016$, Open Problem 6.4. Original source indexed by AMR-027-0604. https://afonsobandeira.wordpress.com/2015/12/07/10l42pcompressedsensing/.
• S3 A. S. Bandeira, Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science, corresponding numbered problem and surrounding definitions. https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf.

Verbatim supplied catalogue question

Does the Paley Equiangular tight frame satisfy the Restricted Isometry Property pass the square root bottleneck? (even by logarithmic factors?).

Attempt and results

Let $p\equiv1\pmod4$ be prime and keep the frame in the original definition. Write $\chi$ for the quadratic character with $\chi(0)=0$, and $e_p(t)=e^{2\pi it/p}$. We derive its Gram entries directly, avoiding a dependence on the sign convention for the quadratic Gauss sum.

Character-sum calculation.

Set $G=\sum_{t\ne0}\chi(t)e_p(t)$. Half the nonzero field elements are squares: the map $x\mapsto x^2$ has exactly two preimages for every nonzero square. Thus $\sum_{t\ne0}\chi(t)=0$. Since $\chi(-1)=1$, complex conjugation followed by $t\mapsto-t$ shows $G$ is real. Moreover, put $x=uy$ in the double sum to obtain \[ |G|^2=\sum_{u\ne0}\chi(u)\sum_{y\ne0}e_p((u-1)y) =(p-1)-\sum_{u\ne0,1}\chi(u)=p. \] Here the inner sum equals $p-1$ at $u=1$ and $-1$ otherwise, by the finite geometric series. Hence $G=\varepsilon\sqrt p$ for some $\varepsilon\in\{-1,1\}$; its sign is unnecessary below. For $i\ne j$ in $\mathbb F_p$, the given row weights give \[ \langle a_i,a_j\rangle =\frac1p\left(1+2\sum_{r\in Q}e_p(r(j-i))\right) =\frac{\chi(j-i)G}{p}. \] Indeed $2\boldsymbol1_Q(r)=1+\chi(r)$ for $r\ne0$, the nontrivial additive-character sum over the whole field is zero, and scaling its argument multiplies the character sum by $\chi(j-i)$. The infinity column has inner product $1/\sqrt p$ with every finite column. All columns have norm one.

Exact error on a clique.

If $J\subset\mathbb F_p$ is a Paley clique of size $q\ge2$, every off-diagonal character in its Gram matrix is one. Thus its Gram error equals $\varepsilon(J_q-I_q)/\sqrt p$ and has norm $(q-1)/\sqrt p$. The same conclusion holds for an independent set, with the sign reversed. In particular, if $\delta_s(A_p)\le\delta<1$ and $s>1+\delta\sqrt p$, there cannot be a clique of size exceeding $1+\delta\sqrt p$: a larger clique has a subset of size $\lfloor1+\delta\sqrt p\rfloor+1\le s$, contradicting that bound. This necessary condition does not prove RIP, even if all cliques are small; arbitrary supports with mixed signs and arbitrary complex coefficients remain.

The attempted absolute-value argument.

For every support of size $t\le s$, the preceding Gram entries and $(\sum|x_i|)^2\le t\sum|x_i|^2$ imply $|\|Ax\|^2-\|x\|^2|\le(t-1)\|x\|^2/\sqrt p$. Consequently $\delta_s\le(s-1)/\sqrt p$ is a sound elementary bound. But as $s/\sqrt p\to\infty$ it cannot supply any fixed distortion below one. The clique computation shows why replacing every sign by a favorable cancellation assumption is unjustified: some supports have perfectly aligned signs. It does not show that sufficiently large such supports exist.

Context, audit, and remaining scope

The original Paley-frame question and its relationship to clique questions were checked in Bandeira's primary notes on 11 October 2026. These are elementary standard Gram calculations, not a new cancellation bound. The audit checked $q=1$ separately (error zero), the infinity column, Gauss-sum sign independence, and the all-support/all-coefficient quantifiers. No numerical computation or theorem prover was used in this record. No unconditional estimate for $s/\sqrt p\to\infty$ was established, and no unproved character-pseudorandomness hypothesis has been substituted for it.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. No uniform cancellation estimate for arbitrary supports and coefficients above square-root sparsity is proved; clique obstructions alone do not characterize RIP.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Bandeira, lecture notes $2016$, Section 6.5.3 and Open Problem 6.4; source question inspected. https://people.math.ethz.ch/~abandeira/TenLecturesFortyTwoProblems.pdf.

Final status

Unresolved in this attempt. No uniform cancellation estimate for arbitrary supports and coefficients above square-root sparsity is proved; clique obstructions alone do not characterize RIP.