Lesezeit ca. 14 Min.

MATHEMATIK MIT FLIESEN UND BAUKLÖTZEN


Logo von Spektrum der Wissenschaft
Spektrum der Wissenschaft - epaper ⋅ Ausgabe 3/2022 vom 19.02.2022

Artikelbild für den Artikel "MATHEMATIK MIT FLIESEN UND BAUKLÖTZEN" aus der Ausgabe 3/2022 von Spektrum der Wissenschaft. Dieses epaper sofort kaufen oder online lesen mit der Zeitschriften-Flatrate United Kiosk NEWS.

Bildquelle: Spektrum der Wissenschaft, Ausgabe 3/2022

VIELFACH GESTAPELT Das Füllen eines Volumens kann verblüffend kompliziert werden.

spektrum.de/ artikel/1974565

Vor 90 Jahren stellte Ott-Heinrich Keller (1906–1990) während seiner Dissertation eine inzwischen nach ihm benannte Vermutung auf, die mit der Kachelung von Räumen zu tun hat. Keller war kein Fliesenleger, sondern Mathematiker. Die Räume, denen er sich widmete, gingen deshalb über gewöhnliche dreidimensionale Quader hinaus. Er fing aber mit einem einfachen Beispiel an: Angenommen, man wolle die unendlich große zweidimensionale Ebene mit quadratischen Fliesen bedecken, ohne dass diese sich überlappen oder Freiräume entstehen. Dann müssen die Kanten von mindestens zwei Fliesen vollständig aufeinandertreffen. Die Vorhersage weitete er auf jede beliebige Dimension aus: Füllt man etwa einen zwölfdimensionalen Raum mit zwölfdimensionalen »quadratischen« Kacheln, werden am Ende stets zumindest zwei genau aneinanderstoßen.

AUF EINEN BLICK HARTNÄCKIGE SIEBEN

1 Die Kellersche ...

Weiterlesen
epaper-Einzelheft 5,99€
NEWS Jetzt gratis testen
Bereits gekauft?Anmelden & Lesen
Leseprobe: Abdruck mit freundlicher Genehmigung von Spektrum der Wissenschaft. Alle Rechte vorbehalten.
Lesen Sie jetzt diesen Artikel und viele weitere spannende Reportagen, Interviews, Hintergrundberichte, Kommentare und mehr aus über 1000 Magazinen und Zeitungen. Mit der Zeitschriften-Flatrate NEWS von United Kiosk können Sie nicht nur in den aktuellen Ausgaben, sondern auch in Sonderheften und im umfassenden Archiv der Titel stöbern und nach Ihren Themen und Interessensgebieten suchen. Neben der großen Auswahl und dem einfachen Zugriff auf das aktuelle Wissen der Welt profitieren Sie unter anderem von diesen fünf Vorteilen:

  • Schwerpunkt auf deutschsprachige Magazine
  • Papier sparen & Umwelt schonen
  • Nur bei uns: Leselisten (wie Playlists)
  • Zertifizierte Sicherheit
  • Freundlicher Service
Erfahren Sie hier mehr über United Kiosk NEWS.

Mehr aus dieser Ausgabe

Titelbild der Ausgabe 3/2022 von EWIGE FEUER. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
EWIGE FEUER
Titelbild der Ausgabe 3/2022 von SPEKTROGRAMM. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
SPEKTROGRAMM
Titelbild der Ausgabe 3/2022 von WENN GALAXIEN KOLLIDIEREN. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
WENN GALAXIEN KOLLIDIEREN
Titelbild der Ausgabe 3/2022 von TUMOREN ZAPFEN DIE KRAFTWERKE DES IMMUNSYSTEMS AN. Zeitschriften als Abo oder epaper bei United Kiosk online kaufen.
TUMOREN ZAPFEN DIE KRAFTWERKE DES IMMUNSYSTEMS AN
Mehr Lesetipps
Blättern im Magazin
FINGERSCHNIPPEN MIT KNALLEFFEKT
Vorheriger Artikel
FINGERSCHNIPPEN MIT KNALLEFFEKT
ECKIGE WELLEN
Nächster Artikel
ECKIGE WELLEN
Mehr Lesetipps

1 Die Kellersche Vermutung besagt, dass jeder lückenlos mit gleich großen Kacheln bedeckte Raum notwendigerweise zwei Fliesen enthält, die eine gemeinsame Kante vollständig teilen.

