🔢 mathematics

Three-color van der Waerden numbers grow super-exponentially

Dit artikel stelt vast dat het driekleuren van de van der Waerden-getal $w(k;3)$ super-exponentieel groeit door een driekleuring van gehele getallen tot $2^{k (\log^* k)/4}$ te construeren die vrij is van monochromatische $k$ -term rekenkundige progressies, terwijl het tegelijkertijd een nieuwe ondergrens biedt die een langdurig probleem van Erdős en Graham met betrekking tot canonieke van der Waerden-getallen oplost.

Oorspronkelijke auteurs: Jacob Fox, Zach Hunter

Gepubliceerd 2026-06-02

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Jacob Fox, Zach Hunter

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een zeer lange rij genummerde tegels hebt, van 1 tot een enorm groot getal $N$ . Je wilt elke tegel een van de drie kleuren schilderen (laten we zeggen Rood, Blauw en Groen).

De grote vraag waar wiskundigen al bijna een eeuw over nadenken is: Hoe lang moet de rij zijn voordat je gedwongen bent om een "monochromatische rekenkundige progressie" te creëren?

Een rekenkundige progressie is simpelweg een reeks getallen die met dezelfde stapjes omhoog gaan, zoals 5, 10, 15, 20. Als je 5, 10, 15 en 20 allemaal Rood schildert, heb je een "monochromatische" (één kleur) progressie gemaakt.

Het getal $w(k; 3)$ is de lengte van de rij waarbij je, ongeacht hoe slim je de tegels schildert, niet kunt voorkomen dat je een reeks van $k$ tegels achter elkaar (met gelijke tussenpozen) krijgt die allemaal dezelfde kleur hebben.

Het Oude Mysterie

Lange tijd wisten wiskundigen dat deze getallen bestonden, maar ze wisten niet hoe snel ze groeiden naarmate $k$ groter werd.

Sommigen dachten dat deze getallen groeiden als een standaard exponentiële functie (zoals $2^k$ ).
Anderen, waaronder de beroemde wiskundige Paul Erdős, vermoedden dat de getallen voor drie of meer kleuren super-exponentieel groeien. Dit betekent dat ze zo snel groeien dat ze zelfs de krachtigste exponentiële functies overtreffen. Het is also kind met het vergelijken van een slak met een raket die sneller dan het licht versnelt.

Erdős bood een prijs van $500 aan iedereen die dit super-exponentiële groei voor drie kleuren zou kunnen bewijzen.

De Nieuwe Ontdekking

In dit artikel bewijzen Jacob Fox en Zach Hunter eindelijk dat Erdős gelijk had.

Zij tonen aan dat voor drie kleuren de rij astronomisch lang moet zijn voordat je gedwongen wordt om een monochromatische reeks te maken. Specifiek bewijzen zij dat het getal groter is dan $2^{k(\log^* k)/4}$ .

Om de omvang hiervan te begrijpen, stel je de "geïtereerde logaritme" ( $\log^* k$ ) voor. Dit is een getal dat zo traag groeit dat het bijna vlak is. Zelfs voor een getal zo enorm als het aantal atomen in het universum, is $\log^* k$ slechts ongeveer 5.

De Analogie: Als standaard exponentiële groei als een konijnenpopulatie is die elke dag verdubbelt, dan is dit nieuwe resultaat als een konijnenpopulatie die verdubbelt, en dan de snelheid van het verdubbelen verdubbelt, en dan de snelheid van die snelheid verdubbelt, enzovoort, maar pas nadat je een getal hebt afgewacht dat nauwelijks verandert. Het resultaat is een getal zo massief dat het de verbeelding tart.

Hoe Hebben Ze Het Gedaan? (De Magische Trucs)

De auteurs hebben niet alleen gegokt; ze hebben een "constructie" gebouwd (een specifieke manier om de tegels te schilderen) die het patroon zo lang mogelijk vermijdt. Ze gebruikten een paar slimme wiskundige trucs:

Het "Spraag Net" (De Gaten Vinden):
Eerst vonden ze een manier om een enorme groep getallen te kiezen die zeer "dens" (compact) zijn, maar op de een of andere manier geen rekenkundige progressies vormen. Denk aan een visnet met zeer grote gaten. Je kunt veel vis (getallen) vangen, maar de gaten zijn zo perfect gerangschikt dat je nooit een specifiek patroon van vissen die in een rechte lijn zwemmen, vangt.
De "Random Shift" (De Verschuiving):
Ze namen twee van deze speciale groepen en combineerden ze. Maar in plaats van ze gewoon op elkaar te stapelen, gebruikten ze een "random shift". Stel je voor dat je twee steven kaarten hebt. Je schudt één deck en schuift de andere dan een klein stukje over de eerste heen. Deze willekeurige beweging breekt de patronen die gevormd zouden kunnen worden als je ze gewoon netjes op elkaar zou stapelen.
De "Ladder" (Het Proces Itereren):
De echte magie is dat ze dit proces van verschuiven en combineren keer op keer kunnen herhalen.
- Begin met een kleine groep.
- Verschuif en combineer om een grotere groep te krijgen die nog steeds het patroon vermijdt.
- Doe het opnieuw om een nóg grotere groep te krijgen.
- Ze kunnen dit proces ongeveer $\log^* k$ keer herhalen.

