Archive

Posts Tagged ‘expanders’

Using expanders to prove sum-product inequalities in finite fields

September 23rd, 2009 No comments

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 {A}, define the sum set

\displaystyle A+A = \{a+b \mid a,b \in A\}

and the product set

\displaystyle A \cdot A = \{ab \mid a,b \in A\}.

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

Estimating the maximum of {|A+A|} and {|A \cdot A|} is the sum-product problem. It was posed in a paper by Erdos and Szemeredi, who proved the existence of a small constant {c} such that

\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+c} \right)

for any finite {A}. They conjecture that we actually have

\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{2-\delta} \right)

for any {\delta > 0} and sufficiently large {|A|}. In other words, the value of {c} in their bound can be made arbitrarily close to 1.

Much ink has been spilled in attempts to push up the value of {c}. At present, the best sum-product bound is due to Solymosi and gives {c \approx 3/11}. As an aside, I want to mention an extremely simple and elegant probabilistic proof of Elekes that gives {c=1/4}; 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 {A} is a subset of {\mathbb F_p}, the finite field of prime order {p}, what can we say about the maximum of {|A+A|} and {|A \cdot A|}? 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 {A} to be a subring and end up with the degenerate case {|A|=|A+A|=|A \cdot A|}.

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

Theorem 1 For all {\epsilon > 0} there exists {\delta > 0} such that if {A \subseteq \mathbb F_p } with {p^{\epsilon} < |A| < p^{1+\epsilon}} then

\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( |A|^{1+\delta} \right).

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

Theorem 2 If {A \subseteq \mathbb F_p} then

\displaystyle \max\{ |A+A|, |A \cdot A| \} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2},|A|^2p^{-1/2} \right\} \right).

To illustrate the theorem, observe that if {|A| \approx p^{2/3}} then {\max\{ |A+A|, |A \cdot A| \} = \Omega( |A|^{5/4})}. 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 {d}-regular graph {G} and let the eigenvalues of its adjacency matrix be

\displaystyle d=\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n.

As usual, we define

\displaystyle \lambda(G) = \max\{ \lambda_2,|\lambda_n|\}.

Recall that if {G} is connected and non-bipartite then {\lambda(G)} is strictly smaller than {d}, and such a graph is an expander if {d-\lambda(G)} is bounded below by some constant.

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

Lemma 3 Let {G} be a {d}-regular graph with {n} vertices. For all {S,T \subseteq V(G)} we have

\displaystyle \left| e(S,T) - \frac{d}{n}|S||T| \right| \leq \lambda(G) \sqrt{|S||T|}

where {e(S,T)} is the number of edges with one endpoint in {S} and the other in {T}.

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 {\mathbb F_p} and a subset {A}. Solymosi proves the desired lower bound on {\max\{ |A+A|, |A \cdot A| \}} by constructing a sum-product graph {G_{SP}} over {\mathbb F_p} and using its spectral properties to reason about {|A+A|} and {|A \cdot A|}. So without further ado, let’s define {G_{SP}}.

The vertex set of {G_{SP}} is {\left( \mathbb F_p \setminus \{0\} \right) \times \mathbb F_p}, and two vertices {(a,b),(c,d)} have an edge between them if {ac=b+d}. It is easy to see that {G_{SP}} has {p(p-1)} vertices and is {(p-1)}-regular (some edges are loops). We also have the following key fact.

Lemma 4 Consider {(a,b),(c,d) \in V(G_{SP})}. If {a=c} or {b=d} 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

\displaystyle \begin{array}{c} ax=b+y \\ cx=d+y \end{array}

is given by

\displaystyle \begin{array}{c} x = (b-d)(a-c)^{-1}\\ 2y = x(a+c)-b-d \end{array}

which is only defined when {a \neq c, b \neq d}. \Box

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

Lemma 5 {\lambda(G_{SP}) < \sqrt{3p}}.

Proof: Let {M} be the adjacency matrix of {G_{SP}}. Recall that the {(u,v)}-entry of {M^2} is the number of walks from {u} to {v} of length 2. If {u=v}, this number is the degree {p-1}, while if {u \neq v}, with {u=(a,b)} and {v=(c,d)}, Lemma 4 tells us that this number is 1 if {a\neq c} and {b \neq d} and 0 otherwise. It follows that

\displaystyle M^2 = J+(p-2)I-E \ \ \ \ \ (1)

where {J} is the all-1 matrix, {I} is the identity matrix, and {E} is the adjacency matrix of the graph {G_E} whose vertex set is the same as {G_{SP}}, and in which two vertices {(a,b)} and {(c,d)} are connected by an edge if {a=c} or {b=d}. It is easy to see that {G_E} is a {(2p-3)}-regular graph.

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

Given such an eigenvalue {\theta}, let {\bf v} be a corresponding eigenvector. Then by equation~(1),

\displaystyle \theta^2 \mathbf{v} = (p-2)\mathbf{v} - E \mathbf v

since {J\mathbf v} is the all-0 vector. Therefore {p-2-\theta^2} is an eigenvalue of {E}.

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

\displaystyle p-2-\theta^2 \geq -2p+3

which implies {|\theta| < \sqrt{3p}}, as desired. \Box

So {G_{SP}} is an expander; very good, but what about {A}? Solymosi introduces {A} into the proof through very clever use of the expander mixing lemma: if we define {S,T \subseteq V(G_{SP})} by

\displaystyle S=(A \cdot A) \times (-A), \ \quad T=(A^{-1}) \times (A+A)

then that lemma tells us that

\displaystyle e(S,T) \leq \frac{|S||T|}{p} + \lambda(G_{SP}) \sqrt{|S||T|} < \frac{|A\cdot A||A+A||A|^2}{p} + \sqrt{3p|A \cdot A||A+A||A|^2}

where the second inequality used Lemma 5.

But for every {a,b,c \in A} there is an edge between {(ab,-c) \in S} and {(b^{-1},a+c) \in T}, so that {e(S,T) \geq |A|^3}. Using this observation and rearranging the resulting inequality gives

\displaystyle \sqrt{|A \cdot A||A+A|} > \left( \frac{\sqrt{|A \cdot A||A+A|}}{p|A|}+\sqrt{3}\frac{p^{1/2}}{|A|^2} \right)^{-1}.

Now, since {(x+y)^{-1} \geq \frac{1}{2}\min\{x^{-1},y^{-1}\}} for positive {x} and {y}, we find that

\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ \frac{p|A|}{\sqrt{|A \cdot A||A+A|}}, |A|^2 p^{-1/2} \right\} \right)

which in turn implies

\displaystyle \sqrt{|A \cdot A||A+A|} = \Omega\left( \min\left\{ |A|^{1/2}p^{1/2}, |A|^2 p^{-1/2} \right\} \right).

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

\displaystyle \max\{ |A+A|, |A \cdot A| \} \geq \frac{|A \cdot A|+|A+A|}{2} \geq \sqrt{|A \cdot A||A+A|} .

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.

Igor Gorodezky

Categories: theory Tags: , , , ,