Satz von Szemerédi

Der Satz von Szemerédi in der arithmetischen Kombinatorik, Der Satz von Szemerédi ist ein Ergebnis über arithmetische Progressionen in Teilmengen der ganzen Zahlen. Im 1936, Erdős und Turán vermuteten[1] dass jede Menge von ganzen Zahlen A mit positiver natürlicher Dichte eine arithmetische Progression mit k-Termen für jedes k enthält. Endre Szemerédi bewies die Vermutung in 1975.

Inhalt 1 Aussage 2 Geschichte 3 Quantitative Grenzen 4 Erweiterungen und Verallgemeinerungen 5 Siehe auch 6 Anmerkungen 7 Weiterlesen 8 External links Statement A subset A of the natural numbers is said to have positive upper density if {displaystyle limsup _{nto infty }{frac {|häufig {1,2,3,Punktec ,n}|}{n}}>0} .

Der Satz von Szemerédi besagt, dass eine Teilmenge der natürlichen Zahlen mit positiver oberer Dichte unendlich viele arithmetische Progressionen der Länge k für alle positiven ganzen Zahlen k enthält.

Eine häufig verwendete äquivalente endliche Version des Satzes besagt, dass für jede positive ganze Zahl k und reelle Zahl {displaystyle delta in (0,1]} , es gibt eine positive ganze Zahl {Anzeigestil N=N(k,Delta )} so dass jede Teilmenge von {1, 2, ..., N} der Größe mindestens δN enthält eine arithmetische Folge der Länge k.

Eine andere Formulierung verwendet die Funktion rk(N), die Größe der größten Teilmenge von {1, 2, ..., N} ohne arithmetische Progression der Länge k. Der Satz von Szemerédi entspricht der asymptotischen Grenze {Anzeigestil r_{k}(N)=o(N)} .

Das ist, rk(N) wächst weniger als linear mit N.

History Van der Waerden's theorem, der Vorläufer des Satzes von Szemerédi, wurde bewiesen in 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. Der Fall k = 3, bekannt als Satz von Roth, wurde gegründet in 1953 von Klaus Roth[2] über eine Adaption der Hardy-Littlewood-Kreismethode. Endre Szemeredi[3] bewies den Fall k = 4 durch Kombinatorik. Unter Verwendung eines ähnlichen Ansatzes wie für den Fall k = 3, Roth[4] gab einen zweiten Beweis dafür in 1972.

Der allgemeine Fall wurde beigelegt 1975, auch von Szemerédi,[5] der eine geniale und komplizierte Erweiterung seines vorherigen kombinatorischen Arguments für k = entwickelt hat 4 (genannt "ein Meisterwerk des kombinatorischen Denkens" von Erdős[6]). Mehrere andere Beweise sind jetzt bekannt, die wichtigsten sind die von Hillel Fürstenberg[7][8] in 1977, unter Verwendung der Ergodentheorie, und von Timothy Gowers[9] in 2001, unter Verwendung von Fourier-Analyse und Kombinatorik. Terence Tao hat die verschiedenen Beweise des Satzes von Szemerédi a genannt "Rosetta Stone" zur Verbindung verschiedener Bereiche der Mathematik.[10] Quantitative bounds It is an open problem to determine the exact growth rate of rk(N). Die bekanntesten allgemeinen Schranken sind {Displaystyle CNexp links(-n2^{(n-1)/2}{quadrat[{n}]{Protokoll N}}+{frac {1}{2n}}log log Nright)leq r_{k}(N)leq {frac {N}{(Protokoll Protokoll N)^{2^{-2^{k+9}}}}},} wo {displaystyle n=lceil log krceil } . Die untere Grenze ist O'Bryant zu verdanken[11] aufbauend auf der Arbeit von Behrend,[12] Rankin,[13] und Elkin.[14][15] Die Obergrenze liegt bei Gowers.[9] Für kleine k, es gibt engere Grenzen als im allgemeinen Fall. Wenn k = 3, Bourgain,[16][17] Heath-Brown,[18] Sie gehört dir,[19] und Sander[20] lieferten immer kleinere Obergrenzen. Die aktuellen Bestgrenzen sind {Anzeigestil N2^{-{quadrat {8Protokoll N}}}leq r_{3}(N)leq C{frac {(Protokoll Protokoll N)^{4}}{Protokoll N}}N} wegen O'Bryant[11] und Blümchen[21] beziehungsweise.

Für k = 4, Grün und Tao[22][23] geprüft, dass {Anzeigestil r_{4}(N)leq C{frac {N}{(Protokoll N)^{c}}}} 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.[24] Timothy Gowers,[25] Vojtěch Rödl und Jozef Skokan[26][27] mit Brendan Nagle, Rödl, und Matthias Schacht,[28] und Terence Tao[29] kombinatorische Beweise geliefert.

