On the equivalence between additive and linear codes

Aquí presento un resumen técnico detallado del artículo "On the equivalence between additive and linear codes" (Sobre la equivalencia entre códigos aditivos y lineales), escrito por Kanat Abdukhalikov y Duy Ho.

1. Planteamiento del Problema

Los códigos aditivos sobre campos finitos, particularmente sobre $\mathbb{F}_{q^2}$, han ganado relevancia debido a su capacidad para superar los límites de rendimiento de los códigos lineales tradicionales, especialmente en la construcción de códigos cuánticos. Sin embargo, existe una ambigüedad fundamental en la literatura: distinguir si un código aditivo es estrictamente aditivo (no equivalente a ningún código lineal) o si, de hecho, es equivalente a un código lineal bajo transformaciones monomiales.

Hasta la fecha, los métodos para resolver esta ambigüedad se basaban principalmente en técnicas geométricas (como arcos pseudo y distribuciones de Desargues), las cuales son complejas y no siempre aplicables de manera general. El artículo aborda la necesidad de un método determinista y puramente algebraico para verificar la equivalencia de un código aditivo dado con un código lineal, utilizando únicamente su matriz generadora.

2. Metodología

Los autores desarrollan un marco algebraico basado en la representación regular de campos finitos y el análisis de la estructura de la matriz generadora.

• Representación Matricial: Se define una aplicación $\phi$ que mapea el espacio vectorial $\mathbb{F}_{q^2}^n$ a $\mathbb{F}_q^{2n}$. Un código aditivo $C$ se representa mediante una matriz generadora $G \in \mathbb{F}_q^{k \times 2n}$.
• Condición de Equivalencia (Teorema 3.1): Se establece que un código aditivo $C$ es equivalente a un código lineal sobre $\mathbb{F}_{q^2}$ si y solo si existe una matriz invertible $R \in GL_k(\mathbb{F}_q)$ y una matriz diagonal por bloques $A$ tal que:
  $$RG = G(AM_\omega A^{-1})$$
  Donde $M_\omega$ es la matriz compañera del elemento primitivo $\omega$ de $\mathbb{F}_{q^2}$ sobre $\mathbb{F}_q$.
• Análisis de Subespacios Invariantes: El problema se reduce a encontrar una matriz $R$ que preserve ciertos subespacios definidos por las columnas de $G$. Si tal $R$ existe y no tiene valores propios en $\mathbb{F}_q$, el código es equivalente a uno lineal.
• Sistema Lineal Homogéneo: Para computar $R$, los autores transforman la ecuación matricial en un sistema lineal homogéneo $S\mathbf{x} = 0$ utilizando productos de Kronecker y vectorización. La matriz $S$ tiene dimensiones $2nk \times (k^2 + 4n)$.
• Criterio de No Equivalencia (Teorema 3.3): Se demuestra que si la nulidad (dimensión del espacio nulo) de la matriz $S$ es impar, entonces el código aditivo es estrictamente aditivo (no equivalente a ningún código lineal). Esto se debe a que la existencia de un código lineal equivalente implicaría que el espacio de soluciones tiene una dimensión par (estructura de pares).
• Algoritmo Propuesto: Se presenta un algoritmo determinista (Algoritmo 1) que:
  1. Verifica el rango de los bloques de columnas de $G$.
  2. Calcula la nulidad de la matriz $S$.
  3. Si la nulidad es impar o si algún bloque tiene rango 1, concluye que el código es estrictamente aditivo.
  4. Si la nulidad es par, busca explícitamente una transformación que demuestre la equivalencia.

3. Contribuciones Clave

1. Test Determinista Algebraico: Se introduce el primer método puramente algebraico que requiere solo la matriz generadora para determinar la equivalencia entre códigos aditivos y lineales, eliminando la dependencia de técnicas geométricas complejas.
2. Caracterización Teórica: Se proveen teoremas rigurosos (3.1, 3.2 y 3.3) que vinculan la estructura algebraica de la matriz generadora con la propiedad de linealidad del código.
3. Algoritmo Computacional: Se formaliza un procedimiento paso a paso implementable en sistemas de álgebra computacional (como MAGMA) para clasificar códigos.
4. Reclasificación de Códigos Existentes: Se aplica el método para reevaluar códigos reportados en la literatura reciente, resolviendo dudas sobre su naturaleza estrictamente aditiva.

4. Resultados Experimentales

Los autores aplicaron su test a varios conjuntos de códigos cuaternarios ($q=2$, campo $\mathbb{F}_4$):

• Códigos de Guan et al. [14]:
  • Se verificaron los códigos aditivos cuaternarios listados en la Tabla II de [14].
  • Resultado: Todos los códigos verificados mostraron una nulidad impar de la matriz $S$, confirmando que son estrictamente aditivos y no equivalentes a códigos lineales. Esto valida algebraicamente hallazgos previos obtenidos mediante métodos geométricos.
• Códigos ACD (Aditivos Complementarios Duales) de [14]:
  • Se analizaron códigos ACD que superaban los límites conocidos de códigos LCD hermitianos lineales.
  • Hallazgo Sorprendente: El código ACD con parámetros $[22, 10, 9]_2^2$ (Línea 1 de la Tabla IV de [14]) resultó tener una nulidad par. Una búsqueda directa en el espacio nulo permitió construir una transformación que demostró que este código es equivalente a un código lineal Hermitiano LCD con los mismos parámetros.
  • Impacto: Esto mejora el límite conocido para códigos lineales Hermitianos LCD en la literatura.
  • Por el contrario, otros códigos candidatos (líneas 5, 6 y 10 de la misma tabla) tuvieron nulidad impar, confirmando que son estrictamente aditivos.
• Códigos de [18]:
  • Se verificaron diez códigos ACD cuaternarios construidos mediante la suma de Plotkin.
  • Resultado: Todos los diez códigos resultaron ser estrictamente aditivos. Cinco fueron descartados por la condición de rango (Teorema 3.2) y cinco por la nulidad impar de $S$.

5. Significado e Impacto

Este trabajo resuelve una cuestión fundamental en la teoría de códigos al proporcionar una herramienta definitiva para distinguir entre códigos aditivos "nuevos" y aquellos que son simplemente representaciones no lineales de códigos lineales existentes.

• Validación de Códigos Cuánticos: Al confirmar que ciertos códigos son estrictamente aditivos, se valida su utilidad potencial para la construcción de códigos cuánticos donde los códigos lineales fallan.
• Mejora de Límites: El descubrimiento de que el código $[22, 10, 9]_2^2$ es equivalente a un código lineal Hermitiano LCD demuestra que los límites de rendimiento para códigos lineales pueden ser mejorados, reutilizando estructuras aditivas conocidas.
• Eficiencia Computacional: El método propuesto es computacionalmente eficiente y se puede implementar fácilmente, facilitando la investigación futura en la clasificación de códigos óptimos.

En resumen, el artículo cierra la brecha entre la teoría geométrica y algebraica en este dominio, ofreciendo un algoritmo robusto que ha permitido tanto confirmar la naturaleza estrictamente aditiva de varios códigos prometedores como descubrir nuevas equivalencias que mejoran los límites conocidos de códigos lineales.