🔢 mathematics

Three-color van der Waerden numbers grow super-exponentially

Diese Arbeit stellt fest, dass die dreifarbige van-der-Waerden-Zahl $w(k;3)$ superexponentiell wächst, indem sie eine Dreifärbung der bis zu $2^{k (\log^* k)/4}$ Integern konstruiert, die frei von monochromen $k$ -gliedrigen arithmetischen Progressionen ist, während sie gleichzeitig eine neue untere Schranke liefert, die ein langjähriges Problem von Erdős und Graham bezüglich kanonischer van-der-Waerden-Zahlen löst.

Ursprüngliche Autoren: Jacob Fox, Zach Hunter

Veröffentlicht 2026-06-02

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jacob Fox, Zach Hunter

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie haben eine sehr lange Reihe nummerierter Kacheln, von 1 bis zu einer riesigen Zahl $N$ . Sie möchten jede Kachel mit einer von drei Farben bemalen (sagen wir Rot, Blau und Grün).

Die große Frage, die Mathematiker seit fast einem Jahrhundert beschäftigt, lautet: Wie lang muss die Reihe sein, bevor man gezwungen ist, eine „monochromatische arithmetische Progression“ zu erzeugen?

Eine arithmetische Progression ist einfach eine Folge von Zahlen, die in gleichen Abständen ansteigen, wie zum Beispiel 5, 10, 15, 20. Wenn Sie die 5, 10, 15 und 20 alle Rot malen, haben Sie eine „monochromatische“ (einfarbige) Progression erstellt.

Die Zahl $w(k; 3)$ ist die Länge der Reihe, in der Sie – egal wie geschickt Sie malen – nicht vermeiden können, eine Folge von $k$ Kacheln in einer Reihe (mit gleichem Abstand) zu erzeugen, die alle die gleiche Farbe haben.

Das alte Rätsel

Lange Zeit wussten Mathematiker, dass diese Zahlen existieren, aber sie wussten nicht, wie schnell sie mit steigendem $k$ wachsen.

Einige dachten, diese Zahlen wachsen wie eine Standard-Exponentialfunktion (wie $2^k$ ).
Andere, einschließlich des berühmten Mathematikers Paul Erdős, vermuteten, dass die Zahlen für drei oder mehr Farben super-exponentiell wachsen. Das bedeutet, sie wachsen so schnell, dass sie selbst die mächtigsten Exponentialfunktionen in den Schatten stellen. Es ist wie der Vergleich zwischen einer Schnecke und einer Rakete, die schneller als das Licht beschleunigt.

Erdős bot ein Preisgeld von 500 Dollar für jeden, der beweisen konnte, dass dieses super-exponentielle Wachstum für drei Farben besteht.

Die neue Entdeckung

In dieser Arbeit beweisen Jacob Fox und Zach Hunter schließlich, dass Erdős recht hatte.

Sie zeigen, dass die Reihe der Kacheln für drei Farben astronomisch lang sein muss, bevor man gezwungen ist, eine monochromatische Sequenz zu erzeugen. Speziell beweisen sie, dass die Zahl größer als $2^{k(\log^* k)/4}$ ist.

Um die Größe dieser Zahl zu verstehen, stellen Sie sich den „iterierten Logarithmus“ ( $\log^* k$ ) vor. Dies ist eine Zahl, die so langsam wächst, dass sie fast flach verläuft. Selbst für eine Zahl, die so groß ist wie die Anzahl der Atome im Universum, beträgt $\log^* k$ nur etwa 5.

Die Analogie: Wenn exponentielles Wachstum wie eine Kaninchenpopulation ist, die sich jeden Tag verdoppelt, dann ist dieses neue Ergebnis wie eine Kaninchenpopulation, die sich verdoppelt, dann die Geschwindigkeit der Verdopplung sich verdoppelt, dann die Geschwindigkeit der Geschwindigkeit der Verdopplung sich verdoppelt und so weiter, aber erst, nachdem man eine Zahl gewartet hat, die sich kaum verändert. Das Ergebnis ist eine Zahl, die so gewaltig ist, dass sie jeder Vorstellungskraft spottet.

