Szemerédi's theorem

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

:$\backslash limsup\_\{n\; \backslash to\; \backslash infty\}\backslash frac$

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 $\backslash delta\; \backslash in\; (0,\; 1]$, there exists a positive integer

:$N\; =\; N(k,\backslash delta)$

such that every subset of {1, 2, ..., N} of size at least $\backslash 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

:$r\_k(N)\; =\; o(N).$

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

Van der Waerden's theorem, a precursor of Szemerédi's theorem, was proved 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{{cite journal|author-link=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=On certain sets of integers|journal=Journal of the London Mathematical Society|volume=28|pages=104–109|year=1953|zbl=0050.04002|mr=0051853|doi=10.1112/jlms/s1-28.1.104|issue=1}} via an adaptation of the Hardy–Littlewood circle method. Szemerédi{{cite journal|author-link=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no four elements in arithmetic progression|journal=Acta Mathematica Academiae Scientiarum Hungaricae|volume=20|pages=89–104|year=1969|issue=1–2|zbl=0175.04301|mr=0245555|doi=10.1007/BF01894569|doi-access=free}} next proved the case k = 4 through combinatorics. Using an approach similar to the one he used for the case k = 3, Roth{{cite journal|author-link=Klaus Friedrich Roth|first=Klaus Friedrich|last=Roth|title=Irregularities of sequences relative to arithmetic progressions, IV|journal=Periodica Math. Hungar.|volume=2|pages=301–326|year=1972|issue=1–4|mr=0369311|doi=10.1007/BF02018670|s2cid=126176571}} gave a second proof for k = 4 in 1972.

