Erdős–Szemerédi theorem

Template:Short description In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set Template:Mvar of integers, at least one of the sets Template:Math and Template:Math (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 Template:Mvar and Template:Mvar such that, for any non-empty set Template:Math,

$\max (|A+A|,|A\cdot A|)\ge c|A{|}^{1+\epsilon }$.

It was proved by Paul Erdős and Endre Szemerédi in 1983. The notation Template:Math denotes the cardinality of the set Template:Mvar.

The set of pairwise sums is Template:Math and is called the sumset of Template:Mvar.

The set of pairwise products is Template:Math and is called the product set of Template:Mvar; it is also written Template:Math.

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.

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 in 1974 to hold whether Template:Mvar is a set of integers, reals, or complex numbers. More precisely, it proposes that, for any set Template:Math, one has

$\max (|A+A|,|AA|)\ge |A{|}^{2-o(1)}.$

The asymptotic parameter in the Template:Math notation is Template:Math.

Examples

If Template:Math, then Template:Math using asymptotic notation, with Template:Math the asymptotic parameter. Informally, this says that the sum set of Template:Mvar does not grow. On the other hand, the product set of Template:Mvar satisfies a bound of the form Template:Math for all Template:Math. This is related to the Erdős multiplication table problem. The best lower bound on Template:Math for this set is due to Kevin Ford.

This example is an instance of the Few Sums, Many Products 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 (such as an arithmetic progression) has the lower bound on the product set Template:Math. Xu and Zhou proved that Template:Math for any dense subset Template:Mvar of an arithmetic progression in integers, which is sharp up to the Template:Math in the exponent.

Conversely, the set Template:Math satisfies Template:Math, but has many sums: $|B+B|=(\genfrac{}{}{0ex}{}{|B|+1}{2})$. This bound comes from considering the binary representation of a number. The set Template:Mvar is an example of a geometric progression.

For a random set of Template:Mvar numbers, both the product set and the sumset have cardinality $(\genfrac{}{}{0ex}{}{n+1}{2})$; that is, with high probability, neither the sumset nor the product set generates repeated elements.

Sharpness of the conjecture

Erdős and Szemerédi give an example of a sufficiently smooth set of integers Template:Mvar with the bound

$\max \{|A+A|,|A\cdot A|\}\le |A{|}^2{e}^{-\frac{c\log |A|}{\log \log |A|}}$.

This shows that the Template:Math term in the conjecture is necessary.

Extremal cases

Often studied are the extreme cases of the hypothesis:

• few sums, many product (FSMP): if Template:Math, then Template:Math, and
• few products, many sums (FPMS): if Template:Math, then Template:Math.

History and current results

The following table summarizes 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 Template:Math, and represent refinements of the arguments of Konyagin and Shkredov.

Exponent Template:Nobold where Template:Nobold for Template:Nobold

Year	Exponent	Author(s)	Comments
1983	non-explicit Template:Math	Erdős and Szemerédi	Only for Template:Math and of the form Template:Math instead of Template:Math.
1997	Template:Math	Nathanson	Only for Template:Math and of the form Template:Math instead of Template:Math.
1998	Template:Math	Ford	Only for Template:Math and of the form Template:Math instead of Template:Math.
1997	Template:Math	Elekes	Of the form Template:Math. Valid also over Template:Math
2005	Template:Math	Solymosi	Valid also over Template:Math
2009	Template:Math	Solymosi
2015	Template:Math	Konyagin and Shkredov
2016	Template:Math	Konyagin and Shkredov
2016	Template:Math	Rudnev, Shkredov and Stevens
2019	Template:Math	Shakan
2020	Template:Math	Rudnev and Stevens	Current record

Complex numbers

Proof techniques involving only the Szemerédi–Trotter theorem extend automatically to the complex numbers, since the Szemerédi-Trotter theorem holds over Template:Math by a theorem of Tóth. Konyagin and Rudnev matched the exponent of 4/3 over the complex numbers. The results with exponents of the form Template:Math have not been matched over the complex numbers.

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 Template:Math, where Template:Mvar is a (large) prime, that Template:Math for an absolute constant Template:Math. This conjecture had also been formulated in the 1990s by Wigderson motivated by randomness extractors.

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

Example: Let Template:Math be a finite field and take Template:Math. Then since Template:Math is closed under addition and multiplication, Template:Math, and so Template:Math. This pathological example extends to taking Template:Mvar 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)): Let Template:Mvar be prime and let Template:Math with Template:Math for some Template:Math. Then Template:Math for some Template:Math.

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)): Let Template:Mvar be a subset of a finite field Template:Math so that Template:Math for some Template:Math, and suppose thatTemplate:Math. Then there exists a sub-field Template:Math with Template:Math, an element Template:Math, and a set Template:Math with Template:Mathso that Template:Math.

