Théorème de Szemerédi

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les mathématiques
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.

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 | modifier le code]

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 | modifier le code]

À 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 (en)[3], la borne supérieure a été étudiée par Gowers.

Dans le cas où nous avons la majoration suivante, due à Bourgain[4] :

.

Historique[modifier | modifier le code]

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 preuve, 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 | modifier le code]

  1. 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)
  2. Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, no 27,‎ , p. 199–245 (lire en ligne).
  3. (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
  4. (en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9,‎ , p. 968–984
  5. (en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28,‎ , p. 104-109
  6. Dans son post du 13/02/2010 (en) sur son blog, Terence Tao n'en recense pas moins de 16.

Articles connexes[modifier | modifier le code]