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}.

Continue reading