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

Resumo Técnico: A Distribuição de Pesos do Código Reed–Muller de Terceira Ordem de Comprimento 2048

Enunciado do Problema
As distribuições de peso dos códigos Reed–Muller $RM(r, m)$ são um problema clássico na teoria de códigos, mas soluções em forma fechada são conhecidas apenas para ordens $r \leqslant 2$ e seus duais $r \geqslant m-3$. Para códigos de terceira ordem ($r=3$), distribuições completas foram estabelecidas apenas através de computações individuais para comprimentos até 1024 ($RM(3, 10)$). Este artigo aborda o cálculo da distribuição de peso para o próximo passo nesta cadeia: o código Reed–Muller de terceira ordem $RM(3, 11)$ de comprimento 2048. Um objetivo secundário é determinar a não linearidade de segunda ordem $d_2(f)$ para todas as formas cúbicas em dez variáveis, estabelecendo assim o raio de cobertura relativo $\rho_{2,3}(10)$ de $RM(2, 10)$ dentro de $RM(3, 10)$.

Metodologia
O cálculo baseia-se na recursão do tipo Sarwate, que expressa o enumerador de peso de $RM(3, m+1)$ como uma soma dos quadrados dos enumeradores de peso de cossetes de $f + RM(2, m)$ sobre todas as formas cúbicas $f$. Como o enumerador do cossete depende apenas da órbita $GL(m, 2)$ de $f$, a soma reduz-se a representantes de órbita ponderados pelos tamanhos das órbitas.

O gargalo primário para $m=10$ é o enorme número de órbitas (3.691.560 órbitas não nulas) e o custo de avaliar um único enumerador de cossete. A fórmula de divisão padrão de Brier e Langevin requer uma enumeração externa sobre $2^{36}$ formas quadráticas homogêneas para $m=10$, o que é computacionalmente inviável para uma passagem completa do catálogo.

Para superar isso, os autores empregam um teorema estrutural (Teorema 1): toda forma cúbica booleana não degenerada admite uma restrição de hiperplano não degenerada, com exceção de uma única órbita em cada dimensão ímpar. Para $m=10$ (uma dimensão par), este teorema garante que toda órbita não degenerada possui uma restrição a um hiperplano que também é não degenerada. Isso permite que o enumerador do cossete seja computado via um espaço quociente de tamanho $2^{26}$ em vez de $2^{36}$, economizando um fator de $2^{10}$ por órbita.

A avaliação dos enumeradores de peso de cossete é realizada usando transformadas rápidas de Walsh–Hadamard nos cossetes afins resultantes. Toda a passagem de catálogo exigiu aproximadamente 65 anos-CPU. Para verificar a precisão dos resultados e melhorar a eficiência para limites superiores, uma heurística de busca local (combinando descida gananciosa, movimentos $\tau$, busca local iterada e busca de feixe) foi desenvolvida. Esta heurística encontra correções quadráticas $q$ explícitas que minimizam $wt(f+q)$, fornecendo certificados para o raio de cobertura a uma fração do custo da enumeração total.

Contribuições Principais e Resultados

1. Distribuição de Peso de $RM(3, 11)$:
   O artigo apresenta a distribuição de peso completa de $RM(3, 11)$ (Tabela 1). Este resultado é montado somando os quadrados dos enumeradores de peso de cossete de todas as 3.691.560 órbitas $GL(10, 2)$ não nulas de formas cúbicas booleanas em dez variáveis, mais a contribuição da órbita zero.

2. Não Linearidade de Segunda Ordem e Raio de Cobertura Relativo:
   O menor expoente não nulo de cada enumerador de cossete corresponde à não linearidade de segunda ordem $d_2(f)$. O cálculo determina que o valor máximo de $d_2(f)$ sobre todas as formas cúbicas em dez variáveis é 408.

• Teorema 3: O raio de cobertura relativo $\rho_{2,3}(10)$ de $RM(2, 10)$ em $RM(3, 10)$ é exatamente 408.
• Este máximo é atingido em 179 órbitas distintas. Os representantes dessas órbitas e seus "números de beijo" (a contagem de formas quadráticas que atingem o peso mínimo) são listados na Tabela 2.
• Todas as 179 formas extremais são não degeneradas.

3. Limite Inferior Melhorado para o Raio de Cobertura:
   O resultado eleva o melhor limite inferior conhecido para o raio de cobertura de $RM(2, 10)$ de 400 para 408. As 179 órbitas servem como testemunhas explícitas para este limite.

4. Conexão com o Rank Alternante:
   O artigo estabelece uma relação entre $d_2(f)$ e o rank alternante ($arank$) de uma forma cúbica. Usando um limite derivado (Teorema 4), os autores mostram que para qualquer forma com $d_2(f) = 408$, o rank alternante deve ser pelo menos 6. Em $m=10$, o rank alternante máximo é 7. A análise revela que 177 das 179 órbitas extremais têm $arank = 7$, enquanto 2 têm $arank = 6$. Isso contrasta com dimensões menores ($m \leqslant 9$), onde as formas extremais eram forçadas a ter o rank alternante máximo possível para aquela dimensão.

5. Busca Heurística e Limites Cocúbicos:
   A heurística de busca local reproduziu com sucesso o limite $\rho_{2,3}(10) \leqslant 408$ a aproximadamente um milésimo do custo da enumeração total. Aplicada a formas de grau sete, esta heurística melhorou o limite superior sobre o raio de cobertura relativo de $RM(6, 10)$ em $RM(7, 10)$ de 50 para 32 (Lema 2).

Significância
O artigo afirma significância principalmente ao resolver a distribuição de peso para $RM(3, 11)$, estendendo a cadeia conhecida de códigos de terceira ordem. O teorema estrutural sobre restrições de hiperplano não degenerado é apresentado como um facilitador crítico, tornando a passagem completa de catálogo viável onde métodos anteriores estavam "fora de alcance".

A determinação de $\rho_{2,3}(10) = 408$ é significativa para a literatura de raio de cobertura, atualizando o melhor limite inferior conhecido para $RM(2, 10)$. Além disso, a análise das órbitas extremais fornece insights estruturais: a mudança de formas de traço monomial (que anteriormente detinham o recorde de 400) para polinômios de traço binomial e a concentração de formas extremais no rank alternante máximo sugerem novas direções para a busca de formas de alta não linearidade em dimensões mais altas ($m > 10$). Os autores observam que os dados de enumeração e o código de referência são disponibilizados para facilitar pesquisas adicionais em teoria de códigos e análise de funções booleanas.