Théorème de Szemerédi
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Ne doit pas être confondu avec Conjecture d'Erdős-Turán sur les bases additives ou Théorème de Szemerédi-Trotter.
En mathématiques, le théorème de Szemerédi[1],[2] est la conjecture d'Erdős-Turán démontrée par Endre Szemerédi en 1975.
Énoncé modifier
Soient k un entier positif et 0 < δ ≤ 1/2. Alors il existe un entier N = N(k,δ) tel que tout sous-ensemble de {1 ; … ; N} d'au moins δN éléments contienne une progression arithmétique de longueur k.
Bornes sur N modifier
À l'heure actuelle, on ne sait qu'encadrer la valeur de N, dans le cas général le meilleur encadrement connu est celui-ci :
La borne inférieure est due à Behrend et Rankin[3], la borne supérieure a été étudiée par Gowers.
Dans le cas où , on a la majoration suivante, due à Bourgain[4] :
- .
Historique modifier
Le cas k=3 a été démontré en 1953 par Klaus Roth[5], en adaptant la méthode du cercle de Hardy-Littlewood. Cependant sa méthode ne se généralisait pas à tous les cas, et il a fallu attendre 1969 pour que Szeremédi démontre le cas k=4. En 1972, Roth étend à son tour sa méthode au cas k=4, et le cas général est finalement démontré par Szeremédi en 1975. Depuis, ce théorème a connu de nombreuses démonstrations faisant appel à divers domaines des mathématiques[6].
Ce théorème est un cas particulier de la conjecture d'Erdős sur les progressions arithmétiques, dont un autre cas résolu est le théorème de Green-Tao.
Un lemme de la démonstration, appelé lemme de régularité de Szemerédi, est un résultat de théorie des graphes qui s'est révélé très important dans ce domaine.
Notes et références modifier
- Jean-Paul Thouvenot, « La démonstration de Furstenberg du théorème de Szemerédi sur les progressions arithmétiques », Séminaire Bourbaki, no 518, , p. 221-232 (lire en ligne)
- Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, no 27, , p. 199–245 (lire en ligne).
- (en) Robert A. Rankin, « Sets of integers containing not more than a given number of terms in arithmetical progression », Proc. Roy. Soc. Edinburgh Sect. A, vol. 65, , p. 332–344
- (en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9, , p. 968–984
- (en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28, , p. 104-109
- Dans son post du 13/02/2010 (en) sur son blog, Terence Tao n'en recense pas moins de 16.
Voir aussi modifier
- David Conlon, Jacob Fox et Yufei Zhao, « A relative Szemeredi Theorem », Geometric and Functional Analysis, vol. 25, , p. 733–762 (arXiv 1305.5440).
