Problem #52: Let $A$ be a finite set of integers

---

Progress

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{1270}{951}-o(1)}\]due to Bloom [Bl25] (note $1270/951=1.33543\cdots$). A complete history of sum-product bounds can be found at this webpage.

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 Bloom above. The best bound for complex numbers is\[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{4}{3}+c}\]for some absolute constant $c>0$, due to Basit and Lund [BaLu19].


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 there exists $c>0$ such that if $A\subseteq \mathbb{F}_p$ with $\lvert A\rvert <p^{c}$ then\[\max( \lvert A+A\rvert,\lvert AA\rvert)\gg\lvert A\rvert^{\frac{5}{4}+o(1)},\]due to Mohammadi and Stevens [MoSt23].

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.