WIE VIELE FARBEN, UM DEN RAUM ZU BEMALEN? FÜR EIN TYPISCHES LINEAL HÖCHSTENS 2d

Nimm jeden Punkt einer Ebene und gib jedem eine Farbe. Eine Regel: Zwei Punkte im Abstand von genau einer Einheit dürfen nie dieselbe Farbe haben. Wie viele Farben braucht man mindestens?

Das ist das Hadwiger-Nelson-Problem. Es stammt aus dem Jahr 1950 und ist nach den Worten der Autoren eines der berühmtesten offenen Probleme der diskreten Geometrie. Lange wusste man nur, dass die Antwort zwischen 4 und 7 liegt. Ein Durchbruch vor Kurzem hob die untere Schranke auf 5. Die exakte Antwort ist weiterhin unbekannt.

Ein anderes Lineal

Abstände müssen nicht mit einem gewöhnlichen Lineal gemessen werden. Mathematiker definieren viele andere Normen — Arten, Längen zu messen —, die jeweils durch ihre „Einheitskugel“ beschrieben werden: die Menge der Punkte, die höchstens 1 vom Mittelpunkt entfernt sind. Beim üblichen Abstand ist das eine runde Kugel; bei anderen Normen kann es jede konvexe Form sein, die zum Mittelpunkt symmetrisch ist.

Für jede Norm in der Ebene liegt die Antwort auf das Färbungsrätsel zwischen 4 und 7. In d Dimensionen ist sie für jede Norm höchstens exponentiell in d, und für viele natürliche Normen — auch die übliche euklidische — zugleich mindestens exponentiell: Die Zahl der Farben explodiert mit wachsender Dimension.

Ist diese Explosion die Regel? Noga Alon (Princeton University und Universität Tel Aviv), Matija Bucić (Universität Wien) und James Davies (Universität Leipzig) untersuchten eine typische Norm. Es gibt keine natürliche Art, eine Norm „zufällig“ zu wählen, deshalb nutzen sie einen topologischen Begriff: Eine Eigenschaft gilt für eine typische Norm, wenn die Ausnahmen eine vernachlässigbare („magere“) Menge bilden. Frühere Arbeiten von Alon, Bucić und Lisa Sauermann hatten gezeigt, dass eine typische Norm höchstens 2ᵈ Farben braucht, und gefragt, wie nah das an der Wahrheit liegt.

Linear statt exponentiell

Die Antwort: weit davon entfernt. Die neue Arbeit beweist,

• dass für eine typische Norm im d-dimensionalen Raum immer 2d Farben genügen;
• dass das bestmöglich ist: Eine offene Menge von Normen erfordert mindestens 2d Farben. Manche Normen brauchen also genau 2d.

In zehn Dimensionen braucht eine typische Norm höchstens zwanzig Farben, während der übliche Abstand eine exponentiell wachsende Zahl verlangt. Laut den Autoren ist es zudem das erste Mal, dass die Färbungszahl für eine „strikt konvexe“ Norm in beliebiger Dimension d exakt bestimmt wird.

Die untere Schranke nutzt eine raffinierte Falle. Man suche 2d Punkte, die alle genau eine Einheit voneinander entfernt sind, außer zweien, a und b, die eine halbe Einheit auseinanderliegen. Dann füge man das Spiegelbild der ganzen Anordnung an a hinzu. Mit weniger als 2d Farben müssten sowohl b als auch sein Spiegelbild die Farbe von a annehmen — doch die beiden liegen genau eine Einheit auseinander. Widerspruch. Ein Stabilitätslemma zeigt, dass diese Anordnung jede kleine Änderung der Norm übersteht.

Ein einsamer Läufer in hohen Dimensionen

Die obere Schranke färbt jeden Punkt danach, wo eine geschickt gewählte Projektion von ihm landet, in Scheiben der Breite 1/(2d). Damit das funktioniert, braucht es eine Schlüsselzutat, die die Autoren als hochdimensionale Matrixversion der berühmten Lonely-Runner-Vermutung (Vermutung vom einsamen Läufer) beschreiben:

sup over x of minᵢ ‖aᵢ · x − bᵢ‖ ≥ k / (2n)

wobei ‖t‖ der Abstand von t zur nächsten ganzen Zahl ist, für beliebige n Vektoren aᵢ in k Dimensionen, von denen je k linear unabhängig sind. Diese Aussage beweist auch eine Vermutung von I. J. Schoenberg aus dem Jahr 1978 zur „Sichtblockade“ (view obstruction) — der Frage, wie dick periodische Platten sein müssen, um jeden Blick ins Unendliche zu versperren —, die die Autoren als eines der klassischsten offenen Probleme des Gebiets bezeichnen, sowie eine verwandte Vermutung von Henze und Malikiosis.

Die Maschine in der Danksagung

Die Autoren sind deutlich: „ChatGPT 6 Pro hat uns den Beweis der letzten Zutat geliefert, die wir für den Beweis von Theorem 1 brauchten, nämlich den von Lemma 7, nach einer längeren Diskussion“, in der sie ihre eigenen Beobachtungen geteilt hatten — darunter die Idee der Induktion und die allgemeine Strategie. „Auch das Argument für die untere Schranke wurde mithilfe von ChatGPT 6 Pro gefunden.“

Fragen bleiben offen. Der exakte Wert 2d ist auf einer offenen Menge von Normen bewiesen, nicht für alle typischen. Und für den gewöhnlichen euklidischen Abstand erwarten die Autoren in jeder Dimension echt mehr als 2d Farben — was in den Dimensionen 2, 4, 7, 8 sowie ab 9 bereits bekannt ist, in den Dimensionen 3, 5 und 6 aber noch offen.