The general case was settled in 1975, also by Szemerédi,{{cite journal|author-link=Endre Szemerédi|first=Endre|last=Szemerédi|title=On sets of integers containing no k elements in arithmetic progression|journal=Acta Arithmetica|volume=27|pages=199–245|year=1975|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf|zbl=0303.10056|mr=0369312|doi=10.4064/aa-27-1-199-245|doi-access=free}} who developed an ingenious and complicated extension of his previous combinatorial argument for k = 4 (called "a masterpiece of combinatorial reasoning" by Erdős{{cite encyclopedia|last=Erdős|first=Paul|chapter=Some of My Favorite Problems and Results|pages=51–70|year=2013|encyclopedia=The Mathematics of Paul Erdős I|doi=10.1007/978-1-4614-7258-2_3|mr=1425174|editor1-last=Graham|editor1-first=Ronald L.|editor2-last=Nešetřil|editor2-first=Jaroslav|editor3-last=Butler|editor3-first=Steve|edition=Second|isbn=978-1-4614-7257-5|publisher=Springer|location=New York}}). Several other proofs are now known, the most important being those by Hillel Furstenberg{{cite journal|author-link=Hillel Furstenberg|first=Hillel|last=Furstenberg|title=Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions|journal=Journal d'Analyse Mathématique|volume=31|pages=204–256|year=1977|mr=0498471|doi=10.1007/BF02813304|doi-access=free|s2cid=120917478}}.{{cite journal | last1=Furstenberg | first1=Hillel | last2=Katznelson | first2=Yitzhak | last3=Ornstein | first3=Donald Samuel | title=The ergodic theoretical proof of Szemerédi's theorem | journal=Bull. Amer. Math. Soc. | year=1982 | volume=7 | issue=3 | pages=527–552 | mr=0670131 | doi=10.1090/S0273-0979-1982-15052-2| doi-access=free }} in 1977, using ergodic theory, and by Timothy Gowers{{cite journal|author-link=Timothy Gowers|first=Timothy|last=Gowers|title=A new proof of Szemerédi's theorem|journal=Geom. Funct. Anal.|volume=11|issue=3|pages=465–588|url=http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi|year=2001|mr=1844079|doi=10.1007/s00039-001-0332-9|s2cid=124324198}} 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.{{cite encyclopedia | last=Tao | first=Terence | title=Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006 | chapter=The dichotomy between structure and randomness, arithmetic progressions, and the primes | arxiv=math/0512114 | encyclopedia=International Congress of Mathematicians | volume=1 | publisher=European Mathematical Society | location=Zürich | year=2007 | pages=581–608 | mr=2334204 | doi=10.4171/022-1/22 | isbn=978-3-03719-022-7 | editor1-first=Marta | editor1-last=Sanz-Solé | editor2-first=Javier | editor2-last=Soria | editor3-first=Juan Luis | editor3-last=Varona | editor4-first=Joan | editor4-last=Verdera }}

{{See also|Erdős conjecture on arithmetic progressions#Progress and related results|Roth's theorem on arithmetic progressions#Improving bounds|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

:$CN\backslash exp\backslash left(-n2^\{(n\; -\; 1)/2\}\backslash sqrt[n]\{\backslash log\; N\}\; +\; \backslash frac\{1\}\{2n\}\backslash log\; \backslash log\; N\backslash right)\; \backslash leq\; r\_k(N)\; \backslash leq\; \backslash frac\{N\}\{(\backslash log\; \backslash log\; N)^\{2^\{-2^\{k\; +\; 9\}\}\}\},$

where $n\; =\; \backslash lceil\; \backslash log\; k\backslash rceil$. The lower bound is due to O'Bryant{{cite journal | last=O'Bryant | first=Kevin | title=Sets of integers that do not contain long arithmetic progressions | journal=Electronic Journal of Combinatorics | year=2011 | volume=18 | issue=1 | doi=10.37236/546 | url=http://www.combinatorics.org/ojs/index.php/eljc/article/download/v18i1p59/pdf | mr=2788676| doi-access=free | arxiv=0811.3057 }} building on the work of Behrend,{{cite journal|author-link=Felix Behrend|first=Felix A.|last=Behrend|title=On the sets of integers which contain no three terms in arithmetic progression|journal=Proceedings of the National Academy of Sciences|volume=32|issue=12|pages=331–332|year=1946|zbl=0060.10302|doi=10.1073/pnas.32.12.331|doi-access=free|mr=0018694|pmc=1078964|pmid=16578230|bibcode=1946PNAS...32..331B}} Rankin,{{cite journal|author-link=Robert A. Rankin|first=Robert A.|last=Rankin|title=Sets of integers containing not more than a given number of terms in arithmetical progression|journal=Proc. R. Soc. Edinburgh Sect. A|volume=65|pages=332–344|year=1962|zbl=0104.03705|mr=0142526}} and Elkin.{{cite journal | last=Elkin | first=Michael | title=An improved construction of progression-free sets | journal=Israel Journal of Mathematics | year=2011 | volume=184 | pages=93–128 | doi=10.1007/s11856-011-0061-1 | doi-access=free | mr=2823971 | issue=1| arxiv=0801.4310 }}{{cite encyclopedia | last1=Green | first1=Ben | last2=Wolf | first2=Julia| title=Additive Number Theory |author2-link= Julia Wolf | chapter=A note on Elkin's improvement of Behrend's construction | publisher=Springer | location=New York | mr=2744752 | year=2010 | pages=141–144 | encyclopedia=Additive number theory. Festschrift in honor of the sixtieth birthday of Melvyn B. Nathanson | editor1-last=Chudnovsky | editor1-first=David | editor2-last=Chudnovsky | editor2-first=Gregory | isbn=978-0-387-37029-3 | doi=10.1007/978-0-387-68361-4_9| arxiv=0810.0732 | s2cid=10475217 }} The upper bound is due to Gowers.

For small k, there are tighter bounds than the general case. When k = 3, Bourgain,{{cite journal|author-link=Jean Bourgain|first=Jean|last=Bourgain|title=On triples in arithmetic progression|journal=Geom. Funct. Anal.|volume=9|issue=5|year=1999|pages=968–984|mr=1726234|doi=10.1007/s000390050105|s2cid=392820}}{{cite journal|author-link=Jean Bourgain|first=Jean|last=Bourgain|title=Roth's theorem on progressions revisited|volume=104|year=2008|pages=155–192|journal=Journal d'Analyse Mathématique|mr=2403433|doi=10.1007/s11854-008-0020-x|doi-access=free|issue=1|s2cid=16985451}} Heath-Brown,{{cite journal|author-link=D. R. Heath-Brown|first=Roger|last=Heath-Brown|title=Integer sets containing no arithmetic progressions|volume=35|journal=Journal of the London Mathematical Society|issue=3|year=1987|mr=889362|pages=385–394|doi=10.1112/jlms/s2-35.3.385}} Szemerédi,{{cite journal|first=Endre|last=Szemerédi|title=Integer sets containing no arithmetic progressions|journal=Acta Mathematica Hungarica|year=1990|volume=56|issue=1–2|doi=10.1007/BF01903717|doi-access=free|mr=1100788|pages=155–158}} Sanders,{{cite journal|author-link=Tom Sanders (mathematician)|first=Tom|last=Sanders|title=On Roth's theorem on progressions|journal=Annals of Mathematics|volume=174|issue=1|year=2011|pages=619–636|mr=2811612|doi=10.4007/annals.2011.174.1.20|arxiv=1011.0104|s2cid=53331882}} and Bloom{{cite journal | last=Bloom | first=Thomas F. | title=A quantitative improvement for Roth's theorem on arithmetic progressions | arxiv=1405.5800 | year=2016 | issue=3 | volume=93 | pages=643–663 | journal=Journal of the London Mathematical Society |series=Second Series | mr=3509957 | doi=10.1112/jlms/jdw010| s2cid=27536138 }} established progressively smaller upper bounds, and Bloom and Sisask then proved the first bound that broke the so-called "logarithmic barrier".{{cite arXiv |last1=Bloom |first1=Thomas F. |last2=Sisask |first2=Olof |title=Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions |year=2020 |class=math.NT |eprint=2007.03528v2 }} The current best bounds are

:$N\; 2^\{-\backslash sqrt\{8\backslash log\; N\}\}\; \backslash leq\; r\_3(N)\; \backslash leq\; N\; e^\{-c(\backslash log\; N)^\{1/9\}\}$, for some constant $c>0$,

respectively due to O'Bryant, and Bloom and Sisask{{cite arXiv |last1=Bloom |first1=Thomas F. |last2=Sisask |first2=Olof |title=An improvement to the Kelley-Meka bounds on three-term arithmetic progressions |year=2023 |class=math.NT |eprint=2309.02353v1 }} (the latter built upon the breakthrough result of Kelley and Meka,{{cite arXiv |last1=Kelley |first1=Zander |last2=Meka |first2=Raghu |title=Strong Bounds for 3-Progressions |year=2023 |class=math.NT |eprint=2302.05537v5 }} who obtained the same upper bound, with "1/9" replaced by "1/12").

For k = 4, Green and Tao{{cite encyclopedia|last1=Green|first1=Ben|last2=Tao|first2=Terence|title=New bounds for Szemeredi's theorem, II: A new bound for r_4(N)|chapter=New bounds for Szemeredi's theorem. II. A new bound for r₄(N)|arxiv=math/0610604|year=2009|pages=180–204|publisher=Cambridge University Press|location=Cambridge|mr=2508645|encyclopedia=Analytic number theory. Essays in honour of Klaus Roth on the occasion of his 80th birthday|isbn=978-0-521-51538-2|editor1-last=Chen|editor1-first=William W. L.|editor2-last=Gowers|editor2-first=Timothy|editor2-link=Timothy Gowers|editor3-last=Halberstam|editor3-first=Heini|editor3-link=Heini Halberstam|editor4-last=Schmidt|editor4-link=Wolfgang M. Schmidt|editor4-first=Wolfgang|editor5-last=Vaughan|editor5-first=Robert Charles|editor5-link=Bob Vaughan|zbl=1158.11007|bibcode=2006math.....10604G}}{{cite journal| title=New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r₄(N) | year=2017 | last1=Green | first1=Ben | last2=Tao|first2=Terence|arxiv=1705.01703|mr=3731312|journal=Mathematika|volume=63|issue=3|pages=944–1040|doi=10.1112/S0025579317000316| s2cid=119145424 }} proved that

:$r\_4(N)\; \backslash leq\; C\backslash frac\{N\}\{(\backslash log\; N)^c\}$

For k=5 in 2023 and k≥5 in 2024 Leng, Sah and Sawhney proved in preprints {{Cite arXiv |eprint=2402.17995 |first1=James |last1=Leng |first2=Ashwin |last2=Sah |title=Improved Bounds for Szemerédi's Theorem |date=2024 |last3=Sawhney |first3=Mehtaab|class=math.CO }}{{Cite arXiv |eprint=2312.10776 |first1=James |last1=Leng |first2=Ashwin |last2=Sah |title=Improved bounds for five-term arithmetic progressions |date=2023 |last3=Sawhney |first3=Mehtaab|class=math.NT }}{{Cite web |last=Sloman |first=Leila |date=2024-08-05 |title=Grad Students Find Inevitable Patterns in Big Sets of Numbers |url=https://www.quantamagazine.org/grad-students-find-inevitable-patterns-in-big-sets-of-numbers-20240805/ |access-date=2024-08-07 |website=Quanta Magazine |language=en}} that:

:$r\_k(N)\; \backslash leq\; CN\backslash exp(-(\backslash log\backslash log\; N)^c)$

A multidimensional generalization of Szemerédi's theorem was first proven by Hillel Furstenberg and Yitzhak Katznelson using ergodic theory.{{cite journal | last1=Furstenberg | first1=Hillel | author1-link=Hillel Furstenberg | last2=Katznelson | first2=Yitzhak | author2-link=Yitzhak Katznelson | title=An ergodic Szemerédi theorem for commuting transformations | journal=Journal d'Analyse Mathématique | doi=10.1007/BF02790016 | doi-access=free | mr=531279 | volume=38 | year=1978 | pages=275–291 | issue=1| s2cid=123386017 }} Timothy Gowers,{{cite journal | last=Gowers | first=Timothy | author-link=Timothy Gowers | title=Hypergraph regularity and the multidimensional Szemerédi theorem | journal=Annals of Mathematics | volume=166 | year=2007 | issue=3 | pages=897–946 | doi=10.4007/annals.2007.166.897 | mr=2373376| arxiv=0710.3032 | s2cid=56118006 }} Vojtěch Rödl and Jozef Skokan{{cite journal | last1=Rödl | first1=Vojtěch | author1-link=Vojtěch Rödl | last2=Skokan | first2=Jozef | title=Regularity lemma for k-uniform hypergraphs | journal= Random Structures Algorithms | volume=25 | year=2004 | issue=1 | pages=1–42 | mr=2069663 | doi=10.1002/rsa.20017| s2cid=7458739 }}{{cite journal | last1=Rödl | first1=Vojtěch | author1-link=Vojtěch Rödl | last2=Skokan | first2=Jozef | title=Applications of the regularity lemma for uniform hypergraphs | journal=Random Structures Algorithms | volume=28 | year=2006 | issue=2 | pages=180–194 | mr=2198496 | doi=10.1002/rsa.20108| s2cid=18203198 | url=http://www.math.emory.edu/technical-reports/techrep-00076.pdf }} with Brendan Nagle, Rödl, and Mathias Schacht,{{cite journal | last1=Nagle | first1=Brendan | last2=Rödl | first2=Vojtěch | author2-link=Vojtěch Rödl | last3=Schacht | first3=Mathias|author3-link=Mathias Schacht | title=The counting lemma for regular k-uniform hypergraphs | journal=Random Structures Algorithms | volume=28 | year=2006 | issue=2 | pages=113–179 | doi=10.1002/rsa.20117 | mr=2198495| s2cid=14126774 }} and Terence Tao{{cite journal | last=Tao | first=Terence | authorlink=Terence Tao | title=A variant of the hypergraph removal lemma | journal=Journal of Combinatorial Theory | series=Series A | volume=113 | year=2006 | issue=7 | pages=1257–1280 | doi=10.1016/j.jcta.2005.11.006 | doi-access=free | mr=2259060| arxiv=math/0503572 }} provided combinatorial proofs.

Alexander Leibman and Vitaly Bergelson{{cite journal | first1=Vitaly | last1=Bergelson | author1-link=Vitaly Bergelson | first2=Alexander | last2=Leibman | title=Polynomial extensions of van der Waerden's and Szemerédi's theorems | journal=Journal of the American Mathematical Society | volume=9 | issue=3 | year=1996 | pages=725–753 | mr=1325795 | doi=10.1090/S0894-0347-96-00194-4| doi-access=free }} generalized Szemerédi's to polynomial progressions: If $A\; \backslash subset\; \backslash mathbb\{N\}$ is a set with positive upper density and $p\_1(n),p\_2(n),\backslash dotsc,p\_k(n)$ are integer-valued polynomials such that $p\_i(0)\; =\; 0$, then there are infinitely many $u,\; n\; \backslash in\; \backslash mathbb\{Z\}$ such that $u\; +\; p\_i(n)\; \backslash in\; A$ for all $1\; \backslash leq\; i\; \backslash 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.{{cite journal | last1=Furstenberg | first1=Hillel | last2=Katznelson | author1-link=Hillel Furstenberg | first2=Yitzhak | author2-link=Yitzhak Katznelson | title=A density version of the Hales–Jewett theorem | journal=Journal d'Analyse Mathématique | volume=57 | year=1991 | pages=64–119 | mr=1191743 | issue=1 | doi=10.1007/BF03041066 | doi-access=free | s2cid=123036744 }} The finite field analog can be used as a model for understanding the theorem in the natural numbers.{{cite journal | first=Julia | last=Wolf | title=Finite field models in arithmetic combinatorics—ten years on | year=2015 | volume=32 | pages=233–274 | journal=Finite Fields and Their Applications | doi=10.1016/j.ffa.2014.11.003 | mr=3293412| doi-access=free | hdl=1983/d340f853-0584-49c8-a463-ea16ee51ce0f | hdl-access=free }} The problem of obtaining bounds in the k=3 case of Szemerédi's theorem in the vector space $\backslash 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.{{cite journal | first1=David | last1=Conlon | author1-link=David Conlon | first2=Jacob | last2=Fox | author2-link=Jacob Fox | first3=Yufei | last3=Zhao | title=A relative Szemerédi theorem | arxiv=1305.5440 | year=2015 | mr=3361771 | volume=25 | issue=3 | pages=733–762 | doi=10.1007/s00039-015-0324-9 | doi-access=free | journal=Geometric and Functional Analysis| s2cid=14398869 }}{{cite journal | first=Yufei | last=Zhao | title=An arithmetic transference proof of a relative Szemerédi theorem | journal=Mathematical Proceedings of the Cambridge Philosophical Society | volume=156 | year=2014 | pages=255–261 | issue=2 | mr=3177868 | doi=10.1017/S0305004113000662| arxiv=1307.4959 | bibcode=2014MPCPS.156..255Z | s2cid=119673319 }}

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

{{div col|colwidth=20em}}

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

{{div col end}}

{{reflist|colwidth=30em}}

• {{cite encyclopedia | first=Terence | last=Tao | author-link=Terence Tao | chapter=The ergodic and combinatorial approaches to Szemerédi's theorem | pages=145–193 | editor1-first=Andrew | editor1-last=Granville | editor2-first=Melvyn B. | editor2-last=Nathanson| editor3-first=József | editor3-last=Solymosi | encyclopedia=Additive Combinatorics | series=CRM Proceedings & Lecture Notes | volume=43 | publisher=American Mathematical Society | year=2007 | isbn=978-0-8218-4351-2 | zbl=1159.11005 | mr=2359471 | arxiv=math/0604456 | location=Providence, RI| bibcode=2006math......4456T }}

{{div col|colwidth=20em}}

• [http://planetmath.org/encyclopedia/SzemeredisTheorem.html PlanetMath source for initial version of this page] {{Webarchive|url=https://web.archive.org/web/20120716181648/http://planetmath.org/encyclopedia/SzemeredisTheorem.html |date=2012-07-16 }}
• [https://www.math.ucla.edu/~tao/whatsnew.html Announcement by Ben Green and Terence Tao] – the preprint is available at [http://arxiv.org/abs/math/0404188 math.NT/0404188]
• [http://in-theory.blogspot.com/2006/06/szemeredis-theorem.html Discussion of Szemerédi's theorem (part 1 of 5)]
• Ben Green and Terence Tao: [http://www.scholarpedia.org/article/Szemeredi%27s_Theorem Szemerédi's theorem] on Scholarpedia
• {{MathWorld|SzemeredisTheorem|SzemeredisTheorem}}
• {{cite web|last=Grime|first=James|title=6,000,000: Endre Szemerédi wins the Abel Prize|url=http://www.numberphile.com/videos/abel_prize.html|work=Numberphile|year=2012|publisher=Brady Haran|author2=Hodge, David|access-date=2013-04-02|archive-date=2014-01-09|archive-url=https://web.archive.org/web/20140109114940/http://numberphile.com/videos/abel_prize.html|url-status=dead}}

{{div col end}}

{{DEFAULTSORT:Szemeredi's theorem}}

Category:Additive combinatorics

Category:Ramsey theory

Category:Theorems in combinatorics

Category:Theorems in number theory