Zahlenrätsel Der längste Mathe-Beweis der Welt

Drei Mathematiker haben ein Zahlenrätsel geknackt - mithilfe eines Supercomputers. Der Beweis umfasst 200 Terabyte. Sie wollen wissen, worum es geht? Okay, versuchen wir es.
Supercomputer als Mathematiker

Supercomputer als Mathematiker

Foto: dpa

Das Preisgeld war nur symbolisch: 100 Dollar hatte der US-Mathematiker Ronald Graham in den Achtzigerjahren demjenigen versprochen, der ein bis dahin ungelöstes Zahlenrätsel entschlüsselt. Es ging dabei um sogenannte Pythagoreische Tripel , also positive ganze Zahlen a, b, c, welche die Gleichung a2 + b2 = c2 erfüllen - Details zum Problem finden Sie weiter unten.

Nun vermelden drei Forscher , darunter auch der deutsche Informatiker Oliver Kullmann, dass sie das Rätsel geknackt haben. Allerdings mit extrem großem Aufwand: Ein Supercomputer, bestehend aus 800 Hochleistungsprozessoren, war fast zwei Tage lang damit ausgelastet - die 100 Dollar Preisgeld würden nicht mal für die Stromrechnung reichen. Die Lösung belegt auf der Festplatte sagenhafte 200 Terabyte - das entspricht mehr als 40 Millionen Fotos, wenn jedes 5 Megabyte groß ist.

"Mir ist kein anderer mathematischer Beweis von einer solchen Größe bekannt", sagt Oliver Kullmann, der an der Swansea University forscht und sich auf Algorithmen spezialisiert hat, mit denen man beispielsweise riesige Sudokus lösen könnte.

Das nun per Computer geknackte Rätsel ist, anders als die Lösung, noch gut zu verstehen. Gegeben sind die positiven ganzen Zahlen von 1 bis beispielsweise 10. Jede dieser zehn Zahlen soll entweder rot oder blau markiert werden, und zwar so, dass es keine drei gleich gefärbten Zahlen a, b, c gibt, für die gilt: a2 + b2 = c2.

Rot oder blau?

In unserem Beispiel der Zahlen von 1 bis 10 dürfen deshalb sowohl 3, 4 und 5 als auch 6, 8 und 10 nicht gleich gefärbt sein. Denn beide bilden Pythagoreische Tripel, bei ihnen gilt 32 + 42 = 52 beziehungsweise 62 + 82 = 102. Färbt man beispielsweise die 3 und die 6 rot, und alle übrigen acht Zahlen blau, dann ist die Bedingung der Aufgabe erfüllt.

Doch Ronald Graham hat die Frage ganz allgemein für eine beliebige natürliche Zahl n gestellt: Kann man jede der Zahlen von 1 bis n entweder rot oder blau färben, ohne dass es Pythagoreische Tripel a, b, c gibt, die gleich gefärbt sind?

Kullmann sowie seine Kollegen Marijn Heule und Victor Marek haben nun die Antwort geliefert: Bis zur Zahl 7824 ist die Färbung möglich (siehe folgende Grafik), doch bei 7825 ist Schluss. Dann klappt die Farbaufteilung aller natürlichen Zahlen von 1 bis 7825 nicht mehr.

Farbaufteilung der Zahlen von 1 bis 7824: Weiße Felder können blau oder rot sein

Farbaufteilung der Zahlen von 1 bis 7824: Weiße Felder können blau oder rot sein

Foto: Marijn Heule

Um dies zu beweisen, musste der Supercomputer im Prinzip alle möglichen Färbungen der 7825 Zahlen durchprobieren, wobei er raffiniert vorging, um die Rechenzeit zu begrenzen. Denn theoretisch sind 27825 Varianten möglich, was einer Zahl größer als 102300 entspricht. Nach dem systematischen Prüfen musste die Software am Ende feststellen, dass es keine Färbung gibt, bei der die Anforderung des Zahlenrätsels erfüllt ist.

Damit steht außerdem fest, dass die Färbung auch bei allen natürlichen Zahlen größer als 7825 nicht gelingen kann. Denn wenn sich 7825 Zahlen nicht aufteilen lassen, gelingt das erst recht nicht, wenn es noch mehr sind.

Zeile für Zeile überprüft

"Wir wussten nicht, ob es überhaupt eine Zahl gibt, bei der die Aufteilung nicht mehr klappt", sagt Kullmann. Das Finden der Lösungen für die Zahlen von 1 bis 7824 sei sehr schnell gegangen, "weil wir sofort aufgehört haben, wenn wir eine Lösung hatten". Bei 7825 mussten die Forscher dann einen Supercomputer mit 800 Kernen bemühen, der fast zwei Tage damit beschäftigt war.

Um sicherzugehen, dass der Computerbeweis auch stimmt, ließ Kullmanns Team den Algorithmus und das Ergebnis im Anschluss noch von einer anderen Software überprüfen. Hat das Programm wirklich alle Varianten durchgearbeitet? Hat es alle Fälle unterschieden? Das wurde Zeile für Zeile überprüft. Ein Mensch hätte sich nie und nimmer durch die 200 Terabyte arbeiten können.

Die Grafik zeigt eine Lösung für die Zahlen von 1 bis 7824. Ab 7825 gibt es keine Aufteilung mehr.

Die Grafik zeigt eine Lösung für die Zahlen von 1 bis 7824. Ab 7825 gibt es keine Aufteilung mehr.

Foto: Marijn Heule

Zum Aufspüren der Färbungen setzten die Forscher einen sogenannten Sat-Löser ein. Damit könne man auch große Sudokus lösen, erklärt Kullmann. "Die Software rät, was bei Sudokus ja eigentlich verpönt ist. Sie schaut dann nach dem Ergebnis, schlussfolgert, rät noch mal und findet eine Lösung oder einen Widerspruch."

Die nun vorgestellte Lösung sei als Methode interessant, das konkrete Zahlenrätsel hingegen weniger. "Das Problem ist ein hübsches Studienobjekt, um neue Methoden zu finden, die man auch an anderer Stelle anwenden kann", sagt Kullmann. Auf ähnliche Weise würden in der Industrie schwere Probleme gelöst. Mögliche Anwendungen seien das Knacken von Verschlüsselung und die Entwicklung von Mikroprozessoren.

Übrigens: Nicht alle Mathematiker sind begeistert von solchen Computerbeweisen - nicht zuletzt, weil ein Mensch ihre Richtigkeit in der Regel kaum noch prüfen kann. Doch immer öfter bemühen Mathematiker Software, etwa beim Beweis der legendären Kepler-Vermutung, in der es darum geht, Kugeln perfekt zu stapeln.

Womöglich lässt sich das nun geknackte Zahlenfärbungsproblem auch ganz klassisch mit Stift und Papier lösen. So wie man beispielsweise beweist, dass die Seitenlängen eines rechtwinkligen Dreiecks die Gleichung a2 + b2 = c2 erfüllen - der bekannte Satz des Pythagoras .

Ob es einen solchen klassischen Beweis mit Stift und Papier gibt, weiß derzeit niemand. Aber zumindest das, was dabei herauskommen muss, kennt die Welt mittlerweile: Bei 7825 ist Schluss.

Die Wiedergabe wurde unterbrochen.