Erdős–Szemerédi theorem
The Erdős–Szemerédi theorem in arithmetic combinatorics states that for every finite set formula_1 of integers, at least one of formula_2, the set of pairwise sums or formula_3, 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 formula_4 such that for any non-empty set formula_5 It was proved by Paul Erdős and Endre Szemerédi in 1983. The notation formula_7 denotes the cardinality of the set formula_1. The set of pairwise sums is formula_9 and is called sum set of formula_1. The  set of pairwise products is formula_11 and is called the product set of formula_1. 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 formula_13 one has formula_14 The asymptotic parameter in the o(1) notation is |A|. Examples. If formula_15 then formula_16 using asymptotic notation, withformula_7 the asymptotic parameter. Informally, this says that the sum set of formula_1 does not grow. On the other hand, the product set of formula_1 satisfies a bound of the form formula_20 for all formula_21. This is related to  the Erdős multiplication table problem. The best lower bound on formula_22 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 formula_23. Xu and Zhou proved that formula_24 for any dense subset formula_25 of an arithmetic progression in integers, which is sharp up to the formula_26 factor in the exponent. Conversely, the  set formula_27 satisfies formula_28, but has many sums: formula_29-constraint on formula_30 can be replaced with the assumption that formula_1 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 formula_32in the notation of the above table. Large sets. When formula_33 for formula_34 prime, the sum-product problem is considered resolved due to the following result of Garaev: Theorem (Garaev (2007) ): Let formula_35. Then formula_36. This is optimal in the range formula_37. 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 formula_38, as long as one considers enough sums or products: Theorem (Bourgain, Chang (2003) ): Let formula_38 and formula_40. Then there exists formula_41 so that formula_42 . 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 formula_43):