A history of the sum-product problem

We will not attempt to describe any of the ideas that go into proving these bounds, which are varied and often extremely clever and elegant. The reader is encouraged to read the papers cited for further details. (There is also a general survey written in 2016 by Granville and Solymosi \cite{GrSo16} which discusses many of the ideas). Our goal is to provide a helpful roadmap, to help the curious understand exactly what is known and how we got there.

There are many sum-product type problems that we have not even mentioned below, and this survey does not attempt to be complete in that sense, although we have tried to cover the full history of those problems we do consider.

Classic sum-product exponent

The classic sum-product problem considers the two most natural measures of additive and multiplicative structure: the sumset $A+A=\{a+b : a,b\in A\}$ and the product set $\{ab : a,b\in A\}$, and asks whether at least one must be significantly larger than $A$ itself. More precisely, given some suitable ambient ring $R$, one can ask for an exponent $c>0$ such that, for all finite $A\subset R$, \[\max(\lvert A+A\rvert, \lvert AA\rvert) \geq \lvert A\rvert^{1+c-o(1)}\] (where the $o(1)$ term $\to 0$ as $\lvert A\rvert\to \infty$). This was first considered when $R=\mathbb{Z}$ by Erdős and Szemerédi \cite{ErSz83}, but many other cases have been considered since.

If $c(R)$ is the exponent for finite subsets of $R$ then it is trivial that if $R_1\subseteq R_2$ we have $c(R_1)\geq c(R_2)$. The following table gives the history of the known exponents for various rings. We note that the proofs of \cite{ErSz83}, \cite{Na97}, and \cite{Ch99} in fact work for subsets of $\mathbb{R}$, although they were only considering sets of integers. It seems that Ford \cite{Fo98} was the first to observe this.

It is trivial that $c(\mathbb{Z})=c(\mathbb{Q})$, and furthermore $c(\mathbb{R})=c(\mathbb{A})$, where $\mathbb{A}$ is the ring of algebraic numbers. It is not known whether $c(\mathbb{Z})=c(\mathbb{R})$ (although the conjectured truth is that both are $1$).

Most of the results in the literature are for the sum set and product set. Occasionally results are obtained also for the difference sets and ratio set, and various combinations of these operators. We do not mention these in the survey below, unless otherwise noted.

