A new ultrafilter proof of Van der Waerden's theorem

Cet article présente une nouvelle preuve concise du théorème de Van der Waerden sur les progressions arithmétiques monochromatiques, utilisant l'algèbre dans l'espace compact des ultrafiltres $\beta\mathbb{N}$ sans recourir aux ultrafiltres minimaux ou idempotents.

L'essentiel

🎨 Le Grand Jeu de la Couleur : Une Nouvelle Preuve de Van der Waerden

Imaginez que vous avez une infinité de points alignés sur une ligne (les nombres naturels : 1, 2, 3, 4...). Vous décidez de les peindre avec un nombre fini de couleurs (disons, rouge, bleu, vert).

Le problème (Le Théorème de Van der Waerden) :
Peu importe comment vous peignez ces points, si vous allez assez loin, vous finirez inévitablement par trouver une suite de points de la même couleur qui sont espacés de manière régulière.

• Par exemple : Rouge, Rouge, Rouge (espacés de 1).
• Ou : Bleu, Bleu, Bleu, Bleu (espacés de 5).
• Ou : Vert, Vert, Vert, Vert, Vert (espacés de 100).

C'est ce qu'on appelle une progression arithmétique monochromatique. Le théorème dit que c'est impossible d'échapper à ce motif, même avec un coloriage très malin.

🧐 L'Histoire des Preuves

Jusqu'à présent, prouver ce théorème était comme essayer de résoudre un casse-tête géant :