Alexander Leibmann und Vitaly Bergelson[30] verallgemeinerte Szemerédi auf polynomiale Progressionen: Wenn {displaystyle Asubset mathbb {N} } ist eine Menge mit positiver oberer Dichte und {Anzeigestil p_{1}(n),p_{2}(n),Punktec ,p_{k}(n)} sind ganzzahlige Polynome, so dass {Anzeigestil p_{ich}(0)=0} , dann gibt es unendlich viele {Anzeigestil u,nin mathbb {Z} } so dass {Anzeigestil u+p_{ich}(n)in einem} für alle {Anzeigestil 1leq ileq k} . Das Ergebnis von Leibman und Bergelson gilt auch in einem mehrdimensionalen Umfeld.

Die endliche Version des Satzes von Szemerédi kann auf endliche additive Gruppen einschließlich Vektorräumen über endlichen Feldern verallgemeinert werden.[31] Das Finite-Feld-Analogon kann als Modell zum Verständnis des Theorems in den natürlichen Zahlen verwendet werden.[32] Das Problem, Grenzen im Fall von k = 3 des Satzes von Szemerédi im Vektorraum zu erhalten {Anzeigestil mathbb {F} _{3}^{n}} ist als Cap-Set-Problem bekannt.

Das Green-Tao-Theorem behauptet, dass die Primzahlen beliebig lange arithmetische Progressionen enthalten. Es wird durch den Satz von Szemerédi nicht impliziert, weil die Primzahlen eine Dichte haben 0 in den natürlichen Zahlen. Als Teil ihres Beweises, Ben Green und Tao stellten eine vor "relativ" Satz von Szemerédi, der für Teilmengen der ganzen Zahlen gilt (auch die mit 0 Dichte) bestimmte Pseudozufallsbedingungen erfüllen. Ein allgemeineres relatives Szemerédi-Theorem wurde seitdem von David Conlon angegeben, Jakob Fuchs, und Yufei Zhao.[33][34] Die Vermutung von Erdő über arithmetische Progressionen würde sowohl den Satz von Szemerédi als auch den Satz von Green-Tao implizieren.

