title: Nombre de van der Waerden
text: # 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.
  
  