Durch die Übersetzung von Kellers Hypothese in eine computerverständliche Grafiksuchsprache lösten die Forscher schließlich das Problem, Räume mit Kacheln zu bedecken
Ein Team von Mathematikern hat endlich Kellers Hypothese herausgefunden - aber nicht alleine. Stattdessen trainierten sie eine ganze Flotte von Computern und lösten sie.
Kellers Hypothese, die Ott-Heinrich Keller vor 90 Jahren aufgestellt hat, befasst sich mit der Aufgabe, Räume mit identischen Fliesen zu bedecken. Sie argumentiert, dass, wenn Sie einen zweidimensionalen Raum mit zweidimensionalen quadratischen Kacheln pflastern, mindestens zwei von ihnen die Seiten vollständig und nicht teilweise berühren müssen. Die Hypothese macht die gleiche Vorhersage für alle Dimensionen - das heißt, wenn ein 12-dimensionaler Raum mit 12-dimensionalen "Quadraten" gefüllt wird, müssen mindestens zwei von ihnen eine gemeinsame Kante haben.
Jahrelang kämpften Mathematiker um diese Hypothese und bewiesen, dass sie für einige Dimensionen wahr und für andere falsch ist. Und bis zum letzten Herbst blieb die Frage nur für den siebendimensionalen Raum ungelöst.
Aber auch neue computergenerierte Beweise lösten dieses Problem. Der im letzten Oktober veröffentlichte Beweis ist eines der neuesten Beispiele für die Kombination von menschlichem Genie und reiner Rechenleistung, um die aufregendsten Fragen der Mathematik zu beantworten.
Die Autoren der neuen Arbeit, Joshua Breukensik aus Stanford, Marin Hijul und John Mackey von der Carnegie Mellon University sowie David Narvaez vom Rochester Institute of Technology, lösten dieses Problem mit 40 Computern. In nur 30 Minuten gaben die Maschinen eine einsilbige Antwort: Ja, in sieben Dimensionen ist die Hypothese richtig. Und wir müssen diese Schlussfolgerung nicht einmal zum Glauben ziehen.
Der Antwort ist ein langer Beweis beigefügt, der seine Wahrheit erklärt. Der Beweis ist zu lang, als dass ein Mensch ihn verstehen könnte, aber ein anderes Computerprogramm kann ihn überprüfen.
Mit anderen Worten, selbst wenn wir nicht genau wissen, was Computer getan haben, um Kellers Hypothese zu beweisen, können wir zumindest sicherstellen, dass sie es richtig gemacht haben.
Die mysteriöse siebte Dimension
Es ist leicht zu erkennen, dass Kellers Vermutung in zwei Dimensionen wahr ist. Nehmen Sie ein Stück Papier und versuchen Sie, es mit gleichen Quadraten ohne Lücken oder Überlappungen zu bedecken. Schon bald werden Sie feststellen, dass Sie dies nur tun können, wenn mindestens zwei Quadrate dieselbe Seite haben. Wenn Sie Würfel zur Hand haben, können Sie leicht überprüfen, ob die Hypothese für die dritte Dimension zutrifft. 1930 schlug Keller vor, dass diese Beziehung für alle Dimensionen und die entsprechenden Kacheln funktioniert.
Frühe Ergebnisse stützten Kellers Vorhersage. 1940 bewies Oscar Perron, dass die Hypothese für die Messungen eins bis sechs richtig war. Mehr als 50 Jahre später fand jedoch eine neue Generation von Mathematikern das erste Gegenbeispiel zu dieser Hypothese: 1992 Jeffrey Lagarias und Peter Shorebewiesen, dass die Hypothese in der 10. Dimension nicht funktioniert.
Kellers Hypothese sagt voraus, dass beim Füllen eines Raums in einer beliebigen Dimension mindestens zwei Kacheln die Seiten vollständig berühren müssen.
Beim Ausfüllen des zweidimensionalen Raums haben viele Kacheln gemeinsame Seiten (blaue Linien).
Beim Füllen des 3D-Raums haben viele Würfel gemeinsame Flächen (blau).
Es ist leicht zu zeigen, dass eine Hypothese, die in einer bestimmten Dimension versagt, nicht in allen höheren gilt. Daher bleibt es nach der Arbeit von Lagarias und Shor nur noch möglich, das Problem für die siebte, achte und neunte Dimension zu lösen. Im Jahr 2002 bewies Mackey , dass Kellers Hypothese für Dimension acht (und damit neun) falsch war.
Nur die siebte Dimension blieb offen - es war entweder die größte Dimension, für die diese Hypothese richtig ist, oder die kleinste, in der die Hypothese falsch ist.
"Niemand weiß genau, was dort los ist", sagte Khiyul.
Verbinde die Punkte
Während Mathematiker mehrere Jahrzehnte mit diesem Problem zu kämpfen hatten, änderten sich ihre Methoden allmählich. Perron arbeitete an den ersten sechs Dimensionen nur mit Bleistift und Papier. In den neunziger Jahren hatten die Forscher jedoch herausgefunden, wie Kellers Hypothese in eine völlig andere Form übersetzt werden konnte, sodass sie sie mithilfe von Computern lösen konnten.
Die ursprüngliche Formulierung der Keller-Vermutung betrifft einen glatten durchgehenden Raum. In einem solchen Raum gibt es unendlich viele Möglichkeiten, eine unendliche Anzahl von Kacheln zu platzieren. Computer sind jedoch nicht gut darin, Probleme mit einer unendlichen Anzahl von Optionen zu lösen - um mit ihnen fertig zu werden, benötigen sie diskrete und endliche Objekte.
Marin Hijul von der Carnegie Mellon University
1990 entwickelten Kereszteli Korradi und Sandor Shabo ein geeignetes diskretes Objekt. Sie zeigten, dass zu diesem Objekt Fragen gestellt werden können, die Kellers Hypothese entsprechen. Und wenn Sie etwas beweisen, das mit diesen Objekten zusammenhängt, wird die Keller-Hypothese bewiesen. Dies reduzierte die Frage der Unendlichkeit auf ein weniger komplexes arithmetisches Problem mit mehreren Zahlen.
So funktioniert das.
Angenommen, Sie möchten die Keller-Hypothese in zwei Dimensionen verstehen. Corradi und Shabo entwickelten hierfür eine Methode, bei der eine Struktur konstruiert wurde, die sie Keller-Graph nannten.
Stellen Sie sich zunächst vor, dass 16 Würfel auf dem Tisch liegen und alle eine Oberkante mit zwei Punkten haben (zwei Punkte bezeichnen einen zweidimensionalen Raum und warum es 16 Würfel gibt - wir werden etwas später sehen). Alle Würfel werden auf die gleiche Weise gedreht, sodass zwei Punkte für alle gleich sind. Färben Sie jeden Punkt mit einer von vier Farben: Rot, Grün, Weiß oder Schwarz.
Die Punkte auf einem Würfel ändern nicht die Position - einer von ihnen bezeichnet die x-Koordinate und der andere - y. Nachdem wir die Würfel gefärbt haben, beginnen wir, Linien oder Kanten zwischen Würfelpaaren zu zeichnen, wenn zwei Bedingungen erfüllt sind: Die Punkte an derselben Stelle für ein Würfelpaar haben unterschiedliche Farben, und in der anderen - unterschiedlich und gepaart - werden Paare außerdem als rot mit grün oder schwarz betrachtet mit Weiss.
Keller Graph für zwei Dimensionen. Wenn Sie eine Teilmenge von vier Würfeln finden, in denen jeder mit allen anderen verbunden ist, werden Sie Kellers Hypothese für den zweidimensionalen Raum widerlegen. Es gibt jedoch keine solche Teilmenge, und die Hypothese ist richtig.
Unten sehen Sie ein Beispiel für eine vollständig zusammengeführte Clique von vier Würfeln, die nicht in der Grafik enthalten ist.
Das heißt, wenn beispielsweise ein Würfel zwei rote Punkte und der andere zwei schwarze Punkte hat, sind sie nicht durch eine Kante verbunden. Ihre Punkte an denselben Positionen haben unterschiedliche Farben, erfüllen jedoch nicht die Anforderung, Farben zu paaren. Wenn ein Würfel rote und schwarze Punkte hat und der andere zwei grüne Punkte, sind sie durch eine Kante verbunden, da sie an einer Position gepaarte Farben (rot und grün) haben und an der anderen einfach (schwarz und grün).
Es gibt 16 Möglichkeiten, zwei Punkte mit vier Farben zu färben (wir haben also 16 Würfel). Legen Sie all diese 16 Möglichkeiten vor sich. Verbinden Sie alle Würfelpaare, die den Anforderungen entsprechen. Gibt es vier Würfel in Ihrem Schema, von denen jeder mit drei anderen kombiniert wird?
Eine solche vollständig verbundene Teilmenge von Würfeln wird als Clique bezeichnet. Wenn Sie eine finden, werden Sie die Keller-Hypothese in zwei Dimensionen widerlegen. Sie können jedoch nicht - es existiert einfach nicht. Und das Fehlen einer solchen Clique von vier Würfeln bedeutet, dass Kellers Hypothese für zwei Dimensionen gilt.
Diese Würfel sind nicht buchstäblich die gleichen Kacheln wie Kellers Hypothese. Sie können jedoch davon ausgehen, dass jeder Würfel eine Kachel darstellt. Betrachten Sie die den Punkten zugewiesenen Farben als die Koordinaten, die den Würfel im Raum platzieren. Und die Existenz einer Kante beschreibt, wie zwei Würfel relativ zueinander positioniert sind.
Wenn die Farben der Würfel gleich sind, stellen sie Kacheln dar, die im Raum gleich weit voneinander entfernt sind. Wenn sie keine gemeinsamen Farben und Farbpaare haben (eines hat Schwarz und Weiß, das andere hat Grün und Rot), zeigen sie teilweise überlappende Kacheln an - was beim Ausfüllen des Raums nicht zulässig ist. Wenn zwei Würfel einen Satz übereinstimmender Farben und einen Satz derselben Farbe haben (einer rot-schwarz, der andere grün-schwarz), repräsentieren sie Kacheln mit einer gemeinsamen Seite.
Schließlich und vor allem - wenn sie einen Satz gepaarter Farben und einen anderen Satz unterschiedlicher Farben haben - das heißt, wenn sie durch eine Kante verbunden sind - stellen die Würfel Kacheln dar, die miteinander in Kontakt stehen, aber leicht verschoben sind, wodurch ihre Kanten nicht vollständig zusammenfallen ... Es ist diese Bedingung, die wir studieren müssen. Die durch eine Kante verbundenen Würfel bezeichnen benachbarte Kacheln, die keine gemeinsame Seite haben - dies ist die Anordnung, die erforderlich ist, um Kellers Hypothese zu widerlegen.
"Sie sollten berühren, aber nicht vollständig", sagte Khiyul.
Gleiche Färbung - gleiche Anordnung.
Unterschiedliche Farben, keine Paare - überlappend.
Zwei gepaarte Farben und ein Paar derselben sind die gemeinsame Seite.
Zwei gepaarte Farben und zwei verschiedene - teilweiser Kontakt an den Seiten.
Skalierung
Vor dreißig Jahren haben Corradi und Schabo bewiesen, dass Mathematiker ein ähnliches Verfahren anwenden können, um mit Kellers Hypothese in jeder Dimension zu arbeiten und die Parameter des Experiments zu optimieren. Um die Keller-Hypothese in drei Dimensionen zu beweisen, können Sie 216 Würfel mit drei Punkten am Rand und möglicherweise drei Farbpaaren verwenden (hier besteht jedoch eine gewisse Flexibilität). Dann müssen Sie nach acht Würfeln (2 3 ) suchen , die vollständig miteinander verbunden sind, und zwar unter den gleichen Bedingungen, die wir oben angegeben haben.
Um Kellers Vermutung in n Dimensionen zu beweisen, müssen Sie im Allgemeinen Würfel mit n Punkten verwenden und versuchen, eine Clique der Größe 2 n unter ihnen zu finden . Es kann angenommen werden, dass es sich um eine Art Super-Kachel handelt (bestehend aus 2 nkleinere Kacheln), die den gesamten n-dimensionalen Raum abdecken können.
Wenn Sie diese Super-Kachel finden (die keine Kacheln mit einer gemeinsamen Seite hat), können Sie Kopien davon verwenden, um den gesamten Raum mit Kacheln ohne eine gemeinsame Seite abzudecken, was Kellers Hypothese widerlegt.
„Wenn Sie erfolgreich sind, können Sie den gesamten Raum mit Übertragung abdecken. Ein Block ohne gemeinsame Fliesenseiten erstreckt sich über den gesamten Boden “, sagte Lagarias, der jetzt an der Universität von Michigan ist.
Mackey widerlegte Kellers Hypothese in der 8. Dimension und fand eine Clique von 256 Würfeln (2 8 ). Es blieb also, sich mit der Hypothese in der 7. Dimension zu befassen und eine Clique von 128 Würfeln zu finden (2 7)). Das Finden dieser Clique wird die Keller-Hypothese in der siebten Dimension widerlegen. Beweisen Sie, dass es nicht existiert und Sie werden beweisen, dass die Hypothese wahr ist.
Leider ist es besonders schwierig, eine Clique mit 128 Würfeln zu finden. In früheren Arbeiten nutzten die Forscher die Tatsache, dass die Dimensionen 8 und 10 gewissermaßen in Räume niedrigerer Dimension "zerlegt" werden können, mit denen leichter gearbeitet werden kann. Und hier hat das nicht funktioniert.
"Die siebte Dimension ist unpraktisch, weil 7 eine Primzahl ist und man sie nicht in Dimensionen kleinerer Ordnung zerlegen kann", sagte Lagarias. "Daher gab es keinen Ausweg, als sich mit der vollwertigen Kombinatorik dieser Graphen zu befassen."
Das Finden einer Clique mit 128 Würfeln kann für das Gehirn ohne Hilfe eine Herausforderung sein - aber genau diese Fragen können Computer gut beantworten, insbesondere mit ein wenig Hilfe.
Die Sprache der Logik
Um die Suche nach Klicks in eine Aufgabe zu verwandeln, die ein Computer ausführen kann, müssen Sie sie in Form einer Aussagenlogik formulieren . Dies ist eine logische Argumentation, die eine Reihe von Einschränkungen enthält.
Nehmen wir an, Sie drei planen eine Party mit Freunden. Sie versuchen, eine Gästeliste zu erstellen, es bestehen jedoch Interessenkonflikte. Angenommen, Sie möchten entweder Alexei einladen oder Kolya ausschließen. Einer Ihrer Freunde möchte Kolya oder Vlad oder beide einladen. Ein anderer Freund möchte weder Alexei noch Vlad anrufen. Ist es mit solchen Einschränkungen möglich, eine Gästeliste zu erstellen, die alle drei erfüllt?
In der Informatik wird dieses Problem als Akzeptanzproblem bezeichnet. Es kann gelöst werden, indem die Bedingung in der Satzformel beschrieben wird. In diesem Fall sieht es so aus, und A, K und B bezeichnen potenzielle Gäste: (A ODER NICHT K) UND (K ODER B) UND (NICHT A ODER NICHT B).
Der Computer berechnet dies durch Ersetzen von 0 oder 1 in jeder Variablen. 0 ist der Wert der Variablen "false" oder off und 1 ist "true" oder on. Wenn wir 0 anstelle von A einsetzen, sagen wir, dass Alexei nicht eingeladen wurde und 1, dass er eingeladen wurde. In dieser einfachen Formel können 0 und 1 auf viele Arten ersetzt werden (indem eine Gästeliste erstellt wird), und es ist möglich, dass der Computer nach dem Durchlaufen des gesamten Computers zu dem Schluss kommt, dass es unmöglich ist, alle Interessen zu erfüllen. In diesem Fall gibt es jedoch zwei Möglichkeiten, 1 und 0 zu ersetzen, um alle zufrieden zu stellen: A = 1, K = 1, B = 0 (Alexei und Kolya einladen) und A = 0, K = 0, B = 1 (einen Vlad einladen) ).
Das Computerprogramm, das solche Anweisungen löst, wird als SAT-Löser bezeichnet, wobei SAT für Erfüllbarkeit steht. Es untersucht alle Kombinationen von Variablen und gibt eine einsilbige Antwort - entweder JA, es gibt eine Möglichkeit, die Anforderungen der Formel zu erfüllen, oder NEIN, dies ist nicht der Fall.
John Mackie von der Carnegie Mellon University
"Sie wollen nur sehen, ob Sie allen Variablen wahre und falsche Werte zuweisen können, damit die gesamte Formel wahr ist, und wenn ja, dann ist sie zufriedenstellend, und wenn nicht, dann nein", sagte Thomas Hales von Universität von Pittsburgh.
Die Frage, eine Clique von 128 Würfeln zu finden, ist ein ähnliches Problem. Es kann auch als Satzformel umgeschrieben und dem SAT-Löser übergeben werden. Beginnen Sie mit vielen Würfeln mit jeweils 7 Punkten und 6 möglichen Farben. Ist es möglich, die Punkte so zu färben, dass 128 Würfel nach bestimmten Regeln miteinander verbunden sind? Mit anderen Worten, ist es möglich, Farben so zuzuweisen, dass der Klick angezeigt wird?
Die Satzformel für die angeklickte Frage ist ziemlich lang und enthält 39.000 Variablen. Jedem kann einer von zwei Werten zugewiesen werden, 0 oder 1. Infolgedessen betrug die Anzahl der möglichen Optionen zum Anordnen von Werten oder Methoden zum Zuweisen von Farben 2,39.000 - was sehr, sehr viel ist.
Um die Antwort auf die Frage nach der Keller-Hypothese in sieben Dimensionen zu finden, müsste der Computer alle diese Kombinationen überprüfen - und entweder alle ausschließen (was bedeuten würde, dass die Clique der Größe 128 nicht existiert und die Keller-Hypothese in der siebten Dimension korrekt ist) oder zumindest finden wäre eine Arbeitsoption (widerlegt Kellers Hypothese).
"Wenn Sie eine einfache Iteration aller Möglichkeiten durchführen, stoßen Sie auf eine 324-stellige Zahl", sagte Mackey. Der schnellste Computer der Welt würde bis zum Ende der Zeit funktionieren und alle Möglichkeiten durchlaufen.
Die Autoren der neuen Arbeit haben jedoch herausgefunden, wie ein Computer eine bestimmte Antwort geben kann, ohne alle Möglichkeiten zu prüfen. Der Schlüssel dazu ist Effizienz.
Versteckte Effizienz
Mackey erinnert sich an den Tag, an dem das Projekt aus seiner Sicht tatsächlich in Betrieb genommen wurde. Er stand in seinem Büro an der Carnegie Mellon University vor einer Tafel und diskutierte ein Problem mit zwei Mitautoren, Hijul und Breikensik, als Hijul einen Weg vorschlug, die Suche so zu strukturieren, dass sie in angemessener Zeit abgeschlossen werden konnte.
"An diesem Tag arbeitete in meinem Büro ein echtes menschliches Genie", sagte Mackey. - Ich war wie Wayne Gretzky oder LeBron James im NBA-Finale. Ich habe Gänsehaut nur aus der Erinnerung daran. "
Sie können die Suche nach einem bestimmten Keller-Diagramm auf verschiedene Arten anpassen. Stellen Sie sich vor, Sie haben viele Würfel auf dem Tisch und versuchen, 128 davon nach den Regeln von Graf Keller zu lösen. Angenommen, Sie haben 12 richtig ausgewählt, können aber nicht herausfinden, wie Sie die nächste hinzufügen können. Zu diesem Zeitpunkt können Sie jede Konfiguration von 128 Würfeln verwerfen, die diese nicht funktionierende Konfiguration von 12 enthält.
"Wenn Sie wissen, dass Ihre ersten fünf Aufgaben nicht übereinstimmen, müssen Sie nicht nach anderen Variablen suchen, was das Suchfeld normalerweise erheblich einschränkt", sagte Shore, jetzt am MIT.
Eine andere Art der Effizienz ist mit Symmetrie verbunden. Symmetrische Objekte sind etwas gleich. Die Identität ermöglicht es uns, das gesamte Objekt als Ganzes zu verstehen und nur einen Teil davon zu studieren. Wenn Sie die Hälfte des Gesichts einer Person betrachten, können Sie es vollständig wiederherstellen.
Ebenso können Sie bei Keller-Graphen Ecken schneiden. Stellen Sie sich noch einmal vor, Sie versuchen, die Würfel auf dem Tisch auszurichten. Angenommen, Sie beginnen in der Mitte des Tisches und bauen Ihre Hand links auf. Sie legen vier Würfel aus und kommen in eine Sackgasse. Sie haben jetzt eine Startkombination und alle darauf basierenden Kombinationen eliminiert. Sie können jedoch die Spiegelung dieser anfänglichen Kombination ausschließen - die Konfiguration der Cubes, die Sie erhalten, wenn Sie sie auf die gleiche Weise platzieren, nur rechts.
"Wenn Sie einen Weg gefunden haben, um zufriedenstellende Probleme zu lösen, die die Symmetrie geschickt berücksichtigen, haben Sie die Aufgabe erheblich vereinfacht", sagte Hales.
Vier Kollegen nutzten die Effizienz dieser Suche auf neue Weise - insbesondere automatisierten sie die Berücksichtigung symmetrischer Fälle, während Mathematiker sie zuvor fast von Hand verarbeiteten.
Infolgedessen verbesserten sie ihre Suche nach Cliquen der Größe 128 so sehr, dass ihr Programm anstelle von 2,39.000 Konfigurationen nur etwa eine Milliarde ( 2,30 ) überprüfen musste . Dies führte zu einer Suche, die für einen Morgen für immer zu einer Aufgabe werden konnte. Nach nur einer halben Stunde Berechnungen erhielten sie schließlich eine Antwort.
"Die Computer sagten nein, also wissen wir, dass die Hypothese funktioniert", sagte Hiyul. Es ist unmöglich, die 128 Würfel so zu färben, dass sie alle miteinander verschmelzen, so dass Kellers Hypothese für die siebte Dimension bestätigt wird. Bei jeder Platzierung von Fliesen, die einen Raum abdecken, gibt es zwangsläufig mindestens ein Paar vollständig berührender Kanten.
Der Computer gab nicht nur eine einsilbige Antwort. Er fügte einen langen Beweis von 200 GB bei, der diese Schlussfolgerung stützte.
Der Beweis ist nicht nur eine Berechnung aller Variablensätze, die von einem Computer überprüft wurden. Dies ist ein logisches Argument dafür, dass die notwendige Clique nicht existieren kann. Die Forscher führten die Beweise in ein Programm ein, das formale Beweise testet, indem es die Logik des Arguments verfolgt und validiert.
„Wir haben nicht alle Optionen durchgesehen und nichts gefunden. Wir haben alle Optionen durchgesehen und konnten den Beweis aufschreiben, dass so etwas nicht existiert - sagte Mackey. "Wir konnten Beweise für Unzufriedenheit aufschreiben."