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
Let us first look at the statements of the main results. In the following,
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
Now here is what I proved on
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
- both here and in the sum-product theorem, if the set
is too big (say, for some small ) then one gets done in a couple of steps. I proved something of the sort for , 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 this general result states (among other things):
be a subset of . Assume that . Then .
is just the dimension of the lowest-dimensional representation of G. (Well, perhaps the dimension is that minus 1/2.)
- the condition that
generates is natural in the following sense: if does not generate , then we are not dealing with a problem on growth in , but with a problem on the group generated by . As it happens, in the case of , the matter of subgroups is quite simple: a subgroup of 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
This non-growing set
As it turns out, one can prove the same thing about the number of conjugacy classes of
One then shows that, while
This basically forces the set of traces of
We then let
In either case, (
* * *
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
and every subset of with , we have
does not depend on .
The above property is often stated in terms of the Cayley graph of
The girth of a graph is the length of its shortest non-trivial loop. It is easy to see that, if
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
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
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) the number of elements of
(b) the elements of
What must one do, then? Bourgain and Gamburd essentially had to redo my proof for
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
Indeed, if I understand correctly, Bourgain arrived at the problem over
* * *
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
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
In the process, it is inevitable to think harder about sums and products. Here is some hand-waving.
- When one works on
– or on any group other than or, say, – one no longer has a magical identity such as 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 of tuples in and a large set of linear relations such that each relation is satisfied by very many of the tuples in .
- 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
, and it is an action without (non-trivial) fixed points because implies either or . This sort of generalisation turns out to be rather useful when one looks at growth in solvable subgroups of , 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
(such as Erdos-Szemeredi) rather than over is that one can use the geometry of the Euclidean plane. It may be possible to advance further over (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.)