🔢 mathematics

Classification of Boolean Cubic Forms in Ten Variables

Diese Arbeit präsentiert eine vollständige Klassifizierung boolescher kubischer Formen in zehn Variablen bis zur GL(10,2)-Äquivalenz, was einen Katalog von 3.691.560 Nichtnull-Orbits mit detaillierten Strukturdaten liefert und die erste vollständige Klassifizierung alternierender trilinearer Formen in Dimension 10 über GF(2) etabliert.

Ursprüngliche Autoren: Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

Veröffentlicht 2026-06-30

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kirill Khoruzhii, Patrick Gelß, Sebastian Pokutta

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie hätten eine riesige Kiste mit Lego-Steinen. Sie möchten jede mögliche einzigartige 3D-Form bauen, die Sie aus genau zehn spezifischen Arten von Steinen bauen können. Aber es gibt einen Haken: Wenn man eine Form drehen oder wenden kann, sodass sie exakt wie eine andere aussieht, zählen sie als die gleiche Form.

Dieses Papier ist im Wesentlichen ein massiver, erschöpfender Katalog aller jener einzigartigen Formen, die man aus den Lego-Steinen bauen kann, aber anstelle von Lego-Steinen verwenden wir mathematische Bausteine, die Boolesche kubische Formen genannt werden.

Hier ist die Aufschlüsselung dessen, was die Autoren getan haben, unter Verwendung einfacher Analogien:

1. Die große Aufgabe: Das Chaos ordnen

Die Autoren wollten jede mögliche mathematische Expression sortieren, die zehn Variablen umfasst (nennen wir sie $x_1$ bis $x_{10}$ ) und dabei bestimmten Regeln folgt (sie sind „kubisch“, was bedeutet, dass sie drei Variablen miteinander multiplizieren, wie $x_1 \times x_2 \times x_3$ ).

Es gibt Milliarden von Möglichkeiten, diese Ausdrücke zu schreiben. Aber viele von ihnen sind nur „Verkleidungen“ derselben zugrunde liegenden Struktur. Wenn man die Bezeichnungen Ihrer Variablen ändert (ein mathematischer „Basenwechsel“), könnten zwei unterschiedlich aussehende Formeln tatsächlich dieselbe Form sein.

Das Ziel war es, jede einzigartige Form (einen „Orbit“) zu finden und sie alle aufzulisten.

Das Ergebnis: Sie fanden genau 3.691.560 einzigartige Formen. Das ist eine riesige Zahl, aber es ist die vollständige Liste. Nichts fehlt.

2. Wie sie es taten: Die „Rang“-Strategie

Anstatt zu versuchen, alle Möglichkeiten auf einmal aufzulisten (was ewig dauern würde), bauten sie die Formen Schicht für Schicht auf, wie das Erklimmen einer Leiter.

Die Leiter (Alternierender Rang): Sie begannen mit den einfachsten Formen (Rang 1). Dann fragten sie: „Was passiert, wenn ich einen einfachen Baustein zu einer Rang-1-Form hinzufüge?“ Das erzeugt eine Rang-2-Form. Sie fügten immer weiter Blöcke hinzu und stiegen so die Leiter von Rang 1 bis Rang 7 hinauf.
Der Filter: Bei jedem Schritt mussten sie prüfen: „Ist diese neue Form wirklich neu, oder ist sie nur eine getarnte Version einer Form, die wir bereits gefunden haben?“

3. Die Detektivarbeit: Der „Fingerabdruck“

Um festzustellen, ob zwei Formen dieselbe sind, benötigten sie einen perfekten Fingerabdruck.

Der erste Hinweis (Der Orthogonalitätsgraph): Sie verwandelten jede Form in eine Karte (einen Graphen), die zeigt, wie die Variablen miteinander in Beziehung stehen. Für kleinere Probleme (weniger als 10 Variablen) reichte diese Karte aus, um zu beweisen, dass zwei Formen identisch sind.
Das Problem: Bei 10 Variablen erzeugten zwei völlig unterschiedliche Formen manchmal exakt dieselbe Karte. Der erste Hinweis war nicht ausreichend.
Der zweite Hinweis (Der Inzidenzgraph):elf: Sie fügten eine zweite, detailliertere Karte hinzu, die in das „Innere“ der Form blickte.
Der finale Fingerabdruck: Durch die Kombination der Daten aus beiden Karten zu einer einzigen 64-Bit-Zahl (wie ein digitaler Hash-Code) erstellten sie einen perfekten Fingerabdruck. Wenn zwei Formen denselben Fingerabdruck haben, sind sie definitiv dieselbe. Wenn sie unterschiedliche Fingerabdrücke haben, sind sie definitiv verschieden.

4. Was befindet sich im Katalog?

Für jede der 3,6 Millionen einzigartigen Formen haben die Autoren Folgendes festgehalten:

