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,[1] states that, for every finite set of real numbers, at least one of the set of pairwise sums or the set of pairwise products of the numbers in the original set form a significantly larger set. More precisely, it asserts the existence of positive constants c and ${\displaystyle \varepsilon }$ such that

${\displaystyle \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 ${\displaystyle A+A=\{a+b:a,b\in A\}}$ is the sum-set of A with itself, and ${\displaystyle A\cdot A=\{ab:a,b\in A\}}$.

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.[2]

It was conjectured by Erdős and Szemerédi that one can take ${\displaystyle \varepsilon }$ arbitrarily close to 1. The best result in this direction currently is by George Shakan,[3] who showed that one can take ${\displaystyle \varepsilon }$ arbitrarily close to ${\displaystyle 1/3+5/5277}$. Previously, Misha Rudnev, Ilya Shkredov, and Sophie Stevens had shown that one can take ${\displaystyle \varepsilon }$ arbitrarily close to ${\displaystyle 1/3+1/1509}$,[4] improving an earlier result by József Solymosi,[5] who had shown that one can take it arbitrarily close to ${\displaystyle 1/3}$.