2 Diese Hypothese weitete Keller vor 90 Jahren auf jede beliebige Raumdimension aus. Fachleuten gelang es, alle Fälle zu beweisen oder zu widerlegen – bis auf den siebendimensionalen Raum.

3 Indem vier Mathematiker das Problem auf die Graphentheorie übertrugen und mit cleveren Tricks für einen Computer übersetzten, konnten sie nun auch den siebendimensionalen Fall lösen.

TIGGER11TH / GETTY IMAGES / ISTOCK; BEARBEITUNG: SPEKTRUM DER WISSENSCHAFT

Beweisen konnte Keller seinen Verdacht allerdings nicht. Und auch andere Mathematikerinnen und Mathematiker scheiterten: Im Lauf der Jahrzehnte griffen sie die Vermutung immer wieder auf und konnten sie für gewisse Dimensionen sogar belegen. In anderen Fällen zeigten sie hingegen, dass Keller falschlag. 2002 waren schließlich alle Dimensionen abgearbeitet – nur der siebendimensionale Raum blieb übrig. Erst im Oktober 2019 konnte endlich auch diese letzte offene Frage geklärt werden. Geknackt hatten das Rätsel aber nicht allein Wissenschaftler, sondern Computer. Das Ergebnis ist ein weiteres Beispiel dafür, wie menschlicher Einfallsreichtum in Verbindung mit hoher Rechenleistung einige der schwierigsten Probleme der Mathematik lösen kann.

Die Autoren der Arbeit, Joshua Brakensiek von der Stanford University, Marijn Heule und John Mackey von der Carnegie Mellon University und David Narváez vom Rochester Institute of Technology, brauchten 40 Rechner, um die Aufgabe zu bewältigen. Nach nur 30 Minuten lieferten diese eine kurze Antwort: Ja, die Vermutung trifft in sieben Dimensionen zu. Glücklicherweise muss man das Ergebnis nicht einfach nur so hinnehmen. Der elektronische Output wird von einem langen Beweis begleitet, der erklärt, warum die Hypothese in siebendimensionalen Räumen richtig ist.

Zwar ist die Argumentation zu umfangreich, dass Menschen sie verstehen. Aber andere Computerprogramme können sie gesondert überprüfen. Auch wenn man also nicht weiß, wie die Rechner die Kellersche Vermutung im Detail gelöst haben, kann man sicherstellen, dass ihr Resultat richtig ist.

Es lässt sich leicht erkennen, dass die Hypothese in zwei Dimensionen wahr ist. Dazu braucht man nur ein Blatt Papier, das man lückenlos mit gleich großen Quadraten bedeckt, ohne dass sich diese überlappen. Wie man schnell feststellt, müssen in diesem Fall mindestens zwei der Schnipsel eine gemeinsame Kante haben. Mit kubischen Bauklötzen lässt sich ebenfalls rasch einsehen, dass die Annahme in drei Dimensionen gilt.

1930 vermutete Keller, diese Beziehung sei für Räume und Kacheln in jeder Dimension richtig. Frühe Ergebnisse untermauerten seine Vorhersage. Er selbst wies 1937 nach, dass die Dimensionen fünf und sechs seine Hypothese erfüllten und vier Jahre später fand sein Kollege Oskar Perron einen entsprechenden Beweis für alle Räume der Dimensionen eins bis sechs.

Bis zu welcher Dimension ist die Vermutung wahr?

Nach weiteren 55 Jahren kam jedoch ein Rückschlag, den der 1990 verstorbene Keller nicht mehr erlebte. Eine neue Generation von Wissenschaftlern fand das erste Gegenbeispiel zur Kellerschen Vermutung: Wie Jeffrey Lagarias und Peter Shor bewiesen, ist die Annahme in zehn Dimensionen falsch. Tatsächlich hatten sie mit dieser Arbeit einen riesigen Fortschritt auf dem Gebiet gemacht. Denn sobald die Hypothese in einer Dimension widerlegt ist, trifft sie zwangsläufig auch in allen höheren nicht zu, wie aus einem mathematischen Argument folgt.

