Szemerédi's theorem

From Wikipedia, the free encyclopedia

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.


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

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 , there exists a positive integer

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

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


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[edit]

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

where . 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

, for some constant ,

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

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

for some c > 0.

Extensions and generalizations[edit]

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 is a set with positive upper density and are integer-valued polynomials such that , then there are infinitely many such that for all . 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 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[edit]


  1. ^ Erdős, Paul; Turán, Paul (1936). "On some sequences of integers" (PDF). Journal of the London Mathematical Society. 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. MR 1574918.
  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. MR 0051853. Zbl 0050.04002.
  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. MR 0245555. Zbl 0175.04301.
  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. MR 0369311. S2CID 126176571.
  5. ^ Szemerédi, Endre (1975). "On sets of integers containing no k elements in arithmetic progression" (PDF). Acta Arithmetica. 27: 199–245. doi:10.4064/aa-27-1-199-245. MR 0369312. Zbl 0303.10056.
  6. ^ Erdős, Paul (2013). "Some of My Favorite Problems and Results". In 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. MR 1425174.
  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. MR 0498471. S2CID 120917478..
  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. MR 0670131.
  9. ^ a b 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. MR 1844079. S2CID 124324198.
  10. ^ Tao, Terence (2007). "The dichotomy between structure and randomness, arithmetic progressions, and the primes". In Sanz-Solé, Marta; Soria, Javier; Varona, Juan Luis; Verdera, Joan (eds.). Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006. International Congress of Mathematicians. Vol. 1. Zürich: European Mathematical Society. pp. 581–608. arXiv:math/0512114. doi:10.4171/022-1/22. ISBN 978-3-03719-022-7. MR 2334204.
  11. ^ a b O'Bryant, Kevin (2011). "Sets of integers that do not contain long arithmetic progressions". Electronic Journal of Combinatorics. 18 (1). doi:10.37236/546. MR 2788676.
  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. Bibcode:1946PNAS...32..331B. doi:10.1073/pnas.32.12.331. MR 0018694. PMC 1078964. PMID 16578230. Zbl 0060.10302.
  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. MR 0142526. Zbl 0104.03705.
  14. ^ Elkin, Michael (2011). "An improved construction of progression-free sets". Israel Journal of Mathematics. 184 (1): 93–128. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. MR 2823971.
  15. ^ Green, Ben; Wolf, Julia (2010). "A note on Elkin's improvement of Behrend's construction". In Chudnovsky, David; Chudnovsky, Gregory (eds.). Additive Number Theory. Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson. New York: Springer. pp. 141–144. arXiv:0810.0732. doi:10.1007/978-0-387-68361-4_9. ISBN 978-0-387-37029-3. MR 2744752. S2CID 10475217.
  16. ^ Bourgain, Jean (1999). "On triples in arithmetic progression". Geom. Funct. Anal. 9 (5): 968–984. doi:10.1007/s000390050105. MR 1726234. S2CID 392820.
  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. MR 2403433. S2CID 16985451.
  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. MR 0889362.
  19. ^ Szemerédi, Endre (1990). "Integer sets containing no arithmetic progressions". Acta Mathematica Hungarica. 56 (1–2): 155–158. doi:10.1007/BF01903717. MR 1100788.
  20. ^ Sanders, Tom (2011). "On Roth's theorem on progressions". Annals of Mathematics. 174 (1): 619–636. arXiv:1011.0104. doi:10.4007/annals.2011.174.1.20. MR 2811612. S2CID 53331882.
  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. arXiv:1405.5800. doi:10.1112/jlms/jdw010. MR 3509957. S2CID 27536138.
  22. ^ Bloom, Thomas; Sisask, Olof (2020). "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions". arXiv:2007.03528. {{cite journal}}: Cite journal requires |journal= (help)
  23. ^ Kelley, Zander; Meka, Raghu (2023). "Strong bounds for 3-progressions". arXiv:2302.05537. {{cite journal}}: Cite journal requires |journal= (help)
  24. ^ Green, Ben; Tao, Terence (2009). "New bounds for Szemeredi's theorem. II. A new bound for r4(N)". In Chen, William W. L.; Gowers, Timothy; Halberstam, Heini; Schmidt, Wolfgang; Vaughan, Robert Charles (eds.). New bounds for Szemeredi's theorem, II: A new bound for r_4(N). Analytic number theory. Essays in honour of Klaus Roth on the occasion of his 80th birthday. Cambridge: Cambridge University Press. pp. 180–204. arXiv:math/0610604. Bibcode:2006math.....10604G. ISBN 978-0-521-51538-2. MR 2508645. Zbl 1158.11007.
  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. arXiv:1705.01703. doi:10.1112/S0025579317000316. MR 3731312. S2CID 119145424.
  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. MR 0531279. S2CID 123386017.
  27. ^ Gowers, Timothy (2007). "Hypergraph regularity and the multidimensional Szemerédi theorem". Annals of Mathematics. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/annals.2007.166.897. MR 2373376. S2CID 56118006.
  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. MR 2069663. S2CID 7458739.
  29. ^ Rödl, Vojtěch; Skokan, Jozef (2006). "Applications of the regularity lemma for uniform hypergraphs" (PDF). Random Structures Algorithms. 28 (2): 180–194. doi:10.1002/rsa.20108. MR 2198496. S2CID 18203198.
  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. MR 2198495. S2CID 14126774.
  31. ^ Tao, Terence (2006). "A variant of the hypergraph removal lemma". Journal of Combinatorial Theory. Series A. 113 (7): 1257–1280. arXiv:math/0503572. doi:10.1016/j.jcta.2005.11.006. MR 2259060.
  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. MR 1325795.
  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. MR 1191743. S2CID 123036744.
  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. hdl:1983/d340f853-0584-49c8-a463-ea16ee51ce0f. MR 3293412.
  35. ^ Conlon, David; Fox, Jacob; Zhao, Yufei (2015). "A relative Szemerédi theorem". Geometric and Functional Analysis. 25 (3): 733–762. arXiv:1305.5440. doi:10.1007/s00039-015-0324-9. MR 3361771. S2CID 14398869.
  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. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. doi:10.1017/S0305004113000662. MR 3177868. S2CID 119673319.

Further reading[edit]

External links[edit]