Im Frühjahr 2023 sorgte der Fund eines »Einsteins« für Begeisterung: Der pensionierte Druckanlagentechniker David Smith stellte ein 13-Eck vor, mit dem man eine Ebene lückenlos und ohne Überlapp bedecken kann. Das klingt zunächst nicht allzu aufregend, doch jedes entstehende Muster ist zwangsläufig nichtperiodisch – unabhängig davon, wie man die 13-eckigen Kacheln zusammenlegt. Eine solche »aperiodische« Fliese hatten Fachleute und Laien jahrzehntelang gesucht.

Für Mathematikerinnen und Mathematiker sind aber nicht nur geometrische Pflasterungen der Ebene spannend. Sie widmen sich dem Problem außerdem in höheren Dimensionen. Zum Beispiel möchten sie herausfinden, welche Eigenschaften dreidimensionale Steine haben, mit denen sich ein ganzer Raum füllen lässt. Und was sich verändert, wenn man zu noch größeren Dimensionen übergeht.

Insbesondere die Existenz von »Einsteinen« (abgeleitet vom Begriff »ein Stein«, nicht von dem Physiker) wirft Fragen auf. Gibt es auch in hohen Dimensionen einzelne Bausteine, die einen Raum lückenlos füllen und dabei bloß nichtperiodische Muster erzeugen? Lange ging man davon aus, dass sich die Eigenschaften ebener Parkettierungen nicht allzu stark von jenen in höheren Dimensionen unterscheiden würden. Doch wie die Mathematikerin Rachel Greenfeld vom Institute for Advanced Study in Princeton, New Jersey, zusammen mit ihrem Kollegen Terence Tao von der University of California in Los Angeles (UCLA) Ende 2022 zeigen konnte, ist diese Annahme falsch.

Pflasterungen sprengen die Grenzen der Logik

Geometrische Mosaikmuster aus kunstvoll gestalteten Kacheln sind nicht nur schön anzusehen, sondern auch aus mathematischer Sicht extrem interessant. Doch erst in den 1960er Jahren wurde die Bedeutung der Kachelmuster außerhalb der Geometrie deutlich: Die Untersuchung von Fliesen führt schnell an die Grenzen der Logik.

Das hatte der Mathematiker Hao Wang (1921–1995) festgestellt, als er sich mit quadratischen Steinen beschäftigte. Er hatte daraus eine Art Spiel konzipiert: Auf einer Ebene liegen mehrere Quadrate mit unterschiedlich eingefärbten Kacheln, die man so oft wie gewünscht vervielfältigen und nach oben, unten sowie rechts und links verschieben darf. Drehungen und Spiegelungen sind nicht erlaubt. Zudem dürfen sich nur gleichfarbige Kanten berühren. Ziel des Spiels ist es, die gesamte Ebene mit den Fliesen zu bedecken.

Höchst interessant fand Wang die Frage, ob man – anstatt mühsam verschiedene Zusammensetzungen durchzuprobieren – einen Algorithmus entwerfen könnte, der anhand der vorgegebenen Fliesen beurteilt, ob man das Spiel gewinnen kann oder nicht. Wegen der Ähnlichkeit der quadratischen Kacheln zu den Segmenten auf Dominosteinen ist diese Frage inzwischen als »Domino-Problem« bekannt.

Wang ging damals – fälschlicherweise – davon aus, dass jeder Kachelsatz, mit dem man das Spiel gewinnt, die Ebene auch periodisch bedecken kann. Demnach müsste es stets möglich sein, eine zusammenhängende Menge von Kacheln zu finden, die durch reine Verschiebungen die gesamte Fläche pflastert. Wie Wang herausfand, würde daraus folgen, dass das Domino-Problem lösbar ist. Theoretisch könnte man einen Algorithmus entwerfen, der nach gewisser Zeit ausspuckt, ob ein Kachelsatz eine Ebene pflastern kann oder nicht.

