Einen Boden mit einem kreativen Fliesenmuster zu pflastern, ist nicht nur eine anstrengende Aufgabe für Handwerkerinnen und Handwerker – tatsächlich zählt das zu den schwersten Problemen der Mathematik. Seit Jahrzehnten beschäftigen sich Fachleute damit, welche Kachelformen eine Ebene lückenlos bedecken können. Aus mathematischer Sicht sind vor allem jene Parkettierungen spannend, die nicht periodisch sind, deren Muster sich also niemals regelmäßig wiederholen. Bisher brauchte man dafür immer mehrere unterschiedlich geformte Kacheln. Seit etlichen Jahrzehnten suchten Mathematiker und Mathematikerinnen eine »Einstein«-Kachel (benannt nach »ein Stein«, nicht nach dem Physiker), die allein schon Muster hervorruft, die sich niemals regelmäßig wiederholen. Viele hatten die Hoffnung darauf bereits aufgegeben.

Doch im November 2022 glaubte der pensionierte Druckanlagentechniker David Smith aus Yorkshire, eine solche Einstein-Kachel gefunden zu haben. Als er den mathematikbegeisterten Informatiker Craig Kaplan von der University of Waterloo darauf aufmerksam machte, erkannte dieser schnell das Potenzial der Kachel: Zusammen mit dem Softwareentwickler Joseph Samuel Myers und dem Mathematiker Chaim Goodman-Strauss von der University of Arkansas konnte er tatsächlich beweisen, dass die Fliese eine Ebene lückenlos und ohne regelmäßige Wiederholung pflastert. Doch sie fanden noch mehr: Smith hatte nicht nur den Weg zu einer, sondern gleich zu unendlich vielen Einstein-Kacheln geebnet. Ihre Ergebnisse haben sie nun in einer noch nicht begutachteten Arbeit veröffentlicht.

Von schönen Mustern zu unbeweisbaren Fragen

Wer schon einmal durch die Gänge der Alhambra im spanischen Granada geschritten ist, hat sicher noch die atemberaubenden Fliesenmosaikwerke vor Augen. Mit ähnlich kunstvollen Darstellungen beschäftigt sich auch die Mathematik. Doch wie der Mathematiker Robert Berger im Jahr 1966 feststellte, birgt das Themenfeld Fragen, die sich niemals beantworten lassen: Sie sind beweisbar unbeweisbar.

Angenommen, Sie möchten mit unendlich vielen quadratischen Kacheln eine unbegrenzte Ebene fliesen. Allerdings müssen Sie dabei eine Regel befolgen: Die Kanten der Fliesen sind eingefärbt und sich berührende Kanten müssen stets die gleiche Farbe haben. Nun setzt man Ihnen mehrere Typen von gefärbten Fliesen vor (davon aber jeweils unendlich viele) und Sie beginnen die mühselige Aufgabe. Sie pflastern die Ebene nach der vorgegebenen Regel, landen aber irgendwann in einer Sackgasse. Sie können keine nächste Fliese legen, deren Färbung zu der Lücke passt. Mit einer anderen Zusammenstellung von Fliesentypen (zum Beispiel mit nur einer Fliese, deren Ränder alle gleich gefärbt sind) könnten Sie hingegen problemlos vorankommen. Daher fragten sich Mathematiker: Lässt sich anhand der vorgegebenen Fliesentypen vorhersagen, ob man damit die Ebene pflastern kann oder irgendwann in einer Sackgasse landet? Berger fand die Antwort: Nein. Es wird immer Fälle geben, bei denen man nicht vorhersagen kann, ob man damit eine Ebene lückenlos bedecken kann. Die Frage gehört zu den unentscheidbaren Problemen der Mathematik.

Grund für diese Unentscheidbarkeit sind nichtperiodische Parkettierungen: Berger hatte in seiner Arbeit eine Menge von unglaublichen 20 426 unterschiedlich gefärbten Kacheln gefunden, mit denen man die Ebene pflastern kann, ohne dass sich das Farbmuster jemals regelmäßig wiederholt. Und besser noch: Die Kacheln lassen es gar nicht erst zu, ein periodisches Muster zu bilden – egal, wie man sie legt. Damit ergab sich eine weitere Frage: Wie viele Kacheltypen braucht man mindestens, um eine zwingend nichtperiodische Parkettierung zu erzeugen?

Von 20 426 Kacheln bis zu einer einzigen

Mathematikerinnen und Mathematiker versuchten sich in den folgenden Jahrzehnten immer weiter zu unterbieten: Zunächst fand Berger ein Beispiel mit 104 unterschiedlichen Kacheln, die lediglich nichtperiodische Muster erzeugen, 1968 fand der Informatiker Donald Knuth ein Beispiel mit 92, ein Jahr später fand der Mathematiker Rafael Robinson eine Variante mit bloß sechs Fliesentypen – und schließlich präsentierte der Physiker Roger Penrose 1974 eine Lösung mit nur zwei Kacheln.