Nach Lagarias‘ und Shors Beweis waren also nur noch die Dimensionen sieben, acht und neun ungeklärt. Es dauerte weitere zehn Jahre, bis Mackey 2002 zeigen konnte, dass Kellers Verdacht im achtdimensionalen (und somit auch im neundimensionalen) Raum nicht erfüllt ist. Damit blieb nur noch der siebendimensionale Fall offen. Es handelte sich dabei also entweder um die höchste Dimension, in der sich die Vermutung bestätigen lässt, oder die niedrigste, in der sie nicht mehr gilt.

Über die Jahrzehnte, in denen sich die Mathematikerinnen und Mathematiker mit dem Problem beschäftigten, wandelten sich ihre zur Verfügung stehenden Methoden: Perron und Keller benötigten für die ersten sechs Dimensionen lediglich Bleistift und Papier, während Shor und Lagarias in den 1990er Jahren die Vermutung völlig neu formulierten, damit ein Algorithmus sich ihr annehmen konnte.

In Kellers ursprünglicher Form geht es um die Kachelung eines kontinuierlichen Raums, der unendlich ausgedehnt ist. In diesem gibt es unendlich viele Möglichkeiten, unendlich viele Kacheln gleicher Dimension zu platzieren. Computer sind allerdings nicht gut darin, Probleme zu lösen, die unbegrenzte Größen enthalten. Um ihre Fähigkeiten zu entfalten, brauchen sie diskrete, endliche Objekte, die sie untersuchen können. Deshalb schien die Kellersche Vermutung auf den ersten Blick ungeeignet zur Bearbeitung durch Algorithmen.

Doch 1990 fanden die ungarischen Mathematiker Keresztély Corrádi und Sándor Szabó eine Möglichkeit, das zu ändern. Wie sie herausfanden, sind einige Fragestellungen zu einem bestimmten endlichen und diskreten Objekt identisch zur Kellerschen Vermutung. Wenn es also gelänge, etwas über diese Strukturen zu beweisen, würde man damit notwendigerweise auch die Hypothese von Keller belegen oder widerlegen. Dadurch konnten Corrádi und Szabó eine geometrische Frage zu unendlichen Kachelungen auf ein einfacheres Problem über die Arithmetik weniger Zahlen reduzieren.

Die Methode der zwei Mathematiker basiert darauf, einen so genannten Keller-Graphen zu erzeugen. Bei Graphen handelt es sich um Netzwerke, die aus einer endlichen Anzahl von Punkten (oder Knoten) bestehen und durch Kanten miteinander verbunden sind. Angenommen, man wollte die Kellersche Vermutung in zwei Dimensionen lösen. Dafür kann man sich 16 Spielwürfel auf einem Tisch vorstellen, wobei bei allen die Seite mit den zwei Augenpaaren nach oben zeigt (die zwei Punkte spiegeln die Tatsache wider, dass man sich mit der Hypothese in zwei Dimensionen befasst). Nun färbt man jeden Punkt mit einer von vier Farben: rot, grün, weiß oder schwarz. Hat man sie einmal koloriert, darf man die Würfel nicht mehr drehen.

Die Lage der Punkte auf einem einzelnen Würfel sind nicht austauschbar. Anschließend verbindet man zwei Objekte durch Linien oder Kanten, wenn zwei Bedingungen erfüllt sind: An der einen Stelle (zum Beispiel oben rechts auf der Würfelseite) haben die Punkte unterschiedliche Farben und an der anderen Position (etwa unten links) sind sie komplementär zueinander gefärbt, also grün und rot oder schwarz und weiß. Wenn beispielsweise ein Würfel zwei rote und der andere zwei schwarze Punkte hat, verbindet man sie nicht. Sie erfüllen zwar das erste Kriterium, aber die Farben sind nicht komplementär. Ein rot-schwarzer und ein grüngrüner Würfel teilen hingegen eine Kante, weil sie beiden Bedingungen genügen (rot und grün sind komplementär und grün und schwarz sind verschieden).

Es gibt 16 Möglichkeiten, zwei Punkte mit vier Farben zu kolorieren. Deshalb arbeitet man mit 16 Würfeln und verbindet diese entsprechend den formulierten Regeln. Die entscheidende Frage, die mit der Kellerschen Vermutung zusammenhängt, lautet: Gibt es eine Gruppe von vier Würfeln, die alle miteinander verbunden sind?

