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
DPA

Supercomputer als Mathematiker

Von


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
Marijn Heule

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

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.
Marijn Heule

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

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.



insgesamt 65 Beiträge
Alle Kommentare öffnen
Seite 1
austromir 30.05.2016
1. Vergeudung
Eine Vergeudung von Rechenzeit und von wissenschaftlicher Arbeitszeit. Wenn der Bericht stimt haben Wissenschaftler ihre Zeit damit verbracht, ein Programm zu schreiben, das solange Dinge ausprobiert bis eine bestimmte Bedingung nicht mehr erfüllt ist. Nett aber: Supercomputer können erheblich mehr. Was die Kosten angeht dürfte das Ganze bei etwa 800 Euro gekostet haben. Das ist zwar nicht ganz teuer aber positive Werbung für die Wissenschaft sieht auch anders aus.
tomtomtomtom 30.05.2016
2.
Warum sollte man es verpönen für einen Beweis durch Gegenbeispiel auf Rechnerleistung zurückzugreifen? Einen Cluster mit 800 Kernen als Superrechner zu bezeichnen finde ich dagegen höchst amüsant; in öffentlichen verteilten Rechnenetzen wie z.B. Boinc werden für ähnliche Brute-Force-Ansätze Millionen von Kernen bemüht. Schön wäre gewesen, kurz auf die Komplexitätsklasse NP und den Satz von Cook einzugehen und in einigen Sätzen zu erklären warum der SAT-Algorithmus hier einen geschickten Ansatz für die Komplexitätsklasse liefert.
Layer_8 30.05.2016
3.
OK, wenn man vermutet, dass das Problem endlich ist, kann man auch brute force verwenden. Trotzdem ist die Erschaffung des entsprechenden Algorithmus eine menschliche Aufgabe gewesen, und somit hat kein Computer etwas "bewiesen".
frutsch 30.05.2016
4. Und weiter?
Ist das alles? Keine weiteren Nachfragen, Herr/Frau Redakteur? Wie viele solcher Tripel gibt es denn? Könnte man ggf. alle Tripel veröffentlichen? Welches ist der größte Tripel? So eine DPA-Meldung abzudrucken, ist einfach. Aber auch genug?
hartmannsfeld 30.05.2016
5. sorry...
aber ausprobieren ist kein mathematischer Beweis. Ein Zeichen aussterbenden Intellekts wenn das Preisgeld gezahlt würde.
Alle Kommentare öffnen
Seite 1

© SPIEGEL ONLINE 2016
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.