Szemerédi's theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 23:30, 4 June 2015

Szemerédi's theorem is a result in arithmetic combinatorics, 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. This conjecture, which became Szemerédi's theorem, generalizes the statement of van der Waerden's theorem.

Statement

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

\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 infinite arithmetic progressions of length k for all positive integers k.

There is an often-used equivalent finitary version of the theorem states that for every positive integer k and real number $\delta \in (0,1]$ , there exists a positive integer

N=N(k,\delta )\,

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

History

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

Finally, the case of general k was settled in 1975, also by Szemerédi,^[5] via an ingenious and complicated extension of the previous combinatorial argument (called "a masterpiece of combinatorial reasoning" by Erdős^[6]). Several further proofs are now known, the most important amongst them being those by Hillel Furstenberg^[7] in 1977, using ergodic theory, and by Timothy Gowers^[8] 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.^[9]

Bounds on N(k, δ)

It is an open problem to determine how large N(k, δ) needs to be. The best known general bounds for N(k, δ) are

C^{\log(1/\delta )^{k-1}}\leq N(k,\delta )\leq 2^{2^{\delta ^{-2^{2^{k+9}}}}}

with C > 1. The lower bound is due to Behrend^[10] (for k = 3) and Rankin,^[11] and the upper bound is due to Gowers.^[8]

For small k, there are tighter bounds than the general case. When k = 3, Bourgain,^[12]^[13] Heath-Brown,^[14] and Szemerédi^[15] provided increasingly lower upper bounds. The current best bound is

N(3,\delta )\leq C^{\delta ^{-1}(\log(1/\delta ))^{5}}

due to Sanders.^[16] Elkin has improved on Behrend's lower bound for k = 3.^[17]^[18]

For k = 4, Green and Tao^[19] proved the bound

N(4,\delta )\leq e^{e^{C(\log(1/\delta ))^{2}}}

.

Extensions and generalizations

A multidimensional generalization of Szemerédi's theorem was first proven by Furstenberg and Katznelson.^[20]

The finitary version of Szemerédi's theorem can be generalized to finite additive groups including vector spaces over finite fields.^[21] The finite field analog can be used as a model for understanding the theorem in the natural numbers.^[22]

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.

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

Notes

^ 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
^ Roth, Klaus Friedrich (1953), "On certain sets of integers", Journal of the London Mathematical Society, 28: 104–109, doi:10.1112/jlms/s1-28.1.104, MR 0051853, Zbl 0050.04002
^ Szemerédi, Endre (1969), "On sets of integers containing no four elements in arithmetic progression", Acta Math. Acad. Sci. Hung., 20: 89–104, doi:10.1007/BF01894569, MR 0245555, Zbl 0175.04301
^ Roth, Klaus Friedrich (1972), "Irregularities of sequences relative to arithmetic progressions, IV", Periodica Math. Hungar., 2: 301–326, doi:10.1007/BF02018670, MR 0369311
^ Szemerédi, Endre (1975), "On sets of integers containing no k elements in arithmetic progression" (PDF), Acta Arithmetica, 27: 199–245, MR 0369312, Zbl t0303.10056 {{citation}}: Check |zbl= value (help)
^ 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
^ Furstenberg, Hillel (1977), "Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions", J. D'Analyse Math., 31: 204–256, doi:10.1007/BF02813304, MR 0498471.
^ ^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
^ 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.). International Congress of Mathematicians. Vol. I. Zürich: European Mathematical Society. pp. 581–608. arXiv:math/0512114. doi:10.4171/022-1/22. MR 2334204.
^ Behrend, Felix A. (1946), "On the sets of integers which contain no three in arithmetic progression", Proceedings of the National Academy of Sciences, 23 (12): 331–332, doi:10.1073/pnas.32.12.331, Zbl 0060.10302
^ Rankin, Robert A. (1962), "Sets of integers containing not more than a given number of terms in arithmetical progression", Proc. Roy. Soc. Edinburgh Sect. A, 65: 332–344, MR 0142526, Zbl 0104.03705
^ Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Funct. Anal., 9 (5): 968–984, doi:10.1007/s000390050105, MR 1726234
^ Bourgain, Jean (2008), "Roth's theorem on progressions revisited", J. Anal. Math., 104 (1): 155–192, doi:10.1007/s11854-008-0020-x, MR 2403433
^ 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
^ Szemerédi, Endre (1990), "Integer sets containing no arithmetic progressions", Acta Math. Hungar., 56 (1–2): 155–158, doi:10.1007/BF01903717, MR 1100788
^ Sanders, Tom (2011), "On Roth's theorem on progressions", Annals of Mathematics, 174 (1): 619–636, doi:10.4007/annals.2011.174.1.20, MR 2811612
^ 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. MR 2823971.
^ Green, Ben; Wolf, Julia (2010). "A note on Elkin's improvement of Behrend's construction". In Chudnovsky, David; Chudnovsky, Gregory (eds.). 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. MR 2744752.
^ 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; Schmidt, Wolfgang; Vaughan, Robert Charles (eds.), 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, ISBN 978-0-521-51538-2, MR 2508645, Zbl 1158.11007
^ 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.
^ 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.
^ 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. MR 3293412.