Damals waren nichtperiodische Parkettierungen natürlich schon bekannt. Aber die entsprechenden Fliesen ließen sich immer umordnen, damit das Muster periodisch wird. Wie der damalige Doktorand von Wang, Robert Berger, allerdings 1966 zeigen konnte, ist das Domino-Problem unentscheidbar: Es gibt keinen Algorithmus, der für jeden Kachelsatz in endlicher Zeit berechnen kann, ob das Spiel lösbar ist. Das heißt, es wird immer Fliesen geben, für die man niemals beweisen wird, ob sie eine Ebene pflastern.

Damit hatte Berger gleichzeitig nachgewiesen, dass es Kacheln geben muss, die eine Fläche auf bloß nichtperiodische Weise bedecken. Und kurz darauf präsentierte er tatsächlich ein Beispiel dafür: Er hatte einen riesigen Satz von mehr als 20 000 quadratischen Fliesen mit unterschiedlichen Färbungen gefunden, die eine Ebene nachweislich nur nichtperiodisch pflastern. Es war das erste Beispiel aperiodischer Steine.

Wie verändert sich das Ergebnis, wenn man die Größe des Kachelsatzes einschränkt? Mathematikerinnen und Mathematiker interessierte, ob die Domino-Frage für eine feste Anzahl von Fliesenformen entscheidbar ist. Und besonders spannend wird es, wenn man nicht nur quadratische Kacheln betrachtet, sondern auch vielfältige Formen zulässt. Die allermeisten dieser Fragen sind noch offen. Erst recht, wenn man die zweidimensionale Ebene verlässt und zu höheren Dimensionen übergeht.

Je komplexer ein System, desto schneller stößt man auf Unentscheidbarkeiten

»Wenn etwas komplex genug ist, tauchen Unentscheidbarkeiten schnell auf«, sagte der Mathematiker Chaim Goodman-Strauss vom National Museum of Mathematics in New York City auf dem »Hatfest« im Juli 2023, einer Konferenz, die zu Ehren des zweidimensionalen Einsteins in Oxford veranstaltet wurde. Hintergrund dieser Aussage ist ein Konzept aus der theoretischen Informatik, mit dem sich Unentscheidbarkeiten beweisen lassen.

Der Logiker Kurt Gödel (1906–1978) erschütterte in den 1930er Jahren die Grundfesten der Mathematik, als er seine »Unvollständigkeitssätze« vorstellte. Sie besagen, dass es in jedem mathematischen System zwangsläufig Aussagen gibt, die sich weder beweisen noch widerlegen lassen. Damit ist das Fach dazu verdammt, unvollständig zu sein. Das war anfangs ein Schock, aber die meisten Fachleute hofften, es handle sich um eine rein akademische Sonderheit, die keine praktischen Auswirkungen haben würde. Doch sie irrten sich.

Eines der berühmtesten Beispiele für eine unentscheidbare Aussage ist das Halteproblem aus der theoretischen Informatik, wie der britische Mathematiker Alan Turing 1937 zeigte. In moderner Form besagt es, dass es keinen Rechner gibt, der für sämtliche Algorithmen beurteilen kann, ob ein sie ausführender Computer jemals mit der Arbeit fertig wird. Als Turing das Halteproblem formulierte, gab es noch keine Computer, wie wir sie kennen. Deswegen fußt seine Argumentation auf dem theoretischen Modell eines solchen, einer so genannten Turingmaschine. Diese besteht aus einem unendlich langen Band, auf dem Symbole verzeichnet sind, und einem Schreib- und Lesekopf, der die Symbole des Bands ausliest und gegebenenfalls überschreibt. Wie sich herausstellt, kann eine solche Turingmaschine alle möglichen Algorithmen ausführen, so wie unsere Computer.

Möchte man beweisen, dass eine Aussage unentscheidbar ist, greift man in der Theorie häufig auf Turingmaschinen zurück. Man versucht, das zu untersuchende System mit einer Turingmaschine zu identifizieren und zu zeigen, dass die betreffende Aussage in diesem Bild dem Halteproblem entspricht. Das hatte auch Robert Berger, Wangs Doktorand, gemacht, um zu beweisen, dass das Domino-Problem unentscheidbar ist. Er hatte die Funktionen einer Turingmaschine (Auslesen, Beschreiben und Verschieben des Bands) mit Kachelungen identifiziert. Zum Beispiel: Das Anlegen einer Fliese mit rotem rechtem Rand an eine andere mit rotem linkem Rand entspricht im Bild der Turingmaschine dem Verschieben des Bands. Auf diese Weise konnte Berger ein System konstruieren, bei dem die Fliesen genau dann die ganze Ebene bedecken, wenn die dazugehörige Turingmaschine niemals hält und für immer weiterrechnet. Damit müsste man das Halteproblem lösen, um das Domino-Problem zu entscheiden.