Siehe auch Probleme mit arithmetischen Progressionen Ergodische Ramsey-Theorie Arithmetische Kombinatorik Lemma der Szemerédi-Regularität Anmerkungen ^ Erdős, Paul; Turan, Paul (1936). "Über einige Folgen von ganzen Zahlen" (Pdf). Zeitschrift der London Mathematical Society. 11 (4): 261–264. doi:10.1112/jlms/s1-11.4.261. HERR 1574918. ^ Roth, Klaus Friedrich (1953). "Auf bestimmten Mengen von ganzen Zahlen". Zeitschrift der London Mathematical Society. 28 (1): 104–109. doi:10.1112/jlms/s1-28.1.104. HERR 0051853. Zbl 0050.04002. ^ Szemeredi, Veränderung (1969). "Über Mengen von ganzen Zahlen, die keine vier Elemente in arithmetischer Folge enthalten". Mathematische Zeitschrift der Ungarischen Akademie der Wissenschaften. 20 (1–2): 89–104. doi:10.1007/BF01894569. HERR 0245555. Zbl 0175.04301. ^ Roth, Klaus Friedrich (1972). "Unregelmäßigkeiten von Folgen in Bezug auf arithmetische Progressionen, IV". Zeitschrift Math. ungarisch. 2 (1–4): 301–326. doi:10.1007/BF02018670. HERR 0369311. S2CID 126176571. ^ Szemeredi, Veränderung (1975). "Auf Mengen von ganzen Zahlen, die keine k Elemente in arithmetischer Folge enthalten" (Pdf). Zeitschrift für Arithmetik. 27: 199–245. doi:10.4064/aa-27-1-199-245. HERR 0369312. Zbl 0303.10056. ^ Wald, Paul (2013). "Einige meiner Lieblingsprobleme und Ergebnisse". Bei Graham, Roland L.; Er hat nicht geschont, Jaroslav; Diener, Steve (Hrsg.). Die Mathematik von Paul Erdős I (Zweite Aufl.). New York: Springer. pp. 51–70. doi:10.1007/978-1-4614-7258-2_3. ISBN 978-1-4614-7257-5. HERR 1425174. ^ Fürstenberg, Hillel (1977). "Ergodisches Verhalten diagonaler Maße und ein Satz von Szemerédi über arithmetische Progressionen". J. d’Analyse Math. 31: 204–256. doi:10.1007/BF02813304. HERR 0498471. S2CID 120917478.. ^ Fürstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "Der ergodisch-theoretische Beweis des Satzes von Szemerédi". Stier. Amer. Mathematik. Soc. 7 (3): 527–552. doi:10.1090/S0273-0979-1982-15052-2. HERR 0670131. ^ Nach oben springen: a b Gowers, Timotheus (2001). "Ein neuer Beweis des Satzes von Szemerédi". Geom. Funkt. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. HERR 1844079. S2CID 124324198. ^ Tao, Terenz (2007). "Die Dichotomie zwischen Struktur und Zufälligkeit, arithmetische Progressionen, und die Primzahlen". In Sanz-Sole, Marta; Soria, Javier; Männlich, Juan Luis; Grün, Johanna (Hrsg.). Proceedings of the International Congress of Mathematicians Madrid, 22.–30. August, 2006. Internationaler Kongress der Mathematiker. Vol. 1. Zürich: Europäische Mathematische Gesellschaft. pp. 581–608. arXiv:math/0512114. doi:10.4171/022-1/22. ISBN 978-3-03719-022-7. HERR 2334204. ^ Nach oben springen: a b O’Bryant, Kevin (2011). "Mengen von ganzen Zahlen, die keine langen arithmetischen Progressionen enthalten". Elektronische Zeitschrift für Kombinatorik. 18 (1). doi:10.37236/546. HERR 2788676. ^ Behrend, Felix A. (1946). "Über die Mengen ganzer Zahlen, die keine drei Glieder in arithmetischer Folge enthalten". Proceedings of the National Academy of Sciences. 32 (12): 331–332. Bibcode:1946PNAS...32..331B. doi:10.1073/pnas.32.12.331. HERR 0018694. PMC 1078964. PMID 16578230. Zbl 0060.10302. ^ Rankin, Robert A. (1962). "Mengen von ganzen Zahlen, die nicht mehr als eine bestimmte Anzahl von Gliedern in arithmetischer Folge enthalten". Proz. Roy. Soc. Edinburgh Sekte. EIN. 65: 332–344. HERR 0142526. Zbl 0104.03705. ^ Elkin, Michael (2011). "Eine verbesserte Konstruktion progressionsfreier Sätze". Israelisches Journal für Mathematik. 184 (1): 93–128. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. HERR 2823971. ^ Grün, Ben; Wolf, Julia (2010). "Eine Anmerkung zu Elkins Verbesserung von Behrends Konstruktion". In Chudnowski, David; Chudnovsky, Gregor (Hrsg.). Additive Zahlentheorie. Additive Zahlentheorie. Festschrift zu Ehren des sechzigsten Geburtstages von 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. HERR 2744752. S2CID 10475217. ^ Burgan, Jean (1999). "Über Tripel in der arithmetischen Progression". Geom. Funkt. Anal. 9 (5): 968–984. doi:10.1007/s000390050105. HERR 1726234. S2CID 392820. ^ Burgan, Jean (2008). "Roths Theorem über Progressionen noch einmal aufgegriffen". J. Anal. Mathematik. 104 (1): 155–192. doi:10.1007/s11854-008-0020-x. HERR 2403433. S2CID 16985451. ^ Heath-Brown, Roger (1987). "Ganzzahlmengen, die keine arithmetischen Progressionen enthalten". Zeitschrift der London Mathematical Society. 35 (3): 385–394. doi:10.1112/jlms/s2-35.3.385. HERR 0889362. ^ Szemeredi, Veränderung (1990). "Ganzzahlmengen, die keine arithmetischen Progressionen enthalten". Ungarisches Mathematisches Journal. 56 (1–2): 155–158. doi:10.1007/BF01903717. HERR 1100788. ^ Sanders, Tom (2011). "Zum Progressionssatz von Roth". Annalen der Mathematik. 174 (1): 619–636. arXiv:1011.0104. doi:10.4007/annalen.2011.174.1.20. HERR 2811612. S2CID 53331882. ^ Blüte, Thomas F. (2016). "Eine quantitative Verbesserung des Satzes von Roth über arithmetische Progressionen". Zeitschrift der London Mathematical Society. Zweite Serie. 93 (3): 643–663. arXiv:1405.5800. doi:10.1112/jlms/jdw010. HERR 3509957. S2CID 27536138. ^ Grün, Ben; Tao, Terenz (2009). "Neue Schranken für den Satz von Szemeredi. II. Eine neue Grenze für r4(N)". In Chen, Wilhelm W. L.; Gowers, Timotheus; Halberstam, Hi; Schmidt, Wolfgang; Vaughan, Robert Karl (Hrsg.). Neue Schranken für den Satz von Szemeredi, II: Eine neue Grenze für r_4(N). Analytische Zahlentheorie. Essays zu Ehren von Klaus Roth anlässlich seines 80. Geburtstages. Cambridge: Cambridge University Press. pp. 180–204. arXiv:math/0610604. Bibcode:2006Mathematik.....10604G. ISBN 978-0-521-51538-2. HERR 2508645. Zbl 1158.11007. ^ Grün, Ben; Tao, Terenz (2017). "Neue Schranken für den Satz von Szemerédi, III: Eine polylogarithmische Schranke für r4(N)". Mathematik. 63 (3): 944–1040. arXiv:1705.01703. doi:10.1112/S0025579317000316. HERR 3731312. ^ Fürstenberg, Hillel; Katznelson, Yitzhak (1978). "Ein ergodisches Szemerédi-Theorem für Pendeltransformationen". Zeitschrift für mathematische Analyse. 38 (1): 275–291. doi:10.1007/BF02790016. HERR 0531279. S2CID 123386017. ^ Gowers, Timotheus (2007). "Hypergraphenregularität und das mehrdimensionale Szemerédi-Theorem". Annalen der Mathematik. 166 (3): 897–946. arXiv:0710.3032. doi:10.4007/Annalen.2007.166.897. HERR 2373376. S2CID 56118006. ^ Rödl, Vojtěch; Jumper, Joseph (2004). "Regularitätslemma für k-einheitliche Hypergraphen". Algorithmen für zufällige Strukturen. 25 (1): 1–42. doi:10.1002/rsa.20017. HERR 2069663. ^ Rödl, Vojtěch; Jumper, Joseph (2006). "Anwendungen des Regularitätslemmas für gleichförmige Hypergraphen" (Pdf). Algorithmen für zufällige Strukturen. 28 (2): 180–194. doi:10.1002/rsa.20108. HERR 2198496. ^ Nagel, Brendan; Rödl, Vojtěch; Schacht, Matthias (2006). "Das Zähllemma für reguläre k-einheitliche Hypergraphen". Algorithmen für zufällige Strukturen. 28 (2): 113–179. doi:10.1002/rsa.20117. HERR 2198495. ^ Tao, Terenz (2006). "Eine Variante des Lemma zum Entfernen von Hypergraphen". Zeitschrift für kombinatorische Theorie, Serie A. 113 (7): 1257–1280. arXiv:math/0503572. doi:10.1016/j.jcta.2005.11.006. HERR 2259060. ^ Bergelson, Vitaly; Leibmann, Alexander (1996). "Polynomische Erweiterungen der Sätze von van der Waerden und Szemerédi". Zeitschrift der American Mathematical Society. 9 (3): 725–753. doi:10.1090/S0894-0347-96-00194-4. HERR 1325795. ^ Fürstenberg, Hillel; Katznelson, Yitzhak (1991). "Eine Dichteversion des Hales-Jewett-Theorems". Zeitschrift für mathematische Analyse. 57 (1): 64–119. doi:10.1007/BF03041066. HERR 1191743. S2CID 123036744. ^ Wolf, Julia (2015). "Endliche Feldmodelle in der arithmetischen Kombinatorik – zehn Jahre später". Endliche Felder und ihre Anwendungen. 32: 233–274. doi:10.1016/j.ffa.2014.11.003. HERR 3293412. ^ Conlon, David; Fuchs, Jacob; Zhao, Yufei (2015). "Der relative Satz von Szemerédi". Geometrische und Funktionsanalyse. 25 (3): 733–762. arXiv:1305.5440. doi:10.1007/s00039-015-0324-9. HERR 3361771. S2CID 14398869. ^ Zhao, Yufei (2014). "Ein arithmetischer Übertragungsbeweis eines relativen Szemerédi-Theorems". Mathematische Verfahren der Cambridge Philosophical Society. 156 (2): 255–261. arXiv:1307.4959. Bibcode:2014MPCPS.156..255Z. doi:10.1017/S0305004113000662. HERR 3177868. S2CID 119673319. Weiterlesen Tao, Terenz (2007). "Die ergodischen und kombinatorischen Ansätze zum Satz von Szemerédi". In Granville, Andreas; Nathanson, Melvin B.; Solymosi, Joseph (Hrsg.). Additive Kombinatorik. CRM Proceedings & Lecture Notes. Vol. 43. Vorsehung, RI: Amerikanische Mathematische Gesellschaft. pp. 145–193. arXiv:math/0604456. Bibcode:2006Mathematik......4456T. ISBN 978-0-8218-4351-2. HERR 2359471. Zbl 1159.11005. Externe Links PlanetMath-Quelle für die erste Version dieser Seite Ankündigung von Ben Green und Terence Tao – der Vorabdruck ist verfügbar unter math.NT/0404188 Diskussion des Satzes von Szemerédi (Teil 1 von 5) Ben Green und Terence Tao: Satz von Szemerédi auf Scholarpedia Weisstein, Erich W. "Satz von Szemeredis". MathWorld. Schmutz, James; Hodge, David (2012). "6,000,000: Endre Szemerédi gewinnt den Abel-Preis". Zahlenphil. Brady Haran. Kategorien: Additive KombinatorikRamsey-TheorieSätze der KombinatorikSätze der Zahlentheorie