Wie haben sie es geschafft? (Die mathematischen Tricks)

Die Autoren haben nicht nur geraten; sie haben eine „Konstruktion“ (eine spezifische Art, die Kacheln zu bemalen) entworfen, die das Muster so lange wie möglich vermeidet. Sie verwendeten dazu einige kluge mathematische Tricks:

Das „Dünne Netz“ (Die Löcher finden):
Zuerst fanden sie einen Weg, eine riesige Gruppe von Zahlen auszuwählen, die sehr „dicht“ (kompakt) sind, aber irgendwie keine arithmetischen Progressionen bilden. Denken Sie an ein großes Fischernetz mit sehr großen Löchern. Man kann viele Fische (Zahlen) fangen, aber die Löcher sind so perfekt angeordnet, dass man niemals ein bestimmtes Muster von Fischen fängt, die in einer geraden Linie schwimmen.
Der „Zufällige Versatz“ (Das Mischen):
Sie nahmen zwei dieser speziellen Gruppen und kombinierten sie. Aber anstatt sie einfach nur übereinanderzustapeln, verwendeten sie einen „zufälligen Versatz“. Stellen Sie sich vor, Sie haben zwei Kartendecks. Sie mischen ein Deck und schieben das andere dann leicht über das erste. Diese zufällige Bewegung bricht die Muster auf, die entstanden wären, wenn man sie einfach nur ordentlich gestapelt hätte.
Die „Leiter“ (Den Prozess iterieren):
Die wahre Magie liegt darin, dass sie diesen Misch- und Kombinationsprozess immer und immer wieder wiederholen können.

Beginnen Sie mit einer kleinen Gruppe.
Mischen und kombinieren Sie, um eine größere Gruppe zu erhalten, die immer noch das Muster vermeidet.
Machen Sie es erneut, um eine noch größere Gruppe zu erhalten.
Sie können diesen Prozess etwa $\log^* k$ Mal wiederholen.

Da sie diesen Prozess so oft wiederholen können, wird die endgültige Anzahl der Kacheln, die sie bemalen können, ohne ein Muster zu erzeugen, unglaublich groß.

Der Bonus: Ein altes Rätsel lösen

Während sie dies für drei Farben bewiesen, lösten sie auch ein verwandtes Rätsel, das Erdős und Graham über „kanonische“ van der Waerden-Zahlen gestellt hatten.

In dieser Version suchen Sie nicht nur nach einer Sequenz einer einzigen Farbe, sondern nach einer Sequenz, die entweder alle eine Farbe hat ODER alle unterschiedliche Farben (wie Rot, Blau, Grün, Rot, Blau, Grün... nein, nur alle distinkten Farben).

Das Ergebnis: Sie bewiesen, dass die Anzahl der Kacheln, die nötig sind, um dieses Muster zu erzwingen, ebenfalls super-groß ist. Sie wächst schneller als jede einfache Potenz von $k$ . Dies klärt eine jahrzehntealte Frage darüber, ob diese Zahlen schnell genug wachsen, um als „super-exponentiell“ zu gelten.

Zusammenfassung

Das Problem: Wie lang muss die Zahlenreihe sein, bevor man zwangsläufig ein geradliniges Muster derselben Farbe sieht?
Die Antwort: Für drei Farben muss die Reihe unvorstellbar lang sein. Sie wächst viel schneller, als es bisher bewiesen wurde.
Die Methode: Sie bauten einen mathematischen „Schild“ unter Verwendung von zufälligen Verschiebungen und geschichteten Kombinationen, der die Muster für eine rekordverdächtige Zeit fernhält.
Die Bedeutung: Dies bestätigt eine berühmte Vermutung von Paul Erdős und schließt ein bedeutendes Kapitel in der Geschichte der Kombinatorik.

Technisches Resümee: Drei-Farben-van-der-Waerden-Zahlen wachsen superexponentiell

Problemstellung
Die vorliegende Arbeit befasst sich mit der Wachstumsrate von van-der-Waerden-Zahlen, bezeichnet als $w(k; r)$ . Diese Zahl ist definiert als die kleinste ganze Zahl $N$ , sodass jede $r$ -Färbung der Menge $\{1, 2, \dots, N\}$ eine monochromatische arithmetische Progression der Länge $k$ enthält. Während die Existenz dieser Zahlen durch den van-der-Waerden-Satz garantiert ist, bleibt ihre präzise asymptotische Wachstumsrate ein fundamentales offenes Problem.

