22 MULTIPLIKATIONEN, KEINE EINZIGE WENIGER

Interessenkonflikt. Die Autoren geben an, dass KI-Agenten — Claude, von Anthropic — unter ihrer Anleitung den Suchcode und die Lean-Beweise geschrieben haben, die keinen menschlichen Prüfer benötigen, während der Teil, den ein Mensch prüfen muss, von den Autoren entworfen wurde. Auch dieser Artikel wurde von Claude geschrieben.

Zwei quadratische Zahlengitter — Matrizen — nach Schulbuchart zu multiplizieren, erfordert n³ Multiplikationen bei Gittern mit n Zeilen und n Spalten. Strassen zeigte, dass sich zwei 2 × 2-Matrizen mit 7 statt 8 Multiplikationen multiplizieren lassen. Der Trick lässt sich rekursiv anwenden: Man zerlegt eine große Matrix in vier Blöcke, behandelt jeden Block wie eine einzelne Zahl und wiederholt das. Der Aufwand wächst dann wie n^2,807 statt wie n³. Laut dem Paper wurde dieses 2 × 2-Rezept 1971 als optimal bewiesen.

Dieselbe Idee funktioniert für jede feste Größe. Ein Rezept, das zwei 3 × 3-Matrizen mit r Multiplikationen multipliziert und auch dann noch funktioniert, wenn die Einträge Blöcke sind, ergibt einen Aufwand, der wie n hoch log₃ r wächst. Einfache Arithmetik zeigt, worum es geht: Ein solches Rezept schlägt Strassen genau dann, wenn r höchstens 21 ist, und verliert ab 22. Das beste bekannte 3 × 3-Rezept, von Laderman, verwendet 23 Multiplikationen und wurde seit 1976 nicht verbessert.

Eine Tür, die einen Spalt offen blieb

Die bestmögliche Anzahl für ein gegebenes Problem nennt man seinen Rang. Untere Schranken für den Rang der 3 × 3-Multiplikation krochen langsam nach oben: 19 im Jahr 2003, dann 20 im März 2026, berechnet von Wang über einem winzigen Zahlensystem mit nur 0 und 1, in dem 1 + 1 = 0 gilt. Im September 2026 erreichten Wang und ein Team unter Leitung von Yang unabhängig voneinander 21, im Abstand von zehn Tagen. Doch 21 ließ immer noch Raum für ein 3 × 3-Rezept, das schneller ist als das von Strassen.

Isaac Rudich von der Polytechnique Montréal und der Carnegie Mellon University sowie Louis-Martin Rousseau von der Polytechnique Montréal haben die Schranke nun auf 22 angehoben.

Satz 1. Jeder Algorithmus, der zwei 3 × 3-Matrizen mit ganzzahligen Konstanten multipliziert und sich rekursiv auf Blöcke beliebiger Größe anwenden lässt, verwendet mindestens 22 Multiplikationen.

Kein solcher Algorithmus kann also besser sein als etwa n^2,814 — und keiner kann Strassens 2 × 2-Methode schlagen.

496 kleinere Rätsel

Der Beweis baut auf einer von Wang entworfenen Tabelle auf, die das schwere Problem in 496 leichtere zerlegt. Jedes davon fügt der ersten Matrix „Bedingungen“ hinzu — zum Beispiel, dass sich bestimmte ihrer Einträge zu null addieren. Je mehr Bedingungen, desto leichter das Problem, bis hin zum trivialen Fall, in dem die Matrix nur aus Nullen besteht.

Die Autoren bauten zunächst ein exaktes Suchprogramm, das ihnen die wahre Antwort für jedes Rätsel verriet, bevor sie versuchten, sie zu beweisen. Diese Antworten dienten als Landkarte: Sie zeigten, welchen unteren Schranken nachzujagen sich lohnte. Am Ende beschränkt ihr Beweis alle 496 Rätsel, löst 359 davon exakt — gegenüber 195 in Wangs neuesten Ergebnissen — und hebt die untere Schranke für 252 an. Ein eigener „Klebe“-Satz kombiniert Rezepte für zwei leichtere Rätsel zu einem Rezept für ein drittes und lieferte 145 der oberen Schranken.

Zwei Bedingungen spielen in der Endaussage eine Rolle. Ganzzahlige Konstanten: Ein Rezept mit ganzzahligen Konstanten bleibt, im Zahlensystem aus 0 und 1 gelesen, ein gültiges Rezept ohne zusätzliche Multiplikationen, sodass sich die Schranke überträgt. Blöcke: Ohne diese Anforderung gibt es Abkürzungen. Rosowskis 3 × 3-Algorithmus, im Paper zitiert, braucht nur 21 Multiplikationen, beruht aber darauf, dass Zahlen kommutieren, und lässt sich nicht rekursiv anwenden.

Ein von einer Maschine geprüfter Beweis

Der Beweis ist in Lean geschrieben, einer Programmiersprache, in der ein Satz nur kompiliert, wenn jeder Schritt verifiziert ist. Der vollständige Beweis umfasst etwa eine Million Zeilen in 3.521 Modulen, und seine Prüfung dauert auf einem einzelnen Prozessorkern 11,1 Stunden. Niemand muss alles lesen. Ein Prüfer liest eine Bibliothek von etwa 1.000 Zeilen, die die Autoren geschrieben haben, bevor es irgendeinen Beweis gab, und die definiert, was ein Multiplikationsrezept ist, und den Satz formuliert; den Rest prüft der Kern von Lean, und ein unabhängiger Prüfer kann das Ergebnis nachvollziehen.

Die Autoren merken außerdem an, dass die KI-Agenten die Literatur durchsucht haben: Sie haben geprüft, dass jede Quelle existiert, „aber nicht, dass jede genau die Idee enthält, die wir ihr zuschreiben“.

Die letzte Lücke

Eine Frage bleibt: Gibt es ein 3 × 3-Rezept mit 22 Multiplikationen, oder ist Ladermans 23 das wahre Minimum? Die Autoren erwarten, dass die Lücke „unmittelbar geschlossen wird“, und wollen ihren Suchcode veröffentlichen, sobald das geschieht oder sobald das Paper zur Veröffentlichung angenommen ist. Die Schranke lässt außerdem Rezepte mit nicht ganzzahligen Konstanten außen vor.