# Incidences and the Sum-Product Problem

This post is another piece of my project of listing the various applications of incidences bounds. For a couple of previous posts, see here and here. In this post, we consider the sum-product problem.

Given two sets of $n$ numbers $A,B$, we respectively denote their sumset and productset as

$A+B = \left\{ a+b \mid a\in A \text{ and } b\in B \right\},$
$AB = \left\{ ab \mid a\in A \text{ and } b\in B \right\}.$

It is not difficult to choose sets $A,B$ such that $|A+B|=\Theta(n)$ (e.g., $A=B=\{ 1,2,3,\ldots,n\}$), or such that $|AB|=\Theta(n)$ (e.g., $A=B=\{ 2,4,8,\ldots,2^n\}$). However, it can be shown that for any choice of $A,B$, either $A+B$ or $AB$ must be large. The original sum-product conjecture, by Erdős and Szemerédi, considers a slightly more restricted scenario.

Conjecture (Erdős and Szemerédi 83). For any $\varepsilon>0$ there exists $n_0$, such that any set $A$ of $n>n_0$ integers satisfies

$\max\{|A+A|,|AA|\} \ge n^{2-\varepsilon}.$

The best known lower bound for $\max\{|A+A|,|AA|\}$ was gradually improved in a series of papers (see here and here). In 1997, Elekes obtained a big breakthrough by applying a geometric approach for the problem.

Theorem 1 (Elekes 97). Let $A,B$ be two sets of $n$ real numbers. Then

$\max\{|A+B|,|AB|\} \ge n^{5/4}.$

Proof.     Consider the planar point set

${\cal P} = \{ (c,d) \mid c\in A+B \quad \text{ and } \quad d\in AB \}.$

Notice that $|{\cal P}| = |A+B|\cdot|AB|$. We also consider the planar set of lines

${\cal L} = \{ Z\left(y-a(x-a')\right) \mid a,a'\in A \}$

(where by $Z(y-a(x-a'))$ we refer to the zero set of the polynomial $y-a(x-a')$). Notice that $|{\cal L}| = n^2$. Moreover, a line that is defined by the equation $y-a(x-a')$ (where $a,a'\in A$) contains the points of $\cal P$ of the form $(a'+b,ab)$ for every $b\in B$. That is, every line of $\cal L$ is incident to $n$ points of $\cal P$. Therefore, the number of incidences in ${\cal P}\times{\cal L}$ is

$I({\cal P},{\cal L}) = |{\cal L}|n = n^3. \qquad \qquad (1)$

On the other hand, by applying the Szemerédi–Trotter theorem, we obtain

$I({\cal P},{\cal L}) = O\left(|{\cal P}|^{2/3}|{\cal L}|^{2/3} + |{\cal P}| + |{\cal L}|\right)$
$= O\left(|A+B|^{2/3}|AB|^{2/3}n^{4/3} + |A+B|\cdot|AB| + n^2\right). \quad (2)$

By combining $(1)$ and $(2)$, we obtain

$n^3 = O\left(|A+B|^{2/3}|AB|^{2/3}n^{4/3} + |A+B|\cdot|AB| + n^2\right),$

or,

$|A+B|\cdot|AB| = O\left(n^{5/2}\right),$

which immediately implies the assertion of the theorem.     $\Box$

Elekes’s proof was followed by various improvements and generalizations which also use geometric ideas. Currently, the best known bound for the sum-product problem, by Solymosi, is $\max\{|A+A|,|AA|\} \ge n^{4/3}/2\log^{1/3} n$. The proof of this bound is geometric, but does not rely on incidences. Unlike Elekes’s proof, this bound does not seem to extend to the case of $\max\{|A+B|,|AB|\}$. One example of an extension of Elekes’s ideas that does rely on incidenes is the following theorem by Elekes, Nathansona, and Ruzsa.

Theorem 2 (Elekes, Nathansona, and Ruzsa 99). Let $A$ be a set of $n$ real numbers and let $B$ be a set of $m$ points in ${\mathbb R}^2$. Let $f$ be a strictly convex or strictly concave function, and let $f(A) = \{ f(a) \mid a\in A\}$. Then

$|(A\times f(A))+B| =\Omega\left(\min\{mn,m^{1/2}n^{3/2}\right).$

Proof.     Consider the planar point set

${\cal P} = (A\times f(A))+B =\{ (a,f(a)) + b \mid a\in A \text{ and } b\in B \}.$

Consider also the set of planar curves

$\Gamma = \{ Z(y-f(x)) + b \mid b\in B \}.$

That is, $\Gamma$ is a set of $m$ translations of a strictly convex/concave curve. Notice that any two such translations intersect in at most one point. We recall the incidences theorem of Pach and Sharir (which I already stated recently here and here).

Theorem 3 (Pach and Sharir 98). Consider a point set $\cal P$, a set of simple curves $\Gamma$, both in ${\mathbb R}^2$, and two constant positive integers $k$ and $s$, such that
• For every $k$ points of $\cal P$ there are at most $s$ curves of $\Gamma$ that are incident to each of the $k$ points.
• Every two curves of $\Gamma$ intersect in at most $s$ points.
Then $I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),$ where the constant of proportionality depends on $k$ and $s$.

In our case, applying Theorem 3 with $k=2$, implies

$I({\cal P},\Gamma) = O\left(|{\cal P}|^{2/3}|\Gamma|^{2/3} + |{\cal P}|+ \Gamma \right) = O\left(|{\cal P}|^{2/3}m^{2/3} + |{\cal P}|+ m \right).\quad (3)$

On the other hand, every curve of $\Gamma$ contains $n$ points of $\cal P$, we have

$I({\cal P},\Gamma) = mn. \quad (4)$

Combining $(3)$ and $(4)$ implies

$mn = O\left(|{\cal P}|^{2/3}m^{2/3} + |{\cal P}|+ m\right).$
${\cal P} = \Omega(\min \{mn,m^{1/2}n^{3/2}\}).$

This completes the proof of the theorem, since ${\cal P} = (A\times f(A))+B. \qquad \Box$

The general formulation of Theorem 3 allows it to be applied in various scenarios. In a recent work with Joshua Zahl and Frank de Zeeuw, we have applied the theorem to show that a set of points on two orthogonal lines (with sufficiently many points on each of the lines) must yield a large number of distinct distances.

Recent tools, such as the Elekes-Sharir framework and the incidence results of Guth and Katz, prompted additional sum-prodcut-type bounds. For example:

Theorem 4 (Iosevich, Roche-Newton, and Rudnev `11). Let $A$ be a set of $n$ real numbers. Then

$|AA \pm AA| =\Omega\left(\frac{n^2}{\log n}\right).$

There are many other such extensions, and I cannot mention them all here.