Szemerédi's theorem

From HandWiki
Short description: Long dense subsets of the integers contain arbitrarily large arithmetic progressions

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured[1] that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

Statement

A subset A of the natural numbers is said to have positive upper density if

[math]\displaystyle{ \limsup_{n \to \infty}\frac{|A\cap \{1, 2, 3, \dotsc, n\}|}{n} \gt 0. }[/math]

Szemerédi's theorem asserts that a subset of the natural numbers with positive upper density contains infinitely many arithmetic progressions of length k for all positive integers k.

An often-used equivalent finitary version of the theorem states that for every positive integer k and real number [math]\displaystyle{ \delta \in (0, 1] }[/math], there exists a positive integer

[math]\displaystyle{ N = N(k,\delta) }[/math]

such that every subset of {1, 2, ..., N} of size at least δN contains an arithmetic progression of length k.

Another formulation uses the function rk(N), the size of the largest subset of {1, 2, ..., N} without an arithmetic progression of length k. Szemerédi's theorem is equivalent to the asymptotic bound

[math]\displaystyle{ r_k(N) = o(N). }[/math]

That is, rk(N) grows less than linearly with N.

History

Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proven in 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. The case k = 3, known as Roth's theorem, was established in 1953 by Klaus Roth[2] via an adaptation of the Hardy–Littlewood circle method. Endre Szemerédi[3] proved the case k = 4 through combinatorics. Using an approach similar to the one he used for the case k = 3, Roth[4] gave a second proof for this in 1972.

The general case was settled in 1975, also by Szemerédi,[5] who developed an ingenious and complicated extension of his previous combinatorial argument for k = 4 (called "a masterpiece of combinatorial reasoning" by Erdős[6]). Several other proofs are now known, the most important being those by Hillel Furstenberg[7][8] in 1977, using ergodic theory, and by Timothy Gowers[9] in 2001, using both Fourier analysis and combinatorics. Terence Tao has called the various proofs of Szemerédi's theorem a "Rosetta stone" for connecting disparate fields of mathematics.[10]

Quantitative bounds

It is an open problem to determine the exact growth rate of rk(N). The best known general bounds are

[math]\displaystyle{ CN\exp\left(-n2^{(n - 1)/2}\sqrt[n]{\log N} + \frac{1}{2n}\log \log N\right) \leq r_k(N) \leq \frac{N}{(\log \log N)^{2^{-2^{k + 9}}}}, }[/math]

where [math]\displaystyle{ n = \lceil \log k\rceil }[/math]. The lower bound is due to O'Bryant[11] building on the work of Behrend,[12] Rankin,[13] and Elkin.[14][15] The upper bound is due to Gowers.[9]

For small k, there are tighter bounds than the general case. When k = 3, Bourgain,[16][17] Heath-Brown,[18] Szemerédi,[19] Sanders,[20] and Bloom[21] established progressively smaller upper bounds, and Bloom and Sisask then proved the first bound that broke the so-called ``logarithmic barrier".[22] The current best bounds are

[math]\displaystyle{ N 2^{-\sqrt{8\log N}} \leq r_3(N) \leq N e^{-c(\log N)^{1/11}} }[/math], for some constant [math]\displaystyle{ c\gt 0 }[/math],

due to O'Bryant,[11] and Kelley and Meka[23] respectively.

For k = 4, Green and Tao[24][25] proved that

[math]\displaystyle{ r_4(N) \leq C\frac{N}{(\log N)^c} }[/math]

for some c > 0.

Extensions and generalizations

A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.[26] Timothy Gowers,[27] Vojtěch Rödl and Jozef Skokan[28][29] with Brendan Nagle, Rödl, and Mathias Schacht,[30] and Terence Tao[31] provided combinatorial proofs.

Alexander Leibman and Vitaly Bergelson[32] generalized Szemerédi's to polynomial progressions: If [math]\displaystyle{ A \subset \mathbb{N} }[/math] is a set with positive upper density and [math]\displaystyle{ p_1(n),p_2(n),\dotsc,p_k(n) }[/math] are integer-valued polynomials such that [math]\displaystyle{ p_i(0) = 0 }[/math], then there are infinitely many [math]\displaystyle{ u, n \in \mathbb{Z} }[/math] such that [math]\displaystyle{ u + p_i(n) \in A }[/math] for all [math]\displaystyle{ 1 \leq i \leq k }[/math]. Leibman and Bergelson's result also holds in a multidimensional setting.

The finitary version of Szemerédi's theorem can be generalized to finite additive groups including vector spaces over finite fields.[33] The finite field analog can be used as a model for understanding the theorem in the natural numbers.[34] The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space [math]\displaystyle{ \mathbb{F}_3^n }[/math] is known as the cap set problem.

