Die Antwort auf das Leben, das Universum und alles
Ein Team unter der Leitung von Andrew Sutherland vom MIT und Andrew Booker von der Universität Bristol hat das letzte Stück eines berühmten, 65 Jahre alten mathematischen Rätsels gelöst, und zwar mit einer Antwort auf die schwer fassbare Zahl 42.
Die Zahl 42 ist besonders für Fans des Science-Fiction-Romans „Per Anhalter durch die Galaxis“ von Douglas Adams von Bedeutung, denn diese Zahl ist die Antwort, die ein Supercomputer auf „die ultimative Frage nach dem Leben, dem Universum und allem“ gibt.
Booker wollte auch die Antwort auf 42 wissen. Das heißt, gibt es drei Würfel, deren Summe 42 ist?
Dieses Rätsel der Summe von drei Würfeln, das erstmals 1954 an der Universität Cambridge aufgestellt wurde und als Diophantische Gleichung x3+y3+z3=k bekannt ist, forderte Mathematiker heraus, Lösungen für Zahlen von 1-100 zu finden. Bei kleineren Zahlen ist diese Art von Gleichung leichter zu lösen: 29 kann zum Beispiel als 33 + 13 + 13 geschrieben werden, während 32 unlösbar ist. Mit Hilfe verschiedener Techniken und Supercomputer wurden schließlich alle Gleichungen gelöst oder als unlösbar erwiesen, mit Ausnahme von zwei Zahlen: 33 und 42.
Booker entwickelte einen ausgeklügelten Algorithmus und verbrachte Wochen am Supercomputer seiner Universität, als er kürzlich die Lösung für 33 fand. Als er sich jedoch der Lösung für 42 zuwandte, stellte Booker fest, dass der Rechenaufwand um eine Größenordnung höher war und die Fähigkeiten seines Supercomputers übersteigen könnte. Booker sagt, er habe viele Hilfsangebote erhalten, um die Antwort zu finden, aber stattdessen wandte er sich an seinen Freund Andrew „Drew“ Sutherland, einen leitenden Forscher in der Abteilung für Mathematik. „Er ist ein weltweiter Experte für diese Art von Dingen“, sagt Booker.
Sutherland, dessen Spezialgebiet massiv-parallele Berechnungen sind, brach 2017 den Rekord für den größten Compute-Engine-Cluster mit 580.000 Kernen auf Preemptible Virtual Machines, dem größten bekannten High-Performance-Computing-Cluster, der in der öffentlichen Cloud läuft.
Wie andere Zahlentheoretiker, die sich mit arithmetischer Geometrie beschäftigen, kannte er das Problem der „Summe von drei Würfeln“. Und die beiden hatten schon früher zusammengearbeitet, als sie beim Aufbau der L-functions and Modular Forms Database (LMFDB) halfen, einem Online-Atlas mit mathematischen Objekten, die mit dem so genannten Langlands-Programm zusammenhängen. „Ich war begeistert, als Andy mich bat, an diesem Projekt mitzuarbeiten“, sagt Sutherland.
Booker und Sutherland diskutierten die algorithmische Strategie, die bei der Suche nach einer Lösung für 42 verwendet werden sollte. Wie Booker bei seiner Lösung für 33 festgestellt hatte, wussten sie, dass sie nicht alle Möglichkeiten für x, y und z ausprobieren mussten.
„Es gibt einen einzigen ganzzahligen Parameter, d, der eine relativ kleine Menge von Möglichkeiten für x, y und z bestimmt, so dass der absolute Wert von z unter einer gewählten Suchgrenze B liegt“, sagt Sutherland. „Bei dem Versuch, 33 zu knacken, war die Suchgrenze B 1016, aber dieses B erwies sich als zu klein, um 42 zu knacken; wir verwendeten stattdessen B = 1017 (1017 ist 100 Millionen Milliarden).
Ansonsten wäre der Hauptunterschied zwischen der Suche nach 33 und der Suche nach 42 die Größe der Suche und die verwendete Computerplattform. Dank eines großzügigen Angebots der britischen Firma Charity Engine konnten Booker und Sutherland die Rechenleistung von über 400.000 Heim-PCs von Freiwilligen auf der ganzen Welt anzapfen, denen jeweils eine Reihe von Werten für d zugewiesen wurde. Die Berechnungen auf jedem PC laufen im Hintergrund, so dass der Besitzer seinen PC weiterhin für andere Aufgaben nutzen kann.
Sutherland ist auch ein Fan von Douglas Adams, so dass das Projekt unwiderstehlich war.
Die Methode, Charity Engine zu nutzen, ähnelt einem Teil der Handlung um die Zahl 42 im Roman „Per Anhalter“: Nachdem sich die Antwort von Deep Thought auf die Zahl 42 für die Wissenschaftler als unbefriedigend erweist, weil sie die Frage, die sie beantworten soll, nicht kennen, beschließt der Supercomputer, die ultimative Frage zu berechnen, indem er einen Supercomputer baut, der von der Erde angetrieben wird … mit anderen Worten, indem er eine weltweite, massiv parallele Rechenplattform einsetzt.
„Das ist ein weiterer Grund, warum ich diese Berechnung auf der Charity Engine wirklich gerne durchgeführt habe – wir haben tatsächlich einen Computer im Maßstab eines Planeten benutzt, um eine seit langem offene Frage zu klären, deren Antwort 42 ist.“
Sie führten eine Reihe von Berechnungen mit einer geringeren Kapazität durch, um sowohl ihren Code als auch das Charity Engine-Netzwerk zu testen. Dann haben sie eine Reihe von Optimierungen und Anpassungen vorgenommen, um den Code besser für eine massiv verteilte Berechnung geeignet zu machen, als für eine Berechnung auf einem einzelnen Supercomputer, sagt Sutherland.
Warum konnte der Supercomputer in Bristol dieses Problem nicht lösen?
„Nun, jeder Computer *kann* das Problem lösen, vorausgesetzt, man ist bereit, lange genug zu warten, aber mit etwa einer halben Million PCs, die parallel an dem Problem arbeiten (jeder mit mehreren Kernen), konnten wir die Berechnung viel schneller abschließen, als wir es mit der Maschine in Bristol (oder einer der Maschinen hier am MIT) hätten tun können“, sagt Sutherland.
Die Verwendung des Charity-Engine-Netzwerks ist auch energieeffizienter. „Wir nutzen größtenteils Rechenressourcen, die sonst vergeudet würden“, sagt Sutherland. „Wenn Sie an Ihrem Computer sitzen und eine E-Mail lesen oder an einer Tabellenkalkulation arbeiten, nutzen Sie nur einen winzigen Bruchteil der verfügbaren CPU-Ressourcen, und die Charity-Engine-Anwendung, die auf der Berkeley Open Infrastructure for Network Computing (BOINC) basiert, macht sich dies zunutze. Infolgedessen ist der Kohlenstoff-Fußabdruck dieser Berechnung – bezogen auf den Strom, den unsere Berechnungen den PCs im Netzwerk über das hinaus verursacht haben, was sie ohnehin verbraucht hätten – geringer, als wenn wir einen Supercomputer verwendet hätten.“
Sutherland und Booker führten die Berechnungen über mehrere Monate durch, aber der letzte erfolgreiche Lauf wurde in nur wenigen Wochen abgeschlossen. Als die E-Mail von Charity Engine eintraf, enthielt sie die erste Lösung für x3+y3+z3=42:
42 = (-80538738812075974)^3 + 80435758145817515^3 + 12602123297335631^3
„Als ich die Nachricht hörte, war das definitiv ein Moment, in dem ich mir die Hände reiben konnte“, sagt Sutherland. „Bei diesen großen Berechnungen steckt man viel Zeit und Energie in die Optimierung der Implementierung, die Optimierung der Parameter und das Testen und erneute Testen des Codes über Wochen und Monate hinweg, ohne wirklich zu wissen, ob sich der ganze Aufwand lohnt.
Aber beide interessieren sich mehr für ein einfacheres, aber rechnerisch anspruchsvolleres Rätsel: ob es mehr Antworten für die Summe von drei Würfeln für 3 gibt.
„Es gibt vier sehr einfache Lösungen, die dem Mathematiker Louis J. Mordell, der 1953 schrieb: ‚Ich weiß nichts über die ganzzahligen Lösungen von x3 + y3 + z3 = 3 außer der Existenz der vier Dreiergruppen (1, 1, 1), (4, 4, -5), (4, -5, 4), (-5, 4, 4); und es muss in der Tat sehr schwierig sein, etwas über andere Lösungen herauszufinden.‘ Dieses Zitat begründete einen Großteil des Interesses am Problem der Summe von drei Würfeln und insbesondere am Fall k=3. Es wird zwar vermutet, dass es unendlich viele Lösungen geben sollte, aber trotz mehr als 65 Jahren Suche kennen wir nur die einfachen Lösungen, die bereits Mordell bekannt waren. Es wäre sehr spannend, eine weitere Lösung für k=3 zu finden.“