537 ZAHLEN, SECHS FARBEN, KEINE SUMMEN

Hier ist ein Rätsel, das ein Kind verstehen kann. Nimm die Zahlen 1, 2, 3 und so weiter. Gib jeder eine Farbe. Die einzige Regel: Innerhalb einer Farbe dürfen nie zwei Zahlen zusammen mit ihrer Summe vorkommen. Die beiden Zahlen dürfen sogar gleich sein; ist also 2 rot, kann 4 nicht rot sein, denn 2 + 2 = 4.

Eine Menge ohne ein solches Trio heißt summenfrei. Wie weit kommt man, bevor die Regel einen zum Aufhören zwingt? Diese Grenze ist für k Farben die Schur-Zahl S(k). Das Problem geht auf eine Arbeit von I. Schur aus dem Jahr 1916 zurück, den ersten Eintrag im Literaturverzeichnis.

Eine berühmt hartnäckige Folge

Mit einer Farbe steckt man sofort fest: 1 + 1 = 2, also kann die Farbe nur die Zahl 1 enthalten. Die bekannten Werte sind:

• S(1) = 1
• S(2) = 4
• S(3) = 13
• S(4) = 44
• S(5) = 160, bestimmt von M. J. H. Heule (in einer 2018 veröffentlichten Arbeit).

Für sechs Farben kennt niemand die Antwort. Seit 2000 reichte die beste bekannte Konstruktion, gefunden von H. Fredricksen und M. M. Sweet durch eine Suche unter symmetrischen Färbungen, bis 536. Diese Zahl wird seither als beste untere Schranke zitiert – eine Untergrenze: S(6) ist mindestens so groß, und sein wahrer Wert, noch unbekannt, könnte höher liegen.

Eine Zahl mehr

Zhiyang Chen und Fan Long von der University of Toronto sowie Ligeng Zhu von NVIDIA Research schieben sie nun auf 537. Ihr Beweis ist von der Art, die Mathematiker für ihre Unverblümtheit lieben: Sie drucken die Antwort ab. Sechs Zahlenlisten – mit 76, 76, 88, 70, 76 und 151 Zahlen –, die zusammen jede ganze Zahl von 1 bis 537 genau einmal enthalten, wobei keine Farbe x, y und x + y enthält. Die Prüfung besteht darin, jede Summe innerhalb jeder Liste zu testen, eine schnelle Aufgabe für einen Computer.

Die Lösung hat eine auffällige Gestalt. Sie ist symmetrisch: Jede Zahl x hat dieselbe Farbe wie 538 − x. Die ersten vier Farben beginnen bei 1, 2, 3 und 4; die fünfte taucht erst ab 38 auf, die sechste erst ab 151, und die sechste Farbe füllt den gesamten Mittelabschnitt von 237 bis 301. Selbst die erste Farbe lässt sich aus einem Keim von nur 14 kleinen Zahlen durch eine Spiegelung, eine Verschiebung und eine zusätzliche Zahl wieder aufbauen.

Wellen weiter oben

Schur-Zahlen speisen einander. Bekannte Rezepte verwandeln eine gute Färbung mit k Farben in eine mit k + 2 oder k + 5 Farben: S(k + 2) ist mindestens 10 S(k) + 2, und S(k + 5) mindestens 380 S(k) + 148. So hebt die neue 537 weitere Rekorde an:

• acht Farben: von 5.362 auf 5.372 – und das Team hat auch diese Färbung explizit konstruiert;
• elf Farben: von 203.828 auf 204.208;
• dreizehn Farben: von 2.038.282 auf 2.042.082.

Sie verbessert auch eine Ramsey-Zahl, R₆(3): die kleinste Anzahl von Punkten, alle paarweise verbunden, bei der jede Färbung der Verbindungen mit sechs Farben ein einfarbiges Dreieck enthalten muss. Nummeriert man 538 Punkte von 0 bis 537 und färbt die Verbindung zwischen i und j mit der Farbe ihrer Differenz |i − j|, lässt die summenfreie Färbung kein einfarbiges Dreieck entstehen. Also ist R₆(3) mindestens 539, statt bisher 538.

131 Wege, es zu tun

Die Suche fand nicht eine Lösung, sondern 131 wirklich verschiedene, die die Autoren in fünf Familien einteilen und vollständig veröffentlichen. Die meisten bleiben sehr nah an der ersten: Die aus den Familien F1 bis F4 stimmen mit ihr in mindestens 462 der 537 Positionen überein. Eine Familie bricht die Spiegelsymmetrie; eine andere entsteht durch Mischen dreier durcheinandergewürfelter Kopien des Originals.

Die Arbeit erklärt nicht, wie die Suche selbst durchgeführt wurde. Die Autoren betonen, dass ihre 131 Färbungen kein vollständiger Katalog der Lösungen mit sechs Farben sind, sondern nur neue Ausgangspunkte für alle, die 538 versuchen wollen.