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

Resumen Técnico: La Distribución de Pesos del Código Reed–Muller de Tercer Orden de Longitud 2048

Planteamiento del Problema
Las distribuciones de peso de los códigos Reed–Muller $RM(r, m)$ es un problema clásico en la teoría de la codificación, aunque solo se conocen soluciones de forma cerrada para órdenes $r \leqslant 2$ y sus duales $r \geqslant m-3$. Para los códigos de tercer orden ($r=3$), las distribuciones completas se han establecido únicamente mediante computaciones individuales para longitudes de hasta 1024 ($RM(3, 10)$). Este artículo aborda la computación de la distribución de peso para el siguiente paso en esta cadena: el código Reed–Muller de tercer orden $RM(3, 11)$ de longitud 2048. Un objetivo secundario es determinar la no linealidad de segundo orden $d_2(f)$ para todas las formas cúbicas en diez variables, estableciendo así el radio de cobertura relativo $\rho_{2,3}(10)$ de $RM(2, 10)$ dentro de $RM(3, 10)$.

Metodología
La computación se basa en la recursión de tipo Sarwate, que expresa el enumerador de peso de $RM(3, m+1)$ como una suma de los cuadrados de los enumeradores de peso de los cosets de $f + RM(2, m)$ sobre todas las formas cúbicas $f$. Dado que el enumerador del coset depende únicamente de la órbita $GL(m, 2)$ de $f$, la suma se reduce a representantes de órbita ponderados por el tamaño de la órbita.

El cuello de botella principal para $m=10$ es la enorme cantidad de órbitas (3,691,560 órbitas no nulas) y el costo de evaluar un único enumerador de coset. La fórmula de división estándar de Brier y Langevin requiere una enumeración externa sobre $2^{36}$ formas cuadráticas homogéneas para $m=10$, lo cual es computacionalmente inviable para un pase de catálogo completo.

Para superar esto, los autores emplean un teorema estructural (Teorema 1): toda forma cúbica booleana no degenerada admite una restricción a un hiperplano no degenerado, con la excepción de una única órbita en cada dimensión impar. Para $m=10$ (una dimensión par), este teorema garantiza que cada órbita no degenerada tiene una restricción a un hiperplano que también es no degenerada. Esto permite que el enumerador del coset se compute mediante un espacio cociente de tamaño $2^{26}$ en lugar de $2^{36}$, ahorrando un factor de $2^{10}$ por órbita.

La evaluación de los enumeradores de peso de los cosets se realiza utilizando transformadas de Walsh–Hadamard rápidas sobre los cosets afines resultantes. El pase de catálogo completo requirió aproximadamente 65 años-CPU. Para verificar la precisión de los resultados y mejorar la eficiencia para los límites superiores, se desarrolló un heurístico de búsqueda local (combinando descenso voraz, movimientos $\tau$, búsqueda local iterada y búsqueda de haz). Este heurístico encuentra correcciones cuadráticas $q$ explícitas que minimizan $wt(f+q)$, proporcionando certificados para el radio de cobertura a una fracción del costo de la enumeración completa.

Contribuciones Clave y Resultados

1. Distribución de Peso de $RM(3, 11)$:
   El artículo presenta la distribución de peso completa de $RM(3, 11)$ (Tabla 1). Este resultado se ensambla sumando los cuadrados de los enumeradores de peso de los cosets de todas las 3,691,560 órbitas $GL(10, 2)$ no nulas de formas cúbicas booleanas en diez variables, más la contribución de la órbita cero.

2. No Linealidad de Segundo Orden y Radio de Cobertura Relativo:
   El exponente no nulo más bajo de cada enumerador de coset corresponde a la no linealidad de segundo orden $d_2(f)$. La computación determina que el valor máximo de $d_2(f)$ sobre todas las formas cúbicas en diez variables es 408.

• Teorema 3: El radio de cobertura relativo $\rho_{2,3}(10)$ de $RM(2, 10)$ en $RM(3, 10)$ es exactamente 408.
• Este máximo se alcanza en 179 órbitas distintas. Los representantes de estas órbitas y sus "números de beso" (el recuento de formas cuadráticas que alcanzan el peso mínimo) se enumeran en la Tabla 2.
• Todas las 179 formas extremales son no degeneradas.

3. Mejora del Límite Inferior del Radio de Cobertura:
   El resultado eleva el mejor límite inferior conocido para el radio de cobertura de $RM(2, 10)$ de 400 a 408. Las 179 órbitas sirven como testigos explícitos para este límite.

4. Conexión con el Rango Alternante:
   El artículo establece una relación entre $d_2(f)$ y el rango alternante ($arank$) de una forma cúbica. Utilizando un límite derivado (Teorema 4), los autores muestran que para cualquier forma con $d_2(f) = 408$, el rango alternante debe ser al menos 6. En $m=10$, el rango alternante máximo es 7. El análisis revela que 177 de las 179 órbitas extremales tienen $arank = 7$, mientras que 2 tienen $arank = 6$. Esto contrasta con dimensiones menores ($m \leqslant 9$), donde las formas extremales estaban forzadas a tener el rango alternante máximo posible para esa dimensión.

5. Búsqueda Heurística y Límites Cocúbicos:
   El heurístico de búsqueda local reprodujo con éxito el límite $\rho_{2,3}(10) \leqslant 408$ a aproximadamente una milésima parte del costo de la enumeración completa. Aplicado a formas de grado siete, este heurístico mejoró el límite superior sobre el radio de cobertura relativo de $RM(6, 10)$ en $RM(7, 10)$ de 50 a 32 (Lema 2).

Significado
El artículo reclama su significancia principalmente al resolver la distribución de peso para $RM(3, 11)$, extendiendo la cadena conocida de códigos de tercer orden. El teorema estructural respecto a las restricciones a hiperplanos no degenerados se presenta como un habilitador crítico, haciendo que el pase de catálogo completo sea factible donde los métodos anteriores estaban "fuera de alcance".

La determinación de $\rho_{2,3}(10) = 408$ es significativa para la literatura del radio de cobertura, actualizando el mejor límite inferior conocido para $RM(2, 10)$. Además, el análisis de las órbitas extremales proporciona información estructural: el cambio de las formas de traza monomiales (que anteriormente ostentaban el récord de 400) hacia los polinomios de traza binomial y la concentración de las formas extremales en el rango alternante máximo sugieren nuevas direcciones para la búsqueda de formas de alta no linealidad en dimensiones superiores ($m > 10$). Los autores señalan que los datos de enumeración y el código de referencia se ponen a disposición para facilitar la investigación adicional en teoría de la codificación y el análisis de funciones booleanas.