Derart vollständig zusammenhängende Teilmengen innerhalb eines Graphen nennt man »Clique«. Man kann beweisen, dass falls eine solche existiert, die Hypothese von Keller in zwei Dimensionen falsch ist. Doch wie wir bereits wissen, trifft sie für den zweidimensionalen Fall zu. Deshalb wird man in diesem Netzwerk keine Clique aus vier Würfeln finden. Weil Corrádi und Szabó zeigen konnten, dass das geschilderte Cliqueproblem im Keller-Graphen exakt mit der Kellerschen Vermutung übereinstimmt, gilt auch die Umkehrung: Ist man nicht in der Lage, eine entsprechende Clique zu finden, dann ist die Hypothese für den betrachteten Fall wahr.

Komplexe Kachelung

Die Kellersche Vermutung besagt, dass es immer zumindest zwei Fliesen gibt, die eine Kante vollständig miteinander teilen, wenn man eine Ebene lückenlos und ohne Überlapp kachelt. Gleiches gelte für jeden n-dimensionalen Raum.

Die Würfel stellen zwar nicht direkt die Kacheln aus dem ursprünglichen Problem dar, das Keller sich überlegt hatte. Aber es gibt eine gewisse Übereinstimmung zwischen der Positionierung zweier Fliesen zueinander und den verbundenen Würfeln. Wenn zwei Würfel die gleichen Farben haben, entsprechen sie Kacheln, die sich an exakt demselben Ort im Raum befinden. Sind sie hingegen verschieden gefärbt, ohne Komplementärfarben (zum Beispiel falls einer schwarz-weiß ist und der andere grün-rot) zu enthalten, stellen sie überlappende Fliesen dar – was in der Kellerschen Vermutung nicht erlaubt ist. Haben die zwei Würfel eine gleiche und eine komplementäre Farbe (wie rotschwarz und grün-schwarz), dann teilen sich die dazugehörigen Kacheln eine Kante vollständig. Und schließlich der entscheidende und letzte mögliche Fall: Wenn die zwei Würfel unterschiedlich gefärbt und komplementär sind, steht das für sich berührende Kacheln, die jedoch leicht gegeneinander verschoben sind, so dass ihre Kanten nicht exakt aufeinanderliegen.

Das Verfahren funktioniert für jede Dimension, doch die Zahlen wachsen rasant

Das heißt, im Graph verbundene Würfel stellen Kacheln dar, die keine vollständige Seite teilen – genau die Art von Anordnung, welche die Kellersche Vermutung widerlegt. Wenn es eine Clique gibt, kann man sich vorstellen, dass die entsprechenden Kacheln eine bestimmte Fläche lückenlos und ohne Überlapp ausfüllen. Sie bilden ein größeres Objekt, das sich vervielfältigen lässt, um letztlich die komplette Ebene abzudecken. Damit wäre die Kellersche Vermutung widerlegt.

Wie Corrádi und Szabó vor etwa 30 Jahren bewiesen, kann man das Verfahren nutzen, um die Hypothese in jeder beliebigen Dimension zu widerlegen. Man muss dafür bloß die Parameter des Gedankenexperiments anpassen. Doch die Variablen wachsen rasant an: In drei Dimensionen benötigt man schon 216 Würfel mit drei Punkten auf einer Seite und sechs Farben. Wieder müssen die Würfel die gleichen Bedingungen wie zuvor erfüllen, damit man sie durch eine Kante verbinden darf. Eine mögliche Clique würde dann aus acht Würfeln (2³) bestehen, die vollständig miteinander verbunden sind. Um die Kellersche Vermutung in n Dimensionen zu beweisen, verwendet man Würfel mit n Punkten und mehreren Farben und versucht, eine Clique der Größe 2 n zu finden. Wie im zweidimensionalen Fall kann man sich eine solche Clique als eine Art Super-Kachel (bestehend aus 2 n kleineren Kacheln) vorstellen, die den n-dimensionalen Raum füllen könnte.

Mackey griff darauf zurück, um die Kellersche Vermutung in acht Dimensionen zu widerlegen. Ihm gelang es, im Keller-Graph eine Clique aus 256 Würfeln (2 8 ) auszumachen. In sieben Dimensionen muss man eine halb so große Struktur aus 128 Würfeln (2 ) finden. Falls sie existiert, ist die Hypothese in sieben Dimensionen falsch. Beweist man hingegen, dass es eine solche Clique nicht geben kann, hat man die Vermutung für diesen Fall bestätigt.

