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