Home » Subject » Number Theory

Sum-product problem

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

For every $ A \subseteq {\mathbb R} $ we let $ A + A = \{ a+b : a,b \in A\} $ and $ A \cdot A = \{ ab : a,b \in A \} $.

Conjecture   For every $ \epsilon > 0 $, every sufficiently large finite set $ A \subseteq {\mathbb R} $ satisfies \[ \max \{ |A \cdot A|, |A + A| \} \ge |A|^{2 - \epsilon} \]

This famous conjecture asserts that every set of numbers $ A $ must have either a large sumset ($ A+A $) or a large product set ($ A \cdot A $). 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 $ A \subseteq {\mathbb R} $ satisfies $ |A+A| \geq 2|A| - 1 $ (use the order on $ {\mathbb R} $). Furthermore, the sets $ A $ 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 $ c $, every set $ A $ with $ |A + A| < c|A| $ 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 $ |A \cdot A| $ we should choose $ A $ to be a geometric progression, and there is a similar structure theorem for when $ |A \cdot A| < c |A| $ which would imply, in particular, that such sets have $ A + A $ very large. So, in short, when either $ A+A $ or $ A \cdot A $ is very small, we have structure theorems which prove that the other is very large. Unfortunately, we have only rather weak information about sets $ A $ when both $ A+A $ and $ A \cdot A $ are somewhat larger.

Erdos and Szemeredi were the first to prove that there exists $ \delta > 0 $ so that $ \max \{ |A+A|, |A \cdot A| \} \ge |A|^{1 + \delta} $ for all sufficiently large sets $ A $. This parameter $ \delta $ has been steadily improved by a number of authors. One highlight in this sequence is a proof by Elekes that $ \delta $ may be taken arbitrarily close to $ \frac{1}{4} $. 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 $ \delta $ may be taken arbitrarily close to $ \frac{1}{3} $. 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.
add new comment