A new ultrafilter proof of Van der Waerden's theorem

Dit artikel presenteert een nieuwe, beknopte algebraïsche bewijsvoering van de stelling van Van der Waerden over monochromatische rekenkundige rijen in de compacte ruimte van ultrafilters $\beta\mathbb{N}$, waarbij noch minimale noch idempotente ultrafilters worden gebruikt.

De kern

Stel je voor dat je een enorme, oneindige rij van huisjes hebt, genummerd van 1 tot oneindig. Je hebt een pot met een paar kleuren verf (bijvoorbeeld rood, blauw en groen). Je gaat elk huisje in de rij een kleur geven.

Van der Waerden's Theorema zegt iets heel verrassends: hoe je die huisjes ook verft, je kunt nooit voorkomen dat er ergens in die rij een reeks huisjes staat die allemaal dezelfde kleur hebben én die op een perfect gelijkmatige afstand van elkaar staan.

Bijvoorbeeld: als je 3 huisjes wilt, dan moet er ergens een reeks zijn van drie rode huisjes, waarbij het tweede huisje precies even ver van het eerste staat als het derde van het tweede. Of 10 huisjes, of 100. Het is onmogelijk om de chaos zo te organiseren dat zulke perfecte, gekleurde rijen niet ontstaan.

Wat doet dit nieuwe bewijs?

Vroeger waren de bewijzen voor dit theorema ofwel heel ingewikkeld (met veel tellen en schakelen) ofwel gebruikten ze heel abstracte wiskundige "superkrachten" (zoals minimale ultrafilters).

Mauro Di Nasso, de auteur van dit nieuwe artikel, heeft een nieuwe, kortere weg gevonden. Hij gebruikt een ander soort wiskundig gereedschap: ultrafilters.

Laten we ultrafilters eens uitleggen met een metafoor:

De "Super-Lupe" (De Ultrafilter)

Stel je een ultrafilter voor als een super-lupe of een super-geheugen.

• Normaal gesproken kijk je naar één huisje of één groepje huisjes.
• Een ultrafilter kijkt naar de hele oneindige rij en beslist: "Welke groepen huisjes zijn 'belangrijk' genoeg om te onthouden?"
• Als een groep huisjes in dit geheugen zit, dan is die groep "groot" of "belangrijk" in de wiskundige zin.

Het slimme aan Di Nasso's bewijs is dat hij geen van die ingewikkelde "minimale" of "idempotente" super-luies nodig heeft. Hij gebruikt een simpele, slimme truc met twee lagen.

De Truc: Twee Dimensies (Het Labyrint)

In plaats van alleen naar de rij huisjes te kijken, kijkt Di Nasso naar een groot raster (een rooster) van huisjes.

• Stel je voor dat je niet alleen kijkt naar waar een huisje staat (de start), maar ook naar hoe ver de volgende huisjes er vandaan staan (de stapgrootte).
• Hij gebruikt een soort twee-dimensionale super-lupe op dit rooster.

De Analogie van de "Wachtrij":
Stel je voor dat je een wachtrij hebt van mensen die een kaartje willen.

1. De Inductie (De Trap): Het bewijs bouwt op als een trap. Als je al weet dat er een rij van 3 gelijk gekleurde mensen is, laat hij zien hoe je die kennis gebruikt om een rij van 4 te vinden.
2. De "Kleuren" en de "Pigeonhole" (Het Duivenhol): Hij neemt een groep van deze super-luies en zegt: "Als we al deze luies door een paar kleuren (rood, blauw, groen) laten lopen, dan moeten er per definitie twee luies zijn die op dezelfde kleur uitkomen." Dit is als het duivenhol-principe: als je 10 duiven in 9 holletjes stopt, zit er in één holletje zeker twee duiven.
3. De Samenvoeging: Omdat die twee luies op dezelfde kleur uitkomen, kunnen ze hun "krachten" bundelen. Ze vinden samen een startpunt en een stapgrootte die perfect werkt.

Waarom is dit nieuw en cool?

