Szemerédi's theorem

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

${\displaystyle \limsup _{n\to \infty }{\frac {|A\cap \{1,2,3,\dotsc ,n\}|}{n}}>0.}$

Szemerédi's theorem asserts that a subset of the natural numbers with positive upper density contains an arithmetic progression 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 ${\displaystyle \delta \in (0,1]}$, there exists a positive integer

${\displaystyle N=N(k,\delta )}$

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

Another formulation uses the function r_k(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

${\displaystyle r_{k}(N)=o(N).}$

That is, r_k(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. Szemerédi^[3] next 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 k = 4 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 while also introducing what is now called the Gowers norm. Terence Tao has called the various proofs of Szemerédi's theorem a "Rosetta stone" for connecting disparate fields of mathematics.^[10]

Quantitative bounds

See also: Erdős conjecture on arithmetic progressions § Progress and related results, Roth's theorem on arithmetic progressions § Improving bounds, and Salem–Spencer set § Size

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

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

where ${\displaystyle n=\lceil \log k\rceil }$. 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

${\displaystyle N2^{-{\sqrt {8\log N}}}\leq r_{3}(N)\leq Ne^{-c(\log N)^{1/9}}}$, for some constant ${\displaystyle c>0}$,

respectively due to O'Bryant,^[11] and Bloom and Sisask^[23] (the latter built upon the breakthrough result of Kelley and Meka,^[24] who obtained the same upper bound, with "1/9" replaced by "1/12").

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

${\displaystyle r_{4}(N)\leq C{\frac {N}{(\log N)^{c}}}}$

For k=5 in 2023 and k≥5 in 2024 Leng, Sah and Sawhney proved in preprints ^[27][28][29] that:

${\displaystyle r_{k}(N)\leq CN\exp(-(\log \log N)^{c})}$

Extensions and generalizations

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

Alexander Leibman and Vitaly Bergelson^[36] generalized Szemerédi's to polynomial progressions: If ${\displaystyle A\subset \mathbb {N} }$ is a set with positive upper density and ${\displaystyle p_{1}(n),p_{2}(n),\dotsc ,p_{k}(n)}$ are integer-valued polynomials such that ${\displaystyle p_{i}(0)=0}$, then there are infinitely many ${\displaystyle u,n\in \mathbb {Z} }$ such that ${\displaystyle u+p_{i}(n)\in A}$ for all ${\displaystyle 1\leq i\leq k}$. 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.^[37] The finite field analog can be used as a model for understanding the theorem in the natural numbers.^[38] The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space ${\displaystyle \mathbb {F} _{3}^{n}}$ is known as the cap set problem.

The Green–Tao theorem asserts the prime numbers contain arbitrarily 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.^[39][40]

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

See also

• Problems involving arithmetic progressions
• Ergodic Ramsey theory
• Arithmetic combinatorics
• Szemerédi regularity lemma
• Van der Waerden's theorem
• Hypergraph removal lemma § Proof of Szemerédi's theorem

Notes

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. 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. O'Bryant, Kevin (2011). "Sets of integers that do not contain long arithmetic progressions". Electronic Journal of Combinatorics. 18 (1). arXiv:0811.3057. 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 F.; Sisask, Olof (2020). "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions". arXiv:2007.03528v2 [math.NT].
23. Bloom, Thomas F.; Sisask, Olof (2023). "An improvement to the Kelley-Meka bounds on three-term arithmetic progressions". arXiv:2309.02353v1 [math.NT].
24. Kelley, Zander; Meka, Raghu (2023). "Strong Bounds for 3-Progressions". arXiv:2302.05537v5 [math.NT].
25. Green, Ben; Tao, Terence (2009). "New bounds for Szemeredi's theorem. II. A new bound for r₄(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.
26. Green, Ben; Tao, Terence (2017). "New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r₄(N)". Mathematika. 63 (3): 944–1040. arXiv:1705.01703. doi:10.1112/S0025579317000316. MR 3731312. S2CID 119145424.
27. Leng, James; Sah, Ashwin; Sawhney, Mehtaab (2024). "Improved Bounds for Szemerédi's Theorem". arXiv:2402.17995.
28. Leng, James; Sah, Ashwin; Sawhney, Mehtaab (2023). "Improved bounds for five-term arithmetic progressions". arXiv:2312.10776.
29. Sloman, Leila (2024-08-05). "Grad Students Find Inevitable Patterns in Big Sets of Numbers". Quanta Magazine. Retrieved 2024-08-07.
30. 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.
31. 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.
32. 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.
33. 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.
34. 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.
35. 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.
36. 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.
37. 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.
38. 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.
39. 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.
40. 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

• Tao, Terence (2007). "The ergodic and combinatorial approaches to Szemerédi's theorem". In Granville, Andrew; Nathanson, Melvyn B.; Solymosi, József (eds.). Additive Combinatorics. CRM Proceedings & Lecture Notes. Vol. 43. Providence, RI: American Mathematical Society. pp. 145–193. arXiv:math/0604456. Bibcode:2006math......4456T. ISBN 978-0-8218-4351-2. MR 2359471. Zbl 1159.11005.

External links

• PlanetMath source for initial version of this page Archived 2012-07-16 at the Wayback Machine
• Announcement by Ben Green and Terence Tao – the preprint is available at math.NT/0404188
• Discussion of Szemerédi's theorem (part 1 of 5)
• Ben Green and Terence Tao: Szemerédi's theorem on Scholarpedia
• Weisstein, Eric W. "SzemeredisTheorem". MathWorld.
• Grime, James; Hodge, David (2012). "6,000,000: Endre Szemerédi wins the Abel Prize". Numberphile. Brady Haran. Archived from the original on 2014-01-09. Retrieved 2013-04-02.