The Green–Tao theorem asserts the prime numbers contain arbitrary long arithmetic progressions. It is not implied by Szemerédi's theorem because the primes have density 0 in the natural numbers. As part of their proof, Ben Green and Tao introduced a "relative" Szemerédi theorem which applies to subsets of the integers (even those with 0 density) satisfying certain pseudorandomness conditions. A more general relative Szemerédi theorem has since been given by David Conlon, Jacob Fox, and Yufei Zhao.[35][36]

The Erdős conjecture on arithmetic progressions would imply both Szemerédi's theorem and the Green–Tao theorem.

See also

Notes

  1. ↑ Erdős, Paul; Turán, Paul (1936). "On some sequences of integers". Journal of the London Mathematical Society 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. http://www.renyi.hu/~p_erdos/1936-05.pdf. 
  2. ↑ Roth, Klaus Friedrich (1953). "On certain sets of integers". Journal of the London Mathematical Society 28 (1): 104–109. doi:10.1112/jlms/s1-28.1.104. 
  3. ↑ Szemerédi, Endre (1969). "On sets of integers containing no four elements in arithmetic progression". Acta Mathematica Academiae Scientiarum Hungaricae 20 (1–2): 89–104. doi:10.1007/BF01894569. 
  4. ↑ Roth, Klaus Friedrich (1972). "Irregularities of sequences relative to arithmetic progressions, IV". Periodica Math. Hungar. 2 (1–4): 301–326. doi:10.1007/BF02018670. 
  5. ↑ Szemerédi, Endre (1975). "On sets of integers containing no k elements in arithmetic progression". Acta Arithmetica 27: 199–245. doi:10.4064/aa-27-1-199-245. http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf. 
  6. ↑ Erdős, Paul (2013). Graham, Ronald L.; Nešetřil, Jaroslav; Butler, Steve. eds. The Mathematics of Paul Erdős I (Second ed.). New York: Springer. pp. 51–70. doi:10.1007/978-1-4614-7258-2_3. ISBN 978-1-4614-7257-5. 
  7. ↑ Furstenberg, Hillel (1977). "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions". Journal d'Analyse Mathématique 31: 204–256. doi:10.1007/BF02813304. .
  8. ↑ Furstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "The ergodic theoretical proof of Szemerédi's theorem". Bull. Amer. Math. Soc. 7 (3): 527–552. doi:10.1090/S0273-0979-1982-15052-2. 
  9. ↑ 9.0 9.1 Gowers, Timothy (2001). "A new proof of Szemerédi's theorem". Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi. 
  10. ↑ Tao, Terence (2007). "Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006". in Sanz-Solé, Marta; Soria, Javier; Varona, Juan Luis et al.. International Congress of Mathematicians. 1. Zürich: European Mathematical Society. pp. 581–608. doi:10.4171/022-1/22. ISBN 978-3-03719-022-7. 
  11. ↑ 11.0 11.1 O'Bryant, Kevin (2011). "Sets of integers that do not contain long arithmetic progressions". Electronic Journal of Combinatorics 18 (1). doi:10.37236/546. http://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p59/pdf. 
  12. ↑ Behrend, Felix A. (1946). "On the sets of integers which contain no three terms in arithmetic progression". Proceedings of the National Academy of Sciences 32 (12): 331–332. doi:10.1073/pnas.32.12.331. PMID 16578230. Bibcode: 1946PNAS...32..331B. 
  13. ↑ Rankin, Robert A. (1962). "Sets of integers containing not more than a given number of terms in arithmetical progression". Proc. R. Soc. Edinburgh Sect. A 65: 332–344. 
  14. ↑ Elkin, Michael (2011). "An improved construction of progression-free sets". Israel Journal of Mathematics 184 (1): 93–128. doi:10.1007/s11856-011-0061-1. 
  15. ↑ Green, Ben; Wolf, Julia (2010). "Additive Number Theory". in Chudnovsky, David; Chudnovsky, Gregory. Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson. New York: Springer. pp. 141–144. doi:10.1007/978-0-387-68361-4_9. ISBN 978-0-387-37029-3. 
  16. ↑ Bourgain, Jean (1999). "On triples in arithmetic progression". Geom. Funct. Anal. 9 (5): 968–984. doi:10.1007/s000390050105. 
  17. ↑ Bourgain, Jean (2008). "Roth's theorem on progressions revisited". Journal d'Analyse Mathématique 104 (1): 155–192. doi:10.1007/s11854-008-0020-x. 
  18. ↑ Heath-Brown, Roger (1987). "Integer sets containing no arithmetic progressions". Journal of the London Mathematical Society 35 (3): 385–394. doi:10.1112/jlms/s2-35.3.385. 
  19. ↑ Szemerédi, Endre (1990). "Integer sets containing no arithmetic progressions". Acta Mathematica Hungarica 56 (1–2): 155–158. doi:10.1007/BF01903717. 
  20. ↑ Sanders, Tom (2011). "On Roth's theorem on progressions". Annals of Mathematics 174 (1): 619–636. doi:10.4007/annals.2011.174.1.20. 
  21. ↑ Bloom, Thomas F. (2016). "A quantitative improvement for Roth's theorem on arithmetic progressions". Journal of the London Mathematical Society. Second Series 93 (3): 643–663. doi:10.1112/jlms/jdw010. 
  22. ↑ Bloom, Thomas; Sisask, Olof (2020). Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions. 
  23. ↑ Kelley, Zander; Meka, Raghu (2023). Strong bounds for 3-progressions. 
  24. ↑ Green, Ben; Tao, Terence (2009). "New bounds for Szemeredi's theorem, II: A new bound for r_4(N)". in Chen, William W. L.; Gowers, Timothy; Halberstam, Heini et al.. Analytic number theory. Essays in honour of Klaus Roth on the occasion of his 80th birthday. Cambridge: Cambridge University Press. pp. 180–204. ISBN 978-0-521-51538-2. Bibcode: 2006math.....10604G. 
  25. ↑ Green, Ben; Tao, Terence (2017). "New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r4(N)". Mathematika 63 (3): 944–1040. doi:10.1112/S0025579317000316. 
  26. ↑ Furstenberg, Hillel; Katznelson, Yitzhak (1978). "An ergodic Szemerédi theorem for commuting transformations". Journal d'Analyse Mathématique 38 (1): 275–291. doi:10.1007/BF02790016. 
  27. ↑ Gowers, Timothy (2007). "Hypergraph regularity and the multidimensional Szemerédi theorem". Annals of Mathematics 166 (3): 897–946. doi:10.4007/annals.2007.166.897. 
  28. ↑ Rödl, Vojtěch; Skokan, Jozef (2004). "Regularity lemma for k-uniform hypergraphs". Random Structures Algorithms 25 (1): 1–42. doi:10.1002/rsa.20017. 
  29. ↑ Rödl, Vojtěch; Skokan, Jozef (2006). "Applications of the regularity lemma for uniform hypergraphs". Random Structures Algorithms 28 (2): 180–194. doi:10.1002/rsa.20108. http://www.math.emory.edu/technical-reports/techrep-00076.pdf. 
  30. ↑ Nagle, Brendan; Rödl, Vojtěch; Schacht, Mathias (2006). "The counting lemma for regular k-uniform hypergraphs". Random Structures Algorithms 28 (2): 113–179. doi:10.1002/rsa.20117. 
  31. ↑ Tao, Terence (2006). "A variant of the hypergraph removal lemma". Journal of Combinatorial Theory. Series A 113 (7): 1257–1280. doi:10.1016/j.jcta.2005.11.006. 
  32. ↑ Bergelson, Vitaly; Leibman, Alexander (1996). "Polynomial extensions of van der Waerden's and Szemerédi's theorems". Journal of the American Mathematical Society 9 (3): 725–753. doi:10.1090/S0894-0347-96-00194-4. 
  33. ↑ Furstenberg, Hillel; Katznelson, Yitzhak (1991). "A density version of the Hales–Jewett theorem". Journal d'Analyse Mathématique 57 (1): 64–119. doi:10.1007/BF03041066. 
  34. ↑ Wolf, Julia (2015). "Finite field models in arithmetic combinatorics—ten years on". Finite Fields and Their Applications 32: 233–274. doi:10.1016/j.ffa.2014.11.003. 
  35. ↑ Conlon, David; Fox, Jacob; Zhao, Yufei (2015). "A relative Szemerédi theorem". Geometric and Functional Analysis 25 (3): 733–762. doi:10.1007/s00039-015-0324-9. 
  36. ↑ Zhao, Yufei (2014). "An arithmetic transference proof of a relative Szemerédi theorem". Mathematical Proceedings of the Cambridge Philosophical Society 156 (2): 255–261. doi:10.1017/S0305004113000662. Bibcode: 2014MPCPS.156..255Z. 

Further reading

  • Tao, Terence (2007). Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József. eds. Additive Combinatorics. CRM Proceedings & Lecture Notes. 43. Providence, RI: American Mathematical Society. pp. 145–193. ISBN 978-0-8218-4351-2. Bibcode: 2006math......4456T. 

External links



Retrieved from "https://handwiki.org/wiki/index.php?title=Szemerédi%27s_theorem&oldid=3365250"