Logo
All Random Solved Random Open
OPEN - $250
Let $A$ be a finite set of integers. Is it true that for every $\epsilon>0$ \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg_\epsilon \lvert A\rvert^{2-\epsilon}?\]
The sum-product problem. Erdős and Szemerédi [ErSz83] proved a lower bound of $\lvert A\rvert^{1+c}$ for some constant $c>0$, and an upper bound of \[\lvert A\rvert^2 \exp\left(-c\frac{\log\lvert A\rvert}{\log\log \lvert A\rvert}\right)\] for some constant $c>0$. The lower bound has been improved a number of times. The current record is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{1558}{1167}-o(1)}\] due to Rudnev and Stevens [RuSt22] (note $1558/1167=1.33504\cdots$).

There is likely nothing special about the integers in this question, and indeed Erdős and Szemerédi also ask a similar question about finite sets of real or complex numbers. The current best bound for sets of reals is the same bound of Rudnev and Stevens above. The best bound for complex numbers is \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}},\] due to Solymosi [So05].

One can in general ask this question in any setting where addition and multiplication are defined (once one avoids any trivial obstructions such as zero divisors or finite subfields). For example, it makes sense for subsets of finite fields. The current record is that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{5/8}$ then \[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{11}{9}+o(1)},\] due to Rudnev, Shakan, and Shkredov [RSS20].

There is also a natural generalisation to higher-fold sum and product sets. For example, in [ErSz83] (and in [Er91]) Erdős and Szemerédi also conjecture that for any $m\geq 2$ and finite set of integers $A$ \[\max( \lvert mA\rvert,\lvert A^m\rvert)\gg \lvert A\rvert^{m-o(1)}.\] See [53] for more on this generalisation and [808] for a stronger form of the original conjecture. See also [818] for a special case.

Additional thanks to: Akshat Mudgal