Equivalence of Families of Polycyclic Codes over Finite Fields

Resumo Técnico: Equivalência de Famílias de Códigos Policíclicos sobre Corpos Finitos

Enunciado do Problema
O artigo aborda a classificação e a equivalência de famílias de códigos policíclicos sobre corpos finitos $\mathbb{F}_q$. Enquanto os códigos cíclicos e constaciclos são bem compreendidos como ideais em anéis quocientes $\mathbb{F}_q[x]/\langle x^n - \lambda \rangle$, os códigos policíclicos generalizam essas estruturas para ideais em $\mathbb{F}_q[x]/\langle f(x) \rangle$, onde $f(x)$ é um polinômio não nulo arbitrário. Um desafio central na teoria de códigos é a construção de códigos com parâmetros ótimos (comprimento $n$, dimensão $k$ e distância mínima $d$). Como buscas exaustivas por computador para códigos ótimos são computacionalmente intratáveis para parâmetros grandes, os autores visam reduzir o espaço de busca organizando sistematicamente os códigos policíclicos em classes de equivalência. Especificamente, o artigo investiga quando dois espaços ambientes (os anéis quocientes que definem os códigos) são isométricos, permitindo assim que os pesquisadores restrinjam sua busca a representantes dessas classes de equivalência.

Metodologia
Os autores estendem o conceito de $n$-equivalência, previamente definido para códigos constaciclos, para o contexto mais amplo de códigos policíclicos. A metodologia prossegue em três etapas:

1. Definição de Equivalência: Duas famílias de códigos policíclicos associadas aos polinômios $f(x) = x^n - \vec{a}(x)$ e $g(x) = x^n - \vec{b}(x)$ são definidas como $n$-equivalentes se existir um $\alpha \in \mathbb{F}_q^*$ tal que o mapa $\Phi_\alpha: f(x) \mapsto f(\alpha x)$ induza um isomorfismo de $\mathbb{F}_q$-álgebras entre os anéis quocientes $\mathbb{F}_q[x]/\langle g(x) \rangle$ e $\mathbb{F}_q[x]/\langle f(x) \rangle$ que preserve a distância de Hamming.
2. Caracterização Algébrica: O artigo deriva condições necessárias e suficientes para essa equivalência. Isso envolve analisar as raízes de equações binomiais e trinomiais em $\mathbb{F}_q$. As ferramentas-chave incluem:
   • Lemas relativos ao grau de $\gcd(x^n - a, x^m - b)$ e ao número de soluções de $x^n - a = 0$.
   • O uso de produtos de Schur (multiplicação componente a componente) para relacionar os vetores de coeficientes de polinômios equivalentes.
   • Análise teórica de grupos de subgrupos cíclicos gerados por potências de elementos primitivos em $\mathbb{F}_q^* \times \mathbb{F}_q^*$.
3. Especialização e Generalização:
   • Códigos $\ell$-Trinomiais: O estudo foca inicialmente em códigos associados a trinomios da forma $x^n - a_\ell x^\ell - a_0$ (onde $0 < \ell < n$). Os autores derivam fórmulas explícitas para o número de classes de equivalência e condições sob as quais um código trinomial é equivalente a uma forma canônica $x^n - x^\ell - 1$.
   • Códigos $p\ell$-Trinomiais: Uma análise específica é conduzida para códigos de comprimento $n = p^\ell + r$ (onde $p$ é a característica de $\mathbb{F}_q$), utilizando propriedades de polinômios de Artin-Schreier e funções de traço para determinar fatorações irredutíveis.
   • Códigos Policíclicos Gerais: Os resultados são generalizados para códigos policíclicos arbitrários definidos por vetores $\vec{a}$ com $m$ entradas não nulas.

Principais Contribuições e Resultados

• Definição de $(n, \ell)$-Equivalência: O artigo formaliza uma relação de equivalência para códigos $\ell$-trinomiais. Demonstra-se que dois pares de coeficientes $(a_0, a_\ell)$ e $(b_0, b_\ell)$ são equivalentes se e somente se os polinômios $a_0 x^n - b_0$ e $a_\ell x^{n-\ell} - b_\ell$ compartilharem uma raiz comum em $\mathbb{F}_q^*$.
• Contagem de Classes de Equivalência: Os autores fornecem uma fórmula explícita para o número de classes de $n$-equivalência para códigos $\ell$-trinomiais:
  $$N_{(n,\ell)} = (q-1) \gcd(q-1, n, \ell)$$
  Para códigos policíclicos gerais com $m$ coeficientes não nulos, o número de classes é dado por:
  $$N = \frac{(q-1)^m}{\text{lcm}_{0 \le j \le m-1} \left( \frac{q-1}{\gcd(n-i_j, q-1)} \right)}$$
• Redução a Formas Canônicas:
  • Demonstra-se que, se $\gcd(n, n-\ell) = 1$, qualquer família de códigos $\ell$-trinomiais é equivalente a uma família associada ao polinômio $x^n - x^\ell - 1$.
  • Para o caso onde $\gcd(n, n-\ell) \neq 1$, o artigo identifica representantes específicos (envolvendo potências de um elemento primitivo $\xi$) que cobrem todas as classes de equivalência.
• Fatoração de Trinomios Específicos: O artigo analisa a fatoração de trinomios da forma $x^{p^\ell+1} - x^{p^\ell} - 1$ e $x^{p^\ell+s} - x^{p^\ell} - 1$. Estabelece condições sob as quais esses polinômios se decompõem em fatores irredutíveis (frequentemente envolvendo polinômios de Artin-Schreier $x^p - x - \beta$), o que informa diretamente os possíveis polinômios geradores para códigos nessas famílias.
• Construção de Códigos Ótimos: Ao restringir a busca aos representantes das classes de equivalência identificadas, os autores constroem vários exemplos de códigos policíclicos ótimos. Exemplos notáveis incluem:
  • Um código $[27, 3, 18]_3$ e um código $[81, 3, 55]_3$ derivados de códigos $3\ell$-trinomiais sobre $\mathbb{F}_3$.
  • Códigos ótimos sobre $\mathbb{F}_9$ e $\mathbb{F}_4$ com parâmetros que correspondem ou atingem limites conhecidos (por exemplo, limite de Griesmer).

Significado e Alegações
O artigo alega que sua principal relevância reside em fornecer uma estrutura sistemática para organizar e classificar códigos policíclicos. Ao estabelecer critérios explícitos para equivalência, o trabalho reduz a complexidade da busca por códigos com parâmetros ótimos. Em vez de investigar todas as combinações possíveis de coeficientes, os pesquisadores podem focar em um conjunto finito de representantes para cada classe de equivalência.

Além disso, os autores observam que compreender a equivalência de espaços ambientes é crucial para o estudo da dualidade em códigos policíclicos. Como o dual de um código policíclico não é necessariamente policíclico em relação ao mesmo espaço ambiente, mas frequentemente é equivalente a um que surge de um espaço diferente, essa classificação fornece uma base para futuros resultados teóricos sobre dualidade. O artigo conclui que esses resultados estendem a aplicação bem-sucedida de relações de equivalência de códigos constaciclos para o domínio mais geral e complexo dos códigos policíclicos, oferecendo um caminho para a construção de famílias infinitas de códigos com parâmetros quase ótimos.