Théorème de van der Waerden

Le théorème de van der Waerden (d'après Bartel Leendert van der Waerden) est un théorème de combinatoire, plus précisément de la théorie de Ramsey. Le théorème est le suivant

Théorème de van der Waerden — Pour tous les entiers naturels $r$ et $k$ , il existe un entier naturel $N(r,k)$ tel que si l'on colorie les entiers $1,2,\ldots ,N(r,k)$ en $r$ couleurs, il existe une progression arithmétique de longueur $k$ dans $1,2,\ldots ,N(r,k)$ dont les éléments ont tous la même couleur.

De manière plus formelle, l'énoncé dit que si on partitionne l'ensemble $\{1,2,\ldots ,N\}$ en $r$ parties, au moins une des parties contient une progression arithmétique de longueur $k$ . Le théorème affirme seulement l'existence de l'entier $N(r,k)$ mais ne dit rien sur sa valeur ; une formule générale en fonction de $r,k$ n'est pas connue.

Exemples

1.— Pour $k=2$ le théorème dit simplement que si $N$ est assez grand, il existe deux éléments de même couleur parmi $1,2,\ldots ,N$ ; il suffit d'appliquer le principe des tiroirs et de choisir $N>r$ .

2.— Pour $k=3$ et pour trois couleurs $r=3$ voici un exemple :


1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
B	R	V	R	R	B	V	V	B	V	R	R	B	R	R	B	?

Quel que soit le choix de la couleur pour $17$ , on obtient une progression arithmétique de longueur 3 : pour R, c'est $11,14,17$ , pour B c'est $9,13,17$ et pour V, c'est $3,10,17$ . Cet exemple ne dit rien sur la valeur de $N(3,3)$ . On peut montrer que $27$ est un nombre qui convient pour $N(3,3)$ , et il existe une séquence de longueur 26 sans progression de longueur 3, par exemple : RRVVRRVBVBBRBRRVRVVBRBBVBV.

Nombres de van der Waerden

Les nombres de van der Waerden sont les plus petits des nombres $N(r,k)$ . On les note $W(r,k)$ . Seules quelques valeurs sont connues. Les nombres $W(2,k)$ sont la suite A005346 de l'OEIS. Voici une table plus complète de valeurs exactes[1]^,[2] :

r\k	3	4	5	6	7
2 couleurs	9	35	178	1132	> 3703
3 couleurs	27	293	> 2173	> 11191	> 43855
4 couleurs	76	> 1048	> 17705	> 91331	> 393469
5 couleurs	> 170	> 2254	> 98740	> 540025

Historique

En 1926, van der Waerden, avec Emil Artin et Otto Schreier, ont commencé à travailler sur une conjecture du mathématicien néerlandais Baudet qui formule la conjecture suivante[3] :

Si l'on partitionne l'ensemble $\mathbb {N}$ en deux classes, l’une au moins de ces classes contient des progressions arithmétiques arbitrairement longues

Cette conjecture est étendue par Artin au cas d'une partition en $k$ classes ; cette conjecture est affinée par O. Schreier en l’énoncé démontré par van der Waerden[4]. Van der Waerden revient sur la genèse du théorème et de sa démonstration dans un article en 1965[5] republié en 1971[6].

Démonstrations

Plusieurs démonstrations directes existent, purement combinatoires ou topologiques. Deux de ces démonstrations sont reproduites dans le livre Combinatorics on Words de M. Lothaire[3]. La première est combinatoire[7], la deuxième topologique[8]. Une preuve courte est de Graham et Rothschild[9]. Une preuve combinatoire détaillée est dans le livre de Khintchin[10].

Une démonstration indirecte consiste à constater que le théorème est une conséquence assez facile du théorème de Szemerédi que voici :

Soient

k

un entier positif et

0<\delta \leq 1/2

. Alors il existe un entier

N=N(k,\delta )

tel que tout sous-ensemble de

\{1,\ldots ,N\}

d'au moins

\delta N

éléments contienne une progression arithmétique de longueur

k

.

Pour démontrer le théorème de van der Waerden pour deux entiers $k,r$ , on choisit $\delta =1/r$ . Il existe alors, parmi les r parties monochromes de $\{1,\ldots ,N\}$ , l'une au moins qui a plus de $N/r$ éléments. Comme $N/r=\delta N$ , cette partie contient une progression arithmétique de longueur $k$ .

Notes et références

Marijin J. H. Heule, « Improving the odds. New lower bounds for Van der Waerden Numbers », Université de technologie de Delft, 14 mai 2009 (consulté le 10 janvier 2018)
P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren, « A new method to construct lower bounds for Van der Waerden numbers », The Electronic Journal of Combinatorics, vol. 14,‎ 2007, article n^o R6 (lire en ligne, consulté le 9 janvier 2018)
Jean-Éric Pin, « Van der Waerden's Theorem », dans M. Lothaire, Combinatorics on Words, Reading, MA, Addison-Wesley, 1983, p. 39-54 — Réédition cartonnée avec corrections en 1997 dans la Cambridge Mathematical Library, (ISBN 0-521-59924-5).
Bartel L. van der Waerden, « Beweis einer Baudet'schen Vermutung », Nieuw Arch. Wisk., vol. 15,‎ 1927, p. 212-216.
Bartel L. van der Waerden, « Wie der Beweis der Vermutung von Baudet gefunden wurde », Abhandlungen des Mathematischen Seminars der Hanseatischen Univrsität Hamburg, vol. 28,‎ 1965, p. 6-15 (Math Reviews 175875).
Bartel L. van der Waerden, « How the proof of Baudet's conjecture was found », dans Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, 1971, 251-260 p..
Peter G. Anderson, « A Generalization of Baudet's Conjecture (Van Der Waerden's Theorem) », The American Mathematical Monthly, vol. 83, n^o 5,‎ 1976, p. 359-361 (DOI 10.2307/2318651, JSTOR 2318651).
H. Furstenberg et B. Weiss, « Topological dynamics and combinatorial number theory », Journal d'Analyse Mathématique, vol. 34, n^o 1,‎ 1978, p. 61–85 (ISSN 0021-7670, DOI 10.1007/BF02790008).
Ronald Graham et Bruce Lee Rothschild, « A Short Proof of van der Waerdens Theorem on Arithmetic Progressions », Procreedings of the American Mathematical Society, vol. 42, n^o 2,‎ 1974, p. 385-386 (DOI 10.1090/S0002-9939-1974-0329917-8, lire en ligne).
(en) Alexandre I. Khintchine, Three Pearls in Number Theory, Mineola (N. Y.), Dover Publication, 1998, 64 p. (ISBN 0-486-40026-3). — Réédition de la première traduction de 1952.