Omdat ze dit proces zo vaak kunnen herhalen, wordt het uiteindelijke aantal tegels dat ze kunnen schilderen zonder een patroon te maken, ongelooflijk groot.

De Bonus: Een Oude Puzzel Oplossen

Terwijl ze dit bewezen voor drie kleuren, losten ze ook een gerelateerde puzzel op die door Erdős en Graham werd voorgelegd over "Canonieke" van der Waerden-getallen.

In deze versie zoek je niet alleen naar een reeks van één kleur. Je zoekt naar een reeks die ofwel allemaal één kleur is, OF allemaal verschillende kleuren (zoals Rood, Blauw, Groen, Rood, Blauw, Groen... wacht, nee, gewoon alle onderscheidende kleuren).

Het Resultaat: Ze bewezen dat het aantal tegels dat nodig is om dit patroon af te dwingen ook super-groot is. Het groeit sneller dan elke eenvoudige macht van $k$ . Dit beslecht een decennia oude vraag over de vraag of deze getallen snel genoeg groeien om als "super-exponentieel" beschouwd te worden.

Samenvatting

Het Probleem: Hoe lang is de rij met getallen voordat je moet een rechtlijnig patroon van dezelfde kleur zien?
Het Antwoord: Voor drie kleuren moet de rij onvoorstelbaar lang zijn. Het groeit veel sneller dan iemand eerder heeft bewezen.
De Methode: Ze bouwden een wiskundig "schild" met behulp van willekeurige verschuivingen en gelaagde combinaties die de patronen een recordbrekend lang tijd uit de weg gaan.
De Impact: Dit bevestigt een beroemde gok van Paul Erdős en sluit een belangrijk hoofdstuk in de geschiedenis van de combinatoriek.

Technische Samenvatting: Drie-kleuren van der Waerden-getallen groeien super-exponentieel

Probleemstelling
Het artikel behandelt de groeisnelheid van van der Waerden-getallen, aangeduid als $w(k; r)$ . Dit getal wordt gedefinieerd als het kleinste gehele getal $N$ waarvoor elke $r$ -kleuring van de verzameling $\{1, 2, \dots, N\}$ een monochromatische rekenkundige progressie van lengte $k$ bevat. Hoewel de existentie van deze getallen wordt gegarandeerd door de stelling van van der Waerden, blijft hun exacte asymptotische groei een fundamenteel openstaand probleem.

Historisch gezien was de groei van $w(k; r)$ een onderwerp van intense speculatie. Voor een vaste $r$ werd door Erdős geconjectureerd dat $w(k; 2)$ super-exponentieel groeit (dat wil zeggen $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$ ). Daartegenover stonden andere conjecturen die lineair exponentiële groei suggereerden, specifiek $\lim_{k \to \infty} w(k; r)^{1/k} = r$ . Vóór dit werk waren de best bekende ondergrenzen voor $w(k; r)$ grotendeels afgeleid van de Lovász Local Lemma of specifieke algebraïsche constructies, wat grenzen opleverde van de vorm $w(k; r) \geq r^{k-1}/(4k)$ of, voor een vaste $r \geq 5$ , grenzen van de vorm $(3r/3)^{(1-o(1))k}$ . De auteurs merken op dat hoewel een eerder resultaat door Hunter [20] de lineair exponentiële conjectuur voor $r \geq 5$ weerlegde, de casus voor $r=3$ (en het algemene gedrag voor kleine vaste $r$ ) onopgelost bleef.

Methodologie
De auteurs ontwikkelen een nieuwe probabilistische constructie om ondergrenzen voor $w(k; r)$ vast te stellen. De methodologie steunt op drie primaire componenten:

Dichte progressievrije verzamelingen in cyclische groepen:
De auteurs construeren zeer dichte deelverzamelingen van cyclische groepen $\mathbb{Z}_N$ die geen $k$ -term rekenkundige progressies ( $k$ -APs) bevatten. Zij maken gebruik van een uitbreiding van de Erdős-Turán constructie (verzamelingen van gehelen met geen enkel cijfer gelijk aan $p-1$ in grondtal $p$ ) aangepast aan cyclische groepen. Cruciaal is dat zij bewijzen dat er "hit-sets" bestaan (Lemma 2.8) die ijl zijn (dichtheid $\leq \epsilon$ ) maar elke $k$ -AP in een cyclische groep snijden met een constante fractie van de elementen. Dit wordt bereikt door willekeurige congruentieklassen modulo een verzameling priemgetallen te selecteren.
Gevolgen van de Lovász Local Lemma (LLL):
Het artikel gebruikt de symmetrische versie van de Lovász Local Lemma om de existentie van kleuringen aan te tonen waarbij geen enkele kleurklasse een "grote" fractie van een $k$ -AP bevat. Specifiek stelt Corolarium 3.3 vast dat voor groepen van orde $N$ zonder kleine priemfactoren, men deelverzamelingen van kleuren aan vertices kan toewijzen zodat geen enkele $k$ -AP monochromatisch of bijna monochromatisch is.
Random Shifted Product Constructies:
De kern van de technische innovatie is een verfijnde "random shifted product" constructie (Lemma's 4.2 en 4.3). In tegenstelling tot standaard productkleuringen die het aantal kleuren vermenigvuldigen, stelt deze methode de auteurs in staat om kleuringen van kleinere groepen te combineren in een grotere groep terwijl het aantal kleuren vast blijft (of gecontroleerd toeneemt).

Mechanisme: Gegeven een kleuring $c_1$ van $H_1$ en $c_2$ van $H_2$ , definieert de constructie een kleuring op $H_1 \times H_2$ door onafhankelijk de vezels van de projectie op $H_2$ te verschuiven en kleuren te permuteren op basis van de kleur van het basiselement in $H_1$ .
Iteratief proces: De auteurs itereren deze constructie. In elke stap combineren zij een kleuring van een groep $Z_{n_{j-1}}$ met een kleuring van een cyclische groep van priemorde $Z_{q_j}$ . De constructie vergroot de grootte van de groep met een factor exponentieel in $k$ , terwijl er een "dubbel exponentieel" verlies optreedt in de dichtheidsparameter van de "goede" kleurklasse. Door deze parameters zorgvuldig in balans te houden, kan het proces ongeveer $(\log^* k)/2$ keer worden geïtereerd.

Belangrijkste Bijdragen en Resultaten

Super-exponentiële Groei voor Drie Kleuren:
Het primaire resultaat (Theorem 1) bewijst dat voor voldoende grote $k$ , het drie-kleuren van der Waerden-getal voldoet aan:
$w(k; 3) > 2^{k(\log^* k)/4}$
Dit stelt vast dat $w(k; 3)$ sneller groeit dan enige exponentiële functie van $k$ , waarmee de conjectuur dat $\lim_{k \to \infty} w(k; r)^{1/k} = r$ voor $r \geq 3$ wordt weerlegd.
Ondergrenzen voor Veel Kleuren:
Theorem 2 geeft een ondergrens voor het regime waar het aantal kleuren $r$ groot is ten opzichte van $k$ (specifiek $r \geq (\log k)^{3/\epsilon}$ ):
$w(k; r) \geq r^{(1-\epsilon)k \log k}$
Dit verbetert de eerdere grenzen in het "veel kleuren" regime.
Resolutie van het Erdős-Graham Probleem:
De auteurs adresseren het canonieke van der Waerden-getal $H(k)$ , gedefinieerd als het kleinste $N$ waarvoor elke kleuring van $[N]$ een monochromatische of regenboog $k$ -AP bevat. Erdős en Graham conjetureerden of $H(k)^{1/k}/k \to \infty$ . Gebruikmakend van hun verbeterde ondergrens op $w(k; k-1)$ , bewijzen de auteurs (Theorem 3) dat:
$H(k) \geq k^{(1-o(1))k \log k}$
Dit bevestigt dat $H(k)$ super-exponentieel groeit, waarmee het openstaande probleem van Erdős en Graham wordt opgelost.

Significantie
Het artikel beweert dat de groei van van der Waerden-getallen voor drie of meer kleuren super-exponentieel is, een resultaat dat het begrip van deze combinatorische getallen fundamenteel verandert. De significantie ligt in:

Het weerleggen van de Lineair Exponentiële Conjectuur: Het toont definitief aan dat $w(k; r)$ niet gedraagt als $r^k$ voor $r \geq 3$ .
Methodologische Vooruitgang: De introductie van de "random shifted product" constructie maakt het mogelijk om probabilistische argumenten te itereren terwijl het aantal kleuren constant blijft, een techniek die de auteurs naar aanleiding van eerdere versies voor $r \geq 5$ als efficiënter beschouwen.
Canonieke Ramsey-theorie: De resultaten bieden een sterke resolutie van het Erdős-Graham probleem betreffende canonieke van der Waerden-getallen, waarbij zij aantonen dat zelfs wanneer men regenboog-progressies toestaat, de vereiste $N$ vele malen groter is dan voorheen vastgestelde ondergrenzen.

De auteurs merken op dat hoewel hun technieken algemeen zijn, de specifieke toepassing hier zich richt op het vaststellen van deze ondergrenzen. Zij suggereren dat deze constructies ook toegepast kunnen worden voor het verkrijgen van nieuwe grenzen voor andere rekenkundige Ramsey-getallen, een onderwerp dat zij in een begeleidende nota beogen te verkennen. Het artikel claimt niet de exacte groeisnelheid of bovengrenzen te bepalen, maar stelt een aanzienlijk sterkere ondergrens vast dan voorheen bekend.