On the equivalence between additive and linear codes

1. Problématique

Les codes additifs, en particulier les codes additifs quaternaires (sur le corps $\mathbb{F}_{4}$), suscitent un intérêt croissant car ils peuvent offrir de meilleures performances (distances minimales plus élevées) que leurs homologues linéaires pour des paramètres donnés. Cependant, une ambiguïté fondamentale persiste dans la littérature : il est souvent difficile de déterminer si un code additif nouvellement construit est strictement additif (c'est-à-dire non équivalent à aucun code linéaire) ou s'il est simplement une représentation différente d'un code linéaire existant.

Les méthodes précédentes pour distinguer ces deux cas reposaient principalement sur des techniques géométriques complexes (comme les pseudo-arcs et les étalements de Desargues), qui ne s'appliquent pas toujours de manière générale ou déterministe. L'objectif de cet article est de fournir une méthode algébrique déterministe, basée uniquement sur la matrice génératrice du code, pour trancher cette question.

2. Méthodologie

Les auteurs développent un cadre algébrique rigoureux pour tester l'équivalence entre un code additif $C$ (sous-groupe $\mathbb{F}_q$-linéaire de $\mathbb{F}_{q^2}^n$) et un code linéaire sur $\mathbb{F}_{q^2}$.

• Représentation Matricielle : Ils utilisent la représentation régulière du corps $\mathbb{F}_{q^2}$ sur $\mathbb{F}_q$. Soit $\omega$ un élément primitif de $\mathbb{F}_{q^2}$, sa multiplication est représentée par une matrice compagnon $M_\omega \in GL_2(\mathbb{F}_q)$.

• Condition d'Équivalence (Théorème 3.1) : Un code additif $C$ de matrice génératrice $G$ est équivalent à un code linéaire sur $\mathbb{F}_{q^2}$ si et seulement s'il existe une matrice inversible $R \in GL_k(\mathbb{F}_q)$ et une matrice diagonale par blocs $A$ telle que :
  $$RG = G(AM_\omega A^{-1})$$
  Cela implique que l'action de la multiplication par $\omega$ sur le code peut être "conjugée" à une action linéaire sur la matrice génératrice.

• Analyse Spectrale et Espace Null (Théorèmes 3.2 et 3.3) :

  • Les auteurs définissent un sous-espace $\mathcal{R}$ de matrices $R$ qui préservent les sous-espaces colonnes de $G$.
  • Ils construisent un système linéaire homogène $Sx = 0$(où$S$ est une matrice de grande taille construite via des produits de Kronecker) dont l'espace nul correspond aux solutions possibles pour $R$ et les matrices de conjugaison $T_i$.
  • Critère de non-équivalence : Si la nullité de la matrice $S$ (la dimension de son espace nul) est impaire, alors le code est strictement additif. En effet, si le code était linéaire, l'espace $\mathcal{R}$ aurait une dimension paire (car isomorphe à une extension de corps $\mathbb{F}_{q^2}$).
  • Critère de rang : Si l'une des sous-blocs de colonnes de $G$ a un rang de 1, le code n'est pas équivalent à un code linéaire.

• Algorithme 1 : L'article propose un algorithme déterministe en trois étapes :

  1. Vérification des rangs des blocs de colonnes.
  2. Calcul de la nullité de la matrice $S$. Si elle est impaire, le code est strictement additif.
  3. Recherche dans l'espace nul pour trouver une matrice $R$ valide si la nullité est paire (cas où l'équivalence est possible).

3. Contributions Clés

1. Test Algébrique Déterministe : Introduction d'un test basé uniquement sur la matrice génératrice, évitant les techniques géométriques lourdes.
2. Caractérisation Théorique : Preuve que la parité de la nullité de la matrice $S$ est un indicateur décisif de la nature strictement additive d'un code (Théorème 3.3).
3. Application aux Codes Quaternaires : Mise en œuvre de cet algorithme via le système d'algèbre computationnelle MAGMA pour vérifier des codes spécifiques de la littérature récente.

4. Résultats Expérimentaux

Les auteurs ont appliqué leur test à plusieurs ensembles de codes quaternaires ($q=2$, donc $\mathbb{F}_4$) :

• Codes de Guan et al. [14] (Table II) : Ils ont vérifié plusieurs codes additifs quasi-cycliques. Pour tous les codes listés (ex: $[47, 35, 7]_2^2$, $[63, 5, 45]_2^2$, etc.), la nullité de $S$ s'est avérée être 1 (impaire).
  • Conclusion : Ces codes sont strictement additifs et non équivalents à aucun code linéaire.
• Codes ACD (Additive Complementary Dual) de [14] (Table IV) :
  • Le code $[22, 10, 9]_2^2$ (Ligne 1) a une nullité paire (2). Une recherche dans l'espace nul a permis de trouver une transformation explicite montrant qu'il est équivalent à un code linéaire Hermitien LCD (Linear Complementary Dual) de paramètres $[22, 10, 9]_4$.
  • Impact : Ce résultat améliore la borne connue pour les codes linéaires Hermitiens LCD dans la littérature ([2, Table 6]).
  • Les autres codes candidats (Lignes 5, 6, 10) ont une nullité impaire (1), confirmant qu'ils sont strictement additifs.
• Codes de [18] (Table 2) : Dix codes additifs construits via la somme de Plotkin ont été testés. Cinq ont été rejetés par la condition de rang (Théorème 3.2) et cinq par une nullité impaire. Tous sont confirmés comme strictement additifs.

5. Signification et Impact

Cet article résout un problème ouvert majeur en théorie des codes : la capacité à distinguer efficacement les codes additifs "nouveaux" des codes linéaires déguisés.

• Validation de la supériorité des codes additifs : En prouvant que de nombreux codes rapportés dans la littérature récente sont strictement additifs, l'article confirme qu'ils offrent réellement des performances inaccessibles aux codes linéaires classiques.
• Amélioration des bornes linéaires : Paradoxalement, en montrant qu'un code additif spécifique est équivalent à un code linéaire, les auteurs ont réussi à améliorer les meilleures bornes connues pour les codes linéaires Hermitiens LCD, comblant ainsi un fossé entre les deux domaines.
• Outil pratique : L'algorithme proposé fournit un outil standard et automatisable pour les chercheurs travaillant sur la construction de codes, permettant de valider rapidement la nature intrinsèque d'un code sans recourir à des preuves géométriques ad hoc.

En résumé, ce travail établit un pont rigoureux entre l'algèbre linéaire et la théorie des codes additifs, offrant une méthode de classification définitive qui clarifie le paysage des codes optimaux en dimensions supérieures.