Liens externes

(en) Eric W. Weisstein, « van der Waerden's Theorem », sur MathWorld
(en) Eric W. Weisstein, « Baudet's Conjecture », sur MathWorld

Articles liés

Théorie de Ramsey

Portail des mathématiques
Portail de l'informatique théorique

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.

[1] Marijin J. H. Heule, « Improving the odds. New lower bounds for Van der Waerden Numbers », Université de technologie de Delft, 14 mai 2009 (consulté le 10 janvier 2018)

[2] P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren, « A new method to construct lower bounds for Van der Waerden numbers », The Electronic Journal of Combinatorics, vol. 14,‎ 2007, article n^o R6 (lire en ligne, consulté le 9 janvier 2018)

[Lo-3] Jean-Éric Pin, « Van der Waerden's Theorem », dans M. Lothaire, Combinatorics on Words, Reading, MA, Addison-Wesley, 1983, p. 39-54 — Réédition cartonnée avec corrections en 1997 dans la Cambridge Mathematical Library, (ISBN 0-521-59924-5).

[4] Bartel L. van der Waerden, « Beweis einer Baudet'schen Vermutung », Nieuw Arch. Wisk., vol. 15,‎ 1927, p. 212-216.

[5] Bartel L. van der Waerden, « Wie der Beweis der Vermutung von Baudet gefunden wurde », Abhandlungen des Mathematischen Seminars der Hanseatischen Univrsität Hamburg, vol. 28,‎ 1965, p. 6-15 (Math Reviews 175875).

[6] Bartel L. van der Waerden, « How the proof of Baudet's conjecture was found », dans Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, 1971, 251-260 p..

[7] Peter G. Anderson, « A Generalization of Baudet's Conjecture (Van Der Waerden's Theorem) », The American Mathematical Monthly, vol. 83, n^o 5,‎ 1976, p. 359-361 (DOI 10.2307/2318651, JSTOR 2318651).

[FurstenbergWeiss1978-8] H. Furstenberg et B. Weiss, « Topological dynamics and combinatorial number theory », Journal d'Analyse Mathématique, vol. 34, n^o 1,‎ 1978, p. 61–85 (ISSN 0021-7670, DOI 10.1007/BF02790008).

[9] Ronald Graham et Bruce Lee Rothschild, « A Short Proof of van der Waerdens Theorem on Arithmetic Progressions », Procreedings of the American Mathematical Society, vol. 42, n^o 2,‎ 1974, p. 385-386 (DOI 10.1090/S0002-9939-1974-0329917-8, lire en ligne).

[10] (en) Alexandre I. Khintchine, Three Pearls in Number Theory, Mineola (N. Y.), Dover Publication, 1998, 64 p. (ISBN 0-486-40026-3). — Réédition de la première traduction de 1952.