Tatsächlich erweist sich die Aufgabe in sieben Dimensionen als extrem schwer. Obwohl die acht- und zehndimensionalen Varianten wesentlich größere Graphen und Cliquen enthielten, konnten Forscherinnen und Forscher die Räume in einfachere Strukturen aufteilen. Somit ließen sich die Möglichkeiten eingrenzen und man sah sich mit einem simpleren Problem konfrontiert. Das ist für sieben Dimensionen anders. »Sieben ist schwierig, weil sie eine Primzahl ist, was bedeutet, dass man sie nicht in niedrigere Dimensionen aufteilen kann«, so Lagarias. »Wir hatten also keine andere Wahl, als uns mit der gesamten Kombinatorik dieser Graphen zu beschäftigen.«

Unmöglich zu finden

Unten ist ein Keller-Graph für zwei Dimensionen dargestellt. Wenn man eine Clique von vier Würfeln finden kann, die alle miteinander verbunden sind, hätte man die Kellersche Vermutung im zweidimensionalen Fall widerlegt. Da es eine solche Clique aber nicht gibt, ist die Hypothese richtig.

Die Suche nach einer Clique der Größe 128 dürfte für Menschen eine nicht bewältigbare Aufgabe sein. Aber es ist genau die Art von Frage, mit der man einen Computer betraut, obwohl auch dieser sich dabei schwertut. Tatsächlich ist das Cliquenproblem in der Informatik überaus bekannt: Es handelt sich um ein Paradebeispiel für ein »NPvollständiges« Problem. Vereinfacht ausgedrückt heißt das, es gibt bisher keinen Weg, die Aufgabe bei wachsender Größe der Clique effizient zu lösen. Hat man hingegen ein Ergebnis, lässt es sich recht einfach auf Richtigkeit prüfen – wie bei einem ausgefüllten Sudoku.

Damit Computer überhaupt nach Cliquen suchen können, muss man das Problem in eine maschinengerechte Darstellung übersetzen. Die Sprache von Algorithmen basiert auf Aussagenlogik. Dabei handelt es sich um eine Art der logischen Argumentation, die festen Regeln folgt und mehrere Einschränkungen enthält, etwa:

Wenn A die Eigenschaft B bedingt und A wahr ist, dann ist auch B wahr.

Nehmen wir an, Sie und zwei Freunde planen eine Party. Sie versuchen zu dritt, eine Gästeliste zusammenzustellen, allerdings gibt es zwischen einigen potenziellen Gästen Streitigkeiten, die sie vermeiden möchten. Wenn man beispielsweise Anna einlädt, sollte Kevin auch kommen. Ein Mitplaner könnte gl vielleicht einwenden, dass Bernhard sich mit Kevin nicht versteht und deshalb nur Kevin oder Bernhard teilnehmen können. Die dritte Mitplanerin möchte hingegen entweder Anna oder Bernhard oder beide ausschließen. Ist es angesichts all dieser Bedingungen möglich, eine Gästeliste zu erstellen, die alle Partyplaner zufrieden stellt? un

In der Informatik wird diese Art von Frage als Erfüllbarkeitsproblem (englisch: SAT von satisfiability) bezeichnet. Man löst es, indem man es in eine aussagenlogische Formel packt, die im genannten Beispiel wie folgt aussieht (die Buchstaben A, K und B stehen für die potenziellen Gäste): (A ODER NICHT K) UND (K ODER B) UND (NICHT A ODER NICHT B). Ein Computer wertet das aus, indem er für jede Variable entweder 0 oder 1 einsetzt. Null bedeutet falsch, also nicht eingeladen, und eine Eins steht für wahr.

Es gibt viele Möglichkeiten, der Formel Einsen und Nullen zuzuweisen. Gemäß der Rechenregeln für logische Operatoren wie »ODER« und »NICHT« berechnet der Algorithmus einen Wert von 0 oder 1 für die gesamte Aussage. Ersteres bedeutet, dass nicht alle Bedingungen erfüllt sind. Wenn hingegen 1 herauskommt, dann ist das eine Lösung für die Gästeliste. Der Computer könnte nach dem Durchlaufen der Kombinationen zu dem Schluss kommen, dass es unmöglich ist, jede Anforderung zu erfüllen. Für das genannte Beispiel gibt es jedoch zwei zufrieden stellende Ergebnisse: A = 1, K = 1, B = 0, demnach sind Anna und Kevin Gäste, während Bernhard nicht kommen darf, sowie A = 0, K = 0, B = 1, also nur Bernhard ist eingeladen.

