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