Dass riesige Kachelsätze komplex genug sind, um die Funktionen einer Turingmaschine zu codieren, erscheint noch nachvollziehbar. Damit stellt sich allerdings die Frage, ob auch kleinere Mengen von Fliesen – vor allem eine einzige Kachel – genug Komplexität mit sich bringen, um zu unentscheidbaren Aussagen zu führen. Wie Terence Tao und Rachel Greenfeld 2023 in einer noch nicht veröffentlichten Arbeit zeigen konnten, ist das in der Tat so. Damit gibt es einzelne Steine, für die sich niemals bestimmen lässt, ob sie einen Raum lückenlos ausfüllen können.

Die periodische Kachelvermutung

Doch der Weg zu diesem Ergebnis war lang – und keineswegs geradlinig. 2019 kam Greenfeld als Postdoc an die UCLA in die Arbeitsgruppe des renommierten Mathematikers Terence Tao, der 2006 die Fields-Medaille erhielt, eine der bedeutendsten Auszeichnungen des Fachs. Sie und Tao hatten zuvor unabhängig voneinander an einem Problem aus dem Bereich der harmonischen Analysis gearbeitet, das mit Parkettierungen zusammenhängt. Dabei hatten sie viele neue Methoden entwickelt, von denen sie hofften, sie im Gebiet der Kachelungen nutzen zu können.

Eine wichtige Frage der Disziplin ist die so genannte periodische Kachelvermutung, die mit Einstein-Kacheln zu tun hat. Sie besagt, dass es keine einzelne aperiodische Fliese gibt, die eine Ebene allein durch Verschiebungen pflastern kann. »Aus der Vermutung würde folgen, dass man stets herausfinden kann, ob eine Fliese die Ebene bedecken kann oder nicht«, schreibt Tao in seinem Blog. Damit hängt die Vermutung eng mit logischen Fragen der Entscheidbarkeit zusammen.

Die 2023 vorgestellten Hut- und Spectre-Kacheln, die jeweils als Einstein gefeiert werden, widersprechen der periodischen Kachelvermutung nicht. Denn damit sie die Ebene bedecken können, muss man sie zumindest drehen dürfen (die Hut-Kachel ist zusätzlich auf Spiegelungen angewiesen). Dass die periodische Kachelvermutung in einer Dimension gültig ist, haben die Mathematiker Jeffrey C. Lagarias und Yang Wang 1996 bewiesen. In zwei Dimensionen ist die Frage nicht ganz beigelegt, jedoch konnte Rick Kenyon 1992 beweisen: Eine solche Fliese kann unmöglich zusammenhängen, sie muss aus mehreren Stücken bestehen. Ob so eine seltsame Kachel existiert, ist noch offen.

Da die periodische Kachelvermutung so schwer zu beantworten ist, untersuchen Fachleute meist eine vereinfachte Variante, die diskrete periodische Kachelvermutung. Statt einer kontinuierlichen Ebene betrachtet man ein zweidimensionales Gitter, also unendlich viele periodisch angeordnete Punkte. Eine Kachel entspricht im diskreten Fall einer endlichen Menge dieser Punkte. Da die Fliese nicht zusammenhängen muss, kann sie auch Lücken enthalten. Dieser Aufbau ähnelt dem ursprünglichen Domino-Problem: Da die quadratischen Kacheln dort zwangsläufig ein schachbrettähnliches Gitter bildeten, entspricht das einer diskreten Parkettierung.

2016 konnte der Mathematiker Siddhartha Bhattacharya beweisen, dass die diskrete Kachelvermutung in zwei Dimensionen korrekt ist. Das war zwar ein großer Fortschritt, allerdings lässt sich sein Ergebnis nicht direkt auf kontinuierliche Flächen verallgemeinern. Denn in der Ebene sind wesentlich vielfältigere Kachelformen möglich, die auf einem Gitter nicht existieren. Damit könnte es eine komplizierte, unzusammenhängende Einstein-Kachel im Kontinuum geben, mit der sich die Ebene aperiodisch pflastern lässt – ohne dass es im diskreten Gitter ein Äquivalent dazu gibt.

