MANCHE VIERDIMENSIONALEN FORMEN KANN KEIN ALGORITHMUS ERKENNEN

Manche Fragen haben kein Rezept. Nicht, weil noch niemand eines gefunden hat, sondern weil bewiesen ist, dass kein Algorithmus – kein Schritt-für-Schritt-Verfahren, wie lang auch immer, auf welchem Computer auch immer – sie jedes Mal richtig beantworten kann. Cameron McA. Gordon von der University of Texas at Austin fügt zwei solche Fragen über vierdimensionale Formen hinzu.

Ist das dieselbe Form?

In der Mathematik heißen diese Formen 4-Mannigfaltigkeiten: Räume, die aus der Nähe betrachtet überall wie der gewöhnliche vierdimensionale Raum aussehen. Um sie einem Computer zu übergeben, nimmt die Arbeit an, dass sie aus zusammengeklebten flachen Stücken aufgebaut sind („stückweise linear“, englisch piecewise linear oder PL), sodass sich jede durch eine endliche Liste von Daten beschreiben lässt. Die Grundfrage lautet dann: Sind zwei solche Formen gegeben, sind sie bis auf stetige Verformung dieselbe?

1958 zeigte A. A. Markov, dass es für diese Frage keinen Algorithmus gibt. Markovs Beweis verwandelt das Formenproblem in ein Problem über Gruppen: Es gibt Gruppen, definiert durch endlich viele Regeln, für die kein Algorithmus entscheiden kann, ob eine gegebene Kombination ihrer Elemente gleich dem neutralen Element ist – das „Wortproblem“. Aus einer solchen Gruppe lassen sich Formen bauen, die ein Algorithmus nur unterscheiden könnte, indem er dieses unlösbare Problem löst.

Herunterzählen bis sieben

Markovs Argument macht die Schwierigkeit sogar an bestimmten Formen fest. Man nehme S², die Oberfläche einer gewöhnlichen Kugel, und bilde das Produkt S² × S², eine vierdimensionale Form. Man klebe k Kopien davon zusammen (eine „zusammenhängende Summe“, geschrieben #k). Für manche k kann kein Algorithmus entscheiden, ob eine gegebene Form #k(S² × S²) ist. Für welche k?

Die Arbeit zeichnet den Countdown nach. Eine Gruppe mit unlösbarem Wortproblem und 12 Regeln, 1969 von Borisov gefunden, ergab 14 Kopien. Gordon senkte das 2022 auf 12. M. Tancer fand einen neuen Weg, über Freedmans Klassifikation vierdimensionaler Formen, und erreichte 9 in der „topologischen“ Version, in der die Formen nicht aus flachen Stücken gebaut sein müssen. Eine frühere Fassung dieser Arbeit erreichte 8. Dann bauten Kegel, Li und Ren eine viel kleinere unlösbare Gruppe – 3 Erzeuger und 9 Regeln – und erreichten 7 in der topologischen Version und 9 in der Version mit flachen Stücken.

Gordon bringt Tancers Weg auch für Formen aus flachen Stücken zum Funktionieren und beweist:

Es gibt keinen Algorithmus, der entscheidet, ob eine gegebene 4-Mannigfaltigkeit Stück für Stück dieselbe ist wie die zusammenhängende Summe von 7 Kopien von S² × S².

Den Kern des Beweises bildet ein Wörterbuch. Für jedes Wort w in der Gruppe von Kegel, Li und Ren baut Gordon eine vierdimensionale Form. Ist w gleich dem neutralen Element, zeigt eine Folge erlaubter Züge an den Regeln – die Andrews-Curtis-Züge, die die Beschreibung umschreiben, ohne die Form zu verändern –, dass die Form genau sieben Kopien von S² × S² ist. Ist es das nicht, enthält die Form Schleifen, die sich nicht zu einem Punkt zusammenziehen lassen – was in sieben Kopien von S² × S² nie vorkommt –, und kann daher nicht diese sieben Kopien sein. Ein Algorithmus, der #7(S² × S²) erkennt, würde daher das Wortproblem lösen, was unmöglich ist.

Verknotete Sphären

Die zweite Frage betrifft Knoten. Ein gewöhnlicher Knoten ist ein im dreidimensionalen Raum verknoteter Kreis, und ob sich ein Knoten entwirren lässt, kann man entscheiden: Es gibt einen Algorithmus, der auf Haken zurückgeht. Eine Dimension höher kann eine zweidimensionale Sphäre im vierdimensionalen Raum verknotet sein. In höheren Dimensionen ist bekannt, dass das entsprechende Problem keinen Algorithmus hat. Für zweidimensionale Sphären in der vierdimensionalen Sphäre S⁴ weiß es niemand.

Gordon beweist, dass es in #7(S² × S²) keinen Algorithmus gibt, der entscheidet, ob eine zweidimensionale Sphäre – oder eine beliebige Fläche, orientierbar oder nicht – unverknotet ist. Nebenbei konstruiert die Arbeit in dieser Form eine Sphäre, deren umgebender Raum eine Gruppe mit unlösbarem Wortproblem hat, und in 12 Kopien von S² × S² eine Sphäre, deren Gruppe eine Kopie jeder Gruppe enthält, die sich durch einen Computer beschreiben lässt.

Der Preis: null Kopien

Die Arbeit benennt das Ziel klar: die Zahl der Kopien auf null zu senken. Null Kopien bedeutet die vierdimensionale Sphäre S⁴ selbst. In fünf und mehr Dimensionen kann kein Algorithmus die Sphäre erkennen; in zwei und drei Dimensionen kann einer es. Vier Dimensionen bleiben offen – ebenso die Frage, ob sich verknotete Sphären in S⁴ erkennen lassen. Jede entfernte Kopie rückt beide Fragen näher heran.