A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph

Dmitriy Kunisky, Xifan Yu

Abstract

This research explores the intersection of semidefinite programming and number theory, specifically investigating how the Sum-of-Squares (SOS) hierarchy performs on deterministic graphs that exhibit pseudorandom properties. The authors prove that the degree 4 SOS relaxation fails to accurately estimate the clique number of Paley graphs, establishing a lower bound of $\Omega(p^{1/3})$. This result effectively "derandomizes" previous lower bounds established for random graphs and suggests that while SOS may marginally surpass the traditional spectral barrier, it remains unable to reach the conjectured polylogarithmic clique number of Paley graphs.

Introduction

In computational complexity and graph theory, determining the clique number—the size of the largest complete subgraph—is a notoriously difficult NP-hard problem. For random graphs, the true clique number is typically very small, yet standard algorithms often struggle to prove upper bounds better than $\sqrt{n}$, a phenomenon known as the "$\sqrt{n}$ barrier."

Paley graphs serve as a vital testing ground for these limits. Constructed deterministically using quadratic residues in finite fields, they mimic the properties of random graphs. While number theorists conjecture their clique size to be $O(\text{polylog } p)$, the best provable upper bound remains approximately $\sqrt{p/2}$. This paper investigates whether the Sum-of-Squares (SOS) hierarchy, a powerful framework of convex relaxations, can bridge this gap.

Methodology

The SOS Framework and Pseudomoments

To prove a lower bound for the degree 4 SOS relaxation, the authors must demonstrate the existence of a "feasible solution" that satisfies the SOS constraints while claiming a large clique exists. This involves constructing a pseudomoment matrix—a massive matrix representing a pseudo-expectation over potential clique indicators.

The researchers utilized the Feige-Krauthgamer (FK) construction, a specific method for building pseudomoments originally designed for Erdős-Rényi random graphs. The challenge lay in proving that this construction remains valid (specifically, that the matrix remains positive semidefinite) when applied to the deterministic structure of a Paley graph.

Analytical Techniques

To analyze the eigenvalues of the pseudomoment matrix, the authors employed several advanced techniques:

  • Graph Matrices: This framework allowed the decomposition of the matrix into smaller "shapes" or subgraphs, making the spectral analysis tractable.
  • Number Theoretic Bounds: Unlike probabilistic proofs that rely on concentration of measure, this work utilizes character sums and Weil’s bound. By applying the Legendre symbol, the authors proved that the deterministic connections in Paley graphs satisfy the necessary conditions for the FK construction.
  • Schur Complement Analysis: This linear algebra technique was essential for proving the positivity of the matrix, which is the fundamental requirement for a valid SOS lower bound.

Key Results and Insights

The $p^{1/3}$ Lower Bound

The primary theoretical contribution is the proof that for a Paley graph on $p$ vertices, the degree 4 SOS relaxation value is at least $cp^{1/3}$ for some constant $c$. Furthermore, the authors demonstrate that this bound is optimal for the FK construction; no higher lower bound can be achieved using this specific pseudomoment architecture.

Breaking the Spectral Barrier

While the theoretical lower bound is $p^{1/3}$, numerical experiments conducted on primes up to $p=250$ suggest that the actual performance of the degree 4 SOS relaxation might scale as $O(p^{0.4})$. If this scaling holds for larger $p$, it implies that SOS successfully breaks the "trivial" spectral barrier of $\sqrt{p}$ ($p^{0.5}$), providing a tighter (though still inaccurate) estimate of the clique number than simpler methods.

Failure of Pseudocalibration

The authors also found that "pseudocalibration"—a sophisticated technique used to produce tight lower bounds for random graphs—fails when applied to Paley graphs. This suggests that the deterministic, algebraic structure of Paley graphs is "stiffer" than that of random graphs, preventing certain types of "fake" solutions from being feasible.

Conclusion and Future Directions

This research demonstrates that the tools used to fool optimization algorithms on random graphs can be translated into the deterministic realm using number theory. However, a significant gap remains: even if SOS achieves a bound of $p^{0.4}$, it is still far from the conjectured $\log^2 p$ clique size.

Future work remains focused on analyzing higher-degree SOS relaxations (degree 6 and beyond), which present significantly greater mathematical complexity. Additionally, the failure of pseudocalibration suggests that new, purely deterministic methods are required to fully understand the interaction between convex optimization and pseudorandom algebraic structures.

Summary updated

Abstract

We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number p of vertices has value at least Ω(p^{1/3}). This is in contrast to the widely believed conjecture that the actual clique number of the Paley graph is O(polylog(p)). Our result may be viewed as a derandomization of that of Deshpande and Montanari (2015), who showed the same lower bound (up to polylog(p) terms) with high probability for the Erdős-Rényi random graph on p vertices, whose clique number is with high probability O(log(p)). We also show that our lower bound is optimal for the Feige-Krauthgamer construction of pseudomoments, derandomizing an argument of Kelner. Finally, we present numerical experiments indicating that the value of the degree 4 SOS relaxation of the Paley graph may scale as O(p^{1/2 - ε}) for some ε > 0, and give a matrix norm calculation indicating that the pseudocalibration construction for SOS lower bounds for random graphs will not immediately transfer to the Paley graph. Taken together, our results suggest that degree 4 SOS may break the "√p barrier" for upper bounds on the clique number of Paley graphs, but prove that it can at best improve the exponent from 1/2 to 1/3.
BibTeX
@inproceedings{kunisky2023degree,
  author = {Dmitriy Kunisky and Xifan Yu},
  title = {{A Degree 4 Sum-Of-Squares Lower Bound for the Clique Number of the Paley Graph}},
  booktitle = {CCC},
  year = {2023},
  doi = {10.4230/lipics.ccc.2023.30},
}
Figure