« Théorème de Szemerédi » : différence entre les versions
m →Notes et références : + Un référence |
|||
Ligne 30 : | Ligne 30 : | ||
<ref name="refArticleSzemerédi">{{article|nom=Endre Szemerédi|titre=On sets of integers containing no ''k'' elements in arithmetic progression|périodique=Acta Arithmetica|numéro=27|pages=199–245|année=1975|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf|id=Zbl 0303.10056, {{MathSciNet|id=0369312}}}}.</ref> |
<ref name="refArticleSzemerédi">{{article|nom=Endre Szemerédi|titre=On sets of integers containing no ''k'' elements in arithmetic progression|périodique=Acta Arithmetica|numéro=27|pages=199–245|année=1975|url=http://matwbn.icm.edu.pl/ksiazki/aa/aa27/aa27132.pdf|id=Zbl 0303.10056, {{MathSciNet|id=0369312}}}}.</ref> |
||
}} |
}} |
||
== Voir aussi == |
|||
* {{Article |auteur1= David Conlon|auteur2 = Jacob Fox |auteur3 = Yufei Zhao |
|||
|titre= A relative Szemeredi Theorem |
|||
|périodique= [[Geometric and Functional Analysis]] |
|||
|volume= 25 |
|||
|numéro= |
|||
|date= 2015 |
|||
|pages= 733–762 |
|||
|arxiv = 1305.5440 |
|||
}}. |
|||
==Articles connexes== |
==Articles connexes== |
Version du 12 mars 2020 à 17:57
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 :
. La borne inférieure est due à Behrend et Rankin[3], la borne supérieure a été étudiée par Gowers.
Dans le cas où nous avons la majoration suivante, due à Bourgain[4] :
- .
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 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
- 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
- David Conlon, Jacob Fox et Yufei Zhao, « A relative Szemeredi Theorem », Geometric and Functional Analysis, vol. 25, , p. 733–762 (arXiv 1305.5440).