Nombre de van der Waerden

Le théorème de van der Waerden dit que pour tous les entiers naturels ${\displaystyle r}$ et ${\displaystyle k}$, il existe un entier naturel ${\displaystyle N(r,k)}$ tel que si l'on colorie les entiers ${\displaystyle 1,2,\ldots ,N(r,k)}$ en ${\displaystyle r}$ couleurs, il existe une progression arithmétique de longueur ${\displaystyle k}$ dans ${\displaystyle 1,2,\ldots ,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 ${\displaystyle N(r,k)}$ pour lesquels ces progressions arithmétiques existent. On les note ${\displaystyle W(r,k)}$.

Table des nombres de van der Waerden

Peu de valeurs sont connues. Les nombres ${\displaystyle W(2,k)}$ sont la suite A005346 de l'OEIS. Voici une table plus complète de valeurs exactes^, :

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

${\displaystyle W(r,k)\leq 2^{2^{r^{2^{2^{k 9}}}}}}$

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

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

pour tout ${\displaystyle \varepsilon }$ et pour ${\displaystyle k}$ assez grand.

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

${\displaystyle W(2,p 1)>p\cdot 2^{p}.}$

Certificats

Un certificat pour la valeur ${\displaystyle 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 ${\displaystyle W(3,2)}$. La longueur d'un certificat est un minorant strict de ${\displaystyle W(r,k)}$ : si une certificat pour la valeur ${\displaystyle W(r,k)}$ a longueur ${\displaystyle n}$, alors ${\displaystyle 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.

Notes et références

Liens externes

• (en) Eric W. Weisstein, « van der Waerden Number », sur MathWorld

Articles liés

• Théorie de Ramsey

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