Growth, expanders, and the sum-product problem

It is a great pleasure to introduce Harald Helfgott as the first guest author on this blog.  Many of the readers here will be familiar with the sum-product problem of Erdös-Szemerédi: see here for general background, or here for an exposition of Solymosi’s recent breakthrough. The subject of this post is the connection between the sum-product theorem in finite fields, due to Bourgain-Katz-Tao and Konyagin, and recent papers on sieving and expanders, including Bourgain and Gamburd’s papers on SL_2 and on SL_3 and Bourgain, Gamburd and Sarnak’s paper on the affine sieve. Since this connection was made through Harald’s paper on growth in SL_2 (he has since proved a similar result in SL_3 ), I asked Harald if he would be willing to write about it here. His post is below.


Let us first look at the statements of the main results. In the following, |S| means “the number of elements of a set S“. Given a subset A of a ring, we write A+A for \{x+y:\ x,y \in A\} and A\cdot A for \{x\cdot y:\  x,y \in A\}.

Sum-product theorem for {\Bbb Z}/p{\Bbb Z} (Bourgain, Katz, Tao, Konyagin). Let p be a prime. Let A be a subset of {\Bbb Z}/p{\Bbb Z}. Suppose that |A|\leq p^{1-\epsilon},\ \epsilon>0. Then either |A+A| \geq |A|^{1+\delta} or |A\cdot A|\geq  |A|^{1+\delta}, where \delta>0 depends only on \epsilon.

In other words: a subset of {\Bbb Z}/p{\Bbb Z} grows either by addition or by multiplication (provided it has any room to grow at all). One of the nicest proofs of the sum-product theorem can be found in this paper by Glibichuk and Konyagin.

Now here is what I proved on SL_2. Here A\cdot A\cdot A means simply \{x\cdot y\cdot z:\ x,y,z\in A\}.

Theorem (H). Let p be a prime. Let G = SL_2({\Bbb Z}/p{\Bbb Z}). Let A be a subset of G that generates G. Suppose that |A|\leq |G|^{1-\epsilon},\ \epsilon>0. Then |A\cdot A\cdot A| \geq |A|^{1+ \delta}, where \delta >0 depends only on \epsilon.

One of the important things here – as in the sum-product theorem – is that \delta is independent of the ground field, i.e., \delta does not depend on p. By the way,

  • both here and in the sum-product theorem, if the set A is too big (say, |A|\geq |G|^{1-\epsilon} for some small \epsilon) then one gets done in a couple of steps. I proved something of the sort for SL_2({\Bbb Z}/p{\Bbb Z}), but then Gowers came up with a nicer result with a cleaner proof, and Babai, Nikolov and Pyber applied it and generalised it greatly. For G=SL_n({\Bbb Z}/p{\Bbb Z}) this general result states (among other things):

    Let A be a subset of G=SL_n({\Bbb Z}/p{\Bbb Z}). Assume that |A| \geq |G|/(\frac{1}{2} p^{(n-1)/3}). Then A\cdot A\cdot A = G.

    Here \frac{1}{2} p^{(n-1)/3} is just the dimension of the lowest-dimensional representation of G. (Well, perhaps the dimension is that minus 1/2.)

  • the condition that A generates G is natural in the following sense: if A does not generate G, then we are not dealing with a problem on growth in G, but with a problem on the group \langle A\rangle generated by A. As it happens, in the case of SL_2, the matter of subgroups is quite simple: a subgroup of SL_2({\Bbb Z}/p{\Bbb Z}) with more than 120 elements either has a commutative subgroup of index at most 2 (and there a set may very well not grow rapidly) or it is contained in a Borel subgroup, i.e., a group of upper-triangular matrices (for some choice of basis). If we are in this latter case, then either A is very close to being contained in a commutative group (and then it may fail to grow rapidly) or A can be shown to grow rapidly by a fairly easy application of a version of the sum-product theorem that is slightly stronger than the one we stated.

Let me say a couple of words about the proof. (I will summarise the way in which I actually proved things at the time; my perspective has changed somewhat since then.) Assume there is a set A of generators of G=SL_2({\Bbb Z}/p{\Bbb Z}) that does not grow: |A\cdot A \cdot A|\leq |A|^{1+\delta},\ \delta>0 very small. We want to derive a contradiction.

This non-growing set A turns out to have some funny properties. For example, it is not too hard to show (though it may be surprising at first) that A^{-1} A =\{x^{-1} y:\  x,y \in A\} will have to have many elements that commute with each other; they, in fact, lie in a maximal torus, i.e., they are simultaneously diagonalisable. At the same time, one can show that there cannot too many elements like that; there must be just the right number – about |A|^{1/3}. (This makes some sense: a torus in SL_2 is one-dimensional, whereas SL_2 is 3-dimensional; hence dim(torus)/dim (SL_2)= 1/3.)

