Erdős–Szemerédi theorem

In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set $A$ of integers, at least one of the sets $A + A$ and $A \cdot A$ (the sets of pairwise sums and pairwise products, respectively) form a significantly larger set. More precisely, the Erdős–Szemerédi theorem states that there exist positive constants $c$ and $ε$ such that, for any non-empty set $A \subset ℕ$ ,

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

.

It was proved by Paul Erdős and Endre Szemerédi in 1983. The notation $| A |$ denotes the cardinality of the set $A$ .

The set of pairwise sums is $A + A = {a + b : a, b \in A}$ and is called the sumset of $A$ .

The set of pairwise products is $A \cdot A = {a \cdot b : a, b \in A}$ and is called the product set of $A$ ; it is also written $AA$ .

The theorem is a version of the maxim that additive structure and multiplicative structure cannot coexist. 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.