Nombre de van der Waerden
# 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,\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.

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 suite A005346 de l'OEIS. Voici une table plus complète de valeurs $exactes^,$ :

    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)\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

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

pour tout $\varepsilon$ 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.

