The Weight Distribution of the Third-Order Reed-Muller Code of Length 2048

Sintesi Tecnica: La Distribuzione dei Pesi del Codice di Reed–Muller di Terzo Ordine di Lunghezza 2048

Enunciato del Problema
Le distribuzioni dei pesi dei codici di Reed–Muller $RM(r, m)$ rappresentano un problema classico nella teoria della codifica, tuttavia soluzioni in forma chiusa sono note solo per ordini $r \leqslant 2$ e i loro duali $r \geqslant m-3$. Per i codici di terzo ordine ($r=3$), le distribuzioni complete sono state stabilite solo attraverso computazioni individuali per lunghezze fino a 1024 ($RM(3, 10)$). Questo articolo affronta il calcolo della distribuzione dei pesi per il passo successivo in questa catena, ovvero il codice di Reed–Muller di terzo ordine $RM(3, 11)$ di lunghezza 2048. Un obiettivo secondario è determinare la non linearità del secondo ordine $d_2(f)$ per tutte le forme cubiche in dieci variabili, stabilendo così il raggio di copertura relativo $\rho_{2,3}(10)$ di $RM(2, 10)$ all'interno di $RM(3, 10)$.

Metodologia
Il calcolo si basa sulla ricorsione di tipo Sarwate, che esprime l'enumeratore dei pesi di $RM(3, m+1)$ come una somma dei quadrati degli enumeratori dei pesi dei cosetti di $f + RM(2, m)$ su tutte le forme cubiche $f$. Poiché l'enumeratore del cosetto dipende solo dall'orbita $GL(m, 2)$ di $f$, la somma si riduce ai rappresentanti delle orbite ponderati per la dimensione delle orbite stesse.

Il collo di bottiglia primario per $m=10$ è l'enorme numero di orbite (3.691.560 orbite non nulle) e il costo di valutazione di un singolo enumeratore di cosetto. La standard formula di scomposizione di Brier e Langevin richiede un enumerazione esterna su $2^{36}$ forme quadratiche omogenee per $m=10$, il che è computazionalmente impraticabile per un passaggio completo del catalogo.

Per superare questo ostacolo, gli autori utilizzano un teorema strutturale (Teorema 1): ogni forma cubica booleana non degenere ammette una restrizione su un iperpiano non degenere, con l'eccezione di un'unica orbita in ogni dimensione dispari. Per $m=10$ (una dimensione pari), questo teorema garantisce che ogni orbita non degenere abbia una restrizione su un iperpiano che sia anch'essa non degenere. Ciò consente di calcolare l'enumeratore del cosetto tramite uno spazio quoziente di dimensione $2^{26}$ anziché $2^{36}$, risparmiando un fattore di $2^{10}$ per ogni orbita.

La valutazione degli enumeratori dei pesi dei cosetti viene eseguita utilizzando trasformate rapide di Walsh–Hadamard sugli affini cosetti risultanti. L'intero passaggio del catalogo ha richiesto circa 65 anni di CPU. Per verificare la precisione dei risultati e migliorare l'efficienza per i limiti superiori, è stata sviluppata un'euristica di ricerca locale (che combina discesa greedy, $\tau$-moves, ricerca locale iterata e beam search). Questa euristica trova correzioni quadratiche esplicite $q$ che minimizzano $wt(f+q)$, fornendo certificati per il raggio di copertura a una frazione del costo della piena enumerazione.

Contributi Chiave e Risultati

1. Distribuzione dei Pesi di $RM(3, 11)$:
   Il documento presenta la distribuzione completa dei pesi di $RM(3, 11)$ (Tabella 1). Questo risultato è assemblato sommando i quadrati degli enumeratori dei pesi dei cosetti di tutte le 3.691.560 orbite $GL(10, 2)$ non nulle di forme cubiche booleane in dieci variabili, più il contributo dell'orbita nulla.

2. Non Linearità del Secondo Ordine e Raggio di Copertura Relativo:
   L'esponente non nullo più basso di ogni enumeratore del cosetto corrisponde alla non linearità del secondo ordine $d_2(f)$. Il calcolo determina che il valore massimo di $d_2(f)$ su tutte le forme cubiche in dieci variabili è 408.

• Teorema 3: Il raggio di copertura relativo $\rho_{2,3}(10)$ di $RM(2, 10)$ in $RM(3, 10)$ è esattamente 408.
• Questo massimo è raggiunto da 179 orbite distinte. I rappresentanti di queste orbite e i loro "numeri di kissing" (il conteggio delle forme quadratiche che raggiungono il peso minimo) sono elencati nella Tabella 2.
• Tutte le 179 forme estreme sono non degenerate.

3. Miglioramento del Limite Inferiore sul Raggio di Copertura:
   Il risultato innalza il miglior limite inferiore noto sul raggio di copertura di $RM(2, 10)$ da 400 a 408. Le 179 orbite fungono da testimoni espliciti per questo limite.

4. Connessione con il Rango Alternante:
   Il documento stabilisce una relazione tra $d_2(f)$ e il rango alternante ($arank$) di una forma cubica. Utilizzando un limite derivato (Teorema 4), gli autori dimostrano che per qualsiasi forma con $d_2(f) = 408$, il rango alternante deve essere almeno 6. In $m=10$, il rango alternante massimo è 7. L'analisi rivela che 177 delle 179 orbite estreme hanno $arank = 7$, mentre 2 hanno $arank = 6$. Ciò contrasta con le dimensioni inferiori ($m \leqslant 9$), dove le forme estreme erano costrette ad avere il massimo rango alternante possibile per quella dimensione.

5. Ricerca Euristica e Limiti Cocubici:
   L'euristica di ricerca locale ha riprodotto con successo il limite $\rho_{2,3}(10) \leqslant 408$ a circa un millesimo del costo della piena enumerazione. Applicata alle forme di grado sette, questa euristica ha migliorato il limite superiore sul raggio di copertura relativo di $RM(6, 10)$ in $RM(7, 10)$ da 50 a 32 (Lemma 2).

Significatività
L'articolo rivendica significatività principalmente risolvendo la distribuzione dei pesi per $RM(3, 11)$, estendendo la nota catena di codici di terzo ordine. Il teorema strutturale riguardante le restrizioni su iperpiani non degeneri è presentato come un abilitatore critico, rendendo fattibile il passaggio completo del catalogo laddove i metodi precedenti erano "fuori portata".

La determinazione di $\rho_{2,3}(10) = 408$ è significativa per la letteratura sul raggio di copertura, aggiornando il miglior limite inferiore noto per $RM(2, 10)$. Inoltre, l'analisi delle orbite estreme fornisce intuizioni strutturali: lo spostamento dalle forme traccia monomiali (che precedentemente detenevano il record a 400) verso i polinomi traccia binomiali e la concentrazione delle forme estreme al massimo rango alternante suggeriscono nuove direzioni per la ricerca di forme ad alta non linearità in dimensioni superiori ($m > 10$). Gli autori segnalano che i dati di enumerazione e il codice di riferimento sono resi disponibili per facilitare ulteriori ricerche nella teoria della codifica e nell'analisi delle funzioni booleane.