They suggest that the constant Template:Math may be independent of Template:Mvar.

Quantitative results towards the finite field sum-product problem in Template:Math typically fall into two categories: when Template:Math is small or large with respect to the characteristic of Template:Math. This is because different types of techniques are used in each setting.

Small sets

In this regime, let Template:Math be a field of characteristic Template:Mvar. Note that the field is not always finite. When this is the case, and the characteristic of Template:Math is zero, then the Template:Mvar-constraint is omitted.

Exponent Template:Nobold where Template:Nobold for Template:Nobold

Year	Exponent	Template:Nobold-constraint: Template:Nobold	Author(s)	Comments
2004	unquantified	Template:Math	Bourgain, Katz, Tao	For finite Template:Math only.
2007	Template:Math	Template:Math	Garaev	For finite Template:Math only. The Template:Mvar-constraint involves a factor of Template:Math
2008	Template:Math	Template:Math	Katz, Shen	For finite Template:Math only.
2009	Template:Math	Template:Math	Bourgain, Garaev	For finite Template:Math only. Template:Math removed by Li.
2012	Template:Math	Template:Math	Rudnev	For finite Template:Math only.
2016	Template:Math	Template:Math	Roche-Newton, Rudnev, Shkredov
2016	Template:Math	Template:Math	Rudnev, Shkredov, Shakan	This result is the best of three contemporaneous results.
2021	Template:Math	Template:Math	Mohammadi, Stevens	Current record. Extends to difference sets and ratio sets.

In fields with non-prime order, the Template:Mvar-constraint on Template:Math can be replaced with the assumption that Template:Mvar does not have too large an intersection with any subfield. The best work in this direction is due to Li and Roche-Newton attaining an exponent of Template:Math in the notation of the above table.

Large sets

When Template:Math for Template:Mvar prime, the sum-product problem is considered resolved due to the following result of Garaev:

Theorem (Garaev (2007)): Let Template:Math. Then Template:Math.

This is optimal in the range Template:Math.

This result was extended to finite fields of non-prime order by Vinh in 2011.

Variants and generalizations

Other combinations of operators

Bourgain and Chang proved unconditional growth for sets Template:Math, as long as one considers enough sums or products:

Theorem (Bourgain, Chang (2003)): Let Template:Math. Then there exists Template:Math so that for all Template:Math, one has Template:Math .

In many works, addition and multiplication are combined in one expression. With the motto addition and multiplication cannot coexist, one expects that any non-trivial combination of addition and multiplication of a set should guarantee growth. Note that in finite settings, or in fields with non-trivial subfields, such a statement requires further constraints.

Sets of interest include (results for Template:Math):

• Template:Math: Stevens and Warren show that Template:Math
• Template:Math: Murphy, Roche-Newton and Shkredov show that Template:Math
• Template:Math: Stevens and Warren show that Template:Math
• Template:Math: Stevens and Rudnev show that Template:Math

See also

• Sum-free set
• Restricted sumset
• Additive combinatorics
• Additive number theory
• Multiplicative number theory

External links

• Template:Cite journal