1. L'ancienne méthode : C'était une preuve purement combinatoire, très longue et complexe, un peu comme essayer de construire une tour de cartes en comptant chaque grain de poussière.
2. La méthode "Ultrafiltre" (1989) : Des mathématiciens ont utilisé des outils très puissants appelés "ultrafiltres" (des sortes de lunettes magiques qui voient l'infini). Mais ils devaient utiliser des lunettes très spéciales et compliquées (les "ultrafiltres minimaux et idempotents"), un peu comme si on utilisait un canon à eau pour éteindre une bougie.

🚀 La Nouvelle Approche de Mauro Di Nasso

Dans cet article, Mauro Di Nasso propose une nouvelle preuve, plus courte et plus élégante.

• La bonne nouvelle : Il utilise toujours les "lunettes ultrafiltres", mais il n'a pas besoin des versions les plus compliquées (ni minimales, ni idempotentes).
• L'analogie : Au lieu d'utiliser un marteau-piqueur, il utilise un scalpel chirurgical. Il montre qu'on peut prouver le théorème avec des outils plus simples et plus directs.

🔍 Comment ça marche ? (L'Explication avec des Métaphores)

Pour comprendre sa méthode, imaginons que nous ne regardons pas seulement les nombres, mais des paires de nombres (comme des coordonnées sur une carte : position de départ et taille du pas).

1. Les "Lunettes" (Les Ultrafiltres)

Imaginez que vous avez une paire de lunettes magiques (un ultrafiltre) qui vous permet de voir l'infini. Si vous regardez à travers ces lunettes, vous ne voyez pas un seul nombre, mais un "monde" de nombres.

• Si vous avez une couleur (disons le rouge), et que vos lunettes disent "Le rouge est partout ici", alors vous savez que vous pouvez trouver une suite rouge.

2. Le Secret : Regarder deux choses à la fois

La preuve de Di Nasso est basée sur une idée brillante : au lieu de regarder les nombres un par un, il regarde des paires $(a, d)$ où :

• $a$ est le premier nombre de la suite.
• $d$ est l'espacement (le pas).

Il utilise une "lunette" spéciale sur ces paires. Cette lunette a une propriété magique : elle voit la même couleur, peu importe comment on déplace la suite.

• Si la lunette voit la suite $(a, a+d, a+2d)$ en rouge, elle voit aussi $(a, a+d, a+2d, a+3d)$ en rouge, et ainsi de suite.

3. L'Induction : Monter les marches de l'escalier

La preuve fonctionne comme une escalier :

• Étape 1 : On suppose qu'on sait déjà trouver des suites de longueur 2 (deux points de la même couleur).
• Étape 2 : On utilise cette hypothèse pour construire une "super-lunette" qui garantit des suites de longueur 3.
• Étape 3 : On répète le processus pour aller de la longueur $\ell$ à la longueur $\ell+1$.

4. Le "Piège" de la Colombe (Le Principe des Tiroirs)

C'est le moment clé de la preuve.
Imaginons que nous ayons plusieurs "lunettes" différentes (appelées $Z_1, Z_2, \dots$). Chacune de ces lunettes "voit" une couleur différente dans le monde infini.

• Si nous avons 3 couleurs (Rouge, Bleu, Vert) et 4 lunettes, le principe des tiroirs nous dit qu'au moins deux lunettes doivent "voir" la même couleur.
• Di Nasso montre que si deux lunettes voient la même couleur, on peut les combiner pour créer une nouvelle progression encore plus longue.

C'est comme si vous aviez deux cartes au jeu de l'oie qui vous disent "Avancez de 3 cases". En les combinant, vous pouvez avancer de 6 cases, ou créer un chemin plus complexe qui mène inévitablement à la victoire (la suite monochromatique).

💡 Pourquoi est-ce important ?

1. Simplicité : Cette preuve évite les outils mathématiques les plus lourds et les plus obscurs. Elle rend le théorème plus accessible.
2. Nouveauté : Elle montre qu'il existe plusieurs chemins pour atteindre la vérité mathématique. Parfois, on n'a pas besoin de la "force brute" (les ultrafiltres complexes), mais d'une "astuce intelligente" (l'induction sur les paires).
3. Universalité : Cela renforce notre compréhension de la structure des nombres. Même si l'on essaie de cacher les motifs en les coloriant de manière chaotique, l'ordre finit toujours par émerger.

En résumé

Mauro Di Nasso nous dit : "Pour prouver que l'ordre existe toujours dans le chaos, vous n'avez pas besoin d'un marteau géant. Il suffit de regarder les nombres par paires, d'utiliser un peu de logique sur les couleurs, et de monter un à un les échelons de la longueur des suites."

C'est une preuve élégante, courte, qui utilise la magie des "lunettes infinies" sans en abuser.

Résumé technique

Voici un résumé technique détaillé de l'article « A NEW ULTRAFILTER PROOF OF VAN DER WAERDEN'S THEOREM » de Mauro Di Nasso, rédigé en français.

1. Le Problème : Le Théorème de Van der Waerden

L'article aborde l'un des résultats fondamentaux de la combinatoire, le théorème de Van der Waerden. Ce théorème stipule que pour toute partition finie (ou coloration) des entiers naturels $\mathbb{N} = C_1 \cup \dots \cup C_r$, il existe, pour tout entier $\ell \ge 1$, une progression arithmétique de longueur $\ell$ qui est monochromatique. Autrement dit, il existe un entier $a$ (le premier terme) et un entier $d > 0$ (la raison) tels que la suite $a, a+d, \dots, a+(\ell-1)d$ soit entièrement contenue dans l'une des classes de la partition $C_i$.

Bien que le théorème ait été prouvé à l'origine par une procédure combinatoire doublement inductive complexe, et que d'autres preuves existent (notamment celle de Shelah), l'auteur se concentre sur les preuves utilisant la théorie des ultrafiltres. Les preuves antérieures par ultrafiltres (Bergelson, Furstenberg, Hindman, Katznelson, Koppelberg) reposaient sur l'utilisation d'ultrafiltres minimaux et idempotents dans le demi-groupe compact $(\beta\mathbb{N}, \oplus)$.

2. Méthodologie : Une Approche Algébrique sans Ultrafiltres Minimaux

La contribution centrale de Di Nasso est de fournir une preuve nouvelle, courte et inductive qui évite l'utilisation des ultrafiltres minimaux ou idempotents, qui sont souvent considérés comme des outils lourds ou non constructifs dans ce contexte.

La méthodologie repose sur les éléments suivants :

• Espace de travail : L'auteur utilise l'algèbre dans l'espace des ultrafiltres $\beta\mathbb{N}$, mais étend la construction aux ultrafiltres sur le carré cartésien $\mathbb{N} \times \mathbb{N}$.
• Outils algébriques :
  • Produit tensoriel ($\otimes$) : Défini sur les produits cartésiens d'ensembles.
  • Somme pseudo ($\oplus$) : Une opération associative (mais non commutative) sur $\beta\mathbb{N}$, définie par $A \in U \oplus V \iff \{n \mid A-n \in V\} \in U$.
  • Fonctions de translation : L'auteur introduit des applications $T_j : (n, m) \mapsto n + jm$ pour relier les coordonnées du produit cartésien aux termes d'une progression arithmétique.
• Caractérisation par ultrafiltres (Lemme 1.3) :
  Le cœur de la preuve repose sur l'équivalence suivante : l'existence de progressions arithmétiques monochromatiques de longueur $\ell$ est équivalente à l'existence d'un ultrafiltre $W$ sur $\mathbb{N} \times \mathbb{N}$ tel que les images de $W$ par les translations $T_0, T_1, \dots, T_{\ell-1}$ soient identiques ($T_0(W) = T_1(W) = \dots = T_{\ell-1}(W)$).
• Induction : La preuve procède par récurrence sur la longueur $\ell$ de la progression.
  • Hypothèse de récurrence : On suppose l'existence d'un ultrafiltre $W$ satisfaisant la condition pour une longueur $\ell$.
  • Étape inductive : Pour passer à $\ell+1$, l'auteur construit de nouveaux ultrafiltres sur $\mathbb{N}$ en combinant des puissances tensorielles et des sommes pseudo de $W$ et d'autres ultrafiltres dérivés. En utilisant le principe des tiroirs (pigeonhole principle) sur les couleurs, il identifie une intersection non vide entre deux ultrafiltres construits, ce qui permet d'extraire une progression de longueur $\ell+1$.

3. Contributions Clés et Résultats

• Élimination des ultrafiltres minimaux/idempotents : C'est la contribution la plus significative. Contrairement aux preuves de 1989 et 2004, cette démonstration n'a pas besoin de la théorie complexe des ultrafiltres minimaux ni de la propriété d'idempotence ($U \oplus U = U$). Elle utilise uniquement des ultrafiltres "génériques" construits par induction.
• Simplicité et brièveté : La preuve est présentée comme étant plus courte et conceptuellement plus directe que les approches précédentes, bien qu'elle utilise toujours l'algèbre non triviale de $\beta\mathbb{N}$.
• Lien avec les extensions non standard : Le texte note en remarque (Remark 2.2) que cette preuve a été initialement obtenue via des extensions non standard itérées (une technique de logique mathématique) avant d'être reformulée en langage d'ultrafiltres. Cette reformulation rend la preuve accessible aux spécialistes de la théorie des ultrafiltres sans nécessiter de maîtriser la théorie des modèles non standard.
• Preuve constructive (au sens ultrafiltre) : Le lemme 1.3 fournit une caractérisation précise de la régularité de partition via l'existence d'un ultrafiltre spécifique, servant de pont entre la combinatoire et l'algèbre topologique.

4. Signification et Impact

• Nouvelle perspective théorique : En démontrant que le théorème de Van der Waerden peut être prouvé sans recourir aux ultrafiltres minimaux, l'article suggère que la structure algébrique de base de $\beta\mathbb{N}$ (associativité, produit tensoriel, somme pseudo) est suffisante pour capturer la régularité des progressions arithmétiques. Cela pourrait ouvrir la voie à des preuves similaires pour d'autres théorèmes de régularité de partition.
• Unification des techniques : L'article fait le pont entre les techniques de logique non standard (extensions non standard) et la théorie des ultrafiltres, montrant qu'elles sont deux faces d'une même médaille pour ce type de problèmes combinatoires.
• Accessibilité pédagogique : Bien que l'algèbre des ultrafiltres reste technique, l'élimination des concepts les plus abstraits (minimalité, idempotence) rend la preuve potentiellement plus accessible pour l'enseignement ou l'application dans d'autres domaines des mathématiques discrètes.

En résumé, Mauro Di Nasso propose une démonstration élégante du théorème de Van der Waerden qui simplifie les outils nécessaires en se passant des ultrafiltres minimaux, tout en conservant la puissance de l'algèbre des ultrafiltres sur $\mathbb{N}$ et $\mathbb{N} \times \mathbb{N}$.