The Accidental Mathematician

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 and on and Bourgain, Gamburd and Sarnak’s paper on the affine sieve. Since this connection was made through Harald’s paper on growth in (he has since proved a similar result in ), 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, means “the number of elements of a set “. Given a subset of a ring, we write for and for .

Sum-product theorem for (Bourgain, Katz, Tao, Konyagin). Let be a prime. Let be a subset of . Suppose that . Then either or , where depends only on .

In other words: a subset of 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 . Here means simply .

Theorem (H). Let be a prime. Let . Let be a subset of that generates . Suppose that . Then , where depends only on .

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

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 of generators of that does not grow: very small. We want to derive a contradiction.

This non-growing set turns out to have some funny properties. For example, it is not too hard to show (though it may be surprising at first) that 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 . (This makes some sense: a torus in is one-dimensional, whereas is 3-dimensional; hence dim(torus)/dim 1/3.)

As it turns out, one can prove the same thing about the number of conjugacy classes of occupied by elements of (or, rather, by elements of ( times itself 10 times, say)). The number of such conjugacy classes will have to be about .

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

This basically forces the set of traces of 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 and vary within a large set of simultaneously diagonalisable matrices in , fix some in but not in , and observe that is basically the sum of and – or, rather, a linear combination of and with coefficients that are constant for 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 must be considerably larger than .

Thus, either is considerably larger than , or is considerably larger than ; in the latter case, violates one of the properties of slowly-growing sets we mentioned before, and so times itself 10 times (say) is considerably larger than (and, hence, considerably larger than ).

In either case, () times itself 100 times (say) turns out to be considerably larger than – say, larger than . 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 times itself just twice (that is, ) has to be quite a bit larger than – say, larger than . 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 , where is a set of generators of the finite group , we say form a family of expanders if the following is true:

For every and every subset of with , we have

where does not depend on .

The above property is often stated in terms of the Cayley graph of . The Cayley graph of a pair , where is a set of generators of , is simply the graph having the set of vertices and the set of edges . (From now on we assume to be symmetric, i.e., if contains an element , it also contains its inverse ; 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 (say) and is the reduction modulo of a subset of , then the girth of is relatively large – namely, larger than , where is a constant not depending on .

Theorem (Bourgain-Gamburd). Let be an infinite set of primes. For every , let and let be a set of generators of . Suppose that the girth of is , where is a constant. Then 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 must grow under multiplication by itself, they get a result stating that a measure must go down in 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 is a set such that a large number of the sums , fall within a small set (due to many repetitions), then has a large subset such that is small.) Since 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 . (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 , whereas we want a gap , where epsilon is independent of . Bourgain and Gamburd remove this factor of 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 has no complex representations of small (i.e., ) dimension) to amplify the effect that too small a gap would have on the speed at which convolutions in make measures go down in 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 of the complex group . (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 , a result on the growth of finite sets is not enough to prove a result on how measures go down in norm when they are convolved by themselves. One must show that, when a finite subset of is multiplied by itself (twice, to get ),

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

and, moreover,

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

What must one do, then? Bourgain and Gamburd essentially had to redo my proof for in the case of , replicating the same steps ( is a lot like , 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 (or ) instead of . Rather, they need a result on sum and products in (or ) that keeps track of distances. Such a result was proven by Bourgain shortly before he proved the sum-product theorem over 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 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 on itself by addition; the sieve procedures in 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 one needs is a consequence of the expansion property for 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 . 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 .)

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