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, 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 ε such that

whenever A is a finite non-empty set of real numbers of cardinality |A|, where A + A = { a + b : a , b ∈ A } is the sum-set of A with itself, and A ⋅ A = { a b : a , b ∈ 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.

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