External links

PlanetMath source for initial version of this page
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.

[erdos_turan-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

[2] Roth, Klaus Friedrich (1953), "On certain sets of integers", Journal of the London Mathematical Society, 28: 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 Math. Acad. Sci. Hung., 20: 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: 301–326, doi:10.1007/BF02018670, MR 0369311

[5] Szemerédi, Endre (1975), "On sets of integers containing no k elements in arithmetic progression" (PDF), Acta Arithmetica, 27: 199–245, MR 0369312, Zbl t0303.10056 {{citation}}: Check |zbl= value (help)

[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", J. D'Analyse Math., 31: 204–256, doi:10.1007/BF02813304, MR 0498471.

[gowers-8] 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

[9] 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.). International Congress of Mathematicians. Vol. I. Zürich: European Mathematical Society. pp. 581–608. arXiv:math/0512114. doi:10.4171/022-1/22. MR 2334204.

[10] Behrend, Felix A. (1946), "On the sets of integers which contain no three in arithmetic progression", Proceedings of the National Academy of Sciences, 23 (12): 331–332, doi:10.1073/pnas.32.12.331, Zbl 0060.10302

[11] Rankin, Robert A. (1962), "Sets of integers containing not more than a given number of terms in arithmetical progression", Proc. Roy. Soc. Edinburgh Sect. A, 65: 332–344, MR 0142526, Zbl 0104.03705

[12] Bourgain, Jean (1999), "On triples in arithmetic progression", Geom. Funct. Anal., 9 (5): 968–984, doi:10.1007/s000390050105, MR 1726234

[13] Bourgain, Jean (2008), "Roth's theorem on progressions revisited", J. Anal. Math., 104 (1): 155–192, doi:10.1007/s11854-008-0020-x, MR 2403433

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

[15] Szemerédi, Endre (1990), "Integer sets containing no arithmetic progressions", Acta Math. Hungar., 56 (1–2): 155–158, doi:10.1007/BF01903717, MR 1100788

[16] Sanders, Tom (2011), "On Roth's theorem on progressions", Annals of Mathematics, 174 (1): 619–636, doi:10.4007/annals.2011.174.1.20, MR 2811612

[17] 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. MR 2823971.

[18] Green, Ben; Wolf, Julia (2010). "A note on Elkin's improvement of Behrend's construction". In Chudnovsky, David; Chudnovsky, Gregory (eds.). 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. MR 2744752.

[19] 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; Schmidt, Wolfgang; Vaughan, Robert Charles (eds.), 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, ISBN 978-0-521-51538-2, MR 2508645, Zbl 1158.11007

[20] 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.

[21] 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.

[22] 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. MR 3293412.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

@@ Line 30: / Line 30: @@
 :<math>N(3,\delta) \leq C^{\delta^{-1}(\log(1/\delta))^5}</math>
-due to [[Tom Sanders (mathematician)|Sanders]].<ref>{{citation|authorlink=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}}</ref> Elkin has improved on Behrend's lower bound for ''k'' = 3.<ref>{{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 | mr=2823971 | issue=1}}</ref><ref>{{cite book | last1=Green | first1=Ben | last2=Wolf | first2=Julia | chapter=A note on Elkin's improvement of Behrend's construction | publisher=Springer | location=New York | mr=2744752 | year=2010 | pages=141-144 | title=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}}</ref>
+due to [[Tom Sanders (mathematician)|Sanders]].<ref>{{citation|authorlink=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}}</ref> Elkin has improved on Behrend's lower bound for ''k'' = 3.<ref>{{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 | mr=2823971 | issue=1}}</ref><ref>{{cite book | last1=Green | first1=Ben | last2=Wolf | first2=Julia | chapter=A note on Elkin's improvement of Behrend's construction | publisher=Springer | location=New York | mr=2744752 | year=2010 | pages=141-144 | title=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}}</ref>
 For ''k'' = 4, Green and Tao<ref>{{citation|last1=Green|first1=Ben|last2=Tao|first2=Terence|chapter=New bounds for Szemeredi's theorem. II. A new bound for <math>r_4(N)</math>|arxiv=math/0610604|year=2009|pages=180-204|publisher=[[Cambridge University Press]]|location=Cambridge|mr=2508645|title=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}}</ref> proved the bound