Category Archives: guest blogging

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.

Continue reading


Filed under guest blogging, mathematics: research