Théorème de Szemerédi

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é

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}}\leq N(k,\delta )\leq 2^{2^{\delta ^{-2^{2^{k+9}}}}}$ . La borne inférieure est due à Behrend et Rankin[3], la borne supérieure a été étudiée par Gowers.

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

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

.

Historique

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

Jean-Paul Thouvenot, « La démonstration de Furstenberg du théorème de Szemerédi sur les progressions arithmétiques », Séminaire Bourbaki, n^o 518,‎ 1978, p. 221-232 (lire en ligne)
Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, n^o 27,‎ 1975, 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,‎ 1962, p. 332–344
(en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9,‎ 1999, p. 968–984
(en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28,‎ 1953, 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

David Conlon, Jacob Fox et Yufei Zhao, « A relative Szemeredi Theorem », Geometric and Functional Analysis, vol. 25,‎ 2015, p. 733–762 (arXiv 1305.5440).

Articles connexes

Norme de Gowers (en)
Théorèmes de van der Waerden et de Hales-Jewett
Théorème des coins (en)
Théorème de Behrend

Portail des mathématiques

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[refArticleThouvenot-1] Jean-Paul Thouvenot, « La démonstration de Furstenberg du théorème de Szemerédi sur les progressions arithmétiques », Séminaire Bourbaki, n^o 518,‎ 1978, p. 221-232 (lire en ligne)

[refArticleSzemerédi-2] Endre Szemerédi, « On sets of integers containing no k elements in arithmetic progression », Acta Arithmetica, n^o 27,‎ 1975, 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,‎ 1962, p. 332–344

[4] (en) Jean Bourgain, « On triples in arithmetic progression », Geom. Func. Anal., vol. 9,‎ 1999, p. 968–984

[5] (en) K. F. Roth, « On certain sets of integers, I », J. London Math. Soc., vol. 28,‎ 1953, p. 104-109

[6] Dans son post du 13/02/2010 (en) sur son blog, Terence Tao n'en recense pas moins de 16.