The expansion of the Paley graph

Suppose that we want to construct a very good family of ${d}$ -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 ${\lambda_2 \leq 2 \sqrt{d-1}}$ , and we would certainly be very happy with a family of graphs in which ${\lambda_2 \leq O(\sqrt d)}$ .

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 ${\Gamma}$ is a group with operation ${\cdot}$ and ${a^{-1}}$ is the inverse of element ${a}$ , and ${S}$ is a symmetric set of generators, then the Cayley graph ${Cay(\Gamma, S)}$ is the graph whose vertices are the elements of ${\Gamma}$ and whose edges are the pairs ${(a,b)}$ such that ${a\cdot b^{-1} \in S}$ .

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 ${\Gamma}$ ) 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 ${d_n = n/2}$ , where ${n}$ is the number of vertices. Even with such high degree, the weak version of the Alon-Boppana theorem still implies that we must have ${\sigma_2 \geq \Omega(\sqrt d_n)}$ , and so we will be happy if we get a graph in which ${\sigma_2 \leq O(\sqrt d) = O(\sqrt n)}$ . Highly expanding graphs of degree ${n/2}$ are interesting because they have some of the properties of random graphs from the ${G_{n,\frac 12}}$ distribution. In turn, graphs from ${G_{n,\frac 12}}$ 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 ${p}$ is a prime, ${{\mathbb Z} / p {\mathbb Z}}$ is the group of addition modulo ${p}$ , and ${Q}$ is the set of elements of ${{\mathbb Z}/ p{\mathbb Z}}$ of the form ${r^2 \bmod p}$ , then the graph is just ${Cay ( {\mathbb Z}/p{\mathbb Z}, Q)}$ . That is, the graph has a vertex ${v}$ for each ${v\in \{ 0,\ldots,p-1\}}$ , and two vertices ${a,b}$ are adjacent if and only if there is an ${r\in \{ 0,\ldots,p-1\}}$ such that ${a-b \equiv r^2 \pmod p}$ .

Consider ${{\mathbb F}_p}$ , the finite field with ${p}$ elements of which ${{\mathbb Z} / p {\mathbb Z}}$ is the additive group; of the ${p-1}$ nonzero elements of ${{\mathbb F}_p}$ , half of them are quadratic residues, and thus elements of ${Q}$ , each with two square roots, and half of them are not. Thus, our graph has degree ${d = (p-1)/2}$ .

The characterization of the eigenvalues of an Abelian Cayley graph tells us that we are going to have an eigenvalue ${\lambda_a}$ for each ${a\in \{ 0,\ldots,p-1\}}$ , given by the formula

$\displaystyle \lambda_a = \sum_{q \in Q} e^{2\pi i aq /p}$

and so we just have to estimate the above sums. If we sum over all ${x^2}$ for ${x}$ in ${{\mathbb Z}/p{\mathbb Z}}$ instead of just summering over ${Q}$ we get

$\displaystyle s_a := \sum_{x\in {\mathbb F}_p} e^{2\pi i a x^2/p } = 1 + 2 \lambda_a$

because every term in the formula for ${\lambda_2}$ occurs twice, and we also get an extra 1 from the case ${x=0}$ . The sums ${s_a}$ are called Gauss (quadratic) sums, and Gauss himself proved that, for ${a\neq 0}$ , we have ${|s_a| = \sqrt p}$ . This means that, for ${a\neq 0}$ , we have ${|\lambda_a| \leq \frac 12 ( 1 + \sqrt p)}$ , and so we have the desired expansion.

Here is how we prove Gauss’s result.

For non-zero ${x}$ , define ${\chi(x)=1}$ if ${x}$ is quadratic residue and ${\chi(x)-1}$ otherwise. Then ${\chi}$ is a character of the multiplicative group of ${{\mathbb F}_p}$ : indeed we have ${\chi(1) = 1}$ , ${\chi(x\cdot y) = \chi(x) \cdot \chi(y)}$ and ${\chi(x^{-1}) = \overline {\chi(x)}}$ . A well-known name for ${\chi(x)}$ is that it is the Legendre symbol ${\left( \frac xp \right)}$ .

To simplify notation, let us also call ${\phi_a( x) := e^{2\pi i a x/p}}$ . Thus, we have

