Erdős–Szemerédi theorem

In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set ${\displaystyle A}$ of integers, at least one of ${\displaystyle A+A}$, the set of pairwise sums or ${\displaystyle A\cdot A}$, the set of pairwise products form a significantly larger set. More precisely, the Erdős–Szemerédi theorem states that there exist positive constants c and ${\displaystyle \varepsilon }$ such that for any non-empty set ${\displaystyle A\subset \mathbb {N} }$

${\displaystyle \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 ${\displaystyle |A|}$ denotes the cardinality of the set ${\displaystyle A}$.

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

The set of pairwise products is ${\displaystyle A\cdot A=\{ab:a,b\in A\}}$ and is called the product set of ${\displaystyle A}$.

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.