Equivalence of Families of Polycyclic Codes over Finite Fields

Sintesi Tecnica: Equivalenza di Famiglie di Codici Policiclici su Campi Finiti

Enunciato del Problema
Il lavoro affronta la classificazione e l'equivalenza di famiglie di codici policiclici su campi finiti $\mathbb{F}_q$. Mentre i codici ciclici e costaciclici sono ben compresi come ideali in anelli quoziente $\mathbb{F}_q[x]/\langle x^n - \lambda \rangle$, i codici policiclici generalizzano queste strutture a ideali in $\mathbb{F}_q[x]/\langle f(x) \rangle$, dove $f(x)$ è un polinomio non nullo arbitrario. Una sfida centrale nella teoria dei codici è la costruzione di codici con parametri ottimali (lunghezza $n$, dimensione $k$ e distanza minima $d$). Poiché le ricerche esaustive al computer per codici ottimali sono computazionalmente intrattabili per parametri elevati, gli autori mirano a ridurre lo spazio di ricerca organizzando sistematicamente i codici policiclici in classi di equivalenza. Nello specifico, il lavoro indaga quando due spazi ambientali (gli anelli quoziente che definiscono i codici) sono isometrici, permettendo così ai ricercatori di limitare la loro ricerca ai rappresentanti di tali classi di equivalenza.

Metodologia
Gli autori estendono il concetto di $n$-equivalenza, precedentemente definito per i codici costaciclici, al contesto più ampio dei codici policiclici. La metodologia procede in tre fasi:

1. Definizione di Equivalenza: Due famiglie di codici policiclici associate ai polinomi $f(x) = x^n - \vec{a}(x)$ e $g(x) = x^n - \vec{b}(x)$ sono definite $n$-equivalenti se esiste un $\alpha \in \mathbb{F}_q^*$ tale che la mappa $\Phi_\alpha: f(x) \mapsto f(\alpha x)$ induca un isomorfismo di $\mathbb{F}_q$-algebre tra gli anelli quoziente $\mathbb{F}_q[x]/\langle g(x) \rangle$ e $\mathbb{F}_q[x]/\langle f(x) \rangle$ che preservi la distanza di Hamming.
2. Caratterizzazione Algebrica: Il lavoro deriva condizioni necessarie e sufficienti per tale equivalenza. Ciò comporta l'analisi delle radici di equazioni binomie e trinomie in $\mathbb{F}_q$. Gli strumenti chiave includono:
   • Lemma riguardanti il grado di $\gcd(x^n - a, x^m - b)$ e il numero di soluzioni di $x^n - a = 0$.
   • L'uso dei prodotti di Schur (moltiplicazione componente per componente) per relazionare i vettori dei coefficienti dei polinomi equivalenti.
   • Analisi teorico-grupale dei sottogruppi ciclici generati dalle potenze di elementi primitivi in $\mathbb{F}_q^* \times \mathbb{F}_q^*$.
3. Specializzazione e Generalizzazione:
   • Codici $\ell$-Trinomiali: Lo studio si concentra inizialmente sui codici associati a trinomi della forma $x^n - a_\ell x^\ell - a_0$ (dove $0 < \ell < n$). Gli autori derivano formule esplicite per il numero di classi di equivalenza e le condizioni sotto le quali un codice trinomio è equivalente a una forma canonica $x^n - x^\ell - 1$.
   • Codici $p\ell$-Trinomiali: Viene condotta un'analisi specifica per codici di lunghezza $n = p^\ell + r$ (dove $p$ è la caratteristica di $\mathbb{F}_q$), utilizzando le proprietà dei polinomi di Artin-Schreier e delle funzioni traccia per determinare le fattorizzazioni irriducibili.
   • Codici Policiclici Generali: I risultati sono generalizzati a codici policiclici arbitrari definiti da vettori $\vec{a}$ con $m$ voci non nulle.

Contributi e Risultati Chiave

• Definizione di $(n, \ell)$-Equivalenza: Il lavoro formalizza una relazione di equivalenza per i codici $\ell$-trinomiali. Dimostra che due coppie di coefficienti $(a_0, a_\ell)$ e $(b_0, b_\ell)$ sono equivalenti se e solo se i polinomi $a_0 x^n - b_0$ e $a_\ell x^{n-\ell} - b_\ell$ condividono una radice comune in $\mathbb{F}_q^*$.
• Conteggio delle Classi di Equivalenza: Gli autori forniscono una formula esplicita per il numero di classi di $n$-equivalenza per i codici $\ell$-trinomiali:
  $$N_{(n,\ell)} = (q-1) \gcd(q-1, n, \ell)$$
  Per i codici policiclici generali con $m$ coefficienti non nulli, il numero di classi è dato da:
  $$N = \frac{(q-1)^m}{\text{lcm}_{0 \le j \le m-1} \left( \frac{q-1}{\gcd(n-i_j, q-1)} \right)}$$
• Riduzione a Forme Canoniche:
  • È dimostrato che se $\gcd(n, n-\ell) = 1$, qualsiasi famiglia di codici $\ell$-trinomiali è equivalente a una famiglia associata al polinomio $x^n - x^\ell - 1$.
  • Per il caso in cui $\gcd(n, n-\ell) \neq 1$, il lavoro identifica rappresentanti specifici (che coinvolgono potenze di un elemento primitivo $\xi$) che coprono tutte le classi di equivalenza.
• Fattorizzazione di Trinomi Specifici: Il lavoro analizza la fattorizzazione di trinomi della forma $x^{p^\ell+1} - x^{p^\ell} - 1$ e $x^{p^\ell+s} - x^{p^\ell} - 1$. Stabilisce le condizioni sotto le quali questi polinomi si spezzano in fattori irriducibili (spesso coinvolgendo polinomi di Artin-Schreier $x^p - x - \beta$), il che informa direttamente i possibili polinomi generatori per i codici in queste famiglie.
• Costruzione di Codici Ottimali: Limitando la ricerca ai rappresentanti delle classi di equivalenza identificate, gli autori costruiscono diversi esempi di codici policiclici ottimali. Esempi notevoli includono:
  • Un codice $[27, 3, 18]_3$ e un codice $[81, 3, 55]_3$ derivati da codici $3\ell$-trinomiali su $\mathbb{F}_3$.
  • Codici ottimali su $\mathbb{F}_9$ e $\mathbb{F}_4$ con parametri che corrispondono o raggiungono limiti noti (ad esempio, il limite di Griesmer).

Significato e Affermazioni
Il lavoro afferma che il suo significato primario risiede nel fornire un quadro sistematico per organizzare e classificare i codici policiclici. Stabilendo criteri espliciti per l'equivalenza, il lavoro riduce la complessità della ricerca di codici con parametri ottimali. Invece di investigare tutte le possibili combinazioni di coefficienti, i ricercatori possono concentrarsi su un insieme finito di rappresentanti per ogni classe di equivalenza.

Inoltre, gli autori osservano che comprendere l'equivalenza degli spazi ambientali è cruciale per lo studio della dualità nei codici policiclici. Poiché il duale di un codice policiclico non è necessariamente policiclico rispetto allo stesso spazio ambientale ma è spesso equivalente a uno che nasce da uno spazio diverso, questa classificazione fornisce una base per futuri risultati teorici sulla dualità. Il lavoro conclude che questi risultati estendono l'applicazione di successo delle relazioni di equivalenza dai codici costaciclici al dominio più generale e complesso dei codici policiclici, offrendo una via per costruire famiglie infinite di codici con parametri quasi ottimali.