OP-00040 Open

The clique number of Paley graphs

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. A random graph of the same degree has logarithmic clique number. Known bounds are $\omega(G_p) \le \sqrt p$, from a spectral argument or the Lovász number, and $\omega(G_p) \le (1 + o(1))\sqrt{p/2}$ (Hanson and Petridis).

Problem. Prove or disprove that $\omega(G_p) = O(\operatorname{polylog} p)$.

Source: A well-known conjecture; Open Problem 8.4 of Bandeira's Ten Lectures and Forty-Two Open Problems (2016). Conjecture 25 of Randomstrasse101, in Bandeira's “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: NT — Number Theory
Secondary: CO
Keywords: clique number, Paley graph, pseudorandom graphs, 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}
}

@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}
}

@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}
}

@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}
}

Canonical Lean statement

A submission resolves this problem by proving the constant Problem_OP_00040.

/-- OP-00040: The clique number of Paley graphs -/
def Problem_OP_00040 : Prop :=
  ∃ (C : ℝ) (k : ℕ), ∀ p : ℕ, p.Prime → p % 4 = 1 →
  ((SimpleGraph.fromRel fun (x y : ZMod p) => IsSquare (x - y)).cliqueNum : ℝ) ≤
    C * Real.log p ^ k

Authored by —; reviewed by clemens-admin.

Available to match against in: Lean v4.33.1 with Mathlib v4.33.1.

Resolving this problem in Lean

Add the problems package as a dependency, import this problem's module, and prove the constant. Any published revision works.

In lakefile.toml:

[[require]]
name = "RegistryProblems"
git = "https://github.com/cthalhammer/registry-problems"
rev = "753bebc58e3fee845f4fffec7d24e7c8cc2a689a"

In your proof:

import RegistryProblems.OP_00040

theorem resolution : RegistryProblems.Problem_OP_00040 := by
  sorry

In preprint.toml, mapping the claim to the declaration that establishes it:

[[statements]]
label = "Theorem 1"
lean = "resolution"
latex = "..."
problem = "OP-00040"
claim = "full"

To disprove it instead, prove the negation and claim "disproof", or "counterexample" if the proof exhibits one:

theorem disproof : ¬ RegistryProblems.Problem_OP_00040 := by
  sorry

You can also write the statement out in full; the verifier checks it matches up to definitional equality. Partial results and reductions are not matched against this statement.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00040, "The clique number of Paley graphs", clopen.solutions.