Théorème de Szemerédi

Théorème de Szemerédi En combinatoire arithmétique, Le théorème de Szemerédi est un résultat concernant les progressions arithmétiques en sous-ensembles des entiers. Dans 1936, Erdős et Turán ont conjecturé[1] que chaque ensemble d'entiers A de densité naturelle positive contient une progression arithmétique à k termes pour chaque k. Endre Szemerédi a prouvé la conjecture dans 1975.

Contenu 1 Déclaration 2 Histoire 3 Limites quantitatives 4 Extensions et généralisations 5 Voir également 6 Remarques 7 Lectures complémentaires 8 External links Statement A subset A of the natural numbers is said to have positive upper density if {style d'affichage limsup _{pas trop }{frac {|souvent {1,2,3,pointsc ,n}|}{n}}>0} .

Le théorème de Szemerédi affirme qu'un sous-ensemble des nombres naturels de densité supérieure positive contient une infinité de progressions arithmétiques de longueur k pour tous les entiers positifs k.

Une version finitaire équivalente souvent utilisée du théorème stipule que pour chaque entier positif k et nombre réel {delta de style d'affichage dans (0,1]} , il existe un entier positif {displaystyle N=N(k,delta )} de sorte que chaque sous-ensemble de {1, 2, ..., N} de taille au moins δN contient une progression arithmétique de longueur k.

Une autre formulation utilise la fonction rk(N), la taille du plus grand sous-ensemble de {1, 2, ..., N} sans progression arithmétique de longueur k. Le théorème de Szemerédi est équivalent à la borne asymptotique {style d'affichage r_{k}(N)=o(N)} .

C'est-à-dire, rk(N) croît moins que linéairement avec N.

History Van der Waerden's theorem, le précurseur du théorème de Szemerédi, a fait ses preuves dans 1927.

The cases k = 1 and k = 2 of Szemerédi's theorem are trivial. Le cas k = 3, connu sous le nom de théorème de Roth, a été établi en 1953 de Klaus Roth[2] via une adaptation de la méthode du cercle de Hardy-Littlewood. Endre Szemerédi[3] prouvé le cas k = 4 grâce à la combinatoire. En utilisant une approche similaire à celle qu'il a utilisée pour le cas k = 3, Roth[4] en a donné une seconde preuve dans 1972.

Le cas général a été réglé en 1975, aussi par Szemerédi,[5] qui a développé une extension ingénieuse et compliquée de son argument combinatoire précédent pour k = 4 (appelé "un chef d'oeuvre de raisonnement combinatoire" par Erdős[6]). Plusieurs autres preuves sont maintenant connues, les plus importants étant ceux de Hillel Furstenberg[7][8] dans 1977, en utilisant la théorie ergodique, et de Timothy Gowers[9] dans 2001, utilisant à la fois l'analyse de Fourier et la combinatoire. Terence Tao a appelé les diverses preuves du théorème de Szemerédi un "Pierre de Rosette" pour relier des domaines disparates des mathématiques.[10] Quantitative bounds It is an open problem to determine the exact growth rate of rk(N). Les bornes générales les plus connues sont {style d'affichage CNexp gauche(-n2^{(n-1)/2}{sqrt[{n}]{journal N}}+{frac {1}{2n}}log log Nright)leq r_{k}(N)leq {frac {N}{(journal journal N)^{2^{-2^{m+9}}}}},} où {style d'affichage n=lceil log krceil } . La borne inférieure est due à O'Bryant[11] s'appuyant sur les travaux de Behrend,[12] Rankin,[13] et Elkin.[14][15] La borne supérieure est due à Gowers.[9] Pour petit k, il y a des bornes plus étroites que le cas général. Lorsque k = 3, Bourgain,[16][17] Bruyère-Brun,[18] Elle t'appartient,[19] et ponceuses[20] fourni des bornes supérieures de plus en plus petites. Les meilleures limites actuelles sont {style d'affichage N2^{-{sqrt {8journal N}}}leq r_{3}(N)leq C{frac {(journal journal N)^{4}}{journal N}}N} à cause d'O'Bryant[11] et fleurir[21] respectivement.

Pour k = 4, Vert et Tao[22][23] Prouvé cela {style d'affichage r_{4}(N)leq C{frac {N}{(journal 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] Timothée Gowers,[25] Vojtech Rödl et Jozef Skokan[26][27] avec Brendan Nagle, Rodl, et Mathias Schacht,[28] et Terence Tao[29] fourni des preuves combinatoires.

Alexander Leibman et Vitaly Bergelson[30] progressions de Szemerédi généralisées en polynômes: Si {style d'affichage Sous-ensemble mathbb {N} } est un ensemble de densité supérieure positive et {style d'affichage p_{1}(n),p_{2}(n),pointsc ,p_{k}(n)} sont des polynômes entiers tels que {style d'affichage p_{je}(0)=0} , alors il y a une infinité {style d'affichage u,nin mathbb {Z} } tel que {style d'affichage u+p_{je}(n)dans un} pour tous {style d'affichage 1leq ileq k} . Le résultat de Leibman et Bergelson est également valable dans un cadre multidimensionnel.

La version finitaire du théorème de Szemerédi peut être généralisée à des groupes additifs finis comprenant des espaces vectoriels sur des corps finis.[31] L'analogue de champ fini peut être utilisé comme modèle pour comprendre le théorème des nombres naturels.[32] Le problème de l'obtention de bornes dans le cas k=3 du théorème de Szemerédi dans l'espace vectoriel {style d'affichage mathbb {F} _{3}^{n}} est connu comme le problème du cap set.

Le théorème de Green-Tao affirme que les nombres premiers contiennent de longues progressions arithmétiques arbitraires. Il n'est pas impliqué par le théorème de Szemerédi car les nombres premiers ont une densité 0 dans les nombres naturels. Dans le cadre de leur preuve, Ben Green et Tao ont présenté un "relatif" Théorème de Szemerédi qui s'applique aux sous-ensembles des entiers (même ceux avec 0 densité) satisfaisant certaines conditions de pseudo-aléatoire. Un théorème de Szemerédi relatif plus général a depuis été donné par David Conlon, Jacob Renard, et Yufei Zhao.[33][34] La conjecture d'Erdős sur les progressions arithmétiques impliquerait à la fois le théorème de Szemerédi et le théorème de Green-Tao.

Voir aussi Problèmes impliquant des progressions arithmétiques Théorie ergodique de Ramsey Combinatoire arithmétique Lemme de régularité de Szemerédi Notes ^ Erdős, Paul; Touran, Paul (1936). "Sur certaines suites d'entiers" (PDF). Journal de la Société mathématique de Londres. 11 (4): 261–264. est ce que je:10.1112/jlms/s1-11.4.261. M 1574918. ^ Roth, Claus Friedrich (1953). "Sur certains ensembles d'entiers". Journal de la Société mathématique de Londres. 28 (1): 104–109. est ce que je:10.1112/jlms/s1-28.1.104. M 0051853. Zbl 0050.04002. ^ Szemeredi, Changer (1969). "Sur des ensembles d'entiers ne contenant pas quatre éléments en progression arithmétique". Journal mathématique de l'Académie hongroise des sciences. 20 (1–2): 89–104. est ce que je:10.1007/BF01894569. M 0245555. Zbl 0175.04301. ^ Roth, Claus Friedrich (1972). "Irrégularités des séquences relatives aux progressions arithmétiques, IV". Mathématiques périodiques. hongrois. 2 (1–4): 301–326. est ce que je:10.1007/BF02018670. M 0369311. S2CID 126176571. ^ Szemeredi, Changer (1975). "Sur des ensembles d'entiers ne contenant aucun élément k en progression arithmétique" (PDF). Journal d'arithmétique. 27: 199–245. est ce que je:10.4064/aa-27-1-199-245. M 0369312. Zbl 0303.10056. ^ Forêt, Paul (2013). "Certains de mes problèmes et résultats préférés". à Graham, Ronald L.; Il n'a pas épargné, Jaroslav; Majordome, Steve (éd.). Les Mathématiques de Paul Erdős I (Deuxième éd.). New York: Springer. pp. 51–70. est ce que je:10.1007/978-1-4614-7258-2_3. ISBN 978-1-4614-7257-5. M 1425174. ^ Fürstenberg, Hillel (1977). "Comportement ergodique des mesures diagonales et un théorème de Szemerédi sur les progressions arithmétiques". J. d'Analyse Mathématiques. 31: 204–256. est ce que je:10.1007/BF02813304. M 0498471. S2CID 120917478.. ^ Fürstenberg, Hillel; Katznelson, Yitzhak; Ornstein, Donald Samuel (1982). "La preuve théorique ergodique du théorème de Szemerédi". Taureau. Amer. Math. Soc. 7 (3): 527–552. est ce que je:10.1090/S0273-0979-1982-15052-2. M 0670131. ^ Sauter à: a b Gowers, Timothée (2001). "Une nouvelle preuve du théorème de Szemerédi". Géom. Fonction. Anal. 11 (3): 465–588. est ce que je:10.1007/s00039-001-0332-9. M 1844079. S2CID 124324198. ^ Taô, Térence (2007). "La dichotomie entre structure et aléa, progressions arithmétiques, et les nombres premiers". à Sanz Solé, Marta; Soria, Javier; Homme, Juan Luis; verdure, Jeanne (éd.). Actes du Congrès international des mathématiciens de Madrid, 22 au 30 août, 2006. Congrès international des mathématiciens. Volume. 1. Zurich: Société mathématique européenne. pp. 581–608. arXiv:mathématiques/0512114. est ce que je:10.4171/022-1/22. ISBN 978-3-03719-022-7. M 2334204. ^ Sauter à: a b O'Bryant, Kévin (2011). "Ensembles d'entiers qui ne contiennent pas de longues progressions arithmétiques". Journal électronique de combinatoire. 18 (1). est ce que je:10.37236/546. M 2788676. ^ Behrend, Félix A.. (1946). "Sur les ensembles d'entiers qui ne contiennent pas trois termes en progression arithmétique". Actes de l'Académie nationale des sciences. 32 (12): 331–332. Code bib:1946PNAS...32..331B. est ce que je:10.1073/pnas.32.12.331. M 0018694. PMC 1078964. PMID 16578230. Zbl 0060.10302. ^ Rankin, Robert A.. (1962). "Ensembles d'entiers contenant au plus un nombre donné de termes en progression arithmétique". Proc. Roy. Soc. Secte d'Édimbourg. UN. 65: 332–344. M 0142526. Zbl 0104.03705. ^ Elkins, Michael (2011). "Une construction améliorée d'ensembles sans progression". Journal israélien de mathématiques. 184 (1): 93–128. arXiv:0801.4310. est ce que je:10.1007/s11856-011-0061-1. M 2823971. ^ Vert, Ben; Loup, Julia (2010). "Une note sur l'amélioration par Elkin de la construction de Behrend". À Chudnovsky, David; Chudnovsky, Grégory (éd.). Théorie additive des nombres. Théorie additive des nombres. Festschrift en l'honneur du soixantième anniversaire de Melvyn B. Nathanson. New York: Springer. pp. 141–144. arXiv:0810.0732. est ce que je:10.1007/978-0-387-68361-4_9. ISBN 978-0-387-37029-3. M 2744752. S2CID 10475217. ^ Bourgain, Jean (1999). "Sur les triplets en progression arithmétique". Géom. Fonction. Anal. 9 (5): 968–984. est ce que je:10.1007/s000390050105. M 1726234. S2CID 392820. ^ Bourgain, Jean (2008). "Théorème de Roth sur les progressions revisité". J. Anal. Math. 104 (1): 155–192. est ce que je:10.1007/s11854-008-0020-x. M 2403433. S2CID 16985451. ^ Heath-Brown, Roger (1987). "Ensembles d'entiers ne contenant aucune progression arithmétique". Journal de la Société mathématique de Londres. 35 (3): 385–394. est ce que je:10.1112/jlms/s2-35.3.385. M 0889362. ^ Szemeredi, Changer (1990). "Ensembles d'entiers ne contenant aucune progression arithmétique". Journal mathématique hongrois. 56 (1–2): 155–158. est ce que je:10.1007/BF01903717. M 1100788. ^ Ponceuses, À M (2011). "Sur le théorème de Roth sur les progressions". Annales de Mathématiques. 174 (1): 619–636. arXiv:1011.0104. est ce que je:10.4007/annales.2011.174.1.20. M 2811612. S2CID 53331882. ^ Fleurir, Thomas F.. (2016). "Une amélioration quantitative du théorème de Roth sur les progressions arithmétiques". Journal de la Société mathématique de Londres. Deuxième série. 93 (3): 643–663. arXiv:1405.5800. est ce que je:10.1112/jlms/jdw010. M 3509957. S2CID 27536138. ^ Vert, Ben; Tao, Térence (2009). "Nouvelles bornes pour le théorème de Szemeredi. II. Une nouvelle destination pour r4(N)". À Chen, Guillaume W. L; Gowers, Timothée; Halberstam, Salut; Schmidt, Wolfgang; Vaughan, Robert-Charles (éd.). Nouvelles bornes pour le théorème de Szemeredi, II: Une nouvelle borne pour r_4(N). Théorie analytique des nombres. Essais en l'honneur de Klaus Roth à l'occasion de son 80e anniversaire. Cambridge: la presse de l'Universite de Cambridge. pp. 180–204. arXiv:mathématiques/0610604. Code bib:2006maths.....10604G. ISBN 978-0-521-51538-2. M 2508645. Zbl 1158.11007. ^ Vert, Ben; Tao, Térence (2017). "Nouvelles bornes pour le théorème de Szemerédi, III: Une borne polylogarithmique pour r4(N)". Mathématiques. 63 (3): 944–1040. arXiv:1705.01703. est ce que je:10.1112/S0025579317000316. M 3731312. ^ Fürstenberg, Hillel; Katznelson, Yitzhak (1978). "Un théorème ergodique de Szemerédi pour les transformations commutantes". Journal d'Analyse Mathématique. 38 (1): 275–291. est ce que je:10.1007/BF02790016. M 0531279. S2CID 123386017. ^ Gowers, Timothée (2007). "Régularité hypergraphique et théorème de Szemerédi multidimensionnel". Annales de Mathématiques. 166 (3): 897–946. arXiv:0710.3032. est ce que je:10.4007/annales.2007.166.897. M 2373376. S2CID 56118006. ^ Rodl, Vojtech; Sauteur, Joseph (2004). "Lemme de régularité pour les hypergraphes k-uniformes". Algorithmes de structures aléatoires. 25 (1): 1–42. est ce que je:10.1002/rsa.20017. M 2069663. ^ Rodl, Vojtech; Sauteur, Joseph (2006). "Applications du lemme de régularité pour les hypergraphes uniformes" (PDF). Algorithmes de structures aléatoires. 28 (2): 180–194. est ce que je:10.1002/rsa.20108. M 2198496. ^ Nagle, Brendan; Rodl, Vojtech; Schacht, Mathias (2006). "Le lemme de comptage pour les hypergraphes k-uniformes réguliers". Algorithmes de structures aléatoires. 28 (2): 113–179. est ce que je:10.1002/rsa.20117. M 2198495. ^ Taô, Térence (2006). "Une variante du lemme de suppression d'hypergraphe". Journal de théorie combinatoire, Série A. 113 (7): 1257–1280. arXiv:mathématiques/0503572. est ce que je:10.1016/j.jcta.2005.11.006. M 2259060. ^ Bergelson, vitaly; Leibman, Alexandre (1996). "Extensions polynomiales des théorèmes de van der Waerden et de Szemerédi". Journal de l'American Mathematical Society. 9 (3): 725–753. est ce que je:10.1090/S0894-0347-96-00194-4. M 1325795. ^ Fürstenberg, Hillel; Katznelson, Yitzhak (1991). "Une version de densité du théorème de Hales-Jewett". Journal d'Analyse Mathématique. 57 (1): 64–119. est ce que je:10.1007/BF03041066. M 1191743. S2CID 123036744. ^ Loup, Julia (2015). "Modèles de corps finis en combinatoire arithmétique — dix ans après". Les champs finis et leurs applications. 32: 233–274. est ce que je:10.1016/j.ffa.2014.11.003. M 3293412. ^ Conlon, David; Renard, Jacob; Zhao, Yufei (2015). "Le théorème relatif de Szemerédi". Analyse géométrique et fonctionnelle. 25 (3): 733–762. arXiv:1305.5440. est ce que je:10.1007/s00039-015-0324-9. M 3361771. S2CID 14398869. ^ Zhao, Yufei (2014). "Une preuve de transfert arithmétique d'un théorème de Szemerédi relatif". Actes mathématiques de la Cambridge Philosophical Society. 156 (2): 255–261. arXiv:1307.4959. Code bib:2014MPCPS.156..255Z. est ce que je:10.1017/S0305004113000662. M 3177868. S2CID 119673319. Lectures complémentaires Tao, Térence (2007). "Les approches ergodiques et combinatoires du théorème de Szemerédi". à Granville, André; Nathanson, Melvin B.; Solymossi, Joseph (éd.). Combinatoire additive. CRM Proceedings & Lecture Notes. Volume. 43. Providence, IR: Société mathématique américaine. pp. 145–193. arXiv:mathématiques/0604456. Code bib:2006maths......4456T. ISBN 978-0-8218-4351-2. M 2359471. Zbl 1159.11005. Liens externes Source PlanetMath pour la version initiale de cette page Annonce de Ben Green et Terence Tao – la prépublication est disponible sur math.NT/0404188 Discussion du théorème de Szemerédi (partie 1 de 5) Ben Green et Terence Tao: Théorème de Szemerédi sur Scholarpedia Weisstein, Eric W. "Théorème de Szemeredis". MathWorld. Crasse, James; Hodge, David (2012). "6,000,000: Endre Szemerédi remporte le prix Abel". Numérophile. Brady Haran. Catégories: Combinatoire additiveThéorie de RamseyThéorèmes en combinatoireThéorèmes en théorie des nombres