Classification of Boolean Cubic Forms in Ten Variables

Technische Samenvatting: Classificatie van Booleaanse Cubische Vormen in Tien Variabelen

Probleemstelling
Het artikel behandelt de classificatie van Booleaanse cubische vormen in tien variabelen over het lichaam $\mathbb{F}_2$ tot $GL(10, 2)$-equivalentie. Een Booleaanse cubische vorm is een polynoom $f(x) = \sum T_{ijk} x_i x_j x_k$ waarbij de coëfficiënten in $\mathbb{F}_2$ liggen en de variabelen voldoen aan $x_j^2 = x_j$. Twee vormen zijn equivalent als de ene naar de andere getransformeerd kan worden via een inverteerbare lineaire verandering van variabelen, waarbij constante, lineaire en kwadratische termen genegeerd worden. Deze classificatie komt overeen met het enumereren van de niet-nul banen van de ruimte $RM^*(3, 10)$ (de derde laag van Reed–Muller-codes) onder de werking van $GL(10, 2)$. Hoewel volledige classificaties bestaan voor dimensies $m \leq 9$ over diverse lichamen, was de casus $m=10$ voorheen niet behandeld over enig lichaam.

Methodologie
De auteurs hanteren een rang-gestratificeerde enumeratiestrategie gecombineerd met een nieuw volledig invariant voor baanidentificatie.

1. Rang-gestratificeerde Enumeratie (BFS):
   De enumeratie verloopt via "alternerende rang", gedefinieerd als het minimale aantal $r$ waarvoor een vorm $f$ gedecomposeerd kan worden in een som van $r$ decomponeerbare cubische termen $u(x)v(x)w(x)$. Het proces begint met de nulvorm en voegt iteratief rang-1 vormen (de decomposeerbare cubische termen) toe aan representanten van de huidige laag. Dit genereert kandidaten voor de volgende rang-laag. De zoekruimte wordt aanzienlijk verkleind door $GL(10, 2)$-banen te identificeren in elke stap, in plaats van alle $2^{\binom{10}{3}}$ vormen te enumereren.

2. Constructie van een Volledig Invariant:
   Om banen efficiënt te onderscheiden, construeren de auteurs een $GL(10, 2)$-invariant.

   • Orthogonaliteitsgraaf ($G_f$): Gebaseerd op de relatie $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$. Hoewel de isomorfieklasse van $G_f$ een volledig invariant is voor $m < 10$, faalt dit voor $m=10$, wat leidt tot 51 onopgeloste botsingen (collisions).
   • Incidentie-graaf ($B_f$): Een bipartiete graaf afgeleid van de polaire bilineaire vormen, waarbij randen afbeeldingrelaties vertegenwoordigen ($u \to_f v$).
   • Lokale Statistieken: In plaats van volledige graaf-isomorfietesten (die computationeel duur zijn), extraheren de auteurs lokale statistieken:
     • $\mu_5(f)$: De multiset van gesloten wandelingen van lengte 5 in $G_f$.
     • $\theta(f)$: Een specifieke set van rechts-graad-codegraad tellingen uit $B_f$.
     • $\rho(f)$: Een resolver gebaseerd op gemarkeerde triples voor het enkele resterende botsingspaar ($f_{381}, f_{382}$).
   • De triple $(\mu_5, \theta, \rho)$ wordt gecomprimeerd tot een enkele 64-bits woord. Dit invariant is geverifieerd als botsingsvrij over alle representanten.

3. Verificatie:
   Volledigheid wordt onafhankelijk geverifieerd door twee methoden:

   • Burnside's Lemma: De totale telling van banen komt overeen met de theoretische som afgeleid van de groepswerking.
   • Orbit-Stabilizer Identiteit: De som van $|GL(10, 2)| / |St(f)|$ over alle catalogus-representanten is gelijk aan het totaal aantal niet-nul vormen ($2^{\binom{10}{3}} - 1$).

Belangrijkste Bijdragen en Resultaten

• De Catalogus: Het artikel presenteert een expliciete catalogus van alle 3.691.560 niet-nul $GL(10, 2)$-banen van Booleaanse cubische vormen in tien variabelen.
• Representanten: Voor elke baan levert de catalogus een representant met een geminimaliseerd aantal monomialen (maximaal geobserveerd is 17), de orde van zijn stabilizer in $GL(10, 2)$, en een expliciete alternerende rang-decompositie.
• Structurele Data:
  • Alternerende Rang: De maximale alternerende rang in dimensie 10 is 7. De distributie laat zien dat rang 6 vormen de dominante laag vormen onder niet-degeneratieve vormen.
  • Stabilizers: Er zijn 143 verschillende stabilizer-ordes. De meeste vormen in $m=10$ hebben een triviale stabilizer.
  • Dimensionaliteit: Van de totale banen hebben 348 niet-triviale radicalen (geërfd van lagere effectieve dimensies), terwijl 3.691.212 niet-degeneratief zijn in dimensie 10.
• Prestaties van het Invariant: Het 64-bits invariant evalueert in gemiddeld 0,20 ms per vorm, wat aanzienlijk sneller is dan directe canonieke labeling (die tot 8,9 s duurde voor botsingsklassen).

Betekenis en Toepassingen
De auteurs positioneren dit werk als een fundamentele bron voor verschillende gebieden:

• Coderingstheorie: De catalogus levert de noodzakelijke input voor het berekenen van coset weight enumerators en de covering radii voor derde-orde Reed–Muller-codes $RM(3, 10)$ en gerelateerde structuren zoals $RM^*(7, 10)$. Het levert ook de baan-indexering laag die vereist is voor Sarwate-type recursies voor $RM(3, 11)$.
• Quantum Computing: De classificatie biedt een lookup-tabel voor het optimaliseren van quantumcircuits. Omdat de alternerende rang van het cubische deel van een fase-polynoom het Toffoli-gate aantal bepaelt, maakt de catalogus het mogelijk om cubische fragmenten (tot 10 variabelen) te vervangen door optimale decomposities, analoog aan subcircuit-vervanging voor AND-count minimalisatie.
• Wiskundige Classificatie: Dit vormt de eerste volledige classificatie van alternerende trilineaire vormen in dimensie 10 over een willekeurig lichaam. Door polarisatie zijn de resultaten direct toepasbaar op de geometrie van trivectoren en de classificatie van code-loops via associator-vormen.

Het artikel concludeert dat hoewel de classificatie compleet is voor $m=10$, het uitbreiden hiervan naar $m=11$ aanzienlijk efficiëntere invarianten zou vereisen vanwege de exponentiële groei in het aantal banen (geschat op $\approx 6 \times 10^{13}$). De data en code zijn beschikbaar via Zenodo en GitHub.