Da die diskrete Vermutung in einer und zwei Dimensionen bereits bewiesen war, nahmen sich Greenfeld und Tao vor, den dreidimensionalen Fall der diskreten periodischen Kachelvermutung zu untersuchen: Falls man eine dreidimensionale Form nur verschieben darf und damit den Raum vollständig ausfüllt, dann müsste sich stets ein periodisches Muster ergeben können. So zumindest die Erwartung.

Daher versuchten sie, das zweidimensionale Ergebnis von Bhattacharya mit ihren Methoden erneut für die Ebene zu beweisen. Diese Mühe machten sie sich, weil sie hofften, auf diese Weise einen Beweisweg für den dreidimensionalen Fall zu finden. Doch sie landeten immer in einer Sackgasse. Deswegen beschlossen sie, nach einem Gegenbeispiel zur Vermutung zu suchen. Die Jagd auf eine aperiodische Kachel, die allein durch Verschiebungen einen Raum füllt, war eröffnet.

Aber was bedeutet es für eine hochdimensionale Fliese, aperiodisch zu sein? In zwei Dimensionen erzeugt sie zwangsläufig entlang beider Raumrichtungen ein nichtperiodisches Muster. In drei Dimensionen muss das nicht so sein. Man könnte beispielsweise der 2023 gefundenen zweidimensionalen Einstein-Kachel eine endliche Höhe verpassen und sie in einen flachen, dreidimensionalen Klotz verwandeln. Füllt man damit den Raum, ist das Muster zwar in beiden Richtungen der Ebene nichtperiodisch, in der dritten Raumrichtung bildet es aber ordentlich übereinander geschichtete Lagen. Einen solchen Block bezeichnet man daher als »schwach aperiodisch«, im Gegensatz zu »stark aperiodischen« Kacheln, die entlang aller Raumdimensionen nichtperiodisch sind.

Um die periodische Kachelvermutung zu widerlegen, genügt es, eine schwach aperiodische Kachel zu finden. Die bereits erwähnte Einstein-Kachel eignet sich zur Konstruktion jedoch nicht, da man sie auch drehen muss, um damit die Ebene (und somit auch den Raum) zu füllen. Da Tao und Greenfeld ein Gegenbeispiel zur periodischen Kachelvermutung finden wollten, war das Ausweichen auf ein diskretes Gitter vorteilhaft: Sollten sie tatsächlich eine aperiodische Fliese im diskreten Fall finden, würde das automatisch auch die kontinuierliche periodische Kachelvermutung widerlegen. Denn sie könnten die einzelnen Gitterpunkte, welche die aperiodische Kachel definieren, zu Puzzlestücken vergrößern. Damit hätten sie eine Fliese konstruiert, die den dreidimensionalen Raum füllen kann.

Doch auch im Dreidimensionalen stießen die Mathematikerin und der Mathematiker auf unüberwindbare Hürden. Daher wollten sie untersuchen, ob sie in höheren Dimensionen ein Gegenbeispiel zur diskreten periodischen Kachelvermutung finden würden. Im August 2021 kamen Greenfeld und Tao einem Ergebnis nahe. Sie konnten beweisen, dass es Dimensionen gibt, in denen sich nicht entscheiden lässt, ob Kachelsätze, bestehend aus zwei Formen, einen Raum allein durch Verschiebungen füllen können oder nicht. Daraus folgt, dass in hohen Dimensionen aperiodische Pflasterungen mit bloß zwei Fliesenformen existieren.

Eine neue Sprache und ein Sudoku-Rätsel

