A Lovász-number bound for the 2-localization of the Paley graph
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. Let $\vartheta$ be the Lovász number, with the convention $\vartheta(G) \ge \alpha(G)$, so that $\omega(G) \le \vartheta(\overline{G})$, and let the 2-localization $G_{p,2}$ be the subgraph of $G_p$ induced on the common neighbours of $0$ and $1$; up to isomorphism it does not depend on the choice of adjacent pair. Then $\omega(G_p) \le \omega(G_{p,2}) + 2 \le \vartheta(\overline{G_{p,2}}) + 2$. Numerical experiments of Kunisky suggest that this approach can improve on the Hanson–Petridis bound $\omega(G_p) \le (1 + o(1))\sqrt{p/2}$.
Problem. Prove or disprove that $\vartheta(\overline{G_{p,2}}) \le \frac23 \sqrt p$ for all sufficiently large primes $p \equiv 1 \pmod 4$.
Source: Bandeira, Conjecture 27 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
- CO — Combinatorics
- Secondary
- NT, OC
- Keywords
- clique number, Lovász theta function, Paley graph, Randomstrasse101
- 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}
}
@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}
}
@inproceedings{magsino2019paley,
author = {Magsino, Mark and Mixon, Dustin G. and Parshall, Hans},
title = {Linear programming bounds for cliques in {P}aley graphs},
booktitle = {Wavelets and Sparsity XVIII},
series = {Proc. SPIE},
volume = {11138},
year = {2019}
}
@article{hanson2021paley,
author = {Hanson, Brandon and Petridis, Giorgis},
title = {Refined estimates concerning sumsets contained in the roots of unity},
journal = {Proceedings of the London Mathematical Society},
volume = {122},
number = {3},
pages = {353--358},
year = {2021},
doi = {10.1112/plms.12322}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00042, "A Lovász-number bound for the 2-localization of the Paley graph", clopen.solutions.