Ein Computerprogramm, das solche Aufgaben der Aussagenlogik löst, heißt SAT-Solver. Es untersucht jede Konfiguration von Variablen und liefert eine simple Antwort: Entweder 1 (ja), es gibt einen Weg, die Bedingungen zu erfüllen, oder 0 (nein), es existiert keiner. »Man entscheidet einfach, ob es eine Kombination von wahren und falschen Variablen gibt, damit die gesamte Formel wahr ist. Wenn man das kann, ist die Formel erfüllbar, und wenn nicht, dann nicht«, so Thomas Hales von der University of Pittsburgh.

Die Frage, ob man eine Clique der Größe 128 finden kann, ist eine ähnliche Art von Problem. Sie lässt sich auch als aussagenlogische Formel ausdrücken und in einen SAT-Solver einfügen. Man beginnt mit einer großen Anzahl von Würfeln mit je sieben Punkten und mehreren Farben. Ist es möglich, die Punkte so zu kolorieren, dass man 128 Würfel nach den vorgegebenen Regeln miteinander verbinden kann?

Keller-Wörterbuch

Fachleute haben die Kellersche Vermutung gelöst, indem sie die Anordnung von Kacheln durch das Färben von Würfeln ersetzt haben.

Die Formel, die diese Frage erfasst, ist sehr viel länger als im vorangehenden Beispiel: Sie enthält allein 39 000 verschiedene Variablen! Jede kann einen von zwei Werten (0 oder 1) annehmen, woraus sich unvorstellbare 2 39 Möglichkeiten ergeben, die Farben auf den Würfeln anzuordnen. Um Kellers Vermutung in sieben Dimensionen zu beantworten, müsste ein Rechner jede einzelne dieser Kombinationen durchgehen und prüfen, ob es eine Clique der Größe 128 gibt – oder deren Existenz für alle Färbungen ausschlie- ßen. Selbst die schnellsten Computer der Welt bräuchten dafür vermutlich länger, als unser Sonnensystem existieren wird. Doch wie die vier Autoren der neuen Arbeit herausgefunden haben, können die Rechner auch zu einem endgültigen Ergebnis kommen, ohne jede einzelne Möglichkeit prüfen zu müssen.

Mackey erinnert sich an den Tag, an dem das Projekt vor seinen Augen erstmals so richtig Form annahm. Er stand in seinem Büro an der Carnegie Mellon University vor einer Tafel und diskutierte das Problem mit Heule und Brakensiek. Ersterer hatte plötzlich eine Idee, um die Suche so zu strukturieren, dass man sie in einer angemessenen Zeit abschließen könnte. »An diesem Tag war ein echtes intellektuelles Genie am Werk«, erinnert sich Mackey. »Es war, als würde man einen Weltklassesportler im entscheidenden Spielmoment beobachten. Ich habe gerade jetzt eine Gänsehaut, wenn ich nur daran denke.«

Mit automatisierter Erkennung von Symmetrien zu einer effizienteren Suche

Es gibt viele Möglichkeiten, um die Suche in einem Netzwerk zu beschleunigen. Stellen Sie sich vor, man hat einen Tisch voller Würfel und versucht, 128 davon so anzuordnen, dass sie den Regeln eines Keller-Graphen entsprechen.

Vielleicht ordnet man zwölf Stück richtig an, aber man findet keinen Weg, den nächsten Würfel hinzuzufügen. An diesem Punkt könnte man direkt alle Konfigurationen ausschließen, welche die unpassende Ausgangskonfiguration mit den zwölf Würfeln enthalten. »Wenn man weiß, dass die ersten Bausteine nicht zusammenpassen, muss man keine weiteren dazu ansehen. Das verkürzt die Suche im Allgemeinen sehr«, sagt Shor, der jetzt am Massachusetts Institute of Technology arbeitet.

Eine weitere Form der Effizienz ist Symmetrie. Sie ermöglicht es, ein ganzes Objekt zu verstehen, selbst wenn man nur einen Teil davon kennt. Zum Beispiel lässt sich nach einem Blick auf ein halbes Gesicht trotzdem das gesamte Antlitz rekonstruieren. Ähnliche Ansätze funktionieren auch bei Keller-Graphen. Angenommen, man ordnet wieder die Würfel auf einem Tisch an. Vielleicht beginnt man in der Mitte des Tischs und baut eine Konfiguration nach links aus. Man legt vier Würfel hin und stößt auf ein Hindernis – man kommt nicht weiter. Dann lässt sich diese Startkonfiguration ausschließen, samt allen darauf aufbauenden Kombinationen. Doch nicht nur das: Man kann auch die gespiegelte Version dieser Ausgangskonfiguration ignorieren, also die Würfelanordnung, bei der man sich von der Mitte aus nach rechts vorarbeitet.

