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, either the pairwise sums or the pairwise products of the numbers in the set form a significantly larger set. More precisely, it asserts the existence of positive constants c and $\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\}$ .

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 $\varepsilon$ arbitrarily close to 1. The best result in this direction currently is by Solymosi,^[3] who showed that one can take $\varepsilon$ arbitrarily close to 1/3.

References

↑ Erdős, P.; Szemerédi, E. (1983), "On sums and products of integers", Studies in Pure Mathematics, Basel: Birkhäuser, pp. 213–218, MR 820223 .
↑ Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics 4 (2): 59–82, arXiv:0806.2497, MR 2592424 .
↑ Solymosi, József (2009), "Bounding multiplicative energy by the sumset", Advances in Mathematics 222 (2): 402–408, arXiv:0806.1040, doi:10.1016/j.aim.2009.04.006, MR 2538014 .