Um die periodische Kachelvermutung zu widerlegen, ist aber ein Gegenbeispiel mit bloß einer Fliese nötig – nicht zwei. Daher brauchten Tao und Greenfeld einen anderen Ansatz. Sie mussten eine neue Art von Sprache entwickeln, in der sie ihr Problem formulieren konnten. Sie wollten eine Gleichung in Form von »Fliesenform verknüpft mit Anordnung = geometrischer Raum« erhalten. Der Raum und die Fliesenform können dabei hochdimensional sein. Damit die Fliese aperiodisch ist, müssen alle Anordnungen (die Unbekannte in der Formel) nichtperiodisch sein. Eine Lösung für eine solche Gleichung zu finden, bei der alle Anordnungen nichtperiodisch sind, ist allerdings extrem kompliziert.

Daher haben Greenfeld und Tao das Problem in viele kleine Teilaufgaben gegliedert. »Das Ganze funktioniert wie ein Sandwich«, erklärt Greenfeld. Anstatt direkt eine aperiodische Kachel in d Dimensionen zu konstruieren, betrachten sie einzelne d−1-dimensionale Schichten – das ist, als würde man einen dreidimensionalen Block in einzelne Ebenen aufteilen. Der Trick besteht darin, d−1-dimensionale Kacheln zu finden, die den Raum mit identischen Verschiebungen ausfüllen. Das lässt sich am Beispiel von quadratischen Fliesen erklären: Diese muss man jeweils um die eigene Seitenlänge nach oben, unten, rechts oder links verschieben, um die gesamte Ebene abzudecken. Wenn man eine Kerbe in die linke Seite des Quadrats schneidet und eine Ausbuchtung an der rechten Seite hinzufügt, erhält man eine neue Fliese, die mit denselben Verschiebungen die Ebene pflastert. Indem man alle Fliesenformen übereinanderstapelt, die diesen Verschiebungen genügen, hat man eine Kachel in d Dimensionen erzeugt.

»Lustigerweise ist die Lösung fast periodisch, aber eben nicht ganz«Rachel Greenfeld, Mathematikerin

Für jede d−1-dimensionale Fliesenform lässt sich ebenfalls eine Gleichung der Form »Fliesenform verknüpft mit Anordnung = geometrischer Raum« formulieren, die jedoch einfacher ist. »Der Vorteil dieser Umformulierung ist, dass sie eine ›Sprache‹ schafft, in der jeder Satz die Lösung einschränkt«, erklärt Tao in seinem Blog. Diese Gleichungen könnten zum Beispiel Anlegeregeln (falls es solche gäbe) entsprechen, etwa »Nur gleichfarbige Kanten dürfen aneinandergrenzen«. Nun brauchten Tao und Greenfeld noch die passenden Einschränkungen, damit die von ihnen konstruierte d-dimensionale Fliese aperiodisch ist – also keine periodische Pflasterung zulässt. Gleichzeitig durften die Einschränkungen nicht zu stark sein, so dass eine Parkettierung überhaupt möglich ist.

Um diesen Ansprüchen zu genügen, haben die Forscherin und der Forscher die vielen Gleichungen weiter umformuliert, bis sie einer Art Rätsel entsprachen. »Es ist wie ein riesiges Sudoku-Spiel«, erläutert Greenfeld, »wobei jede Spalte nichtperiodisch sein muss, damit das endgültige Ergebnis, die Kachel, aperiodisch ist.« Die Schwierigkeit bestand nicht nur darin, das Sudoku-Rätsel zu finden, also die passenden Einschränkungen zu definieren. Die beiden mussten auch sicherstellen, dass sich diese Einschränkungen in ihre Sprache übersetzen lassen, um sie als Gleichungen auszudrücken. Nach viel Mühe war ihnen das Kunststück gelungen. »Lustigerweise ist die Lösung fast periodisch, aber eben nicht ganz«, sagt Greenfeld.

Sie mussten die Lösung nur noch zusammenfügen und daraus eine einzelne d-dimensionale Gleichung ableiten. Diese führte zu einem Gegenbeispiel der diskreten periodischen Kachelvermutung. Das Ergebnis ist eine aperiodische Fliese in d Dimensionen, die den Raum allein durch Verschiebungen füllt. Indem Tao und Greenfeld die Punkte, aus denen die Kachel besteht, zu hochdimensionalen Puzzleteilen aufbliesen, konnten sie das Resultat auf den kontinuierlichen Raum verallgemeinern.

