On the clique number of the Paley Graph (problems 25-29)

Given a prime number $p$ such that $p \equiv 1 \pmod{4}$ the Paley graph on $p$ nodes $G_p$ is the graph where nodes $i$ and $j$ are connected if $i-j$ is a quadratic residue modulo $p$. This graph is a regular graph with degree $\frac{p-1}{2}$ and it is believed to have many pseudo-random properties (mimicking in many ways a uniformly random regular graph of the same degree, or even a $G(n,1/2)$). See (Kunisky, 2023) for a nice overview aligned with the topic of this post.

Let $\omega(G_p)$ denote the clique number of $G_p$ i.e. the size of the largest set of nodes that are all pairwise connected by an edge. Since $G_p$ is isomorphic to its complement this is the same as $\alpha(G_p)$ the independence number of $G_p$ (the size of the largest set of nodes that have no edges between them). We will focus on the clique number of ease of exposition. A random graph of the same degree has logarithmic clique number, which motivates the following well known conjecture (see, e.g., Open Problem 8.4 in (Bandeira, 2016))

Conjecture 25 (Paley Graph Clique Number)

Let $\omega(G_p)$ denote the clique number of the Paley Graph for $p \equiv 1 \pmod{4}$ prime. \(\omega(G_p)=O(\mathrm{polylog(p)}).\)

An upper bound of $\omega(G_p)\leq \sqrt{p}$ can be shown either by a spectral method or by computing the Lovasz’s theta function $\vartheta(\overline{G_p})$ of the complement of $G_p$ (the Lovasz’s theta function corresponds to an SDP and is defined on Post 9 of this blog) and recalling that $\omega(G_p)\leq \vartheta(\overline{G_p})$. Recently, Hanson and Petridis (Hanson & Petridis, 2021) showed that $\omega(G_p) \leq (1 + o(1))\sqrt{p/2}$. The post is mostly devoted to the question of whether convex relaxations such as the Lovasz’s theta function can provide interesting upper bounds on this quantity.

We start with the notion of localization (Magsino et al., 2019), (Kunisky, 2023): Let $G_{p,1}$ denote the induced subgraph on the vertices adjacent to the node 0, which we call the 1-localization. Because the 1-localization does not depend on the node picked (see (Kunisky, 2023)) we have $\omega(G_p) \leq \omega(G_{p,1}) + 1 \leq \vartheta(\overline{G_p})+1$. It was observed empirically in (Magsino et al., 2019) that $\vartheta(\overline{G_{p,1}}) \sim \sqrt{p/2}$, which would recover the Hanson-Petridis bound (also, note that $G_{p,1}$ is a circulant graph and so the SDP corresponding to $\vartheta(\overline{G_{p,1}})$ reduces to an LP).

Conjecture 26 (1-Localization of the Paley Graph)

We have, for $p \equiv 1 \pmod{4}$ prime, $\vartheta(\overline{G_{p,1}}) \sim \sqrt{p/2}$, where $G_{p,1}$ is the 1-localization of the Paley Graph described above.

This process can be iterated: Let $G_{p,2}$ denote the induced subgraph on the vertices adjacent to 0 and 1. While the resulting graph is no longer circulant, it is still the case that there is only one 2-localization (up to isomorphism), and so $\omega(G_p) \leq \omega(G_{p,2}) + 2\leq \vartheta(\overline{G_{p,2}})+2$. (Kunisky, 2023) observed empirically that $\omega(G_{p,2}) \sim (\sqrt{1/2} - \epsilon)\sqrt{p}$ (for some $\epsilon>0$), suggesting this approach could improve on the Hanson-Petridis bound. Perhaps $\omega(G_{p,2}) \sim \frac{\sqrt{p}}{2}$. We note that for 3-localizations several graphs would have to be checked (picking different triplets of nodes may yield non-isomorphic subgraphs).

Conjecture 27 (2-Localization of the Paley Graph)

For $p \equiv 1 \pmod{4}$ prime and large enough we have $\vartheta(\overline{G_{p,2}}) \leq \frac23 \sqrt{p}$, where $G_{p,2}$ is the 2-localization of the Paley Graph described above.

We note that Conjectures 17 and 18 in this Blog are consistent with these conjectures and the fact that one expects $G_p$ and their localizations to have pseudo-random properties.