$\displaystyle s_a = \sum_{x\in {\mathbb F}_p} \phi(x^2)$

In the following, it will simplify notation to make ${\chi}$ be defined over all of ${{\mathbb F}_p}$ , so we will set ${\chi(0) := 0}$ . Here is where ${\chi}$ comes in:

Lemma 1 For ${a\neq 0}$ ,

$\displaystyle s_a = \sum_{x\in {\mathbb F}_p} \chi(x) \phi_a(x)$

Proof: This is a one-observation proof: for every ${x\in {\mathbb F}_p}$ , we have

$\displaystyle \chi(x) = ( \# (\mbox{ square roots of } x ) - 1 )$

and so

$\displaystyle \sum_x \chi(x) \phi_a(x) = \sum_x ( \# (\mbox{ square roots of } x ) - 1 ) \phi_a(x)$

$\displaystyle \sum_{x,r} I[r^2 = x] \phi_a(x) - \sum_x \phi_a(x)$

$\displaystyle = \sum_r \phi_a(r^2)$

where all the summations are over ${{\mathbb F}_p}$ and, in the last line, we use the fact that ${\sum_x \phi_a (x) = 0}$ for ${a\neq 0}$ . $\Box$

And now we do the last calculation.

Lemma 2 For every non-trivial multiplicative character ${\chi}$ of ${{\mathbb F}^\times_p}$ and every non-trivial additive character ${\phi}$ of ${{\mathbb Z}/p{\mathbb Z}}$ we have

$\displaystyle | \sum_{x\in {\mathbb F}_p} \chi(x) \phi(x) |^2 = p$

where we extended ${\chi}$ to all of ${{\mathbb F}_p}$ by defining ${\chi(0):= 0}$ .

Proof: We write down the sum and use the fact that ${\chi}$ is a multiplicative character and ${\phi}$ is an additive character.

$\displaystyle | \sum_{x\in {\mathbb F}_p} \chi(x) \phi(x) |^2 = \sum_{x,y} \chi(x) \phi(x) \overline{\chi(y) \phi(y)}$

$\displaystyle = \sum_{x,y} \chi(xy^{-1} ) \phi(x-y)$

Do a change of variable ${z=xy^{-1}}$

$\displaystyle = \sum_z \chi(z) \sum_y \phi(y\cdot(z-1))$

and ${\sum_y \phi( y \cdot (z-1))}$ is always zero except, when ${z=1}$ , in which case it is ${p}$ .

(The above is not completely rigorous because we have “divided by zero.” A more precise accounting is to take the above sums for all ${x\in {\mathbb F}_p}$ but only the nonzero ${y\in{\mathbb F}_p^\times}$ . In this case, after the change of variable, ${z}$ will range over ${{\mathbb F}_p}$ and ${y}$ still only on ${{\mathbb F}^\times_p}$ . We can then bring back the ${y=0}$ case in the summation by noting that ${\sum_z \chi(z) \cdot \phi(0) =\sum_z \chi(z) = 0}$ .) $\Box$

So, putting it all together, we have ${s_a = \pm \sqrt p}$ for every ${a\neq 0}$ , and so the second smallest eigenvalue of the adjacency matrix of the Paley graph is, in absolute value, at most ${\frac 12 ( 1+ \sqrt p) = \frac 12 ( 1 + \sqrt {2d +1} )}$ , where ${d}$ is the degree.

Notice that all we used about our set of generators is that their indicator function is a multiplicative character.

3 thoughts on “The expansion of the Paley graph”

Albert on September 10, 2014 at 11:38 pm said:

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.
Pascal on September 17, 2014 at 11:27 am said:

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.
voloch on September 19, 2014 at 3:55 pm said:

There is Cayley, Paley but no Payley.

Enter your comment here...

Fill in your details below or click an icon to log in:

Email (required) (Address never made public)

Name (required)

Website

You are commenting using your WordPress.com account. ( Log Out / Change )

You are commenting using your Twitter account. ( Log Out / Change )

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

The expansion of the Paley graph

3 thoughts on “The expansion of the Paley graph”

Leave a Reply

Share this:

Like this:

Related

3 thoughts on “The expansion of the Paley graph”

Leave a Reply