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

Sum-Product Conjecture

The sum-product conjecture informally says that one of the sum set or the product set of any set must be nearly as large as possible. It was originally conjectured by Erdős and Szemerédi over the integers,^[1] but is thought to hold over the real numbers.

Conjecture: For any set ${\displaystyle A\subset \mathbb {R} }$ one has ${\displaystyle \max(|A+A|,|AA|)\geq |A|^{2-o(1)}.}$

The asymptotic parameter in the o(1) notation is |A|.

Examples

If ${\displaystyle A=\{1,2,3,\dots ,n\}}$ then ${\displaystyle |A+A|=2|A|-1=O(|A|)}$ using asymptotic notation, with${\displaystyle |A|}$ the asymptotic parameter. Informally, this says that the sum set of ${\displaystyle A}$ does not grow. On the other hand, the product set of ${\displaystyle A}$ satisfies a bound of the form ${\displaystyle |A\cdot A|\geq |A|^{2-\epsilon }}$ for all ${\displaystyle \epsilon >0}$. This is related to the Erdős multiplication table problem.^[3] The best lower bound on ${\displaystyle |A\cdot A|}$ for this set is due to Kevin Ford.^[4]

This example is an instance of the Few Sums, Many Products^[5] version of the sum-product problem of György Elekes and Imre Z. Ruzsa. A consequence of their result is that any set with small additive doubling, for example an arithmetic progression has the lower bound on the product set ${\displaystyle |AA|=\Omega (|A|^{2}\log ^{-1}(|A|))}$. Xu and Zhou ^[6] proved that ${\displaystyle |AA|=\Omega (|A|^{2}\log ^{1-2\log 2-o(1)}(|A|))}$ for any dense subset ${\displaystyle A}$ of an arithmetic progression in integers, which is sharp up to the ${\displaystyle o(1)}$ factor in the exponent.

Conversely, the set ${\displaystyle B=\{2,4,8,\dots ,2^{n}\}}$ satisfies ${\displaystyle |B\cdot B|=2|B|-1}$, but has many sums: ${\displaystyle |B+B|={\binom {|B|+1}{2}}}$. This bound comes from considering the binary representation of a number. The set ${\displaystyle B}$ is an example of a geometric progression.

For a random set of ${\displaystyle n}$ numbers, both the product set and the sum set have cardinality ${\displaystyle {\binom {n+1}{2}}}$; that is, with high probability the sum set generates no repeated elements, and the same for the product set.

History and current results

The following table summarises progress on the sum-product problem over the reals. The exponents 1/4 of György Elekes and 1/3 of József Solymosi are considered milestone results within the citing literature. All improvements after 2009 are of the form ${\displaystyle {\frac {1}{3}}+c}$, and represent refinements of the arguments of Konyagin and Shkredov.^[8]

Exponent ${\displaystyle \delta }$ where ${\displaystyle \max(|A+A|,|AA|)\geq |A|^{1+\delta -o(1)}}$ for ${\displaystyle A\subset \mathbb {R} }$

Year	Exponent	Author(s)	Comments
1983	non-explicit ${\displaystyle \delta >0}$	Erdős and Szemerédi [9]	Only for ${\displaystyle A\subseteq \mathbb {Z} }$ and of the form ${\displaystyle 1+\delta }$ instead of ${\displaystyle 1+\delta -o(1)}$.
1997	${\displaystyle {\frac {1}{31}}}$	Nathanson[10]	Only for ${\displaystyle A\subseteq \mathbb {Z} }$ and of the form ${\displaystyle 1+\delta }$ instead of ${\displaystyle 1+\delta -o(1)}$.
1998	${\displaystyle {\frac {1}{15}}}$	Ford [11]	Only for ${\displaystyle A\subseteq \mathbb {Z} }$ and of the form ${\displaystyle 1+\delta }$ instead of ${\displaystyle 1+\delta -o(1)}$
1997	${\displaystyle {\frac {1}{4}}}$	Elekes [12]	Of the form ${\displaystyle 1+\delta -o(1)}$. Valid also over ${\displaystyle \mathbb {C} .}$
2005	${\displaystyle {\frac {3}{11}}}$	Solymosi[13]	Valid also over ${\displaystyle \mathbb {C} }$
2009	${\displaystyle {\frac {1}{3}}}$	Solymosi [14]
2015	${\displaystyle {\frac {1}{3}}+{\frac {1}{20598}}=0.333381\dots }$	Konyagin and Shkredov [8]
2016	${\displaystyle {\frac {1}{3}}+{\frac {5}{9813}}=0.333842\dots }$	Konyagin and Shkredov [15]
2016	${\displaystyle {\frac {1}{3}}+{\frac {1}{1509}}=0.333996\dots }$	Rudnev, Shkredov and Stevens [16]
2019	${\displaystyle {\frac {1}{3}}+{\frac {5}{5277}}=0.334280\dots }$	Shakan [17]
2020	${\displaystyle {\frac {1}{3}}+{\frac {2}{1167}}=0.335047\dots }$	Rudnev and Stevens [18]	Current record

Over finite fields

The sum-product problem is particularly well-studied over finite fields. Motivated by the finite field Kakeya conjecture, Wolff conjectured that for every subset ${\displaystyle A\subseteq \mathbb {F} _{p}}$, where ${\displaystyle p}$ is a (large) prime, that ${\displaystyle \max\{|A+A|,|AA|\}\geq \min\{p,|A|^{1+\epsilon }\}}$ for an absolute constant ${\displaystyle \epsilon >0}$. This conjecture had also been formulated in the 1990s by Wigderson^[21] motivated by randomness extractors.

