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 numbers , we respectively denote their

*sumset*and*productset*as

It is not difficult to choose sets such that (e.g., ), or such that (e.g., ). However, it can be shown that for any choice of , either or 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 there exists , such that any set of integers satisfies*

The best known lower bound for 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 be two sets of real numbers. Then*

Advertisements