Suppose that we want to construct a very good family of -regular expander graphs. The Alon-Boppana theorem says that the best we can hope for, from the point of view of spectral expansion, is to have , and we would certainly be very happy with a family of graphs in which .
Known constructions of expanders produce Cayley graphs (or sometimes Schreier graphs, which is a related notion), because it is easier to analyze the spectra of such graphs. If is a group with operation and is the inverse of element , and is a symmetric set of generators, then the Cayley graph is the graph whose vertices are the elements of and whose edges are the pairs such that .
When the group is Abelian, there is good news and bad news. The good news is that the eigenvectors of the graphs are completely characterized (they are the characters of ) and the eigenvalues are given by a nice formula. (See here and here.) The bad news is that constant-degree Cayley graphs of Abelian groups cannot be expanders.
That’s very bad news, but it is still possible to get highly expanding graphs of polylogarithmic degree as Cayley graphs of Abelian groups.
Here we will look at the extreme case of a family of graphs of degree , where is the number of vertices. Even with such high degree, the weak version of the Alon-Boppana theorem still implies that we must have , and so we will be happy if we get a graph in which . Highly expanding graphs of degree are interesting because they have some of the properties of random graphs from the distribution. In turn, graphs from have all kind of interesting properties with high probabilities, including being essentially the best known Ramsey graphs and having the kind of discrepancy property that gives seedless extractors for two independent sources. Unfortunately, these properties cannot be certified by spectral methods. The graph that we will study today is believed to have such stronger properties, but there is no known promising approach to prove such conjectures, so we will content ourselves with proving strong spectral expansion.
The graph is the Paley graph. If is a prime, is the group of addition modulo , and is the set of elements of of the form , then the graph is just . That is, the graph has a vertex for each , and two vertices are adjacent if and only if there is an such that .
Consider , the finite field with elements of which is the additive group; of the nonzero elements of , half of them are quadratic residues, and thus elements of , each with two square roots, and half of them are not. Thus, our graph has degree .
The characterization of the eigenvalues of an Abelian Cayley graph tells us that we are going to have an eigenvalue for each , given by the formula
and so we just have to estimate the above sums. If we sum over all for in instead of just summering over we get
because every term in the formula for occurs twice, and we also get an extra 1 from the case . The sums are called Gauss (quadratic) sums, and Gauss himself proved that, for , we have . This means that, for , we have , and so we have the desired expansion.
Here is how we prove Gauss’s result.
For non-zero , define if is quadratic residue and otherwise. Then is a character of the multiplicative group of : indeed we have , and . A well-known name for is that it is the Legendre symbol .
To simplify notation, let us also call . Thus, we have
In the following, it will simplify notation to make be defined over all of , so we will set . Here is where comes in:
Lemma 1 For ,
Proof: This is a one-observation proof: for every , we have
where all the summations are over and, in the last line, we use the fact that for .
And now we do the last calculation.
Lemma 2 For every non-trivial multiplicative character of and every non-trivial additive character of we have
where we extended to all of by defining .
Proof: We write down the sum and use the fact that is a multiplicative character and is an additive character.
Do a change of variable
and is always zero except, when , in which case it is .
(The above is not completely rigorous because we have “divided by zero.” A more precise accounting is to take the above sums for all but only the nonzero . In this case, after the change of variable, will range over and still only on . We can then bring back the case in the summation by noting that .)
So, putting it all together, we have for every , and so the second smallest eigenvalue of the adjacency matrix of the Paley graph is, in absolute value, at most , where is the degree.
Notice that all we used about our set of generators is that their indicator function is a multiplicative character.