Erdős–Szemerédi theorem

In arithmetic combinatorics, the Erdős–Szemerédi theorem, proven by Paul Erdős and Endre Szemerédi in 1983,[1] states that, for every finite set of real numbers, at least one of the set of pairwise sums or the set of pairwise products of the numbers in the original set form a significantly larger set. More precisely, it asserts the existence of positive constants c and $\varepsilon$ such that

\max(|A+A|,|A\cdot A|)\geq c|A|^{1+\varepsilon }

whenever A is a finite non-empty set of real numbers of cardinality |A|, where $A+A=\{a+b:a,b\in A\}$ is the sum-set of A with itself, and $A\cdot A=\{ab:a,b\in A\}$ .

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.[2]

It was conjectured by Erdős and Szemerédi that one can take $\varepsilon$ arbitrarily close to 1. The best result in this direction currently is by George Shakan,[3] who showed that one can take $\varepsilon$ arbitrarily close to $1/3+5/5277$ . Previously, Misha Rudnev, Ilya Shkredov, and Sophie Stevens had shown that one can take $\varepsilon$ arbitrarily close to $1/3+1/1509$ ,[4] improving an earlier result by József Solymosi,[5] who had shown that one can take it arbitrarily close to $1/3$ .

External links

Hartnett, Kevin (6 February 2019). "How a Strange Grid Reveals Hidden Connections Between Simple Numbers". Quanta Magazine.

References

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] 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.

[2] 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.

[3] Shakan, George (2018). "On higher energy decompositions and the sum-product phenomenon". arXiv:1803.04637 [math.NT].

[4] Rudnev, Misha; Shkredov, Ilya D.; Stevens, Sophie (2016). "On The Energy Variant of the Sum-Product Conjecture". arXiv:1607.05053 [math.CO].

[5] 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.