Damit ist nun klar: Die periodische Kachelvermutung gilt nicht in allen Dimensionen. »Wir haben d aber nicht berechnet«, kommentiert Greenfeld. »Wir könnten es zwar, doch es ist nicht interessant. Denn wir haben nicht versucht, ein optimales Ergebnis zu erhalten – wir wollten bloß wissen, ob es überhaupt eine Dimension gibt, in der die periodische Kachelvermutung nicht erfüllt ist.« Höchstwahrscheinlich überschätzt das Ergebnis der Mathematikerin und ihres Kollegen die Dimension, ab der die Vermutung nicht mehr gilt. »Sie könnte schon in vier Dimensionen falsch sein«, sagt Greenfeld. »Das war eine echte Überraschung. Ich hatte erwartet, dass die periodische Kachelvermutung für alle Dimensionen gilt«, sagte der Mathematiker Mihalis Kolountzakis von der Universität Kreta dem »Quanta Magazine«. »Aber wenn es um hohe Dimensionen geht, kommt man mit reiner Intuition meist nicht sehr weit.«

Auch das genaue Aussehen der aperiodischen Kachel haben die beiden Forscher nicht untersucht, sie sei jedoch wahrscheinlich unzusammenhängend und nicht besonders schön, wie Greenfeld erklärt. Aber was wäre, wenn man die periodische Kachelvermutung auf zusammenhängende Kacheln beschränken würde? In zwei Dimensionen ist die Vermutung für Fliesen aus einem Stück beispielsweise bewiesen. Wie Greenfeld jedoch gemeinsam mit Kolountzakis im Mai 2023 herausfand, ist es in hohen Dimensionen sogar möglich, eine zusammenhängende aperiodische Kachel zu konstruieren.

Damit blieb noch die Frage zur Unentscheidbarkeit zu klären: Lässt sich stets vorhersagen, ob eine einzige Fliese einen Raum lückenlos ausfüllen kann? »Die Unentscheidbarkeit ist stärker als die Aperiodizität«, sagt Greenfeld. Wenn man zeigen kann, dass es Fälle gibt, in denen man nicht beurteilen kann, ob eine einzelne Kachel einen Raum kachelt, folgt daraus sofort, dass aperiodische Fliesen existieren. Umgekehrt kann man den Schluss jedoch nicht ziehen. Aus Aperiodizität folgt nicht zwangsweise Unentscheidbarkeit.

»Ich kann mich kaum von der Arbeit abwenden. Ich habe selbst im Flugzeug WLAN-Zugang gekauft, um weiterzumachen, ich bin richtig besessen«Rachel Greenfeld, Mathematikerin

Greenfeld und Tao hofften, mit ihren neu entwickelten Methoden nun auch diese Frage angehen zu können. Damit eine einzelne Kachel unentscheidbar ist, muss man ihre Parkettierungen letztlich auf das Halteproblem aus der Informatik abbilden. Dafür muss man unter anderem zeigen, dass sie alle Funktionen einer Turingmaschine – und damit eines Computers – ausführen können. Die Frage war also, ob eine einzelne Kachel komplex genug ist, um diese Funktionen zu ermöglichen.

In einer noch nicht veröffentlichten Arbeit konnten Greenfeld und Tao beweisen, dass das tatsächlich der Fall ist: Es gibt Dimensionen, in denen man niemals entscheiden kann, ob eine einzelne Fliese den Raum füllen kann. »Es macht wirklich Spaß«, sagt Greenfeld über ihre Arbeit. »Ich kann kaum damit aufhören. Ich habe selbst im Flugzeug WLAN-Zugang gekauft, um weiterzumachen, ich bin richtig besessen.«

Diese Begeisterung ist viel versprechend angesichts der zahlreichen offenen Fragen, die das Gebiet birgt. Etwa was die kleinste Dimension ist, bei der die periodische Kachelvermutung noch gilt. Oder ob die Vermutung gültig bleibt, wenn man bloß zusammenhängende Fliesen zulässt. Und natürlich: ob es im Zweidimensionalen eine unzusammenhängende aperiodische Kachel gibt, die allein durch Verschiebungen die Ebene bedeckt. Vielleicht erwarten uns bei der Lösung dieser Probleme weitere Überraschungen.