There is another approach to to use convex relaxation to potentially improve over upper bounds on the $\omega(G_p)$. Recall that the Lovasz $\vartheta$ function can be viewed a as degree-2 Sum-of-Squares relaxation of the clique (or independence) number. A fascinating question is whether the degree-4 Sum-of-Squares relaxation significantly improves on the $\sqrt{p}$ bound, perhaps even improving over the state of the art (see (Kunisky & Yu, 2023) for a precise construction of this relaxation). There have been several encouraging numerical experiments (for this and other SDPs) (Kunisky & Yu, 2023) ,(Kobzar & Mody, 2023), (Wang et al., 2024). We particularly note that the numerical experiments in (Kunisky & Yu, 2023) suggest even a polynomial improvement may be possible, although the authors prove that it cannot improve beyond $\Omega(p^{\frac13})$.

Conjecture 28 (Sum-of-Squares bound for Paley clique number)

There exists $\varepsilon>0$ such that the Sum-of-Squares relaxation of degree 4 for the clique number of the Paley graph gives a bound of $O(p^{\frac12-\varepsilon})$.

The Paley Clique Conjecture has been formally related to a conjecture related to sparse recovery known as the Paley ETF conjecture (Bandeira et al., 2014), (Bandeira et al., 2013). For $p \equiv 1 \pmod{4}$ prime the Paley ETF (see Definition 21.8 in (Bandeira, 2025)) is an Equiangular Tight Frame (as defined in post 11 of this blog) with $n=p+1$ vectors in $\mathbb{C}^{\frac{p+1}{2}}$. We defer the detailed construction to the references above but in a nutshell the matrix whose columns are this frame is built by taking a submatrix of the Discrete Fourier Transform matrix corresponding to rows whose indices are quadratic residues (after an appropriate scaling a canonical basis column is added, see Definition 21.8 in (Bandeira, 2025) or (Bandeira et al., 2014), (Bandeira et al., 2013)). The resulting $\frac{p+1}{2}\times (p+1)$ matrix is conjectured to satisfy the Restricted Isometry Property beyond the so-called square-root bottleneck (Tao, 2007), (Bandeira et al., 2013) (see also Open Problem 6.4 in (Bandeira, 2016)).

Conjecture 29 (Paley ETF)

The Paley Equiangular Tight Frame construction satisfies the Restricted Isometry Property beyond the square-root bottleneck. In other words, there exists $\varepsilon>0$ such that, for $m \sim p^{1/2+\varepsilon}$, any matrix formed by picking $m$ (distinct) vectors in the Paley ETF has condition number bounded by a constant independent of $p$.

References

1. Kunisky, D. (2023). Spectral pseudorandomness and the road to improved clique number bounds for Paley graphs. ArXiv Preprint ArXiv:2303.16475.
2. Bandeira, A. S. (2016). Ten Lectures and Forty-Two Open Problems in the Mathematics of Data Science. https://people.math.ethz.ch/ abandeira//TenLecturesFortyTwoProblems.pdf
3. Hanson, B., & Petridis, G. (2021). Refined estimates concerning sumsets contained in the roots of unity. Proceedings of the London Mathematical Society, 122(3), 353–358.
4. Magsino, M., Mixon, D. G., & Parshall, H. (2019). Linear programming bounds for cliques in Paley graphs. Wavelets and Sparsity XVIII, 11138, 111381H.
5. Kunisky, D., & Yu, X. (2023). A degree 4 sum-of-squares lower bound for the clique number of the Paley graph. 38th Computational Complexity Conference (CCC 2023).
6. Kobzar, V. A., & Mody, K. (2023). Revisiting block-diagonal sdp relaxations for the clique number of the paley graphs. 2023 International Conference on Sampling Theory and Applications (SampTA), 1–5.
7. Wang, Y., Shen, Y., & Kobzar, V. A. (2024). Lower Bounds on Block-Diagonal SDP Relaxations for the Clique Number of the Paley Graphs and Their Localizations.
8. Bandeira, A. S., Mixon, D. G., & Moreira, J. (2014). A conditional construction of restricted isometries. Available Online at ArXiv:1410.6457 [Math.FA].
9. Bandeira, A. S., Fickus, M., Mixon, D. G., & Wong, P. (2013). The Road to Deterministic Matrices with the Restricted Isometry Property. Journal of Fourier Analysis and Applications, 19(6), 1123–1149.
10. Bandeira, A. S. (2025). A Tour Through the Mathematics of Signals, Networks, and Learning. https://people.math.ethz.ch/ abandeira//MathofSNLnotes2025.pdf
11. Tao, T. (2007). What’s new BLOG: Open question: deterministic UUP matrices.