De oude bewijzen waren als het bouwen van een kasteel met duizenden kleine, complexe blokken die je op de perfecte manier moest plaatsen.
Di Nasso's bewijs is als het bouwen van een brug met twee sterke pijlers.

• Hij gebruikt geen "magische" blokken (geen minimale ultrafilters).
• Hij gebruikt gewoon de basiswetten van hoe deze super-luies met elkaar werken (algebra in de ruimte van ultrafilters).
• Het is korter, strakker en laat zien dat je de theorie kunt begrijpen zonder de zwaarste wiskundige "zwaargewichten" in te zetten.

Samenvattend in één zin:

Dit papier laat zien dat je, zelfs als je een oneindige rij van dingen willekeurig in kleuren verdeelt, altijd een perfecte, gelijkmatige rij van dezelfde kleur kunt vinden, en dat je dit kunt bewijzen met een slimme, simpele truc in plaats van met ingewikkelde, zware wiskunde.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "A NEW ULTRAFILTER PROOF OF VAN DER WAERDEN'S THEOREM" van Mauro Di Nasso, geschreven in het Nederlands.

Titel: Een nieuwe ultrafilter-bewijs van de stelling van Van der Waerden

Auteur: Mauro Di Nasso

---

1. Het Probleem

De stelling van Van der Waerden is een fundamenteel resultaat in de combinatoriek. Deze stelling stelt dat voor elke eindige partitie (kleuring) van de natuurlijke getallen $\mathbb{N} = C_1 \cup \dots \cup C_r$, er voor elke lengte $\ell$ een monochromatische rekenkundige rij van lengte $\ell$ bestaat. Dat wil zeggen, er bestaan getallen $a$ en $d$ zodanig dat $\{a, a+d, \dots, a+(\ell-1)d\} \subseteq C_i$ voor een bepaalde kleur $i$.

Hoewel er al diverse bewijzen bestaan, waaronder:

• Het originele combinatorische bewijs (gebaseerd op dubbele inductie).
• Bewijzen door S. Shelah.
• Bewijzen die gebruikmaken van minimale idempotente ultrafilters in de compacte halfgroep $(\beta\mathbb{N}, \oplus)$ (o.a. Bergelson, Furstenberg, Hindman, Katznelberg, Koppelberg).
• Bewijzen gebaseerd op "translatie-invariante" filters.

Bestond er tot nu toe geen kort bewijs dat geen beroep doet op de complexe theorie van minimale of idempotente ultrafilters.

2. Methodologie

Di Nasso presenteert een nieuw, beknopt bewijs dat algebra in de ruimte van ultrafilters $(\beta\mathbb{N}, \oplus)$ gebruikt, maar met een cruciaal verschil: het vermijdt de noodzaak van minimale of idempotente ultrafilters.

De kern van de methodologie bestaat uit de volgende stappen:

• Karakterisering via Ultrafilters op $\mathbb{N} \times \mathbb{N}$:
  In plaats van alleen ultrafilters op $\mathbb{N}$ te gebruiken, introduceert de auteur een karakterisering (Lemma 1.3) die ultrafilters op het Cartesische product $\mathbb{N} \times \mathbb{N}$ gebruikt. Een ultrafilter $W$ op $\mathbb{N} \times \mathbb{N}$ "getuigt" van de aanwezigheid van rekenkundige rijen als de afbeeldingen $T_j(n, m) = n + jm$ (voor $j=0, \dots, \ell-1$) allemaal dezelfde ultrafilter op $\mathbb{N}$ induceren, d.w.z. $T_0(W) = T_1(W) = \dots = T_{\ell-1}(W)$.

• Inductief Bewijs:
  Het bewijs verloopt via inductie op de lengte $\ell$ van de rekenkundige rij.

  • Basisgeval: Voor $\ell=1, 2$ is het triviaal.
  • Inductiestap: Aannemende dat er voor lengte $\ell$ een ultrafilter $W$ bestaat die voldoet aan de bovenstaande eigenschap, wordt een nieuwe constructie gemaakt voor lengte $\ell+1$.