Historisch gesehen war das Wachstum von $w(k; r)$ Gegenstand intensiver Spekulationen. Für ein festes $r$ wurde von Erdős vermutet, dass $w(k; 2)$ superexponentiell wächst (d. h. $\limsup_{k \to \infty} w(k; 2)^{1/k} = \infty$ ). Im Gegensatz dazu legten andere Vermutungen ein lineares exponentielles Wachstum nahe, spezifisch $\lim_{k \to \infty} w(k; r)^{1/k} = r$ . Vor dieser Arbeit waren die besten bekannten unteren Schranken für $w(k; r)$ weitgehend aus dem Lovász Local Lemma oder spezifischen algebraischen Konstruktionen abgeleitet worden, was Schranken der Form $w(k; r) \geq r^{k-1}/(4k)$ oder, für ein festes $r \geq 5$ , Schranken der Form $(3r/3)^{(1-o(1))k}$ ergab. Die Autoren merken an, dass ein vorangegangenes Ergebnis von Hunter [20] die lineare exponentielle Vermutung für $r \geq 5$ widerlegt hat, der Fall für $r=3$ (und das allgemeine Verhalten für kleine feste $r$ ) jedoch ungelöst blieb.

Methodik
Die Autoren entwickeln eine neuartige probabilistische Konstruktion, um untere Schranken für $w(k; r)$ zu etablieren. Die Methodik stützt sich auf drei primäre Komponenten:

Dichte progressionsfreie Mengen in zyklischen Gruppen:
Die Autoren konstruieren sehr dichte Teilmengen zyklischer Gruppen $\mathbb{Z}_N$ , die keine $k$ -gliedrigen arithmetischen Progressionen ( $k$ -APs) enthalten. Sie nutzen eine Erweiterung der Erdős-Turán-Konstruktion (Mengen von ganzen Zahlen, bei denen in der Basis $p$ keine Ziffer gleich $p-1$ vorkommt), die an zyklische Gruppen angepasst wurde. Entscheidend ist, dass sie beweisen, dass es „Hitting Sets“ (Lemma 2.8) gibt, die spärlich sind (Dichte $\leq \epsilon$ ), aber jede $k$ -AP in einer zyklischen Gruppe mit einem konstanten Bruchteil ihrer Elemente schneiden. Dies wird durch die Auswahl zufälliger Kongruenzklassen modulo einer Menge von Primzahlen erreicht.
Konsequenzen des Lovász Local Lemma (LLL):
Das Papier verwendet die symmetrische Version des Lovász Local Lemma, um die Existenz von Färbungen zu demonstrieren, bei denen keine Farbklasse einen „großen“ Bruchteil irgendeiner $k$ -AP enthält. Speziell etabliert Korollar 3.3, dass man für Gruppen der Ordnung $N$ , die keine kleinen Primfaktoren besitzen, Teilmengen von Farben den Vertices zuordnen kann, sodass keine $k$ -AP monochromatisch oder nahezu monochromatisch ist.
Random Shifted Product Konstruktionen:
Die zentrale technische Innovation ist eine verfeinerte „Random Shifted Product“-Konstruktion (Lemmata 4.2 und 4.3). Im Gegensatz zu Standard-Produktfärbungen, welche die Anzahl der Farben multiplizieren, ermöglicht diese Methode den Autoren, Färbungen kleinerer Gruppen in eine größere Gruppe zu kombinieren, während die Anzahl der Farben fix bleibt (oder kontrolliert erhöht wird).

