Nombre de van der Waerden

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

Table des nombres de van der Waerden

Peu de valeurs sont connues. Les nombres W ( 2 , k ) {\displaystyle 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  

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

W ( r , k ) ≤ 2 2 r 2 2 k + 9 {\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

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

pour tout ε {\displaystyle \varepsilon } et pour k {\displaystyle k} assez grand[4].

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

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

Certificats

Un certificat pour la valeur W ( r , k ) {\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 W ( 3 , 2 ) {\displaystyle W(3,2)} . La longueur d'un certificat est un minorant strict de W ( r , k ) {\displaystyle W(r,k)}  : si une certificat pour la valeur W ( r , k ) {\displaystyle W(r,k)} a longueur n {\displaystyle n} , alors W ( r , k ) > n {\displaystyle W(r,k)>n} . L'article de P. Herwig, M. J. H. Heule, M. van Lambalgen et H. van Maaren[2] décrit l'usage de divers logiciels pour construire des certificats.

Notes et références

  1. ↑ Marijin J. H. Heule, « Improving the odds. New lower bounds for Van der Waerden Numbers », Université de technologie de Delft, (consulté le )
  2. ↑ a et b 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,‎ , article no R6 (lire en ligne, consulté le )
  3. ↑ Timothy Gowers: A new proof of Szemerédi's theorem, Geom. Funct. Anal., 11(3): S. 465-588, 2001. Online-Version bei http://www.dpmms.cam.ac.uk/~wtg10/papers.html.
  4. ↑ Zoltán Szabó, « An application of Lovász' local lemma -- a new lower bound for the van der Waerden number », Random Struct. Algorithms, vol. 1, no 3,‎ , p. 343–360
  5. ↑ E. Berlekamp, « A construction for partitions which avoid long arithmetic progressions », Canadian Mathematics Bulletin, vol. 11,‎ , p. 409–414.

Liens externes

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

Articles liés

  • icône décorative Portail des mathématiques
  • icône décorative Portail de l'informatique théorique