• Constructie van Geïntegreerde Ultrafilters:
  De auteur definieert een reeks nieuwe ultrafilters op $\mathbb{N}$ door tensorproducten ($\otimes$) en pseudo-sommen ($\oplus$) te combineren. Specifiek worden ultrafilters $Z_s$ geconstrueerd die bestaan uit een mengsel van $U$ (een afbeelding van $W$) en $V$ (de gemeenschappelijke afbeelding van $W$ via $T_0, \dots, T_{\ell-1}$).

  • Door het duivenhokprincipe (pigeonhole principle) wordt aangetoond dat er twee ultrafilters $Z_p$ en $Z_q$ ($p < q$) zijn die dezelfde kleur $C$ bevatten.
  • Uit deze overlap worden nieuwe verzamelingen $\Gamma, \Gamma_1, \Gamma_2$ afgeleid die leiden tot de constructie van een nieuwe rekenkundige rij van lengte $\ell+1$.

• Gebruik van Algebraïsche Eigenschappen:
  Het bewijs maakt gebruik van de associativiteit van tensorproducten en pseudo-sommen, en de relatie tussen deze operaties en somfuncties (via Lemma 1.2). De auteur toont aan dat de gevonden elementen voldoen aan de vorm $a + j \cdot d$ voor $j=0, \dots, \ell$.

3. Belangrijkste Bijdragen

1. Vermijding van Minimale/Idempotente Ultrafilters: Dit is de meest significante bijdrage. Eerdere ultrafilter-bewijzen waren afhankelijk van de diepe theorie van de Stone-Čech compactificatie, specifiek het bestaan van minimale idempotente ultrafilters. Di Nasso's bewijs is "elementair" in de zin dat het alleen standaard algebraïsche eigenschappen van ultrafilters gebruikt.
2. Kort en Zelfstandig Bewijs: Het bewijs is aanzienlijk korter dan eerdere bewijzen en biedt een nieuwe, directe route naar het resultaat.
3. Nieuwe Karakterisering: De introductie van ultrafilters op $\mathbb{N} \times \mathbb{N}$ als "witness" voor de inductiestap biedt een flexibel nieuw perspectief op partition regularity.
4. Transformatie van Non-standaard Analyse: De auteur merkt op dat het bewijs oorspronkelijk werd afgeleid met iteratieve non-standaard extensies, maar dat de vertaling naar ultrafilter-taal eenvoudiger en origineler is.

4. Resultaten

Het artikel levert een volledig en rigoureus bewijs van de Stelling van Van der Waerden op.

• Stelling 2.1: Voor elke $\ell \in \mathbb{N}$ en elke eindige kleuring van $\mathbb{N}$ bestaat er een monochromatische rekenkundige rij van lengte $\ell$.
• Het bewijs toont expliciet hoe, gegeven een ultrafilter voor lengte $\ell$, een ultrafilter voor lengte $\ell+1$ kan worden geconstrueerd zonder de structuur van de halfgroep $(\beta\mathbb{N}, \oplus)$ te hoeven analyseren op het niveau van minimale ideaalstructuren.

5. Betekenis en Impact

• Toegankelijkheid: Door de afhankelijkheid van zware theorie (minimale idempotente ultrafilters) te verwijderen, wordt het bewijs toegankelijker voor wiskundigen die niet gespecialiseerd zijn in topologische dynamica of de diepere theorie van $\beta\mathbb{N}$.
• Methodologische Innovatie: Het bewijs illustreert dat krachtige resultaten in de Ramsey-theorie ook bereikt kunnen worden met "lichtere" ultrafilter-technieken. Dit opent mogelijk de deur voor nieuwe bewijzen van andere stellingen in de partitie-regulariteit die voorheen alleen met zware middelen bewezen konden worden.
• Verbinding tussen Gebieden: Het artikel versterkt de link tussen non-standaard analyse en ultrafilter-algebra, en toont aan dat resultaten uit het ene domein elegant kunnen worden vertaald naar het andere.

Samenvattend biedt dit artikel een elegante, korte en zelfstandige alternatieve route naar een van de klassieke stellingen van de combinatoriek, waarbij de complexiteit van eerdere ultrafilter-bewijzen wordt geëlimineerd.