Classification of Boolean Cubic Forms in Ten Variables

Resumo Técnico: Classificação de Formas Cúbicas Booleanas em Dez Variáveis

Enunciado do Problema
O artigo aborda a classificação de formas cúbicas booleanas em dez variáveis sobre o corpo $\mathbb{F}_2$ até a equivalência por $GL(10, 2)$. Uma forma cúbica booleana é um polinômio $f(x) = \sum T_{ijk} x_i x_j x_k$ onde os coeficientes estão em $\mathbb{F}_2$ e as variáveis satisfazem $x_j^2 = x_j$. Duas formas são equivalentes se uma pode ser transformada na outra via uma mudança de variáveis linear invertível, ignorando termos constantes, lineares e quadráticos. Esta classificação corresponde à enumeração das órbitas não nulas do espaço $RM^*(3, 10)$ (a terceira camada dos códigos de Reed–Muller) sob a ação de $GL(10, 2)$. Embora existam classificações completas para dimensões $m \leq 9$ sobre vários corpos, o caso $m=10$ não havia sido abordado sobre nenhum campo antes deste trabalho.

Metodologia
Os autores empregam uma estratégia de enumeração estratificada por posto combinada com um novo invariante completo para identificação de órbitas.

1. Enumeração Estratificada por Posto (BFS):
   A enumeração procede por "posto alternante", definido como o número mínimo $r$ tal que uma forma $f$ pode ser decomposta em uma soma de $r$ cúbicas decomponíveis $u(x)v(x)w(x)$. O processo começa com a forma zero e adiciona iterativamente formas de posto-1 (cúbicas decomponíveis) a representantes da camada atual. Isso gera candidatos para a próxima camada de posto. O espaço de busca é significativamente reduzido ao identificar órbitas de $GL(10, 2)$ em cada etapa, em vez de enumerar todas as $2^{\binom{10}{3}}$ formas.

2. Construção de Invariante Completo:
   Para distinguir órbitas de forma eficiente, os autores constroem um invariante de $GL(10, 2)$.

   • Grafo de Ortogonalidade ($G_f$): Baseado na relação $u \perp_f v \iff \Delta_u \Delta_v f(x) = 0$. Embora a classe de isomorfismo de $G_f$ seja um invariante completo para $m < 10$, ela falha para $m=10$, deixando 51 colisões não resolvidas.
   • Grafo de Incidência ($B_f$): Um grafo bipartido derivado das formas bilineares polares, onde as arestas representam relações de imagem ($u \to_f v$).
   • Estatísticas Locais: Em vez de testes completos de isomorfismo de grafos (que são computacionalmente caros), os autores extraem estatísticas locais:
     • $\mu_5(f)$: O multiconjunto de caminhadas fechadas de comprimento 5 em $G_f$.
     • $\theta(f)$: Um conjunto específico de contagens de grau-codegrado à direita de $B_f$.
     • $\rho(f)$: Um resolvedor baseado em triplas marcadas para o par de colisão restante ($f_{381}, f_{382}$).
   • O triplo $(\mu_5, \theta, \rho)$ é comprimido em uma única palavra de 64 bits. Este invariante é verificado como livre de colisões em todos os representantes.

3. Verificação:
   A completude é verificada independentemente por dois métodos:

   • Lema de Burnside: A contagem total de órbitas coincide com a soma teórica derivada da ação do grupo.
   • Identidade Ordem-Estabilizador: A soma de $|GL(10, 2)| / |St(f)|$ sobre todos os representantes do catálogo é igual ao número total de formas não nulas ($2^{\binom{10}{3}} - 1$).

Contribuições Principais e Resultados

• O Catálogo: O artigo apresenta um catálogo explícito de todas as 3.691.560 órbitas de $GL(10, 2)$ de formas cúbicas booleanas em dez variáveis.
• Representantes: Para cada órbita, o catálogo fornece um representante com uma contagem de monômios minimizada (máximo observado é 17), a ordem de seu estabilizador em $GL(10, 2)$ e uma decomposição explícita de posto alternante.
• Dados Estruturais:
  • Posto Alternante: O posto alternante máximo em dimensão 10 é 7. A distribuição mostra que as formas de posto 6 constituem a camada dominante entre as formas não degeneradas.
  • Estabilizadores: Existem 143 ordens de estabilizador distintas. A maioria das formas em $m=10$ possui um estabilizador trivial.
  • Dimensionalidade: Do total de órbitas, 348 possuem radicais não triviais (herdados de dimensões efetivas menores), enquanto 3.691.212 são não degeneradas em dimensão 10.
• Desempenho do Invariante: O invariante de 64 bits avalia em uma média de 0,20 ms por forma, significativamente mais rápido do que a rotulagem canônica direta (que levou até 8,9 s para classes de colisão).

Significância e Aplicações
Os autores posicionam este trabalho como um recurso fundamental para diversas áreas:

• Teoria de Códigos: O catálogo fornece o dado necessário para calcular enumeradores de peso de cossete e raios de cobertura para códigos de Reed–Muller de terceira ordem $RM(3, 10)$ e estruturas relacionadas como $RM^*(7, 10)$. Também fornece a camada de indexação de órbitas necessária para recursões do tipo Sarwate para $RM(3, 11)$.
• Computação Quântica: A classificação oferece uma tabela de consulta para otimizar circuitos quânticos. Como o posto alternante da parte cúbica do polinômio de fase controla a contagem de portas Toffoli, o catálogo permite a substituição de fragmentos cúbicos (até 10 variáveis) por decomposições otimizadas, analogamente à substituição de subcircuitos para minimização de contagem de AND.
• Classificação Matemática: Isto constitui a primeira classificação completa de formas trilineares alternantes em dimensão 10 sobre qualquer corpo. Por polarização, os resultados aplicam-se diretamente à geometria de trivetores e à classificação de loops de código via formas associadoras.

O artigo conclui que, embora a classificação seja completa para $m=10$, estender isso para $m=11$ exigiria invariantes substancialmente mais eficientes devido ao crescimento exponencial no número de órbitas (estimado em $\approx 6 \times 10^{13}$). Os dados e o código foram disponibilizados via Zenodo e GitHub.