Classification of Boolean Cubic Forms in Ten Variables

Sintesi Tecnica: Classificazione delle Forme Cubiche Booleane in Dieci Variabili

Enunciato del Problema
Il documento affronta la classificazione delle forme cubiche booleane in dieci variabili in $\mathbb{F}_2$ fino all'equivalenza $GL(10, 2)$. Una forma cubica booleana è un polinomio $f(x) = \sum T_{ijk} x_i x_j x_k$ dove i coefficienti sono in $\mathbb{F}_2$ e le variabili soddisfano $x_j^2 = x_j$. Due forme sono equivalenti se una può essere trasformata nell'altra tramite un cambiamento di variabili lineare invertibile, ignorando i termini costanti, lineari e quadratici. Questa classificazione corrisponde all'enumerazione degli orbite non nulle dello spazio $RM^*(3, 10)$ (lo strato terzo dei codici di Reed–Muller) sotto l'azione di $GL(10, 2)$. Mentre esistono classificazioni complete per dimensioni $m \leq 9$ su vari campi, il caso $m=10$ non era stato affrontato su alcun campo prima di questo lavoro.

Metodologia
Gli autori impiegano una strategia di enumerazione stratificata per rango combinata con un nuovo invariante completo per l'identificazione delle orbite.

1. Enumerazione Stratificata per Rango (BFS):
   L'enumerazione procede per "rango alternato", definito come il numero minimo $r$ tale che una forma $f$ possa essere decomposta in una somma di $r$ cubiche decomponibili $u(x)v(x)w(x)$. Il processo parte dalla forma nulla e aggiunge iterativamente forme di rango-1 (cubiche decomponibili) ai rappresentanti dell'attuale strato. Questo genera candidati per il successivo strato di rango. Lo spazio di ricerca è significativamente ridotto identificando le orbite $GL(10, 2)$ ad ogni passaggio piuttosto che enumerando tutte le $2^{\binom{10}{3}}$ forme.

2. Costruzione dell'Invariante Completo:
   Per distinguere efficientemente tra le orbite, gli autori costruiscono un invariante $GL(10, 2)$.

   • Grafo di Ortogonalità ($G_f$): Basato sulla relazione $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$. Sebbene la classe di isomorfismo di $G_f$ sia un invariante completo per $m < 10$, essa fallisce per $m=10$, lasciando 51 collisioni irrisolte.
   • Grafo di Incidenza ($B_f$): Un grafo bipartito derivato dalle forme bilineari polari, dove gli archi rappresentano le relazioni di immagine ($u \to_f v$).
   • Statistiche Locali: Invece del test completo di isomorfismo di grafi (computazionalmente costoso), gli autori estraggono statistiche locali:
     • $\mu_5(f)$: Il multinsieme dei cammini chiusi di lunghezza 5 in $G_f$.
     • $\theta(f)$: Un insieme specifico di conteggi grado-codegrado destri da $B_f$.
     • $\rho(f)$: Un risolutore basato su triple marcate per la singola coppia di collisione rimanente ($f_{381}, f_{382}$).
   • La terna $(\mu_5, \theta, \rho)$ è compressa in una singola parola a 64 bit. Questo invariante è verificato come privo di collisioni tra tutti i rappresentanti.

3. Verifica:
   La completezza è verificata indipendentemente tramite due metodi:

   • Lemma di Burnside: Il conteggio totale delle orbite corrisponde alla somma teorica derivata dall'azione del gruppo.
   • Identità Stabilizzatore-Orbita: La somma di $|GL(10, 2)| / |St(f)|$ su tutti i rappresentanti del catalogo è uguale al numero totale di forme non nulle ($2^{\binom{10}{3}} - 1$).

Contributi Chiave e Risultati

• Il Catalogo: Il documento presenta un catalogo esplicito di tutte le 3.691.560 orbite $GL(10, 2)$ non nulle di forme cubiche booleane in dieci variabili.
• Rappresentanti: Per ogni orbita, il catalogo fornisce un rappresentante con un conteggio di monomi minimizzato (massimo osservato: 17), l'ordine del suo stabilizzatore in $GL(10, 2)$ e una decomposizione esplicita del rango alternato.
• Dati Strutturali:
  • Rango Alternato: Il rango alternato massimo in dimensione 10 è 7. La distribuzione mostra che le forme di rango 6 costituiscono lo strato dominante tra le forme non degenerate.
  • Stabilizzatori: Esistono 143 ordini distinti di stabilizzatore. La maggior parte delle forme in $m=10$ ha uno stabilizzatore banale.
  • Dimensionalità: Di tutte le orbite, 348 hanno radicali non banali (ereditati da dimensioni effettive inferiori), mentre 3.691.212 sono non degenerate in dimensione 10.
• Prestazioni dell'Invariante: L'invariante a 64 bit viene valutato in una media di 0,20 ms per forma, significativamente più veloce della marcatura canonica diretta (che richiedeva fino a 8,9 s per le classi di collisione).

Significato e Applicazioni
Gli autori pongono questo lavoro come una risorsa fondamentale per diverse aree:

• Teoria dei Codici: Il catalogo fornisce l'input necessario per calcolare i pesi dei coset e i raggi di copertura per i codici di Reed–Muller di terzo ordine $RM(3, 10)$ e strutture correlate come $RM^*(7, 10)$. Fornisce inoltre lo strato di indicizzazione delle orbite richiesto per le ricorsioni di tipo Sarwate per $RM(3, 11)$.
• Informatica Quantistica: La classificazione offre una tabella di consultazione per ottimizzare i circuiti quantistici. Poiché il rango alternato della parte cubica di un polinomio di fase controlla il conteggio delle porte Toffoli, il catalogo permette di sostituire frammenti cubici (fino a 10 variabili) con decomposizioni ottimali, analogamente alla sostituzione di sottocircuiti per la minimizzazione del conteggio AND.
• Classificazione Matematica: Questo costituisce la prima classificazione completa di forme trilineari alternate in dimensione 10 su qualsiasi campo. Per polarizzazione, i risultati si applicano direttamente alla geometria dei trivettori e alla classificazione dei loop di codice tramite forme associatrici.

Il documento conclude che, sebbene la classificazione sia completa per $m=10$, estenderla a $m=11$ richiederebbe invarianti sostanzialmente più efficienti a causa della crescita esponenziale del numero di orbite (stimato a $\approx 6 \times 10^{13}$). I dati e il codice sono resi disponibili tramite Zenodo e GitHub.