Erdős–Szemerédi theorem

In arithmetic combinatorics, the Erdős–Szemerédi theorem, proven by Paul Erdős and Endre Szemerédi in 1983, asserts the existence of positive constants c, $\varepsilon$ such that

$\max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }$

whenever A is a finite non-empty set of real numbers of cardinality |A|, where $A+A=\{a+b:a,b\in A\}$ is the sum-set of A with itself, and $A\cdot A=\{ab:a,b\in A\}$. Note that it is possible for A+A to be of comparable size to A if A is an arithmetic progression, and it is possible for A·A to be of comparable size to A if A is a geometric progression. The Erdős–Szemerédi theorem can thus be viewed as an assertion that it is not possible for a large set to behave like an arithmetic progression and as a geometric progression simultaneously. It can also be viewed as an assertion that the real line does not contain any set resembling a finite subring or finite subfield; it is the first example of what is now known as the sum-product phenomenon, which is now known to hold in a wide variety of rings and fields, including finite fields.

It was conjectured by Erdős and Szemerédi that one can take $\varepsilon$ arbitrarily close to 1. The best result in this direction currently is by Solymosi, who showed that one can take $\varepsilon$ arbitrarily close to 1/3.