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

Technische Samenvatting: De Gewichtsverdeling van de Derde-Orde Reed–Muller-code van Lengte 2048

Probleemstelling
De gewichtsverdelingen van Reed–Muller-codes $RM(r, m)$ vormen een klassiek probleem in de coderingstheorie, maar gesloten vormoplossingen zijn alleen bekend voor orden $r \leqslant 2$ en hun dualen $r \geqslant m-3$. Voor derde-orde codes ($r=3$) zijn volledige verdelingen pas vastgesteld via individuele berekeningen voor lengtes tot 1024 ($RM(3, 10)$). Dit artikel behandelt de berekening van de gewichtsverdeling voor de volgende stap in deze keten: de derde-orde Reed–Muller-code $RM(3, 11)$ van lengte 2048. Een secundair doel is het bepalen van de tweede-orde nonlineariteit $d_2(f)$ voor alle kubische vormen in tien variabelen, waarmee de relatieve dekkingsstraal $\rho_{2,3}(10)$ van $RM(2, 10)$ binnen $RM(3, 10)$ wordt vastgesteld.

Methodologie
De berekening berust op de Sarwate-type recursie, die de gewichtsenumerator van $RM(3, m+1)$ uitdrukt als een som van gekwadrateerde coset-gewichtsenumeratoren van $f + RM(2, m)$ over alle kubische vormen $f$. Omdat de coset-enumerator alleen afhangt van de $GL(m, 2)$-baan van $f$, reduceert de som tot baanrepresentanten gewogen door baanafmetingen.

De primaire flessenhals voor $m=10$ is het enorme aantal banen (3.691.560 niet-nul banen) en de kosten van het evalueren van een enkele coset-enumerator. De standaard splitsformule van Brier en Langevin vereist een uiterlijke enumeratie over $2^{36}$ homogene kwadratische vormen voor $m=10$, wat computationeel onhaalbaar is voor een volledige catalogus-pass.

Om dit te overwinnen, maken de auteurs gebruik van een structurele stelling (Stelling 1): elke niet-degeneratieve Booleaanse kubische vorm heeft een niet-degeneratieve hypervlakrestrictie, met uitzondering van een enkele baan in elke oneven dimensie. Voor $m=10$ (een even dimensie) garandeert deze stelling dat elke niet-degeneratieve baan een restrictie heeft naar een hypervlak dat ook niet-degeneratief is. Dit maakt het mogelijk om de coset-enumerator te berekenen via een quotientruimte van grootte $2^{26}$ in plaats van $2^{36}$, wat een factor $2^{10}$ bespaart per baan.

De evaluatie van de coset-gewichtsenumeratoren wordt uitgevoerd met snelle Walsh–Hadamard-transformaties op de resulterende affiene cosets. De volledige catalogus-pass vereiste ongeveer 65 CPU-jaren. Om de nauwkeurigheid van de resultaten te verifiëren en de efficiëntie voor bovengrenzen te verbeteren, is een lokale zoekheuristiek ontwikkeld (combinatie van greedy descent, $\tau$-moves, iterated local search en beam search). Deze heuristiek vindt expliciete kwadratische correcties $q$ die $wt(f+q)$ minimaliseren, waardoor certificaten voor de dekkingsstraal worden geleverd tegen een fractie van de kosten van de volledige enumeratie.

Belangrijkste Bijdragen en Resultaten

1. Gewichtsverdeling van $RM(3, 11)$:
   Het artikel presenteert de volledige gewichtsverdeling van $RM(3, 11)$ (Tabel 1). Dit resultaat wordt samengesteld door de gekwadrateerde coset-gewichtsenumeratoren van alle 3.691.560 niet-nul $GL(10, 2)$-banen van Booleaanse kubische vormen in tien variabelen op te tellen, plus de bijdrage van de nul-baan.

2. Tweede-orde Nonlineariteit en Relatieve Dekkingsstraal:
   De laagste niet-nul exponent van elke coset-enumerator komt overeen met de tweede-orde nonlineariteit $d_2(f)$. De berekening bepaalt dat de maximale waarde van $d_2(f)$ over alle kubische vormen in tien variabelen 408 is.

• Stelling 3: De relatieve dekkingsstraal $\rho_{2,3}(10)$ van $RM(2, 10)$ in $RM(3, 10)$ is exact 408.
• Deze maximumwaarde wordt bereikt door 179 verschillende banen. De representanten van deze banen en hun "kissing numbers" (het aantal kwadratische vormen dat het minimumgewicht bereikt) staan vermeld in Tabel 2.
• Alle 179 extreme vormen zijn niet-degeneratief.

3. Verbeterde Ondergrens op de Dekkingsstraal:
   Het resultaat verhoogt de best bekende ondergrens op de dekkingsstraal van $RM(2, 10)$ van 400 naar 408. De 179 banen dienen als expliciete getuigen voor deze grens.

4. Verbinding met Alternerende Rang:
   Het artikel legt een relatie vast tussen $d_2(f)$ en de alternerende rang ($arank$) van een kubische vorm. Met behulp van een afgeleide grens (Stelling 4) tonen de auteurs aan dat voor elke vorm met $d_2(f) = 408$, de alternerende rang ten minste 6 moet zijn. In $m=10$ is de maximale alternerende rang 7. De analyse laat zien dat 177 van de 179 extreme banen een $arank = 7$ hebben, terwijl 2 een $arank = 6$ hebben. Dit staat in contrast met lagere dimensies ($m \leqslant 9$), waar de extreme vormen gedwongen waren de maximale mogelijke alternerende rang voor die dimensie te hebben.

5. Heuristische Zoekopdracht en Cocubische Grenzen:
   De lokale zoekheuristiek slaagde erin de grens $\rho_{2,3}(10) \leqslant 408$ te reproduceren tegen ongeveer één-duizendste van de kosten van de volledige enumeratie. Toegepast op graad-zeven vormen, verbeterde deze heuristiek de bovengrens op de relatieve dekkingsstraal van $RM(6, 10)$ in $RM(7, 10)$ van 50 naar 32 (Lemma 2).

Betekenis
Het artikel claimt betekenis primair door de gewichtsverdeling voor $RM(3, 11)$ op te lossen, waarmee de bekende keten van derde-orde codes wordt uitgebreid. De structurele stelling betreffende niet-degeneratieve hypervlakrestricties wordt gepresenteerd als een cruciale facilitator, die de volledige catalogus-pass mogelijk maakt waar voorheen methoden "onbereikbaar" waren.

De bepaling van $\rho_{2,3}(10) = 408$ is significant voor de literatuur over de dekkingsstraal, aangezien het de best bekende ondergrens voor $RM(2, 10)$ actualiseert. Bovendien biedt de analyse van de extreme banen structurele inzichten: de verschuiving van monomiale trace-vormen (die eerder het record van 400 vasthielden) naar binomiale trace-polynomen en de concentratie van extreme vormen bij de maximale alternerende rang suggereren nieuwe richtingen voor het zoeken naar hoog-nonlineariteit vormen in hogere dimensies ($m > 10$). De auteurs merken op dat de enumeratiegegevens en de referentiecode beschikbaar worden gesteld om verder onderzoek in de coderingstheorie en de analyse van Booleaanse functies te faciliteren.