Théorème de Szemerédi

Modèle:Ébauche Modèle:Confusion En mathématiques, le théorème de SzemerédiModèle:Références multiples est la conjecture d'Erdős-Turán démontrée par Endre Szemerédi en 1975.

Énoncé

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

À 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 :

$$C^{\log (1/\delta {)}^{k-1}}\le N(k,\delta )\le \exp \exp {\delta }^{-2^{2^{k+9}}}.$$

La borne inférieure est due à Behrend et Rankin, la borne supérieure a été étudiée par Gowers.

Dans le cas où $k=3$, on a la majoration suivante, due à Bourgain :

$N(3,\delta )\le C^{{\delta }^{-2}\log (1/\delta )}$.

Historique

Le cas k=3 a été démontré en 1953 par Klaus Roth, 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.

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.

Voir aussi

• Modèle:Article.

Articles connexes

• Modèle:Lien
• Théorèmes de van der Waerden et de Hales-Jewett
• Modèle:Lien
• Théorème de Behrend