As it turns out, one can prove the same thing about the number of conjugacy classes of SL_2 occupied by elements of A (or, rather, by elements of A\cdot A\cdot A \dotsb A (A times itself 10 times, say)). The number of such conjugacy classes will have to be about |A|^{1/3}.

One then shows that, while A itself might have such properties, A times itself a few times cannot. The key idea is basically this: the conjugacy class of an element of SL_2 is given away by its trace, and traces in SL_2 (though not in SL_3, or SL_n!) obey the rule

tr(g) tr(h) = tr(g h) + tr(g h^{-1}).

This basically forces the set of traces of A to grow under addition: if they didn’t, they wouldn’t grow under multiplication either, and that would contradict the sum-product theorem.

We then let g and h vary within a large set S of simultaneously diagonalisable matrices in A, fix some a in A but not in S, and observe that tr(a g a^{-1} h) is basically the sum of tr(g h) and tr(g h^{-1}) – or, rather, a linear combination of tr(g h) and tr(g h^{-1}) with coefficients that are constant for a fixed. Using the fact that the set of traces has to grow under addition (for the reasons we saw before), we can show that the set of traces has to grow under this linear combination as well. Hence tr(A A A^{-1} A) must be considerably larger than tr(A).

Thus, either A A A^{-1} A is considerably larger than A, or tr(A A A^{-1} A) is considerably larger than |A A A^{-1} A|^{1/3}; in the latter case, A A A^{-1} A violates one of the properties of slowly-growing sets we mentioned before, and so A A A^{-1} A times itself 10 times (say) is considerably larger than A A A^{-1} A (and, hence, considerably larger than A).

In either case, (A \cup A^{-1}) times itself 100 times (say) turns out to be considerably larger than A – say, larger than |A|^{1 + \Delta},\ \Delta>0. Then, by means of a standard result in additive combinatorics that is also true for non-abelian groups (the Ruzsa distance inequality), one conclude that A times itself just twice (that is, A \cdot A\cdot A) has to be quite a bit larger than A – say, larger than |A|^{1+\Delta/100},\  \Delta>0. We reach a contradiction, and are done.

* * *

Let us go ahead and talk about expanders. Here we are speaking of a somewhat different kind of growth. Let me skip some definitions and say the following: given a set of pairs (G_j,A_j), where A_j is a set of generators of the finite group G_j, we say \{(G_j,A_j)\} form a family of expanders if the following is true:

For every j and every subset B_j of G_j with |B_j|\leq  (1/2) |G_j|, we have

|A_j\cdot B_j \cup B_j| \geq (1 + \epsilon) |B_j|,

where \epsilon does not depend on j.

The above property is often stated in terms of the Cayley graph of (G_j,A_j). The Cayley graph \Gamma(G,A) of a pair (G,A), where A is a set of generators of G, is simply the graph having the set of vertices G and the set of edges \{(g,ag):\ g \in G, a \in A\}. (From now on we assume A_j to be symmetric, i.e., if A_j contains an element x, it also contains its inverse x^{-1}; thus, this is an undirected graph.)

The girth of a graph is the length of its shortest non-trivial loop. It is easy to see that, if G_p = SL_n({\Bbb Z}/p{\Bbb Z}) (say) and A_p is the reduction modulo p of a subset A of SL_n({\Bbb Z}), then the girth of \Gamma(G_p,A_p) is relatively large – namely, larger than c \log p, where c is a constant not depending on A.

Theorem (Bourgain-Gamburd). Let P be an infinite set of primes. For every p \in P, let G_p = SL_2({\Bbb Z}/p{\Bbb Z}) and let A_p be a set of generators of G_p. Suppose that the girth of \Gamma(G_p,A_p) is > c \log p, where c >0 is a constant. Then \{(G_p, A_p)\}_{p\in P} is an expander family.

Bourgain and Gamburd derive this theorem from the result of mine I mentioned before. They proceed in two steps.

