## Using expanders to prove sum-product inequalities in finite fields

I am happy to have the first guest post of BigRedBits written by Igor Gorodezky about an elegant and exciting result in combinatorics.

————————-

I’m fortunate enough to be spending this semester in beautiful Los Angeles as a core participant in the 2009 long program on combinatorics at IPAM (an NSF-funded math institute on UCLA’s campus). We’ve recently wrapped up the first part of the program, which consisted of tutorial lectures on various topics in combinatorics. There was an abundance of gorgeous mathematics, and with Renato’s kind permission I’d like to hijack his blog and write about what to me was one of the most memorable lectures.

This was a lecture by Jozsef Solymosi of the University of British Columbia describing some of his recent work on the sum-product problem in finite fields. In particular, he outlined a spectral-graph-theoretic proof of a recent sum-product inequality due to Garaev. Solymosi’s proof is an extremely clever and elegant application of spectral graph theory to a classical problem in combinatorial number theory, and so I thought I’d present it here. Before stating the result and giving Solymosi’s proof, let us begin with a very brief introduction to the sum-product problem.

**1. Introduction **

Given a finite set of real numbers , define the sum set

and the product set

Both the sum set and the product set clearly must have cardinality between and . Observe that if is an arithmetic progression then while , while if is a geometric progression then while . Intuition suggests that keeping small by giving lots of additive structure inevitably blows up , while keep small by giving lots of multiplicative structure in turn blows up . For an arbitrary , one would expect at least one of these sets, if not both, to be fairly large.

Estimating the maximum of and is the *sum-product problem*. It was posed in a paper by Erdos and Szemeredi, who proved the existence of a small constant such that

for any finite . They conjecture that we actually have

for any and sufficiently large . In other words, the value of in their bound can be made arbitrarily close to 1.

Much ink has been spilled in attempts to push up the value of . At present, the best sum-product bound is due to Solymosi and gives . As an aside, I want to mention an extremely simple and elegant probabilistic proof of Elekes that gives ; it is detailed in Alon and Spencer’s classic text *The Probabilistic Method*, and is an absolute gem (look in the chapter on crossing numbers of graphs).

**2. The finite field variant **

Solymosi’s IPAM lecture was not, however, on this original sum-product problem, but rather on its natural finite field analogue: if is a subset of , the finite field of prime order , what can we say about the maximum of and ? Observe that it is important to consider fields whose order is prime and not the power of a prime, for in the latter case we could take to be a subring and end up with the degenerate case .

Bourgain, Katz and Tao got the party started in 2004 by proving the following sum-product bound.

Theorem 1For all there exists such that if with then

We note that the implied constant also depends on . The best known bound is the following, due to Garaev (2007).

Theorem 2If then

To illustrate the theorem, observe that if then . It is this theorem that Solymosi proves using spectral graph theory (Garaev’s original proof went by way of Fourier analysis and the estimation of exponential sums).

**3. Solymosi’s proof **

In this section we give Solymosi’s proof of Theorem 2 (we will assume familiarity with basic facts about eigenvalues and eigenvectors of adjacency matrices). Let us first establish some notation. Consider a -regular graph and let the eigenvalues of its adjacency matrix be

As usual, we define

Recall that if is connected and non-bipartite then is strictly smaller than , and such a graph is an expander if is bounded below by some constant.

We will make use of a fundamental result in spectral graph theory: the expander mixing lemma.

Lemma 3Let be a -regular graph with vertices. For all we have

where is the number of edges with one endpoint in and the other in .

The proof of the lemma is straightforward; we omit it because of space considerations, but it can be found in the survey on expanders by Linial, Hoory, and Wigderson.

Now, back to Theorem 2: we have a finite field and a subset . Solymosi proves the desired lower bound on by constructing a *sum-product graph* over and using its spectral properties to reason about and . So without further ado, let’s define .

The vertex set of is , and two vertices have an edge between them if . It is easy to see that has vertices and is -regular (some edges are loops). We also have the following key fact.

Lemma 4Consider . If or then these two vertices have no common neighbor, otherwise they have precisely one.

*Proof:* This follows from the fact that the unique solution of the system

is given by

which is only defined when .

Lemma 4 can be used to show that is in fact a very good expander (those more familiar with the literature on expanders will recognize that moreover, is almost a Ramanujan graph).

*Proof:* Let be the adjacency matrix of . Recall that the -entry of is the number of walks from to of length 2. If , this number is the degree , while if , with and , Lemma 4 tells us that this number is 1 if and and 0 otherwise. It follows that

where is the all-1 matrix, is the identity matrix, and is the adjacency matrix of the graph whose vertex set is the same as , and in which two vertices and are connected by an edge if or . It is easy to see that is a -regular graph.

Since is regular and its adjacency matrix is symmetric, we know that the all-1 vector is an eigenvector of and all other eigenvectors are orthogonal to it. It is easy to check that is connected and not bipartite, so that the eigenvalue has multiplicity 1, and for any other eigenvalue we have .

Given such an eigenvalue , let be a corresponding eigenvector. Then by equation~(1),

since is the all-0 vector. Therefore is an eigenvalue of .

Now, the degree of is an upper bound on the absolute value of every eigenvalue of . It follows that

which implies , as desired.

So is an expander; very good, but what about ? Solymosi introduces into the proof through very clever use of the expander mixing lemma: if we define by

then that lemma tells us that

where the second inequality used Lemma 5.

But for every there is an edge between and , so that . Using this observation and rearranging the resulting inequality gives

Now, since for positive and , we find that

which in turn implies

To finish the proof, we need only cite the two-term AM-GM inequality:

**4. A very terse bibliography **

Solymosi’s proof is from his paper “Incidences and the spectra of graphs” (requires institutional access).

A more knowledgeable treatment of sum-product problems than I could ever provide can be found in these two entries from Terry Tao’s blog. In these, Tao provides a detailed introduction to the problem, gives the probabilistic proof of Elekes’ bound, discusses an interesting cryptographic application, and provides many references.