Mechanismus: Gegeben sei eine Färbung $c_1$ von $H_1$ und $c_2$ von $H_2$ . Die Konstruktion definiert eine Färbung auf $H_1 \times H_2$ , indem sie die Fasern der Projektion auf $H_2$ unabhängig verschiebt und die Farben basierend auf der Farbe des Basiselements in $H_1$ permutiert.
Iterativer Prozess: Die Autoren iterieren diesen Konstruktionsschritt. In jedem Schritt kombinieren sie eine Färbung einer Gruppe $\mathbb{Z}_{n_{j-1}}$ mit einer Färbung einer zyklischen Gruppe primärer Ordnung $\mathbb{Z}_{q_j}$ . Die Konstruktion vergrößert die Größe der Gruppe um einen Faktor, der exponentiell in $k$ ist, während sie einen „doppel-exponentiellen“ Verlust im Dichteparameter der „guten“ Farbklasse erleidet. Durch eine sorgfältige Abstimmung dieser Parameter kann der Prozess etwa $(\log^* k)/2$ -mal iteriert werden.

Wesentliche Beiträge und Ergebnisse

Superexponentielles Wachstum für drei Farben:
Das primäre Resultat (Theorem 1) beweist, dass für hinreichend große $k$ die Drei-Farben-van-der-Waerden-Zahl erfüllt:
$w(k; 3) > 2^{k(\log^* k)/4}$
Dies etabliert, dass $w(k; 3)$ schneller wächst als jede Exponentialfunktion von $k$ , und widerlegt damit die Vermutung, dass $\lim_{k \to \infty} w(k; r)^{1/k} = r$ für $r \geq 3$ gilt.
Untere Schranken für viele Farben:
Theorem 2 liefert eine untere Schranke für das Regime, in dem die Anzahl der Farben $r$ groß im Verhältnis zu $k$ ist (speziell $r \geq (\log k)^{3/\epsilon}$ ):
$w(k; r) \geq r^{(1-\epsilon)k \log k}$
Dies verbessert die bisherigen Schranken im „viele Farben“-Regime.
Lösung des Erdős-Graham-Problems:
Die Autoren adressieren die kanonische van-der-Waerden-Zahl $H(k)$ , definiert als die kleinste Zahl $N$ , sodass jede Färbung von $[N]$ eine monochromatische oder Regenbogen- $k$ -AP enthält. Erdős und Graham vermuteten, ob $H(k)^{1/k}/k \to \infty$ . Unter Verwendung ihrer verbesserten unteren Schranke auf $w(k; k-1)$ beweisen die Autoren (Theorem 3), dass:
$H(k) \geq k^{(1-o(1))k \log k}$
Dies bestätigt, dass $H(k)$ superexponentiell wächst, und löst das von Erdős und Graham formulierte offene Problem.

Bedeutung
Das Papier behauptet, dass das Wachstum von van-der-Waerden-Zahlen für drei oder mehr Farben superexponentiell ist, ein Ergebnis, das das Verständnis dieser kombinatorischen Zahlen grundlegend verändert. Die Bedeutung liegt in:

Widerlegung der linearen exponentiellen Vermutung: Es zeigt definitiv, dass $w(k; r)$ nicht wie $r^k$ für $r \geq 3$ verhält.
Methodische Weiterentwicklung: Die Einführung der „Random Shifted Product“-Konstruktion erlaubt es, probabilistische Argumente zu iterieren, während die Anzahl der Farben konstant gehalten wird – eine Technik, die die Autoren als effizienter als frühere Versionen für $r \geq 5$ beschreiben.
Kanonische Ramsey-Theorie: Die Ergebnisse liefern eine starke Lösung für das Erdős-Graham-Problem bezüglich kanonischer van-der-Waerden-Zahlen und zeigen, dass selbst wenn man für Regenbogen-Progressionen erlaubt ist, die erforderliche $N$ weitaus größer ist als bisherige untere Schranken nahelegten.

Die Autoren merken an, dass ihre Techniken zwar allgemein sind, die spezifische Anwendung hier jedoch darauf abzielt, diese unteren Schranken zu etablieren. Sie legen nahe, dass diese Konstruktionen auch zur Erzielung neuer Schranken für andere arithmetische Ramsey-Zahlen anwendbar sein könnten, ein Thema, das sie in einer Begleitnotiz untersuchen wollen. Das Papier beansprucht nicht, die exakte Wachstumsrate oder obere Schranken zu bestimmen, sondern etabliert eine signifikant stärkere untere Schranke als bisher bekannt.