Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs

Dmitriy KuniskyExp. Math 2023

Abstract

We study subgraphs of Paley graphs of prime order $p$ induced on the sets of vertices extending a given independent set of size $a$ to a larger independent set. Using a sufficient condition proved in the author's recent companion work, we show that a family of character sum estimates would imply that, as $p \to \infty$, the empirical spectral distributions of the adjacency matrices of any sequence of such subgraphs have the same weak limit (after rescaling) as those of subgraphs induced on a random set including each vertex independently with probability $2^{-a}$, namely, a Kesten-McKay law with parameter $2^a$. We prove the necessary estimates for $a = 1$, obtaining in the process an alternate proof of a character sum equidistribution result of Xi (2022), and provide numerical evidence for this weak convergence for $a \geq 2$. We also conjecture that the minimum eigenvalue of any such sequence converges (after rescaling) to the left edge of the corresponding Kesten-McKay law, and provide numerical evidence for this convergence. Finally, we show that, once $a \geq 3$, this (conjectural) convergence of the minimum eigenvalue would imply bounds on the clique number of the Paley graph improving on the current state of the art due to Hanson and Petridis (2021), and that this convergence for all $a \geq 1$ would imply that the clique number is $o(\sqrt{p})$.

Introduction

Paley graphs $G_p$ of prime order $p \equiv 1 \pmod 4$ are central objects in additive combinatorics and graph theory, known for their "pseudorandom" properties. Despite their deterministic construction via quadratic residues, they mimic Erdős-Rényi random graphs in many respects. However, a significant gap persists in our understanding of their clique number, $\omega(G_p)$. While random graphs typically have $\omega(G) \approx 2\log_2 p$, the best known upper bound for Paley graphs has long hovered around $\sqrt{p}$. The current state-of-the-art bound, $\omega(G_p) \le \frac{1}{\sqrt{2}}\sqrt{p} + \frac{1}{2}$, was established by Hanson and Petridis in 2021. This paper introduces a novel spectral strategy to break this $\sqrt{p}$ barrier by investigating the "localizations" of Paley graphs.

Methodology: Localization and Spectral Pseudorandomness

The core technique presented is localization. Instead of analyzing the global structure of $G_p$, the study focuses on subgraphs induced by vertices that are non-adjacent to a fixed independent set of size $a$. The author conjectures that these localized subgraphs exhibit spectral pseudorandomness, meaning their rescaled adjacency matrices have an empirical spectral distribution (e.s.d.) converging to the Kesten-McKay law—a distribution characteristic of random regular graphs.

To bridge number theory and graph theory, the author introduces necklace character sums. These multivariate character sums are used to estimate the moments of the e.s.d., providing a path to prove spectral convergence. Furthermore, tools from free probability, such as asymptotic freeness and Wachter’s MANOVA law, are employed to model the interaction between different graph components. To support these theoretical frameworks, numerical experiments were conducted on primes up to $p \approx 20,000$.

The Localization Tradeoff

A key conceptual contribution is the identification of a tradeoff between the complexity of the bounding method (e.g., Sum-of-Squares (SOS) relaxations) and the degree of localization $a$. As shown in the table below, increasing the localization degree allows for simpler spectral bounds to potentially achieve results that would otherwise require high-degree SOS relaxations. This strategy suggests that the "randomness" inherent in local subgraphs can be leveraged to bypass the rigidity of the global graph spectrum.

Summary of bounds for the clique number of Paley graphs based on localization degree $a$ and SOS degree.

Key Results

The paper provides a rigorous proof for the first degree of localization ($a=1$), confirming both spectral convergence and the behavior of the minimum eigenvalue. For higher degrees ($a \ge 2$), the author provides strong numerical evidence. The most significant theoretical result is a conditional bound: if the minimum eigenvalue conjecture holds for a localization degree $a$, then $\omega(G_p) \le \frac{\sqrt{2^a - 1}}{2^{a-1}}\sqrt{p} + o(\sqrt{p})$.

  • For $a=2$, this yields $\approx 0.866\sqrt{p}$.
  • For $a=3$, it yields $\approx 0.661\sqrt{p}$, which would improve upon the Hanson-Petridis bound.
  • Crucially, if the conjecture holds for all $a \ge 1$, then $\omega(G_p) = o(\sqrt{p})$, finally breaking the square-root barrier.

Discussion and Future Work

While the "bulk" of the spectrum is well-behaved and controllable via character sums, the clique number bound depends on the "edge" of the spectrum (the minimum eigenvalue). Proving the absence of outlier eigenvalues for $a \ge 2$ remains a formidable challenge, requiring stronger character sum estimates than those currently available. Future research will focus on establishing these estimates and exploring the interplay between localization and more sophisticated convex relaxations like SOS degree 4.

Conclusion

This work outlines a clear roadmap for improving clique number bounds in Paley graphs. By shifting the focus to localized spectral properties, it transforms a hard combinatorial problem into a challenge of analytic number theory, offering a promising path toward the $o(\sqrt{p})$ goal.

Summary updated

Abstract

We study subgraphs of Paley graphs of prime order $p$ induced on the sets of vertices extending a given independent set of size $a$ to a larger independent set. Using a sufficient condition proved in the author's recent companion work, we show that a family of character sum estimates would imply that, as $p \to \infty$, the empirical spectral distributions of the adjacency matrices of any sequence of such subgraphs have the same weak limit (after rescaling) as those of subgraphs induced on a random set including each vertex independently with probability $2^{-a}$, namely, a Kesten-McKay law with parameter $2^a$. We prove the necessary estimates for $a = 1$, obtaining in the process an alternate proof of a character sum equidistribution result of Xi (2022), and provide numerical evidence for this weak convergence for $a \geq 2$. We also conjecture that the minimum eigenvalue of any such sequence converges (after rescaling) to the left edge of the corresponding Kesten-McKay law, and provide numerical evidence for this convergence. Finally, we show that, once $a \geq 3$, this (conjectural) convergence of the minimum eigenvalue would imply bounds on the clique number of the Paley graph improving on the current state of the art due to Hanson and Petridis (2021), and that this convergence for all $a \geq 1$ would imply that the clique number is $o(\sqrt{p})$.
BibTeX
@article{kunisky2023spectral,
  author = {Dmitriy Kunisky},
  title = {{Spectral Pseudorandomness and the Road to Improved Clique Number Bounds for Paley Graphs}},
  journal = {Exp. Math.},
  year = {2023},
}
Figure