$\mathbb{Z}$
Erdős and Szemerédi 1983 \cite{ErSz83} non-explicit $c>0$
Nathanson 1997 \cite{Na97} $\frac{1}{31}$
Chen 1999 \cite{Ch99} $\frac{1}{5}$
$\mathbb{R}$
Ford 1998 \cite{Fo98} $\frac{1}{15}$
Elekes 1997 \cite{El97} $\frac{1}{4}$
Solymosi 2005 \cite{So05} $\frac{3}{11}\approx 0.2727$
Solymosi 2009 \cite{So09} $\frac{1}{3}$
Konyagin and Shkredov 2015 \cite{KoSh15} $\frac{2289}{6866}\approx 0.33338$
Konyagin and Shkredov 2016 \cite{KoSh16} $\frac{1092}{3271}\approx 0.3338$
Shakan 2019 \cite{Sh19} $\frac{588}{1759}\approx 0.33428$
Rudnev and Stevens 2022 \cite{RuSt22} $\frac{1558}{1167}\approx 0.33504$
Bloom 2025 \cite{Bl25} $\frac{1270}{951}\approx 0.33543$
$\mathbb{C}$
Chang 2005 \cite{Ch05} $\frac{1}{54}$
Solymosi 2005 \cite{So05b} $\frac{1}{4}$
Konyagin and Rudnev 2013 \cite{KoRu13} $\frac{1}{3}$
Basit and Lund 2019 \cite{BaLu19} $\frac{1}{3}+c$ for non-explicit $c>0$
$\mathbb{K}$ (Quaternions)
Chang 2005 \cite{Ch05} $\frac{1}{54}$
Solymosi 2005 \cite{So05b} $\frac{1}{4}$
Solymosi and Wong 2018 \cite{SoWo18} $\frac{1}{3}$
Basit and Lund 2019 \cite{BaLu19} $\frac{1}{3}+c$ for non-explicit $c>0$
$\mathbb{F}_p$ (assuming $\lvert A\rvert\leq p^{c'}$)
Bourgain, Katz, and Tao 2004 \cite{BKT04} non-explicit $c>0$
Garaev 2007 \cite{Ga07} $\frac{1}{14}$
Katz and Shen 2008 \cite{KaSh08} $\frac{1}{13}$
Bourgain and Garaev 2009 \cite{BoGa09} $\frac{1}{12}$ (only for $-\div$)
Li 2011 \cite{Li11} $\frac{1}{12}$
Rudnev 2012 \cite{Ru12} $\frac{1}{11}$
Roche-Newton, Rudnev, and Shkredov \cite{RRS16} $\frac{1}{5}$
Stevens and de Zeeuw 2017 \cite{StdZ17} $\frac{1}{5}$
Shakan and Shkredov 2018 \cite{ShSh18} $\frac{13}{61}\approx 0.213$
Chen, Kerr, and Mohammadi 2019 \cite{CKM19} $\frac{7}{32}\approx 0.218$
Rudnev, Shakan, and Shkredov 2020 \cite{RSS20} $\frac{2}{9}\approx 0.222$
Mohammadi and Stevens 2023 \cite{MoSt23} $\frac{1}{4}$
$\mathbb{F}_q$
Katz and Shen 2008 \cite{KaSh08b} $\frac{1}{19}$
Shen 2011 \cite{Sh11} $\frac{1}{16}$
Roche-Newton 2011 \cite{Ro11} $\frac{1}{14}$
Li and Roche-Newton 2011 \cite{LiRo11} $\frac{1}{11}$
$\mathbb{F}_p[t]$
Bloom and Jones 2014 \cite{BlJo14} $\frac{1}{5}$
$\mathbb{Q}_p$
Bloom and Jones 2014 \cite{BlJo14} $\frac{1}{5}$
$\mathbb{C}[x]$
Croot and Hart 2010 \cite{CrHa10} non-explicit $c>0$
$\mathbb{R}^d$ (with pointwise operations)
Mudgal 2020 \cite{Mu20} $\frac{c(\mathbb{R})}{d}$
symmetric $d\times d$ matrices over $\mathbb{R}$
Chang 2007 \cite{Ch07} non-explicit $c_d>0$ depending on $d$
$d\times d$ matrices over $\mathbb{C}$ assuming the matrices are 'well-conditioned'
Solymosi and Vu 2009 \cite{SoVu09} $\frac{1}{4}$
The results for $\mathbb{F}_p$ have the additional assumption that $\lvert A\rvert$ is not too large, namely $\lvert A\rvert\leq p^{c'}$ for some (usually explicit and not too small) $c'>0$. Some condition of this kind is necessary, since Garaev \cite{Ga08} has shown that, for any $N\leq p$, there exists $A\subseteq \mathbb{F}_p$ of size $\lvert A\rvert=N$ such that \[\max(\lvert A+A\rvert, \lvert AA\rvert) \ll p^{1/2}N^{1/2}.\]

The results for $\mathbb{F}_q$ also have some assumption which ensures $A$ is not 'too close' to any subfield. Some of the results listed above for $\mathbb{F}_p$ are also valid for $\mathbb{F}_q$, but have the condition that $\lvert A\rvert\leq p^{c'}$ where $p$ is the characteristic of $\mathbb{F}_q$, and hence we view those as morally results only over $\mathbb{F}_p$ (in particular they are not useful when $q$ is a large power of some fixed small prime $p$).

Furthermore, it does not quite fit into the paradigm of the table below, but Tao \cite{Ta09} has proved a general qualitative sum-product result for arbitrary rings, although care has to be taken to avoid zero divisors and subrings, so the results are quite technical.

For sets of integers Erdős and Szemerédi \cite{ErSz83} proved an upper bound: there exists some constant $c>0$ such that, for all large $N$, there is a finite set of integers of size $N$ such that \[\max(\lvert A+A\rvert,\lvert AA\rvert)\leq \lvert A\rvert^{2-\frac{c}{\log\log \lvert A\rvert}}.\]

Expanders

An alternative type of sum-product result is to study the expansion properties of a single function - that is, we fix some $f:R^d\to R$ and ask for a lower bound of the shape \[\lvert f(A,\ldots,A)\rvert =\lvert\{ f(a_1,\ldots,a_d) : a_i\in A\}\rvert\gg \lvert A\rvert^{1+c-o(1)}\] for some constant $c>0$ and for an arbitrary finite $A\subset R$. (In particular since the left-hand side is larger than $\lvert A\rvert$ we say that $f$ is an expander.) Generally, of course, such an $f$ will be constructed using both addition and multiplication (or some kind of convex function).

In the table below we give a history of the best exponents known for various expanders in various rings. We only record symmetric estimates; many of the papers below prove more general asymmetric versions of their results (i.e. giving lower bounds for $\lvert f(A_1,\ldots,A_d)\rvert$ where the $A_i$ may be distinct sets).

The rows have been ordered first by number of variables in the expander, and within that by the current best known exponent (with ties broken arbitrarily). An exponent has been highlighted in green if it is the best possible exponent for that expander (usually shown by the example $A=\{1,\ldots,n\}$).

As is convention, where all the variables appear only once in $f$ we use the set notation (for example write $AA+AA$ for the expander $(a,b,c,d)\mapsto ab+cd$). The notation $A^2$ means $\{ a^2 : a\in A\}$.

$\mathbb{Z}$
3 variables
$AA+A$ Shakan 2014 \cite{Sh14} $1$
$\mathbb{R}$
2 variables
$A(A+1)$ Garaev and Shen 2010 \cite{GaSh10} $\frac{1}{4}$
Jones and Roche-Newton 2013 \cite{JoRo13} $\frac{5}{19}\approx 0.263$
Stevens and Warren 2022 \cite{StWa22} $\frac{11}{38}\approx 0.289$
$A+f(A)$ for convex $f$ Li and Roche-Newton 2012 \cite{LiRo12} $\frac{5}{19}\approx 0.263$
Stevens and Warren 2022 \cite{StWa22} $\frac{11}{38}\approx 0.289$
3 variables
$\frac{a-b}{a-c}$ Jones 2013 \cite{Jo13} $1$
$f(a+A)+f(a'+A)-f(a+A)$ for convex $f$ and some $a,a'\in A$ Hanson, Roche-Newton, and Senger 2023 \cite{HRS23} $1$
$\frac{a(b-c)}{c(a-b)}$ Jones 2015 \cite{Jo15} $1$
$\frac{A}{A}+A$ Balog 2011 \cite{Ba11} $\frac{1}{2}$
Shkredov 2016 \cite{Sh16} $\frac{21}{41}\approx 0.512$
Roche-Newton 2018 \cite{Ro18} $\frac{7}{13}\approx 0.538$
$A(A-A)$ Folkore via the Szemerédi-Trotter incidence theorem $\frac{1}{2}$
Murphy, Roche-Newton, and Shkredov 2015 \cite{MRS15} $\frac{57}{112}\approx 0.508$
Murphy, Roche-Newton, and Shkredov 2017 \cite{MRS17} $\frac{9}{17}\approx 0.52941$
Bloom 2025 \cite{Bl25} $\frac{2506}{4733}\approx 0.52947$
$A(A+A)$ Murphy, Roche-Newton, and Shkredov 2015 \cite{MRS15} $\frac{45}{89}\approx 0.505$
Murphy, Roche-Newton, and Shkredov 2017 \cite{MRS17} $\frac{63}{121}\approx 0.520$
Bloom 2025 \cite{Bl25} $\frac{11}{21}\approx 0.523$
$AA+A$ A folklore application of the Szemeredi-Trotter theorem; also Balog 2011 \cite{Ba11} $\frac{1}{2}$
Roche-Newton, Ruzsa, Shen, and Shkredov 2019 \cite{RRSS19} $\frac{1}{2}+c$ for $c=2^{-222}$
Roche-Newton and Warren 2021 \cite{RoWa21} $\frac{49}{97}\approx 0.505$
Stevens and Warren 2022 \cite{StWa22} $\frac{44}{85}\approx 0.517$
4 variables
$\frac{(a-b)(c-d)}{(b-c)(a-d)}$ Solymosi and Tardos 2007 \cite{SoTa07} $1$
Jones 2015 \cite{Jo15} $1$
Rudnev 2017 \cite{Ru17} $\frac{13}{11}\approx 1.18$
$\frac{ab-cd}{b-c}$ Roche-Newton and Warren 2021 \cite{RoWa21} $\frac{15}{14}\approx 1.071$
$\frac{a(b-c)}{c-d}$ Shkredov 2019 \cite{Sh19} $1+c$ where $c=\frac{1}{5}2^{-19}$
$\frac{A-A}{A-A}$ Ungar 1982 \cite{Un82} $1$
$(A-A)^2+(A-A)^2$ Moser 1952 \cite{Mo52} $\frac{1}{3}$
Chung 1984 \cite{Ch84} $\frac{3}{7}\approx 0.428$
Beck 1983 \cite{Be83} $\frac{35}{81}\approx 0.432$
Chung, Szemerédi, and Trotter 1992 \cite{CST92} $\frac{3}{5}=0.6$
Szekely 1997 \cite{Sz97} $\frac{3}{5}=0.6$
Solymosi and Toth 2001 \cite{SoTo01} $\frac{5}{7}\approx 0.714$
Tardos 2003 \cite{Ta03} $\frac{3e+1}{5e-1}\approx 0.727$
Katz and Tardos 2004 \cite{KaTa04} $\frac{41-12e}{55-16e}\approx 0.728$
Guth and Katz 2015 \cite{GuKa15} $1$
$(A+A)(A+A)$ Roche-Newton and Rudnev 2015 \cite{RoRu15} $1$
$\frac{A+A}{A+A}$ Balog and Roche-Newton 2015 \cite{BaRo15} $1$
$\frac{g(a,b)-g(c,d)}{b-d}$ for any polynomial $g(x,y)$ that depends on $x$ Makhul 2019 \cite{Ma19} $1$
$AA+ AA$ Iosevich, Roche-Newton, and Rudnev 2018 \cite{IRR18} $\frac{7}{12}\approx 0.583$
Rudnev and Stevens 2022 \cite{RuSt22} $\frac{47}{80}\approx 0.587$
$AA- AA$ Iosevich, Roche-Newton, and Rudnev 2018 \cite{IRR18} $\frac{17}{32}\approx 0.531$
5+ variables
$A(A+A+A+A)$ Murphy, Roche-Newton, and Shkredov 2015 \cite{MRS15} $1$
$(A+A+A+A)^2+\log A$ Murphy, Roche-Newton, and Shkredov 2017 \cite{MRS17} $1$
$(AA+1)(AA+1)(AA+1)$ Hanson, Roche-Newton, and Senger 2023 \cite{HRS23} $\frac{33}{32}$
$(A+A)(A+A)(A+A)$ Roche-Newton and Shkredov 2019 \cite{RoSh19} $\frac{393}{392}$
Hanson, Roche-Newton, and Senger 2023 \cite{HRS23} $\frac{33}{32}$
$(A-A)(A-A)(A-A)$ Balog, Roche-Newton, and Zhelezov 2017 \cite{BRZ17} $\frac{9}{8}\approx 1.125$
$\frac{AA+A}{AA+A}$ Balog, Roche-Newton, and Zhelezov 2017 \cite{BRZ17} $\frac{9}{8}\approx 1.125$
$\frac{AA+AA}{A+A}$ Balog, Roche-Newton, and Zhelezov 2017 \cite{BRZ17} $\frac{9}{8}\approx 1.125$
$\frac{A+A}{A+A}+\frac{A}{A}$ Balog, Roche-Newton, and Zhelezov 2017 \cite{BRZ17} $\frac{19}{17}\approx 1.117$
$AA+AA-AA$ An observation of Garaev (see also \cite{HRS23}) $1$
$2(a+A)^3+2(a'+A)^3-2(a+A)^3-(a'+A)^3$ for some $a,a'\in A$ Hanson, Roche-Newton, and Senger 2023 \cite{HRS23} $\frac{3}{2}$
$\frac{(aA+1)(aA+1)(a'A+1)(a'A+1)}{(aA+1)(aA+1)(a'A+1)(a'A+1)}$ for some $a,a'\in A$ Hanson, Roche-Newton, and Senger 2023 \cite{HRS23} $\frac{3}{2}$
$AA+AA+AA+AA$ Balog 2011 \cite{Ba11} $1$
$\mathbb{C}$
4 variables
$\lvert a-b\rvert^2+\lvert c-d\rvert^2$ Sheffer and Zahl 2021 \cite{ShZa21} $1$
$\mathbb{F}_p$ (assuming $\lvert A\rvert\leq p^{c'}$)
2 variables
$A(A+1)$ Bourgain 2005 \cite{Bo05} non-explicit $c>0$
Garaev and Shen 2010 \cite{GaSh10} $\frac{1}{105}\approx 0.009$
Jones and Roche-Newton 2013 \cite{JoRo13} $\frac{1}{56}\approx 0.017$
Stevens and de Zeeuw 2017 \cite{StdZ17} $\frac{1}{5}=0.2$
Warren 2019 \cite{Wa19} $\frac{2}{9}\approx 0.222$
$A+A^2$ Hart, Li, and Shen \cite{HLS13} $\frac{1}{146}\approx 0.006$
$\frac{A+1}{A}$ Hart, Li, and Shen \cite{HLS13} $\frac{1}{109}\approx 0.009$
$a(a+b)$ Bourgain 2005 \cite{Bo05} non-explicit $c>0$
3 variables
$AA+A$ Glibichuk and Konyagin 2007 \cite{GlKo07} $\frac{1}{6}$
Roche-Newton, Rudnev, and Shkredov 2016 \cite{RRS16} $\frac{1}{2}$
$A(A\pm A)$ Roche-Newton, Rudnev, and Shkredov 2016 \cite{RRS16} $\frac{1}{3}$
5+ variables
$A\pm AA\pm AA$ Roche-Newton, Rudnev, and Shkredov 2016 \cite{RRS16} $\frac{3}{4}$
$(A-A)(A-A)(A-A)+(A-A)(A-A)(A-A)$ Koh, Nassajian Mojarrad, Pham, and Valculescu \cite{KNPV18} $\frac{1}{7}$
$\mathbb{F}_q$
$A(A+1)$ Zhelezov 2015 \cite{Zh15} $\frac{1}{559}$
Mohammadi 2020 \cite{Mo20} $\frac{1}{52}$
(We remark that the stated result of Solymosi and Vu \cite{SoVu08} for $(a-b)^2+(c-d)^2+(e-f)^2$ is weaker than given here, but their result uses as a black box the exponent for the distinct distance problem, and so here we have recorded a stronger exponent which follows immediately from their Theorem 1.2 and the result of Guth and Katz \cite{GuKa15}.)

References