Nombre de van der Waerden

Le théorème de van der Waerden dit que 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,\dots ,N(r,k)$ en $r$ couleurs, il existe une progression arithmétique de longueur $k$ dans $1,2,\dots ,N(r,k)$ dont les éléments ont tous la même couleur.

Les nombres de van der Waerden sont les plus petits des nombres $N(r,k)$ pour lesquels ces progressions arithmétiques existent. On les note $W(r,k)$.

Table des nombres de van der Waerden

Peu de valeurs sont connues. Les nombres $W(2,k)$ sont la Modèle:OEIS. Voici une table plus complète de valeurs exactesModèle:, :

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

Un majorant est donné par Timothy Gowers en 2001, à savoir :

$W(r,k)\le 2^{2^{r^{2^{2^{k+9}}}}}$

en relation avec une démonstration du théorème de Szemerédi. De plus, on a

$W(2,k)>2^k/k^{\epsilon }$

pour tout $\epsilon$ et pour $k$ assez grand.

Pour les nombres $W(2,k)$, donc pour deux couleurs, et des nombres premiers $p$ on a

$W(2,p+1)>p\cdot 2^p.$

Certificats

Un certificat pour la valeur $W(r,k)$ est une suite sur r couleurs qui ne possède pas de progression arithmétique de longueur k. Par exemple, la suite RVB est un certificat pour $W(3,2)$. La longueur d'un certificat est un minorant strict de $W(r,k)$ : si une certificat pour la valeur $W(r,k)$ a longueur $n$, alors $W(r,k)>n$. L'article de P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren décrit l'usage de divers logiciels pour construire des certificats.

Liens externes

• Modèle:MathWorld

Articles liés

• Théorie de Ramsey