Das Repräsentativum: Die einfachste, sauberste Version dieser Form (unter Verwendung der fewest möglichen Terme).
Der Symmetrie-Score: Wie viele Möglichkeiten es gibt, die Form zu drehen oder zu wenden, ohne sie zu verändern. Einige Formen sind sehr symmetrisch (leicht zu drehen), während die meisten einzigartig und starr sind.
Der Bauplan: Eine spezifische Art und Weise, diese Form unter Verwendung der minimalen Anzahl an „zerlegbaren“ Blöcken zu bauen.

5. Warum ist das wichtig? (Laut dem Papier)

Das Papier nennt einige spezifische Gründe, warum diese Liste nützlich ist, wobei es sich strikt an die jeweiligen Behauptungen hält:

Kodierungstheorie: Es hilft, Fehlerkorrekturverfahren (wie die bei der Datenübertragung verwendet werden) zu verbessern, indem das Verständnis der Struktur von „Reed-Muller-Codes“ vertieft wird.
Quantencomputing: Beim Bau fehlertoleranter Quantencomputer benötigen bestimmte Berechnungen „Toffoli-Gatter“. Die Autoren zeigen, dass die Komplexität dieser Berechnungen direkt mit dem „Rang“ dieser Formen verknüpft ist. Das Vorhandensein dieses Katalogs ermöglicht es Ingenieuren, die effizienteste Methode zum Bau dieser Schaltkreise nachzuschlagen.
Mathematische Geometrie: Es löst ein langjähriges Rätsel über die Geometrie von „Trivektoren“ im 10-dimensionalen Raum über dem Körper mit zwei Zahlen (0 und 1).

Zusammenfassung

Betrachten Sie dieses Papier als das Periodensystem für eine bestimmte Art von 10-variablen mathematischen Formen. Vor diesem Zeitpunkt wussten Wissenschaftler zwar, dass diese Formen existieren, hatten aber keine vollständige Liste. Jetzt verfügen sie über einen verifizierten, erschöpfenden Katalog mit über 3,6 Millionen Einträgen, lengkap mit „Fingerabdrücken“ zur Identifizierung und „Bauplänen“ für eine effiziente Konstruktion. Dies hilft Ingenieuren und Mathematikern, Probleme in der Kodierung und im Quantencomputing zu lösen, indem sie ein komplexes Suchproblem in eine einfache Nachschlagetabelle verwandeln.

Technische Zusammenfassung: Klassifizierung boolescher kubischer Formen in zehn Variablen

Problemstellung
Die vorliegende Arbeit befasst sich mit der Klassifizierung boolescher kubischer Formen in zehn Variablen über dem Körper $\mathbb{F}_2$ bis auf $GL(10, 2)$-Äquivalenz. Eine boolesche kubische Form ist ein Polynom $f(x) = \sum T_{ijk} x_i x_j x_k$ , wobei die Koeffizienten in $\mathbb{F}_2$ liegen und die Variablen die Eigenschaft $x_j^2 = x_j$ erfüllen. Zwei Formen sind äquivalent, wenn eine in die andere durch eine invertierbare lineare Änderung der Variablen transformiert werden kann, wobei konstante, lineare und quadratische Terme ignoriert werden. Diese Klassifizierung entspricht der Enumeration der nichtzerogenen Orbits des Raums $RM^*(3, 10)$ (der dritten Schicht der Reed–Muller-Codes) unter der Wirkung von $GL(10, 2)$. Während vollständige Klassifizierungen für Dimensionen $m \leq 9$ über verschiedenen Körpern existieren, wurde der Fall $m=10$ vor dieser Arbeit über keinem Feld behandelt.

Methodik
Die Autoren verwenden eine rangstratifizierte Enumerationsstrategie kombiniert mit einem neuartigen vollständigen Invarianten zur Identifizierung von Orbits.

Rang-stratifizierte Enumeration (BFS):
Die Enumeration erfolgt mittels eines „alternierenden Rangs“, definiert als die minimale Anzahl $r$ , sodass eine Form $f$ in eine Summe von $r$ dekomponierbaren Kubiken $u(x)v(x)w(x)$ zerlegt werden kann. Der Prozess beginnt mit der Nullform und fügt iterativ rang-1-Formen (dekomponierbare Kubiken) zu Repräsentanten der aktuellen Schicht hinzu. Dies generiert Kandidaten für die nächste Rangschicht. Der Suchraum wird signifikant reduziert, indem $GL(10, 2)$-Orbits auf jeder Stufe identifiziert werden, anstatt alle $2^{\binom{10}{3}}$ Formen zu enumerieren.
Konstruktion eines vollständigen Invarianten:
Um Orbits effizient zu unterscheiden, konstruieren die Autoren einen $GL(10, 2)$-Invarianten.

