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

Résumé technique : La distribution de poids du code de Reed–Muller d'ordre 3 de longueur 2048

Énoncé du problème
Les distributions de poids des codes de Reed–Muller $RM(r, m)$ constituent un problème classique en théorie des codes, pourtant des solutions sous forme fermée ne sont connues que pour les ordres $r \leqslant 2$ et leurs duals $r \geqslant m-3$. Pour les codes d'ordre 3 ($r=3$), les distributions complètes n'ont été établies que par des calculs individuels pour des longueurs allant jusqu'à 1024 ($RM(3, 10)$). Cet article traite du calcul de la distribution de poids pour l'étape suivante de cette chaîne : le code de Reed–Muller d'ordre 3, $RM(3, 11)$, de longueur 2048. Un objectif secondaire est de déterminer la non-linéarité de second ordre $d_2(f)$ pour toutes les formes cubiques en dix variables, établissant ainsi le rayon de couverture relatif $\rho_{2,3}(10)$ de $RM(2, 10)$ dans $RM(3, 10)$.

Méthodologie
Le calcul repose sur la récursion de type Sarwate, qui exprime l'énumérateur de poids de $RM(3, m+1)$ comme une somme des carrés des énumérateurs de poids de cosets de $f + RM(2, m)$ sur toutes les formes cubiques $f$. Puisque l'énumérateur de coset dépend uniquement de l'orbite de $f$ sous $GL(m, 2)$, la somme se réduit aux représentants d'orbites pondérés par la taille des orbites.

Le goulot d'étranglement principal pour $m=10$ est le nombre colossal d'orbites (3 691 560 orbites non nulles) et le coût d'évaluation d'un seul énumérateur de coset. La formule de division standard de Brier et Langevin nécessite une énumération extérieure sur $2^{36}$ formes quadratiques homogènes pour $m=10$, ce qui est informatiquement irréalisable pour un passage complet du catalogue.

Pour surmonter cela, les auteurs utilisent un théorème structurel (Théorème 1) : toute forme cubique booléenne non dégénérée admet une restriction à un hyperplan non dégénéré, à l'exception d'une orbite unique dans chaque dimension impaire. Pour $m=10$ (une dimension paire), ce théorème garantit que chaque orbite non dégénérée possède une restriction à un hyperplan qui est également non dégénérée. Cela permet de calculer l'énumérateur de coset via un espace quotient de taille $2^{26}$ plutôt que $2^{36}$, économisant un facteur de $2^{10}$ par orbite.

L'évaluation des énumérateurs de poids de cosets est effectuée à l'aide de transformées de Walsh–Hadamard rapides sur les cosets affines résultants. Le passage complet du catalogue a nécessité environ 65 années-CPU. Pour vérifier la précision des résultats et améliorer l'efficacité des bornes supérieures, une heuristique de recherche locale (combinant descente gloutonne, mouvements $\tau$, recherche locale itérée et recherche en faisceau/beam search) a été développée. Cette heuristique trouve des corrections quadratiques $q$ explicites minimisant $wt(f+q)$, fournissant des certificats pour le rayon de couverture à une fraction du coût de l'énumération complète.

Contributions clés et résultats

1. Distribution de poids de $RM(3, 11)$ :
   L'article présente la distribution de poids complète de $RM(3, 11)$ (Tableau 1). Ce résultat est assemblé en sommant les carrés des énumérateurs de poids de coset de tous les 3 691 560 orbites $GL(10, 2)$ non nulles des formes cubiques booléennes en dix variables, plus la contribution de l'orbite nulle.

2. Non-linéarité de second ordre et rayon de couverture relatif :
   L'exposant non nul le plus bas de chaque énumérateur de coset correspond à la non-linéarité de second ordre $d_2(f)$. Le calcul détermine que la valeur maximale de $d_2(f)$ sur toutes les formes cubiques en dix variables est 408.

• Théorème 3 : Le rayon de couverture relatif $\rho_{2,3}(10)$ de $RM(2, 10)$ dans $RM(3, 10)$ est exactement 408.
• Ce maximum est atteint sur 179 orbites distinctes. Les représentants de ces orbites et leurs « nombres de contact » (le décompte des formes quadratiques atteignant le poids minimum) sont listés dans le Tableau 2.
• Toutes les 179 formes extrémales sont non dégénérées.

3. Amélioration de la borne inférieure du rayon de couverture :
   Le résultat relève la meilleure borne inférieure connue du rayon de couverture de $RM(2, 10)$ de 400 à 408. Les 179 orbites servent de témoins explicites pour cette borne.

4. Lien avec le rang alterné :
   L'article établit une relation entre $d_2(f)$ et le rang alterné ($arank$) d'une forme cubique. En utilisant une borne dérivée (Théorème 4), les auteurs montrent que pour toute forme ayant $d_2(f) = 408$, le rang alterné doit être au moins de 6. Pour $m=10$, le rang alterné maximal est 7. L'analyse révèle que 177 des 179 orbites extrémales ont un $arank = 7$, tandis que 2 ont un $arank = 6$. Cela contraste avec les dimensions inférieures ($m \leqslant 9$), où les formes extrémales étaient contraintes d'avoir le rang alterné maximal possible pour cette dimension.

5. Recherche heuristique et bornes cocubiques :
   L'heuristique de recherche locale a réussi à reproduire la borne $\rho_{2,3}(10) \leqslant 408$ à environ un millième du coût de l'énumération complète. Appliquée aux formes de degré sept, cette heuristique a amélioré la borne supérieure sur le rayon de couverture relatif de $RM(6, 10)$ dans $RM(7, 10)$ de 50 à 32 (Lemme 2).

Signification
L'article revendique sa signification principalement par la résolution de la distribution de poids pour $RM(3, 11)$, prolongeant la chaîne connue des codes de troisième ordre. Le théorème structurel concernant les restrictions à des hyperplans non dégénérés est présenté comme un catalyseur critique, rendant le passage complet du catalogue réalisable là où les méthodes précédentes étaient « hors de portée ».

La détermination de $\rho_{2,3}(10) = 408$ est significative pour la littérature sur le rayon de couverture, mettant à jour la meilleure borne inférieure connue pour $RM(2, 10)$. De plus, l'analyse des orbites extrémales fournit des aperçus structurels : le passage des formes de trace monomiales (qui détenaient auparavant le record de 400) aux polynômes de trace binomiaux et la concentration des formes extrémales au rang alterné maximal suggèrent de nouvelles directions pour la recherche de formes de haute non-linéarité dans des dimensions plus élevées ($m > 10$). Les auteurs notent que les données d'énumération et le code de référence sont mis à disposition pour faciliter la recherche ultérieure en théorie des codes et en analyse de fonctions booléennes.