On the equivalence between additive and linear codes

Título: Sobre a Equivalência entre Códigos Aditivos e Lineares

Autores: Kanat Abdukhalikov e Duy Ho (Universidade dos Emirados Árabes Unidos)

1. O Problema

Os códigos aditivos sobre o corpo finito $\mathbb{F}_{q^2}$ (especificamente códigos quaternários onde $q=2$) têm recebido atenção significativa devido à sua capacidade de superar os códigos lineares tradicionais em termos de parâmetros de distância mínima. No entanto, uma questão fundamental permanece sem resposta clara na literatura: como determinar de forma definitiva se um novo código aditivo construído é estritamente aditivo (ou seja, não equivalente a nenhum código linear) ou se ele é apenas uma representação diferente de um código linear existente?

Atualmente, distinguir códigos estritamente aditivos de códigos equivalentes a lineares depende principalmente de técnicas geométricas complexas (como arcos pseudo e espalhamentos de Desargues), que nem sempre são aplicáveis ou computacionalmente eficientes para todos os casos. A ambiguidade sobre a existência de códigos lineares com os mesmos parâmetros de códigos aditivos recentes (como os apresentados em [14]) impede a classificação correta desses códigos e a atualização precisa das tabelas de limites conhecidos.

2. Metodologia

Os autores propõem uma abordagem puramente algébrica e determinística para resolver esse problema, baseada exclusivamente na matriz geradora do código aditivo.

• Definições Fundamentais:

  • Consideram códigos aditivos $C \subseteq \mathbb{F}_{q^2}^n$ como subgrupos $\mathbb{F}_q$-lineares.
  • Utilizam um isomorfismo $\phi: \mathbb{F}_{q^2}^n \to \mathbb{F}_q^{2n}$ para mapear o código aditivo em um espaço vetorial linear sobre $\mathbb{F}_q$.
  • Definem a equivalência monomial e a SL-equivalência (equivalência onde as transformações locais pertencem a $SL_2(\mathbb{F}_q)$). Para $q$ par (como no caso quaternário), a SL-equivalência é suficiente para preservar a estrutura linear.

• O Teste Algébrico:

  • Seja $M_\omega$ a matriz companheira do elemento primitivo $\omega$ de $\mathbb{F}_{q^2}$ sobre $\mathbb{F}_q$.
  • O teorema central (Teorema 3.1) estabelece que um código aditivo $C$ é equivalente a um código linear se e somente se existir uma matriz $R \in GL_k(\mathbb{F}_q)$ e uma matriz diagonal em blocos $A$ tal que $RG = G(AM_\omega A^{-1})$, onde $G$ é a matriz geradora de $C$.
  • Os autores transformam essa condição em um sistema linear homogêneo $Sx = 0$, onde $S$ é uma matriz construída a partir de $G$ e $M_\omega$.

• Critérios de Decisão (Algoritmo 1):

  1. Verificação de Rango: Se algum bloco de coluna da matriz geradora tiver rango 1, o código é estritamente aditivo (Teorema 3.2).
  2. Teste de Nulidade: Calcula-se a nulidade (dimensão do espaço nulo) da matriz $S$.
     • Se a nulidade for ímpar, o código é estritamente aditivo (Teorema 3.3).
     • Se a nulidade for par, busca-se no espaço nulo uma matriz $R$ que satisfaça as condições de equivalência. Se encontrada, o código é equivalente a um linear.

3. Principais Contribuições

1. Caracterização Algébrica: Forneceram uma condição necessária e suficiente para a equivalência entre códigos aditivos e lineares, baseada na estrutura do anel gerado pela matriz $R$ e no polinômio mínimo de $\omega$.
2. Algoritmo Determinístico: Desenvolveram um algoritmo computacional eficiente que requer apenas a matriz geradora, eliminando a necessidade de técnicas geométricas complexas.
3. Resolução de Ambiguidades na Literatura: Aplicaram o teste para verificar códigos quaternários reportados em trabalhos recentes ([14] e [18]), esclarecendo quais são estritamente aditivos e quais são equivalentes a lineares.

4. Resultados

Os autores aplicaram o teste usando o sistema de álgebra computacional MAGMA em vários conjuntos de dados:

• Códigos de Guan et al. [14] (Tabela II):

  • Verificaram códigos com parâmetros como $[47, 35, 7]_2^2$, $[63, 5, 45]_2^2$, entre outros.
  • Resultado: Todos os códigos verificados apresentaram nulidade ímpar de $S$, confirmando que são estritamente aditivos e não equivalentes a nenhum código linear.

• Códigos Aditivos Complementares Duais (ACD) de [14] (Tabela IV):

  • Investigaram se códigos ACD quaternários poderiam ser equivalentes a códigos lineares LCD Hermitianos (que têm aplicações em criptografia).
  • Caso de Sucesso (Linha 1): O código $[22, 10, 9]_2^2$ foi encontrado como equivalente a um código linear Hermitiano LCD $[22, 10, 9]_4$. Isso melhora o limite conhecido para códigos lineares LCD Hermitianos nessa tabela.
  • Códigos Estritamente Aditivos: Os códigos das linhas 5, 6 e 10 (parâmetros como $[27, 10, 12]_2^2$) apresentaram nulidade ímpar, confirmando que são estritamente aditivos e, portanto, superam os limites dos códigos lineares conhecidos.

• Códigos ACD de [18] (Construção Plotkin):

  • Verificaram 10 códigos reportados como superando os limites lineares.
  • Resultado: Todos os 10 códigos foram confirmados como estritamente aditivos. Cinco foram descartados pela condição de rango (Teorema 3.2) e cinco pela nulidade ímpar (Teorema 3.3).

5. Significância

Este trabalho é fundamental para a teoria de códigos por várias razões:

• Clareza Teórica: Resolve a dúvida sobre a natureza de códigos aditivos recentes, distinguindo claramente entre inovações genuínas (códigos estritamente aditivos) e reparametrizações de códigos lineares.
• Melhoria de Limites: Ao demonstrar que o código $[22, 10, 9]_2^2$ é equivalente a um código linear, os autores conseguiram melhorar o melhor limite conhecido para códigos lineares LCD Hermitianos, um resultado valioso para a construção de códigos quânticos e criptografia.
• Validação de Superioridade: Confirmou que vários códigos reportados na literatura são, de fato, superiores aos códigos lineares existentes, validando o potencial dos códigos aditivos para aplicações práticas.
• Ferramenta Prática: Oferece uma ferramenta computacional acessível (baseada apenas na matriz geradora) para pesquisadores que desenvolvem novos códigos, permitindo uma verificação rápida de equivalência.

Em suma, o artigo fornece a "prova definitiva" algébrica para a classificação de códigos aditivos, fechando lacunas na literatura e refinando os limites de desempenho para códigos lineares e aditivos.