Erdős–Szemerédi theorem
In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set  of integers, at least one of , the set of pairwise sums or , 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  such that for any non-empty set 

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

The set of pairwise sums is  and is called sum set of .

The set of pairwise products is  and is called the product set of .

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 and Szemerédi over the integers, but is thought to hold over the real numbers.

Conjecture:  For any set  one has 

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

Examples 
If  then  using asymptotic notation, with the asymptotic parameter. Informally, this says that the sum set of  does not grow. On the other hand, the product set of  satisfies a bound of the form  for all . This is related to the Erdős multiplication table problem. The best lower bound on   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, for example an arithmetic progression has the lower bound on the product set . Xu and Zhou  proved that  for any dense subset  of an arithmetic progression in integers, which is sharp up to the  factor in the exponent.

Conversely, the set  satisfies , but has many sums: . This bound comes from considering the binary representation of a number. The set  is an example of  a geometric progression.

For a random set of  numbers, both the product set and the sum set have cardinality ; that is, with high probability the sum set generates no repeated elements, and the same for the product set.

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

.

This shows that the o(1) term in the conjecture is necessary.

Extremal cases 
Often studied are the extreme cases of the hypothesis:
 few sums, many product (FSMP): if , then 
 few products, many sums (FPMS): if , then .

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 , and represent refinements of the arguments of Konyagin and Shkredov.

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 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  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 , where  is a (large) prime, that  for an absolute constant . 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  be a finite field and take  . Then since  is closed under addition and multiplication,  and so . This pathological example extends to taking  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  be prime and let  with  for some . Then one has  for some .

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  be a subset of a finite field  so that  for some  and suppose that . Then there exists a sub-field  with ,  and a set  with so that .

They suggest that the constant  may be independent of .

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

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

In fields with non-prime order, the -constraint on  can be replaced with the assumption that  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 in the notation of the above table.

Large sets 
When  for  prime, the sum-product problem is considered resolved due to the following result of Garaev:

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

This is optimal in the range .

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

Variants and generalisations

Other combinations of operators 
Bourgain and Chang proved unconditional growth for sets , as long as one considers enough sums or products:

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

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 ):

  - Stevens and Warren show that 
  - Murphy, Roche-Newton and Shkredov show that 
  - Stevens and Warren show that 
  - Stevens and Rudnev show that

See also 

 Sum-free set

References

External links 
 

Combinatorics
Sumsets
Theorems in discrete mathematics
Theorems in number theory