More precisely, the Erdős–Szemerédi theorem states that there exist positive constants c and ε such that, for any non-empty set A ⊂ ℕ, It was proved by Paul Erdős and Endre Szemerédi in 1983.
It was originally conjectured by Erdős in 1974 to hold whether A is a set of integers, reals, or complex numbers.
[4] The best lower bound on |A · A| for this set is due to Kevin Ford.
[5] This example is an instance of the Few Sums, Many Products[6] version of the sum-product problem of György Elekes and Imre Z. Ruzsa.
Xu and Zhou proved[7] that |AA| = Ω(|A|2 log1−2log(2)−o(1)(|A|)) for any dense subset A of an arithmetic progression in integers, which is sharp up to the o(1) in the exponent.
; that is, with high probability, neither the sumset nor the product set generates repeated elements.
Erdős and Szemerédi give an example of a sufficiently smooth set of integers A with the bound
Often studied are the extreme cases of the hypothesis: 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 1/3 + c, and represent refinements of the arguments of Konyagin and Shkredov.
[20] Konyagin and Rudnev[21] matched the exponent of 4/3 over the complex numbers.
The results with exponents of the form 4/3 + c have not been matched over the complex numbers.
Motivated by the finite field Kakeya conjecture, Wolff conjectured that for every subset A ⊆ 𝔽p, where p is a (large) prime, that max(|A + A|, |AA|) ≥ min(p, |A|1+ε) for an absolute constant ε > 0.
Qualitatively, the sum-product problem has been solved over finite fields: Theorem (Bourgain, Katz, Tao (2004)):[23] Let p be prime and let A ⊂ 𝔽p with pδ < |A| < p1−δ for some 0 < δ < 1.
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)):[23] Let A be a subset of a finite field 𝔽 so that |A| > |𝔽|δ for some 0 < δ < 1, and suppose that|A + A|, |AA| ≤ K|A|.
In fields with non-prime order, the p-constraint on A ⊂ 𝔽 can be replaced with the assumption that A does not have too large an intersection with any subfield.
The best work in this direction is due to Li and Roche-Newton[30] attaining an exponent of δ = 1/19 in the notation of the above table.
This result was extended to finite fields of non-prime order by Vinh[32] in 2011.
Bourgain and Chang proved unconditional growth for sets A ⊆ ℤ, as long as one considers enough sums or products: Theorem (Bourgain, Chang (2003)):[33] Let b ∈ ℕ.
Note that in finite settings, or in fields with non-trivial subfields, such a statement requires further constraints.