Die vier Mathematiker haben solche effizienten Methoden auf eine neue Art und Weise genutzt. Insbesondere haben sie Überlegungen zu Symmetrien automatisiert, damit ein Algorithmus sie selbstständig erkennt. In früheren Arbeiten mussten Fachleute die Merkmale praktisch von Hand erarbeiteten und dem Programm übergeben.

So gelang es ihnen, die Suche nach einer Clique der Größe 128 so zu optimieren, dass ihr SAT-Solver statt der ursprünglichen 2 39 Konfigurationen nur noch etwa eine Milliarde (2 ) Kombinationen durchsuchen musste. Damit dauerten die Berechnungen nur eine halbe Stunde. »Die Computer lieferten das Ergebnis nein, also trifft die Vermutung zu«, so Heule. Denn das heißt, es gibt keine Möglichkeit, 128 Würfel so zu färben, dass sie eine Clique bilden.

Somit ist die Kellersche Vermutung in sieben Dimensionen wahr: Jede Anordnung siebendimensionaler Kacheln, die den Raum lückenlos und ohne Überlapp füllen, enthält zwangsläufig mindestens zwei Objekte, die sich eine gesamte Kante teilen.

Tatsächlich lieferten die Rechner wesentlich mehr als eine einsilbige Antwort. Sie untermauerten ihre Schlussfolgerung mit einem langen Beweis, der über 200 Gigabyte groß ist. Dabei handelt es sich nicht einfach um eine Auflistung aller Konfigurationen von Variablen, welche die Computer überprüft haben. Stattdessen ist es ein logisches Argument, das beweist, weshalb die gewünschte Clique unmöglich existieren kann.

Da die Argumentation viel zu lang ist, als dass ein Mensch sie prüfen könnte, übergaben die vier Forscher sie einem formalen Beweisprüfer. Dabei handelt es sich um ein Computerprogramm, das die logischen Schlüsse des Beweises nachzeichnet. Der Algorithmus konnte die Richtigkeit der Folgerung bestätigen. »Die Rechner gehen nicht einfach alle Fälle durch und finden nichts. Stattdessen gehen sie alle Fälle durch und sind in der Lage, einen Beweis zu formulieren, wonach diese Sache nicht existiert«, so Mackey. »Man ist in der Lage, einen Beweis der Unerfüllbarkeit zu schreiben.«

Damit haben verschiedene Algorithmen durch ihr Zusammenwirken nun endlich eine 90 Jahre alte Vermutung geklärt. Das Vorgehen ist ein Paradebeispiel dafür, wie sich die Mathematik in der Zukunft entwickeln könnte: Wissenschaftler übersetzen ein Problem in computergerechte Sprache und überlegen sich einfallsreiche Methoden, um Computer bei der Lösungssuche zu unterstützen. Diese spucken dann ein Ergebnis samt Beweis aus, das ein weiterer Algorithmus unabhängig prüfen kann. Die Rolle des Menschen ist dabei immer noch entscheidend, gerade im kreativen Bereich, aber Rechner helfen ihnen erheblich – vor allem dort, wo es um Fleißarbeit geht.

QUELLEN

Brakensiek, J. et al.: The resolution of Keller’s conjecture. ArXiv 1910.03740, 2019

Lagarias, J. C., Shor, P. W.: Keller’s cube-tiling conjecture is false in high dimensions. Bulletin of the American Mathematical Society 27, 1992

Mackey, J.: A cube tiling of dimension eight with no facesharing. Discrete & Computational Geometry 28, 2002

Von »Spektrum der Wissenschaft« übersetzte und bearbeitete Fassung des Artikels »Computer Search Settles 90-Year-Old Math Problem« aus »Quanta Magazine«, einem inhaltlich unabhängigen Magazin der Simons Foundation, die sich die Verbreitung von Forschungsergebnissen aus Mathematik und den Naturwissenschaften zum Ziel gesetzt hat.