In arithmetic combinatorics, the Erdős–Szemerédi theorem, proven by Paul Erdős and Endre Szemerédi in 1983, states that, for every finite set of real numbers, either the pairwise sums or the pairwise products of the numbers in the set form a significantly larger set. More precisely, it asserts the existence of positive constants c and such that
whenever A is a finite non-empty set of real numbers of cardinality |A|, where is the sum-set of A with itself, and .
It is possible for A + A to be of comparable size to A if A is an arithmetic progression, and it is possible for A · A to be of comparable size to A if A is a geometric progression. The Erdős–Szemerédi theorem can thus be viewed as an assertion that it is not possible for a large set to behave like an arithmetic progression and as a geometric progression simultaneously. 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.
It was conjectured by Erdős and Szemerédi that one can take arbitrarily close to 1. The best result in this direction currently is by George Shakan, who showed that one can take arbitrarily close to . Previously, Misha Rudnev, Ilya Shkredov, and Sophie Stevens had shown that one can take arbitrarily close to , improving an earlier result by József Solymosi, who had shown that one can take it arbitrarily close to .
- How a Strange Grid Reveals Hidden Connections Between Simple Numbers - Quanta Magazine article about the sum-product phenomenon.
- Erdős, Paul; Szemerédi, Endre (1983), "On sums and products of integers" (PDF), Studies in Pure Mathematics. To the memory of Paul Turán, Basel: Birkhäuser Verlag, pp. 213–218, doi:10.1007/978-3-0348-5438-2_19, ISBN 978-3-7643-1288-6, MR 0820223.
- Tao, Terence (2009), "The sum-product phenomenon in arbitrary rings", Contributions to Discrete Mathematics, 4 (2): 59–82, arXiv:0806.2497, Bibcode:2008arXiv0806.2497T, hdl:10515/sy5r78637, MR 2592424.
- Shakan, George (2018). "On higher energy decompositions and the sum-product phenomenon". arXiv:1803.04637 [math.NT].
- Rudnev, Misha; Shkredov, Ilya D.; Stevens, Sophie (2016). "On The Energy Variant of the Sum-Product Conjecture". arXiv:1607.05053 [math.CO].
- Solymosi, József (2009), "Bounding multiplicative energy by the sumset", Advances in Mathematics, 222 (2): 402–408, arXiv:0806.1040, doi:10.1016/j.aim.2009.04.006, MR 2538014.