On the equivalence between additive and linear codes

Titel: Over de equivalentie tussen additieve en lineaire codes

Auteurs: Kanat Abdukhalikov en Duy Ho (UAE University)

1. Het Probleem

Additieve codes over het veld $\mathbb{F}_{q^2}$ (in het bijzonder quaternaire codes over $\mathbb{F}_4$) hebben de afgelopen jaren veel aandacht getrokken omdat ze in sommige gevallen betere prestaties leveren dan hun lineaire tegenhangers, bijvoorbeeld door een grotere minimale afstand te bereiken voor dezelfde lengte en dimensie.

De fundamentele uitdaging in dit onderzoeksgebied is het onderscheid maken tussen:

1. Strikt additieve codes: Codes die additief zijn (gesloten onder optelling) maar niet equivalent zijn aan enige lineaire code over $\mathbb{F}_{q^2}$.
2. Additieve codes die lineair zijn: Codes die additief lijken, maar die via een monomiale transformatie (permutatie en vermenigvuldiging met niet-nul elementen) in een lineaire code kunnen worden omgezet.

Bestaande methoden om dit onderscheid te maken, zijn voornamelijk gebaseerd op meetkundige technieken (zoals pseudo-arcs en Desarguesiaanse spreidingen), wat vaak complex en niet-algoritmisch is. Er was behoefte aan een deterministische, algebraïsche test die puur gebaseerd is op de generatormatrix van de code.

2. Methodologie

De auteurs ontwikkelen een volledig algebraïsch raamwerk om de equivalentie van een additieve code met een lineaire code te testen. De kern van hun aanpak ligt in de representatie van vermenigvuldiging met elementen uit $\mathbb{F}_{q^2}$ als matrixvermenigvuldiging.

• Representatie: Ze beschouwen $\mathbb{F}_{q^2}$ als een vectorruimte over $\mathbb{F}_q$ met basis $\{1, \omega\}$. Vermenigvuldiging met $\omega$ wordt weergegeven door een $2 \times 2$ companion-matrix $M_\omega$.
• Voorwaarde voor Lineariteit: Een additieve code $C$ met generatormatrix $G$ is equivalent aan een lineaire code dan en slechts dan als er een inverteerbare matrix $R \in GL_k(\mathbb{F}_q)$ en een blokg-diagonale matrix $A$ bestaan zodanig dat:
  $$RG = G(AM_\omega A^{-1})$$
  Dit impliceert dat de actie van $\omega$ op de code kan worden "geconjugueerd" naar een lineaire actie binnen de code.
• Het Lineaire Systeem: De auteurs transformeren deze matrixvergelijking in een lineair homogeen systeem $S\mathbf{x} = 0$ met behulp van Kronecker-producten en vectorisatie. De matrix $S$ wordt geconstrueerd uit de blokken van de generatormatrix $G$.
• De Test (Algoritme 1):
  1. Rank-check: Als een blok van de generatormatrix rang 1 heeft, is de code strikt additief (niet lineair).
  2. Nulliteitstest: Bereken de nulliteit (dimensie van de nulruimte) van de matrix $S$.
     • Als de nulliteit oneven is, is de code niet equivalent aan een lineaire code.
     • Als de nulliteit even is, is de test inconclusief; men moet zoeken naar een specifieke oplossing $R$ in de nulruimte die voldoet aan de voorwaarden (geen eigenwaarden in $\mathbb{F}_q$).

3. Belangrijkste Bijdragen

1. Deterministische Test: De introductie van een puur algebraïsche test die alleen de generatormatrix vereist, in tegenstelling tot eerdere meetkundige benaderingen.
2. Theoretische Karakterisering:
   • Stelling 3.1: Een noodzakelijke en voldoende voorwaarde voor equivalentie.
   • Stelling 3.2: Een noodzakelijke voorwaarde gebaseerd op eigenwaarden (als er een $R$ bestaat zonder eigenwaarden in $\mathbb{F}_q$).
   • Stelling 3.3: Een krachtige sufficientie-stelling: als de nulliteit van de matrix $S$ oneven is, is de code gegarandeerd strikt additief.
3. Efficiëntie: Het algoritme is computatievriendelijk en kan worden geïmplementeerd in computersystemen zoals MAGMA.

4. Resultaten en Toepassingen

De auteurs hebben hun test toegepast op recente literatuur, specifiek op quaternaire codes ($q=2$, dus $\mathbb{F}_4$):

• Verificatie van Strikt Additieve Codes:

  • Ze hebben de quaternaire additieve codes uit [14, Tabel II] (inclusief extended en augmented codes) getest. Alle geteste codes hadden een oneven nulliteit voor de matrix $S$.
  • Conclusie: Deze codes zijn strikt additief en niet equivalent aan enige lineaire code. Dit bevestigt eerdere resultaten die met meetkundige methoden waren verkregen, maar nu met een algebraïsche methode.
  • Ook tien quaternaire additieve complementaire duale (ACD) codes uit [18] werden getest. Vijf werden direct afgekeurd op basis van rang-voorwaarden, en de overige vijf hadden een oneven nulliteit. Alle tien zijn strikt additief.

• Ontdekking van een Nieuwe Lineaire Code:

  • In tegenstelling tot de bovenstaande resultaten, toonden ze aan dat een specifieke ACD-code uit [14, Tabel IV] met parameters $[22, 10, 9]_2^2$ wel equivalent is aan een lineaire code.
  • Ze construeerden expliciet de transformatie die deze additieve code omzet in een Hermitian LCD-code (Linear Complementary Dual) over $\mathbb{F}_4$ met parameters $[22, 10, 9]_4$.
  • Impact: Deze code verbetert de bestaande bekende ondergrenzen voor Hermitian LCD-codes in de literatuur (verwijzend naar [2, Tabel 6]).

5. Significantie

De paper biedt een cruciaal instrument voor code-theoretici:

• Klaring van Ambiguïteit: Het lost de vraag op hoe men systematisch kan bepalen of een nieuw ontdekte additieve code een "nieuwe" familie is of slechts een vermomde lineaire code.
• Verbetering van Grenzen: Door te tonen dat een bepaalde "additieve" code eigenlijk lineair is, kunnen de bestaande tabellen voor lineaire codes worden bijgewerkt met betere parameters.
• Algebraïsche Standaard: De methode verplaatst de focus van complexe meetkunde naar lineaire algebra, wat de analyse van additieve codes toegankelijker en reproduceerbaarder maakt.

Samenvattend bewijzen de auteurs dat de meeste recente "superieure" additieve codes inderdaad strikt additief zijn, maar dat er uitzonderingen zijn die leiden tot verbeteringen in de klassen van lineaire codes.