Seither fragt sich die Fachwelt, ob es auch möglich ist, eine einzige Kachelform zu finden, die die Ebene überdeckt, ohne jemals ein periodisches Muster zu erzeugen. Zahlreiche Menschen haben in den vergangenen Jahrzehnten nach einem solchen »Einstein« gesucht, jedoch erfolglos. Auch Penrose hatte dem heiligen Gral nachgejagt, widmete sich schließlich jedoch anderen Dingen. Nicht so der 64-jährige Frührentner David Smith. Laut »New York Times« spielte er gerne mit dem »PolyForm Puzzle Solver« herum, einer Software, mit der man Kacheln entwerfen und zusammensetzen kann. Wenn eine Form viel versprechend aussah, schnitt Smith daraus mehrere Puzzle-Stücke aus Papier zurecht, um damit herumzuexperimentieren. So stieß er im November 2022 auf die Figur, die er wegen ihrer hutartigen Form als »Hat« bezeichnete – auch wenn Kaplan betont, dass viele darin eher ein T-Shirt sehen.

Als Kaplan eine E-Mail von Smith mit dem »Hat« erhielt, war sein Interesse schnell geweckt. Mit Hilfe einer Software reihte er immer mehr hutförmige Kacheln aneinander, und es schien, als könne man die Ebene wirklich lückenlos bedecken. Und: Es war auch kein sich regelmäßig wiederholendes Muster erkennbar. Doch das musste erst mathematisch bewiesen werden. Schließlich könnte sich das Muster erst nach mehreren Lichtjahren wiederholen. Dann wäre die Periodizität erst nach etlichen Rechenschritten sichtbar. Daher wandte sich Kaplan an Myers und Goodman-Strauss, die sich in der Vergangenheit bereits ausführlich mit Kachelungen beschäftigt hatten.

Zunächst waren sie von der Einfachheit der potenziellen Einstein-Kachel erstaunt: Der »Hat« hat eine recht simple, 13-seitige Form. Wenn man ihn gefragt hätte, wie ein Einstein wohl aussehen würde, erzählt Goodman-Strauss gegenüber »Science News«, »hätte ich auf etwas vollkommen Verrücktes getippt«. Und als sie die Figur genauer unter die Lupe nahmen, erkannten sie, dass sie mit den Längen der Seiten spielen können und immer noch ein lückenloses, nichtperiodisches Muster vorfinden. Damit hatten sie nicht nur eine potenzielle Einstein-Kachel vor sich, sondern unendlich viele!

Ein Muster, das sich niemals regelmäßig wiederholt

Doch zunächst brauchten sie einen stichhaltigen Beweis. Zunächst stützten sich die Wissenschaftler auf bewährte Methoden, die Fachleute seit Jahrzehnten nutzen, um zu zeigen, dass gewisse Kacheltypen eine aperiodisch sind. Doch nicht nur das: Myers konnte darüber hinaus eine zweite, vollkommen neue Beweismethode entwickeln, die sich auch für andere Kachelungen bewähren könnte.

Die bewährte Beweismethode lässt sich gut an der Robinson-Parkettierung mit sechs verschiedenen Kacheln veranschaulichen. Die auf den Fliesen aufgezeichneten Linien sind das Analogon der gefärbten Ränder bei Wangs Quadraten: Man darf die Robinson-Kacheln nur so aneinanderlegen, dass gleichfarbige Linien glatt fortgesetzt werden. Wenn man diese Regel befolgt, ergibt sich daraus ein erkennbares Muster: Die gelben Linien bilden Quadrate, in deren Mittelpunkt die Ecke eines größeren Quadrats startet und so weiter. Man kann der Parkettierung also eine hierarchische Struktur zuordnen: immer größer werdende Quadrate, die sich kreuzen. Deshalb kann die Parkettierung unmöglich periodisch sein. Wäre sie es, dann würden Ausschnitte des Musters an anderer Stelle genau so auftauchen. Wenn man nun aber einen Teil der Parkettierung nimmt und verschiebt, zerstört man zwangsläufig die hierarchische Struktur.

