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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s