Note that the sum-product problem cannot hold in finite fields unconditionally due to the following example:

Example: Let ${\displaystyle \mathbb {F} }$ be a finite field and take ${\displaystyle A=\mathbb {F} }$ . Then since ${\displaystyle \mathbb {F} }$ is closed under addition and multiplication, ${\displaystyle A+A=A\cdot A=\mathbb {F} }$ and so ${\displaystyle |A+A|=|A\cdot A|=|\mathbb {F} |}$. This pathological example extends to taking ${\displaystyle A}$ to be any sub-field of the field in question.

Qualitatively, the sum-product problem has been solved over finite fields:

Theorem (Bourgain, Katz, Tao (2004) ^[22]): Let ${\displaystyle p}$ be prime and let ${\displaystyle A\subset \mathbb {F} _{p}}$ with ${\displaystyle p^{\delta }<|A|<p^{1-\delta }}$ for some ${\displaystyle 0<\delta <1}$. Then one has ${\displaystyle \max(|A+A|,|A\cdot A|)\geq c_{\delta }|A|^{1+\epsilon }}$ for some ${\displaystyle \epsilon =\epsilon (\delta )>0}$.

Bourgain, Katz and Tao extended this theorem to arbitrary fields. Informally, the following theorem says that if a sufficiently large set does not grow under either addition or multiplication, then it is mostly contained in a dilate of a sub-field.

Theorem (Bourgain, Katz, Tao (2004) ^[22]): Let ${\displaystyle A}$ be a subset of a finite field ${\displaystyle \mathbb {F} }$ so that ${\displaystyle |A|>|\mathbb {F} |^{\delta }}$ for some ${\displaystyle 0<\delta <1}$ and suppose that ${\displaystyle |A+A|,|A\cdot A|\leq K|A|}$. Then there exists a sub-field ${\displaystyle G\subset \mathbb {F} }$ with ${\displaystyle |G|\leq K^{C_{\delta }}|A|}$, ${\displaystyle x\in \mathbb {F} \setminus \{0\}}$ and a set ${\displaystyle X\subset \mathbb {F} }$ with ${\displaystyle |X|\leq K^{C_{\delta }}}$so that ${\displaystyle A\subseteq xG\cup X}$.

They suggest that the constant ${\displaystyle C_{\delta }}$ may be independent of ${\displaystyle \delta }$.

Quantitative results towards the finite field sum-product problem in ${\displaystyle \mathbb {F} }$ typically fall into two categories: when ${\displaystyle A\subset \mathbb {F} }$ is small with respect to the characteristic of ${\displaystyle \mathbb {F} }$ and when ${\displaystyle A\subset \mathbb {F} }$ is large with respect to the characteristic of ${\displaystyle \mathbb {F} }$. This is because different types of techniques are used in each setting.

Small sets

In this regime, let ${\displaystyle \mathbb {F} }$ be a field of characteristic ${\displaystyle p}$. Note that the field is not always finite. When this is the case, and the characteristic of ${\displaystyle \mathbb {F} }$ is zero, then the ${\displaystyle p}$-constraint is omitted.

Exponent ${\displaystyle \delta }$ where ${\displaystyle \max(|A+A|,|AA|)\geq |A|^{1+\delta -o(1)}}$ for ${\displaystyle A\subset \mathbb {F} }$

Year	Exponent	${\displaystyle p}$ -constraint : ${\displaystyle |A|<p^{c}}$	Author(s)	Comments
2004	unquantified	${\displaystyle c<1}$	Bourgain, Katz, Tao [22]	For finite ${\displaystyle \mathbb {F} }$ only.
2007	${\displaystyle {\frac {1}{14}}}$	${\displaystyle c=7/13}$	Garaev[23]	For finite ${\displaystyle \mathbb {F} }$ only. The p-constraint involves a factor of ${\displaystyle \log(|A|)}$
2008	${\displaystyle {\frac {1}{13}}}$	${\displaystyle c=1/2}$	Katz, Shen	For finite ${\displaystyle \mathbb {F} }$ only.
2009	${\displaystyle {\frac {1}{12}}}$	${\displaystyle c=12/23}$	Bourgain, Garaev[24]	For finite ${\displaystyle \mathbb {F} }$ only. o(1) removed by Li.[25]
2012	${\displaystyle {\frac {1}{11}}}$	${\displaystyle c=1/2}$	Rudnev[26]	For finite ${\displaystyle \mathbb {F} }$ only.
2016	${\displaystyle {\frac {1}{5}}}$	${\displaystyle c=5/8}$	Roche-Newton, Rudnev, Shkredov[27]
2016	${\displaystyle {\frac {1}{9}}}$	${\displaystyle c=18/35}$	Rudnev, Shkredov, Shakan	This result is the best of three contemporaneous results.
2021	${\displaystyle {\frac {1}{4}}}$	${\displaystyle c=1/2}$	Mohammadi, Stevens [28]	Current record. Extends to difference sets and ratio sets.

In fields with non-prime order, the ${\displaystyle p}$-constraint on ${\displaystyle A\subset \mathbb {F} }$ can be replaced with the assumption that ${\displaystyle A}$ does not have too large an intersection with any subfield. The best work in this direction is due to Li and Roche-Newton^[29] attaining an exponent of ${\displaystyle \delta ={\frac {1}{19}}}$in the notation of the above table.

Variants and generalisations

See also

• Sum-free set

References

External links

• Hartnett, Kevin (6 February 2019). "How a Strange Grid Reveals Hidden Connections Between Simple Numbers". Quanta Magazine.