A degree-4 Sum-of-Squares bound for the Paley clique number
For a prime $p \equiv 1 \pmod 4$ let $G_p$ be the Paley graph on $\mathbb{Z}_p$, in which $i \sim j$ when $i - j$ is a nonzero quadratic residue, and let $\omega$ denote the clique number. The Lovász number, the degree-2 Sum-of-Squares relaxation of the clique number, gives $\omega(G_p) \le \sqrt p$. Kunisky and Yu give a precise construction of the degree-4 relaxation; their numerical experiments suggest that it may improve on $\sqrt p$ by a polynomial factor, and they proved that it cannot go below $\Omega(p^{1/3})$.
Problem. Prove or disprove that there is $\varepsilon > 0$ such that the degree-4 Sum-of-Squares relaxation of the clique number of $G_p$ gives a bound of $O(p^{1/2 - \varepsilon})$.
Source: Bandeira, Conjecture 28 of Randomstrasse101, in “On the clique number of the Paley Graph” (2025); Entry 12 of arXiv:2603.29571.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- OC — Optimization and Control
- Secondary
- CO, NT
- Keywords
- clique number, Paley graph, Randomstrasse101, Sum-of-Squares
- 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}
}
@inproceedings{kunisky2023sos,
author = {Kunisky, Dmitriy and Yu, Xifan},
title = {A degree 4 sum-of-squares lower bound for the clique number of the {P}aley graph},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
year = {2023},
eprint = {2211.02713},
archivePrefix = {arXiv}
}
@misc{kunisky2023paley,
author = {Kunisky, Dmitriy},
title = {Spectral pseudorandomness and the road to improved clique number bounds for {P}aley graphs},
year = {2023},
eprint = {2303.16475},
archivePrefix = {arXiv}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00043, "A degree-4 Sum-of-Squares bound for the Paley clique number", clopen.solutions.