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
and so
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.
Very nice, thanks for sharing! Two minor typos: 1) the lambda_2 immediately after the formula for s_a should be lambda_a, and 2) “=” missing between \chi(x) and -1 in the definition of \chi.
There is also a nice computation of the eigenvalues in the survey on presudo-random graphs by Krivelevich and Sudakov. Their computation is valid not only for the Paley graph but for all strongly regular graphs.
There is Cayley, Paley but no Payley.