First, they translate my result on sets into a result on measures. (Starting from a result stating that a set A must grow under multiplication by itself, they get a result stating that a measure \mu must go down in l_2 norm under convolution by itself.) This is by now almost a routine procedure, at least in the sense that it can be found in previous papers by Bourgain; the main idea is to use the Balog-Szemeredi-Gowers theorem from additive combinatorics. (The Balog-Szemeredi-Gowers theorem states, essentially, that if A is a set such that a large number of the sums x+y,\  x,y \in A, fall within a small set (due to many repetitions), then A has a large subset A' such that A'+A' is small.) Since SL_2 is a non-abelian group, we need a non-abelian result. Tao had pointed out shortly before that the Balog-Szemeredi-Gowers theorem is valid in the non-abelian case.

Second, they have to go from the result on measures to a proof of a so-called spectral gap, i.e., a proof of the fact that the largest and second largest eigenvalues of the spectrum of the adjacency matrix of the Cayley graph (considered as a linear operator) are separated by a gap \epsilon >0. (This has long been known to be equivalent to the expander property; indeed, it is often used as its definition.) If one does this in the easiest way, one gets a result that is too weak, namely, a gap of 1/(\log p), whereas we want a gap \epsilon >0, where epsilon is independent of p. Bourgain and Gamburd remove this factor of \log p by means of a technique due to Sarnak: the idea is to use the high multiplicity of the second largest eigenvalue (a consequence of the fact that G=SL_2({\Bbb Z}/p{\Bbb Z}) has no complex representations of small (i.e., o(p)) dimension) to amplify the effect that too small a gap would have on the speed at which convolutions in G make measures go down in l_2 norm. (The effect is to slow down this speed; a spectral gap of less than a constant, amplified by high multiplicity, would cause the speed to be slow enough to contradict the result on measures they proved using my result on sets.)

In all of this, the sum-product theorem is not used directly; the only “additive-combinatorial” tool used is the Balog-Szemeredi-Gowers theorem.

* * *

Bourgain and Gamburd also proved an expansion property valid for many subsets A of the complex group SU(2). (Here it is certainly best to define the expander property in terms of the spectral gap.) The plan of proof is essentially the same as above. There is one difference, however: in SU(2), a result on the growth of finite sets A is not enough to prove a result on how measures go down in l_2 norm when they are convolved by themselves. One must show that, when a finite subset A of SU(2) is multiplied by itself (twice, to get A \cdot A\cdot A),

(a) the number of elements of A grows (as it does in SL(2)),

and, moreover,

(b) the elements of A do not get clumped together too much by multiplication.

What must one do, then? Bourgain and Gamburd essentially had to redo my proof for SL_2(F_p) in the case of SU(2), replicating the same steps (SU(2) is a lot like SL_2(F_p), as you can see when you go down to the level of Lie algebras) while keeping track of (b). For the most part, they just have to be careful that the maps that get used in the proof do not make the points, well, clump.

However, there is one key difference: the result that lies at the basis of this all cannot be just the statement of the sum-product theorem with {\Bbb C} (or {\Bbb R}) instead of F_p. Rather, they need a result on sum and products in {\Bbb C} (or {\Bbb R}) that keeps track of distances. Such a result was proven by Bourgain shortly before he proved the sum-product theorem over F_p with Katz and Tao; it is part of his proof of the ring discretisation conjecture. (This conjecture was proven independently shortly before Bourgain by Edgar and Miller.)

Indeed, if I understand correctly, Bourgain arrived at the problem over F_p via the problem on ring discretisation, whereas Katz and Tao got to it via their work on the Kakeya problem.

* * *

Bourgain, Gamburd and Sarnak have been proving results on non-commutative sieving (“the affine sieve”) using the results on expansion above. Basically, when you look at classical sieve theory, you are looking at sieves involving the action of {\Bbb Z} on itself by addition; the sieve procedures in {\Bbb Z} use the crucial fact that, as you keep adding 1 to an integer, you go through each congruence class modulo p equally often. (We don’t usually think of this fact simply because it’s obvious.) It turns out – I understand this is an idea that Sarnak was exploring some time ago – that one can do sieving more generally, with the action of a group on a space as the subject of the sieve. This actually has interesting applications. The equidistribution statement modulo p one needs is a consequence of the expansion property for SL_2({\Bbb Z}/p{\Bbb Z}) that Bourgain and Gamburd proved.

Sarnak has written a beautiful exposition of this, and this post is already very long, so I won’t go further into this.

* * *

Where does one go from here? An obvious answer is to try other groups. After spending a couple of years trying, I recently proved growth in SL_3({\Bbb Z}/p{\Bbb Z}). Bourgain and Gamburd have since announced that they can prove results on measures using this result. (There is a non-obvious technicality that appears in the transition from sets to measures for n>2.)

In the process, it is inevitable to think harder about sums and products. Here is some hand-waving.

  • When one works on SL_3 – or on any group other than SU_2 or, say, SO_3 – one no longer has a magical identity such as tr(g) tr(h) = tr(g h) + tr(g h^{-1}) at hand to beckon the sum-product theorem. The form of the beckoning becomes different, and what is beckoned has to be different. The sum-product theorem gets used in the guise of a result on linearity: using the sum-product theorem, one can show that there cannot be a set S of tuples in F_p and a large set of linear relations such that each relation is satisfied by very many of the tuples in S.
  • The sum-product theorem isn’t really about sums, about products or about fields. Rather, it is about a group acting by automorphisms on another group, preferably without fixed points. (It currently seems that the group doing the acting has to be abelian, but that may just be an artifact of the proof.) In the case of a finite field, what we have is that the multiplicative group of the field acts on the additive group of the field; this action is an action by automorphisms because a (b + c) = a b + a c, and it is an action without (non-trivial) fixed points because ab = b implies either a = 1 or b = 0. This sort of generalisation turns out to be rather useful when one looks at growth in solvable subgroups of SL_3, as one indeed must in the course of the proof.
  • The sum-product theorem, and much else in basic additive combinatorics, can be stated and proven in terms of projective geometry. This may seem to be a tautology – but one can do a great deal of these restatements and proofs with great naturality, and a minimum of axioms. (For example, for the Ruzsa distance inequality, one just needs Desargues, or even just little Desargues, if one is looking only at the additive Ruzsa distance.) It has probably been felt by many people that the great advantage when one has to prove results over {\Bbb R} (such as Erdos-Szemeredi) rather than over F_p is that one can use the geometry of the Euclidean plane. It may be possible to advance further over F_p (or finite fields, or fields in general) by thinking geometrically – in terms of the geometry of an abstract projective plane, rather than the geometry of the Euclidean plane. (This is joint work with M. Rudnev and N. Gill; we already have a few statements that don’t have exact analogues in “classical”, non-projective, additive combinatorics.)


Filed under guest blogging, mathematics: research

2 responses to “Growth, expanders, and the sum-product problem

  1. Nice post!

    Regarding the prehistory of my paper with Jean Bourgain and Nets Katz, it all started with a question of Tom Wolff back in 2000, shortly before his unfortunate death. Tom had formulated the finite field version of the Kakeya conjecture (now solved by Dvir), and had observed that there appeared to be a connection between that conjecture (at least in the 3D case) and what is now the sum-product theorem. (Roughly speaking, if the sum-product phenomenon failed, then one could construct “Heisenberg group-like” examples that almost behaved like Kakeya sets.) So he posed the question to me (as a private communication) as to whether the sum-product phenomenon was true. Nets and I chewed on this problem for a while, and found connections to some other problems (the Falconer distance problem, and the Szemeredi-Trotter theorem, over finite fields), but couldn’t settle things one way or another. We then turned to Euclidean analogues, and formulated the discretised ring conjecture and showed that this was equivalent to a non-trivial improvement on the Falconer distance conjecture and on a conjecture of Wolff relating to some sets studied by Furstenberg.

    After chasing some dead ends on both the finite field sum-product problem and the discretised ring problem, we gave both problems to Jean, noting that the sum-product problem would likely have applications to various finite field incidence geometry questions, including Kakeya in F_p^3. Jean managed to solve the discretised ring problem using some multiscale methods, as well as some advanced Freiman theorem type technology based on earlier work of Jean and Mei-Chu Chang. About the same time, as you note, Edgar and Miller solved the qualitative version of the discretised ring problem (i.e. the Erdos ring conjecture).

    This left the finite field sum-product problem. All the methods in our collective toolboxes were insensitive to the presence of subfields (except perhaps for Freiman’s theorem, but the bounds were (and still are) too weak to get the polynomial expansion; the multiscale amplification trick that worked in the discretised ring conjecture was unavailable here) and so were insufficient to solve the problem. We knew that it would suffice to show that some polynomial combination of A with itself exhibited expansion, but we were all stuck on how to do this for about a year, until Jean realised that the Edgar-Miller argument (based on the linear algebra dichotomy between having a maximally large span, and having a collision between generators) could be adapted for this purpose. (I still remember vividly the two-page fax from Jean conveying this point.) After this breakthrough the paper got finished up quite rapidly. Of course nowadays there are many simple proofs and strengthenings of this theorem, but it was certainly a very psychologically imposing problem for us before we found the solution.

    On an unrelated point, in order to work on guest blog posts out of view of the public, one trick I use is to create a subpage of the “About” page (by creating a new page and then setting “About” as its parent). This subpage is then not visible from the blog (unless, of course, you link to it), but can be accessed by its URL. [The search feature on the blog can pick the page up if one guesses some key words on it, but one can of course password-protect the page to prevent this.]

  2. Pingback: Extermal Combinatorics II: Some Geometry and Number Theory « Combinatorics and more