Ähnliches konnten Kaplan, Goodman-Strauss und Myers für die von Smith vorgeschlagene hutförmige Einstein-Kachel zeigen. Allerdings haben sie dafür nicht den Hut selbst unter die Lupe genommen, sondern vier verschiedene Cluster, die sich teilweise aus mehreren Kacheln zusammensetzen: eine sechseckige Struktur aus vier Hut-Kacheln, ein Fünfeck aus zwei Kacheln, ein Parallelogramm aus zwei Kacheln und eine einzelne Kachel, die die Forscher durch ein Dreieck darstellen. Indem sie passende Regeln definierten, wie man die vier Cluster-Polygone zusammenführen darf, lässt sich die Ebene lückenlos bedecken. Gleichzeitig bilden die Cluster-Polygone ein Muster, das – wie sie beweisen – sich niemals regelmäßig wiederholt.

Kombiniert man die vier Cluster miteinander, ergibt sich daraus wieder eines der vier Polygone (Sechseck, Fünfeck, Parallelogramm oder Dreieck). Wie Myers, Kaplan und Goodman-Strauss zeigen konnten, ist diese größere Struktur einzigartig: Sie kann nur aus einer einzigen Anordnung der kleineren Cluster-Polygone entstehen. Nun kann man die großen Vielecke wieder miteinander kombinieren, um noch größere Strukturen zu formen: Auch diese ergeben entweder ein Sechs-, Fünf-, Vier- oder Dreieck – und auch diese setzen sich aus einer eindeutigen Anordnung der kleineren Vielecke zusammen. Das kann man unendlich oft wiederholen und erhält dadurch eine hierarchische Struktur, wie im Fall der Robinson-Parkettierung. Damit ist Periodizität ausgeschlossen: Es lassen sich immer größere Vielecke erzeugen, die sich aus einer eindeutigen Anordnung kleinerer Cluster zusammensetzen. Würde man Ausschnitte daraus einfach an eine andere Stelle verschieben, hätte die übergeordnete Struktur ihre Einzigartigkeit verloren. Und wie sich herausstellt, lässt sich dieser Beweis nicht nur mit dem von Smith vorgestellten »Hat« durchführen, sondern auch mit den Variationen der Kachel.

Zwei Beweise sind besser als einer

Um diesen Beweis zu führen, waren viele aufwändige Berechnungen nötig: Man muss viele Kombinationen durchspielen, wie sich die Cluster zusammenfügen lassen, und sicherstellen, dass die sich daraus ergebende Struktur stets einzigartig ist. Dafür griffen die drei Wissenschaftler auf die Hilfe von Computern zurück. Sie haben zwei Programme unabhängig voneinander entwickelt und frei veröffentlicht, so dass jeder sie auf eventuelle Fehler prüfen kann.

Doch Myers gab sich damit nicht zufrieden: Er führte einen zweiten Beweis, der völlig ohne Computer auskommt, und konnte zeigen, dass die Hut-Kachelung mit zwei anderen Parkettierungen aus so genannten Polydiamanten (geometrischen Formen, die aus gleichseitigen Dreiecken bestehen) zusammenhängt: Wenn die beiden Pflasterungen aus Polydiamanten nichtperiodisch sind, hat die Hut-Kachel automatisch dieselben Eigenschaften. Und tatsächlich lassen sich die Polydiamant-Systeme einfacher untersuchen: Wären sie periodisch, gäbe es Verschiebungsvektoren, die einen Bereich der Parkettierung auf einen identischen überführen. Und die Verschiebungsvektoren der beiden Polydiamanten-Pflasterungen müssten sich laut Myers um einen rationalen Faktor (eine Bruchzahl) unterscheiden. Doch Myers fand ein Verhältnis von √2 – eine irrationale Zahl. Irrationale Werte in Pflasterungen deuten meist auf Nichtperiodizität hin: Würde sich ein Muster regelmäßig wiederholen, dann wäre das Verhältnis bestimmter Größen über die gesamte Fläche gleich und würde damit eine rationale Zahl ergeben. Myers hat also ausgeschlossen, dass die beiden Polydiamanten-Parkettierungen periodisch sind und damit bewiesen: Die Hut-Kachel ist ebenfalls nichtperiodisch – und sogar aperiodisch, das heißt sie kann gar nicht zu einem periodischen Muster gelegt werden.

Damit haben Myers, Kaplan und Goodman-Strauss nicht nur belegt, dass die von Smith gefundene Kachel wirklich der lange gesuchte Einstein ist. Sie haben zudem eine neue Methode vorgestellt, um die Aperiodizität von Musterungen zu beweisen: indem man eine Parkettierung in zwei andere aufspaltet und mit diesen arbeitet. Dieses Verfahren könnte auch für andere Anwendungen hilfreich sein, erklären die Wissenschaftler in ihrem Paper. Die Fachwelt ist von den Ergebnissen begeistert: Der Mathematiker Colin Adams vom Williams College in Massachusetts sagte beispielsweise dem »New Scientist«, er würde sofort sein Bad mit den hutförmigen Kacheln fliesen.