Orthogonalitätsgraph ( $G_f$ ): Basierend auf der Relation $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$ . Während die Isomorphieklasse von $G_f$ ein vollständiger Invariant für $m < 10$ ist, versagt sie für $m=10$ und hinterlässt 51 ungelöste Kollisionen.
Inzidenzgraph ( $B_f$ ): Ein bipartiter Graph, der aus den polaren bilinearen Formen abgeleitet ist, wobei Kanten Bildbeziehungen darstellen ( $u \to_f v$ ).
Lokale Statistiken: Anstatt eines vollständigen Graph-Isomorphie-Tests (der rechenintensiv ist), extrahieren die Autoren lokale Statistiken:
- $\mu_5(f)$ : Die Multimenge der geschlossenen Gänge der Länge 5 in $G_f$ .
- $\theta(f)$ : Eine spezifische Menge von Rechts-Grad-Ko-Grad-Zählungen aus $B_f$ .
- $\rho(f)$ : Ein Resolver basierend auf markierten Tripeln für das verbleibende einzelne Kollisionspaar ( $f_{381}, f_{382}$ ).
  Das Tripel $(\mu_5, \theta, \rho)$ wird in ein einzelnes 64-Bit-Wort komprimiert. Dieser Invariant wurde als kollisionsfrei über alle Repräsentanten hinweg verifiziert.

Verifizierung:
Die Vollständigkeit wird unabhängig durch zwei Methoden verifiziert:

Burnsides Lemma: Die Gesamtzahl der Orbits stimmt mit der theoretischen Summe überein, die aus der Gruppenwirkung abgeleitet wurde.
Orbit-Stabilisator-Identität: Die Summe von $|GL(10, 2)| / |St(f)|$ über alle Katalog-Repräsentanten ergibt die Gesamtzahl der nichtzerogenen Formen ( $2^{\binom{10}{3}} - 1$ ).

Zentrale Beiträge und Ergebnisse

Der Katalog: Die Arbeit präsentiert einen expliziten Katalog aller 3.691.560 nichtzerogenen $GL(10, 2)$-Orbits boolescher kubischer Formen in zehn Variablen.
Repräsentanten: Für jeden Orbit liefert der Katalog einen Repräsentanten mit einer minimierten Monom-Anzahl (maximal beobachtet: 17), der Ordnung seines Stabilisators in $GL(10, 2)$ und einer expliziten alternierenden Rang-Zerlegung.
Strukturelle Daten:
- Alternierender Rang: Der maximale alternierende Rang in Dimension 10 ist 7. Die Verteilung zeigt, dass Rang-6-Formen die dominante Schicht unter den nichtdegeneren Formen bilden.
- Stabilisatoren: Es gibt 143 unterschiedliche Stabilisator-Ordnungen. Die meisten Formen in $m=10$ besitzen einen trivialen Stabilisator.
- Dimensionalität: Von den gesamten Orbits weisen 348 nichttriviale Radikale auf (erbt aus niedrigeren effektiven Dimensionen), während 3.691.212 in Dimension 10 nichtdegener sind.
Performanz des Invarianten: Der 64-Bit-Invariant wird im Durchschnitt in 0,20 ms pro Form evaluiert, was signifikant schneller ist als direktes kanonisches Labeling (das bis zu 8,9 s für Kollisionsklassen dauerte).

Bedeutung und Anwendungen
Die Autoren positionieren diese Arbeit als fundamentale Ressource für mehrere Bereiche:

Kodierungstheorie: Der Katalog liefert die notwendigen Eingaben zur Berechnung von Koset-Gewicht-Enumeratoren und Abdeckungsradien für dritter Ordnung Reed–Muller-Codes $RM(3, 10)$ und verwandte Strukturen wie $RM^*(7, 10)$ . Er liefert zudem die für Sarwate-Typ-Rekursionen erforderliche Orbit-Indizierungsschicht für $RM(3, 11)$.
Quantencomputing: Die Klassifizierung bietet eine Nachschlagetabelle zur Optimierung von Quantenschaltkreisen. Da der alternierende Rang des kubischen Teils eines Phasenpolynoms die Toffoli-Gate-Anzahl kontrolliert, ermöglicht der Katalog den Ersatz von kubischen Fragmenten (bis zu 10 Variablen) durch optimale Zerlegungen, analog zum Subschaltkreis-Ersatz zur Minimierung des AND-Counts.
Mathematische Klassifizierung: Dies stellt die erste vollständige Klassifizierung alternierender trilinearer Formen in Dimension lautet 10 über irgendeinem Körper dar. Durch Polarisation wenden sich die Ergebnisse direkt auf die Geometrie von Tektoren und die Klassifizierung von Code-Loops via Assoziator-Formen an.

Die Autoren kommen zu dem Schluss, dass die Klassifizierung für $m=10$ vollständig ist, eine Erweiterung auf $m=11$ jedoch wesentlich effizientere Invarianten erfordern würde, da das Wachstum der Anzahl der Orbits exponentiell ist (geschätzt auf $\approx 6 \times 10^{13}$ ). Die Daten und der Code werden über Zenodo und GitHub zur Verfügung gestellt.