Some news regarding the Paley graph

Let denote the field with elements, and let denote the multiplicative subgroup of quadratic residues. For each prime , we consider the Paley graph with vertex set , where two vertices are adjacent whenever their difference resides in . For example, the following illustration from Wikipedia depicts :

The purpose of this blog entry is to discuss recent observations regarding the Paley graph.

— New bound on the clique number —

There are several proofs that . In 2006, Maistrelli and Penman proved , and in 2013, Bachoc, Matolcsi and Ruzsa proved that holds for most . This contrasts with the best-known lower bound of . Considering this disparity between upper and lower bounds, I was excited to see progress on the upper bound this year:

Theorem (Hanson–Petridis 2019).   

The proof uses Stepanov’s method of auxiliary polynomials: Given such that , Hanson and Petridis construct a polynomial of degree with coefficients in such that every member of is a root of of multiplicity at least . It follows that .

Considering  when is an even power of an odd prime, the proof necessarily makes use of the fact that is prime. We highlight how in the following proof sketch:

Fix , , and , and let denote the unique solution to the linear system

(Indeed, this Vandermonde system is invertible since the ‘s are distinct.) Define

By our choice of ‘s, an application of the binomial theorem reveals that has degree . (Here, it’s important that is a prime rather than a prime power, since otherwise the coefficient of might be zero.) Since , we have for every . This identity allows us to relate to the polynomial

which equals 1 by the binomial theorem and our choice of ‘s. In particular, for every , it holds that

To show that each is a root of with multiplicity at least , we take derivatives of before evaluating at . For example,

(Notice that division by might not be possible if were a prime power rather than a prime.) Similarly, the th derivative of vanishes on for each . This gives the desired result.

— 3-point bounds on are computationally fast —

Recall that the Lovasz theta number provides a semidefinite relaxation of the clique number of the complement graph. To see this, let denote the indicator vector of any vertex subset of a graph . Defining

then one may write

One may relax this integer program by recording convex constraints that satisfies:

This is known as the Lovasz theta number of , and by virtue of the relaxation, it holds that . When Lovasz first introduced the theta function, he proved that

with equality when is vertex-transitive. Since is both vertex-transitive and self-complementary, it follows that .

For a sharper bound on the clique number, one might consider a higher-order member of an appropriate SDP hierarchy. For example, Gvozdenovic, Laurent and Vallentin proposed such a hierarchy in 2009, and they evaluated its performance on the Paley graph. In this setting, it has become popular to refer to the classical Lovasz program as a 2-point bound, while higher-order programs produce -point bounds for . As an application, Gvozdenovic, Laurent and Vallentin computed 3-point bounds for , denoting them by ; see their Table 2 for explicit estimates. Unfortunately, going up the SDP hierarchy comes at a substantial computational price. Case in point, it took 4.5 hours to compute on a 3GHz processor with 1GB of RAM. In joint work with Mark Magsino and Hans Parshall, we managed to exploit symmetries in the Paley graph to reduce this runtime to under 20 seconds. Thanks to this speedup, we were able to run extensive experiments that suggest that is always away from the Hanson–Petridis bound:

Above, blue dots correspond to the 3-point bound, whereas the red curve gives the closed-form Hanson–Petridis bound. In particular, the 3-point bound improves upon the Hanson–Petridis bound in what appears to be a fraction of primes.

An easy interpretation of the 3-point bound is as follows: Since is vertex-transitive, we know that resides in a maximum clique. As such, we can restrict our search to the local graph , i.e., the subgraph of induced by the neighborhood of . In particular, it holds that

Next, the vertices of form a cyclic multiplicative group, and is circulant over this group. Since is circulant, the Lovasz SDP is invariant under conjugation by circulant permutations, and so we may average over these orbits to reduce to a linear program (this last move is common practice). While our numerical experiments solved this linear program for all primes less than 3000, we suspect that it’s possible to compute with in the millions by exploiting a fast Fourier transform in the LP solver. It would be interesting if one could construct feasible points for the dual LP that improve upon the Hanson–Petridis bound infinitely often. Our experiments suggest that the improvement would be an additive constant of 1 infinitely often, much like Bachoc, Matolcsi and Ruzsa’s improvement over the “trivial” bound.

— Random Paley subgraphs satisfy a Kesten–McKay law —

Select , and consider the random graph obtained by deleting vertices of independently with probability . What can be said about the statistics of such a random graph?

Intuitively, when is small, this random graph resembles the Erdos–Renyi graph with edge probability 1/2. The adjacency matrix of the latter graph is given by

where is symmetric with zeros on the diagonal and independent Rademacher variables on the off-diagonal. Since is a Wigner matrix, its spectrum follows a semi-circle law, and so enjoys a similar spectrum with an additional spike corresponding to the all-ones contribution. To corroborate our intuition, consider the following histograms; one illustrates the bulk of the spectrum of a 998-vertex instance of with and , and the other corresponds to an instance of the Erdos–Renyi graph on 998 vertices with edge probability 1/2. The largest eigenvalue of both graphs is off the chart at about 498. (Can you tell which is which?)

When is larger, we expect to inherit more of the structure from its parent graph , and therefore lose the semicircular behavior. For example, the following is a histogram of the bulk of the spectrum of an instance of with and :

In general, it turns out that the limiting spectral distribution for (where we fix and send ) is the so-called Kesten–McKay distribution. In joint work with Mark Magsino and Hans Parshall, we prove this using the moment method.

This result corresponds to a recent observation by Haikin, Zamir and Gavish: If is a random submatrix of a equiangular tight frame, then the eigenvalues of appear to exhibit a Wachter distribution with parameters determined by and . This observation will likely have implications for compressed sensing, where it’s important to have control over the conditioning of submatrices. To see the connection with the Paley graph, recall that the Paley equiangular tight frame is a real matrix with such that

where is the Seidel adjacency matrix of the Paley graph ; that is, , if , and otherwise . Furthermore, in this special case where , the Wachter distribution reduces to the Kesten–McKay distribution.

We’re excited to tackle more of the Haikin–Zamir–Gavish observations in the coming months.