# Sum-product problem

 Importance: High ✭✭✭
 Author(s): Erdos, Paul Szemeredi, Endre
 Subject: Number Theory
 Keywords: product set sumset
 Posted by: mdevos on: August 8th, 2008

For every we let and .

Conjecture   For every , every sufficiently large finite set satisfies

This famous conjecture asserts that every set of numbers must have either a large sumset () or a large product set (). It is central to our understanding of the interplay between the additive and multiplicative properties of a set of numbers. Although this problem was originally posed just for subsets of integers, it is generally believed to hold true more generally for the reals.

It is relatively easy to show that every set satisfies (use the order on ). Furthermore, the sets which meet this lower bound are precisely the arithmetic progressions. A famous (and very useful) theorem of Freiman gives a rough generalization of this. He proves that for every fixed constant , every set with is efficiently contained in a generalized arithmetic progression. Arithmetic progressions, and more generally the type of sets which appear in Freiman's theorem have large product sets, so they would obey this conjecture. Similarly, to minimize we should choose to be a geometric progression, and there is a similar structure theorem for when which would imply, in particular, that such sets have very large. So, in short, when either or is very small, we have structure theorems which prove that the other is very large. Unfortunately, we have only rather weak information about sets when both and are somewhat larger.

Erdos and Szemeredi were the first to prove that there exists so that for all sufficiently large sets . This parameter has been steadily improved by a number of authors. One highlight in this sequence is a proof by Elekes that may be taken arbitrarily close to . His argument utilizes a clever application of the Szemeredi-Trotter theorem on point-line incidences and is described in detail on Terry Tao's blog. Very recently, Solymosi [S] found a simple and beautiful proof which shows that may be taken arbitrarily close to . An easily-digested simplification of his argument appears on Izabella Laba's blog.

## Bibliography

[S] J. Solymosi, An upper bound on the multiplicative energy.

* indicates original appearance(s) of problem.