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, 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 $\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

How a Strange Grid Reveals Hidden Connections Between Simple Numbers - Quanta Magazine article about the sum-product phenomenon.

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.