théorème de van der Waerden

Écrivons les entiers à la suite et attribuons à chacun une couleur. Même si le coloriage semble désordonné, il finit par faire apparaître des nombres régulièrement espacés qui ont tous la même couleur.

On choisit d’abord le nombre de couleurs et la longueur du motif recherché. Le théorème assure alors qu’une portion assez longue de la suite des entiers force ce motif, quelle que soit la répartition des couleurs.

Une progression arithmétique de longueur k est une liste croissante de k entiers de la forme a, a + d, …, a + (k − 1)d, où le même entier strictement positif d, appelé raison, sépare chaque paire de termes consécutifs. Elle est monochromatique lorsque tous ses termes reçoivent la même couleur.

Fixons un nombre de couleurs r et une longueur k, tous deux entiers naturels strictement positifs. Le théorème affirme l’existence d’un entier N(r, k) tel que toute coloration de 1, 2, …, N(r, k) avec ces r couleurs contient une progression arithmétique monochromatique de longueur k. Le même énoncé se formule en partitionnant cet ensemble en r parties : au moins une partie contient la progression recherchée.

Le nombre de van der Waerden W(r, k) est le plus petit seuil pour lequel cette garantie est vraie ; tout entier supérieur ou égal à ce minimum constitue aussi une borne suffisante. Le résultat répond à une question d’existence : il ne fournit pas, à lui seul, la valeur de ce seuil minimal ni une procédure rapide pour trouver le motif dans une coloration donnée. Issu d’une conjecture de Baudet formulée vers 1926, il a été publié avec une démonstration par van der Waerden en 1927 ; celui-ci en a raconté la genèse dans un article de 1965.

Soient r le nombre de couleurs et k la longueur recherchée, avec r et k strictement positifs. Il existe un plus petit entier W(r, k) tel que, pour tout entier M au moins égal à ce seuil, toute coloration de 1 à M en r couleurs contient des entiers a, a + d, …, a + (k − 1)d de même couleur, où la raison d est strictement positive.

Le domaine est un segment d’entiers consécutifs partant de 1. Il faut fixer un nombre fini r de couleurs, attribuer exactement une couleur à chaque entier du segment et fixer une longueur finie k. La conclusion est garantie lorsque la borne N atteint le seuil associé à ces deux paramètres.

Un segment trop court ne suffit pas en général. Par exemple, sur 1 à 8, colorions 1, 2, 5 et 6 en rouge, puis 3, 4, 7 et 8 en jaune : aucune des deux couleurs ne contient trois termes régulièrement espacés. Dans ce cas, le théorème ne permet pas de conclure ; il faut allonger le segment ou examiner directement la coloration.

Colorions les entiers de 1 à 9 avec deux couleurs. Les entiers 2, 5 et 8 sont rouges ; tous les autres sont jaunes. Nous cherchons trois nombres de même couleur et régulièrement espacés.

1. Choisissons le premier nombre rouge, 2, puis le rouge suivant, 5. Leur écart vaut 5 − 2 = 3.

2. Ajoutons encore cet écart de 3 : 5 + 3 = 8. Le nombre obtenu appartient au segment et il est rouge.

3. Les termes 2, 5 et 8 forment donc une progression arithmétique monochromatique de longueur 3 et de raison 3. La représentation rend simultanément visibles leur couleur commune et leurs deux écarts égaux.

Le contrôle se refait dans les deux sens : 5 − 2 = 3 et 8 − 5 = 3. Cet exemple vérifie la conclusion dans une coloration particulière ; à lui seul, il ne prouve pas que toute coloration de 1 à 9 possède un tel triplet.

Dans un coloriage concret, on recherche un motif en choisissant deux termes de même couleur, puis en vérifiant si la répétition de leur écart conserve cette couleur. Cette inspection directe est préférable lorsque le segment est court et entièrement connu.

Pour établir qu’un motif doit exister dans toute coloration suffisamment longue, une liste d’essais particuliers ne suffit pas. Le théorème apporte précisément cette garantie universelle, sans imposer la manière dont les couleurs sont réparties.

Si l’objectif est de connaître le plus petit seuil ou de produire effectivement une progression, il faut compléter le théorème par un raisonnement adapté ou une exploration exhaustive. Le critère est donc la question posée : existence inévitable, seuil minimal ou recherche d’un témoin.

Une progression arithmétique n’est pas nécessairement une suite d’entiers consécutifs. Le critère est un écart constant strictement positif : 2, 5, 8 convient avec un écart de 3, tandis que trois entiers successifs correspondent seulement au cas particulier d’écart 1.

Une progression monochromatique ne signifie pas que tout le segment possède une seule couleur. Seuls les termes choisis doivent partager leur couleur : dans l’exemple, 2, 5 et 8 sont rouges alors que les six autres entiers sont jaunes.

Le seuil dépend simultanément du nombre de couleurs r et de la longueur k. Écrire un unique nombre N sans fixer ces deux paramètres masque cette dépendance ; il faut toujours préciser le couple étudié.

Le théorème garantit une progression finie de la longueur demandée, pas une progression arithmétique infinie d’une seule couleur. Sur une coloration infinie, on peut appliquer le résultat séparément à chaque longueur fixée, mais les progressions obtenues peuvent changer de couleur, de premier terme et de raison.

Les cas k = 1 et r = 1 sont dégénérés. Une longueur 1 ne demande aucun espacement, et avec une seule couleur toute progression présente dans le segment est monochromatique. Pour étudier le phénomène combinatoire non trivial, on considère donc surtout au moins deux couleurs et une longueur d’au moins 2.

Enfin, constater le motif dans quelques colorations ne démontre pas le mot « toute ». Une preuve du théorème doit couvrir l’ensemble des colorations possibles ; pour un cas fini précis, une vérification exhaustive est une autre démarche.

La théorie de Ramsey replace ce théorème dans l’étude des structures ordonnées qui deviennent inévitables au sein de colorations assez grandes.

La fiche sur la suite arithmétique approfondit l’écart constant qui définit les motifs recherchés ici.

L’article L’ordre selon Ramsey élargit la perspective sur l’apparition forcée d’ordre dans des configurations combinatoires.