Advertencia: En este texto se introducen definiciones de conceptos de forma intuitiva, el objetivo, es que al final de la lectura el lector tenga una idea panorámica de los problemas que involucran a los códigos, sus aplicaciones y principalmente, la relación que tienen con el álgebra conmutativa.
Antes de dar una definición formal de código, iniciaremos con un ejemplo, probablemente uno de los más conocidos y que usamos todos los días, el código llamado Número Internacional Normalizado para Libros, ISBN (por las siglas en inglés de International Standard Book Number). A cada libro se le asigna un ISBN, el cual se encuentra en la contraportada. Por ejemplo, el ISBN de uno de mis libros favoritos es $1-482-23469-6$. Los primeros nueve dígitos $1-482-23469$, contienen información acerca del libro como editorial, país, formato, etc. El último, es un dígito de control que se elige en base a los primeros nueve. Para elegir el dígito $a_{10}$ para el ISBN $a_1-a_2a_3a_4-a_5a_6a_7a_8a_9$ primero se calcula $a^{\prime}_{10}:=a_1+2a_2+3a_3+\cdots +9a_9$. Si $a^{\prime}_{10}\equiv i (mod 11)$ para algún $i$ tal que $0\leq i \leq 9$, elegimos $a_{10}=i$. Si $a^{\prime}_{10}\equiv 10 (mod 11)$ elegimos $a_{10}$ como el símbolo X
.
Por ejemplo para el ISBN, $1-482-23469-6$, nota que $a_{10}^{\prime}=226$ y $226\equiv 6 (mod 11)$ y el último dígito es $6$. El punto es, que a cada libro se le asigna un ISBN usando el mismo sistema para elegir un dígito de control, y su propósito es catalogar y clasificar los títulos para facilitar su posterior localización y listado a las editoriales, librerías, bibliotecas, universidades, etc. Este es un ejemplo entonces de un código cuyos elementos están dados por series numéricas que codifican información.
Los códigos, son objetos de estudio de diferentes áreas de las matemáticas, como la criptografía y la teoría de cógidos. La primera, se encarga del problema de seguridad en el intercambio de información y datos. Y en la teoría de c\'digos los principales problemas son: construir códigos que puedan corregir un número máximo de errores y construir códigos eficientes en el proceso de codificar y decodificar los mensajes, por ejemplo, podrías decodificar el ISBN y descubrir cuál es uno de mis libros favoritos [Vil15]. En tratar de resolver estos problemas se ha establecido una estrecha relación con otras áreas de las matemáticas, en este artículo hablaremos de la relación con el álgebra conmutativa.
Un vector $c\in C$ se llama palabra del código y el número de elementos en $C$, denotado por $\mid C\mid$ es el tamaño del código. Un código de longitud $n$ y tamaño $k$ se denota como $(n,k)-\text{código}$.
Un ejemplo clásico, es el código binario, que se define en un alfabeto con dos elementos, $A=\{0,1\}$.
De forma muy general, podemos decir que un código es un subespacio vectorial, por lo tanto podemos hablar de la distancia entre sus elementos o palabras. Así que introduciremos la noción de distancia de Hamming.
y definimos $d(x,y)=\sum_{i=1}^{n}d(x_i,y_i)$.
Intuitivamente, un código es mejor si todas las palabras están suficientemente separadas, así que nos interesa conocer la distancia mínima del códidgo.
$$ d(C)={\rm min}\{d(c_1,c_2)\mid c_1,c_2\in C, c_1\neq c_2\}. $$ Es decir, $d(C)$ es el mínimo número de entradas distintas de cero de las palabras de $C\setminus \{0\}$.
En el resto de este texto consideraremos a la distancia mínima como el parámetro más importante, esto debido a que este número mide la cantidad de errores que un código puede detectar y corregir en el proceso de transmisión de un mensaje, además que calcularla resulta ser un problema NP-duroIntuitivamente los problemas NP-duros, son aquellos para los que es difícil (y probablemente imposible) de encontrar algoritmos de tiempo polinomial para comprobarlos o resolverlos. [GKR93].
Una familia de códigos que tiene una estrecha relación con el álgebra conmutativa son los códigos Reed-Muller, su nombre se debe a los matemáticos que los propusieron en el año 1954 en trabajos independientes: I. S. ReedIrving Stoy Reed, matemático e ingeniero estadounidense, 1923 - 2012. y D. E. MullerDavid Eugene Muller, matemático e informático teórico estadounidense, 1924 - 2008.. Se sabe que el primero en realizar su construcción fue Muller [Mul54], mientras que su estudio en detalle y decodificación es obra de Reed [Ree54]. Posteriormente en 1968, fueron generalizados a cualquier campo finito [KLP68; Wel68]. Veamos una visión general de su definición sobre cualquier campo finito $\mathbb{F}_q$. Estos códigos son parte de una familia más grande, los códigos evaluación, cuya definición está basada en una función lineal.
Denotemos por $\mathcal{X}$ a un conjunto de elementos, que llamaremos puntos, $\mathcal{X}$ también se conoce como objeto geométrico.
\begin{equation*}\label{ev-map} {\rm ev}_{\mathcal{P}}\colon V \rightarrow \mathbb{F}^{n}_{q},\ \ \ \ f\mapsto {\rm ev}_{\mathcal{P}}(f)=\left(f(p_1),\ldots, f(P_m)\right). \end{equation*}
Si ${\rm ev}_{\mathcal{P}}$ es una función lineal, entonces la imagen ${\rm ev}_{\mathcal{P}}(V)$ será un $\mathbb{F}_{q}$-subespacio vectorial de $\mathbb{F}_{q}^{n}$, es decir, un código lineal de longitud $n$ sobre $\mathbb{F}_{q}$. El código ${\rm ev}_{\mathcal{P}}(V)$ se llama código de evaluación en $\mathcal{P}$ y sus parámetros pueden deducirse de las propiedades de $V$ como $\mathbb{F}_q$ espacio vectorial.
Los códigos Reed-Muller son un caso particular de códigos evaluación, donde $\mathcal{P}=\mathcal{X}=\mathbb{F}_{q}^{m}$, esto es, un anillo conmutativo unitario con estructura de $\mathbb{F}_q$-espacio vectorial, y $V=\mathbb{F}_{q}[x_1,x_2,\ldots,x_m]$ un anillo de polinomios con la graduación estándarRecordemos que el grado de un polinomo se define de manera general como el grado del monomio de mayor grado y el grado de un monomio es la suma de los exponentes de las indeterminadas que lo forman. que además es un anillo conmutativo y unitario.
No es díficil ver, que el kernel de la evaluación que define a un código Reed-Muller es justo $\{f\in R=\mathbb{F}_{q}[x_1,x_2,\ldots,x_m]\mid f(p)=0, \forall p\in\mathcal{X}\}$ y este conjunto define al ideal de anulación del conjunto $\mathcal{X}$, el cual se denota como $I(\mathcal{X})$. Como consecuencia del primer Teorema de Isomorfismos tenemos que $C={\rm ev}_{\mathcal{P}}(V)\simeq R/I(\mathcal{X})$, esto abre la puerta a dar interpretaciones algebraicas de las propiedades de los códigos.
Por ejemplo, analicemos ahora la distancia mínima de los códigos Reed-Muller, a los que denotaremos como $C={\rm ev}_{\mathcal{P}}(V)$, donde $V=\mathbb{F}_{q}[x_1,x_2,\ldots,x_m]$.
Definimos la distancia mínima, como el mínimo número de entradas distintas de cero de las palabras de un código $C$, en el caso de los códigos Reed-Muller, las palabras son de la forma $v=\left(f(p_1),\ldots, f(p_m)\right)$, es decir las entradas de estas palabras son evaluaciones de un polinomio en un conjunto de puntos. Entonces, contar las entradas distintas de cero, es equivalente a contar el número de puntos en los que se anula un polinomio.
Si $V_{\mathcal{X}}(f)$ denota la variedad algebráica definida por $f$, es decir el conjunto de puntos de $\mathcal{X}$ que se se anulan en $f$, entonces $$ |\mathcal{X}|- |V_{\mathcal{X}}(f)| $$ cuenta el número de puntos de $\mathcal{X}$ en los que $f$ no se anula, así tenemos que la distancia mínima es: $$ d(C)= {\rm min}\{|\mathcal{X}|- |V_{\mathcal{X}}(f)|\colon f\notin I(\mathcal{X})\}=|\mathcal{X}|- {\rm max}\{|V_{\mathcal{X}}(f)|\colon f\notin I(\mathcal{X})\}. $$
Básicamente, el problema de calcular la distancia mínima se reduce a calcular la cardinalidad de la variedad algebraica de un polinomio $f$ respecto a un conjunto de puntos $\mathcal{X}$, $|V_{\mathcal{X}}(f)|$.
Sin muchos detalles, cuando $\mathcal{X}$ es un conjunto finito de puntos en un espacio proyectivo y $f$ un polinomio homogéneo Es un polinomio en que cada uno de sus términos (monomios) tienen el mismo grado., $|V_{\mathcal{X}}(f)|$ se calcula como sigue.
donde $(I(\mathcal{X})\colon f)=\{h\in S|h f\in I(\mathcal{X})\}$ es el ideal cociente y en general $\deg (R/I)$ denota al grado o multiplicidad de Hilbert-Samuel de $S/I$, un invariante algebraico que esta presente y tiene implicaciones importantes en otras áreas de las matemáticas como la geometría algebraica (en el estudio de singularidades) y la combinatoria (relación con invariantes de grafos). Una buena referencia para ver los detalles de estas ideas es [MPV17] y otras generalizaciones se pueden consultar en [NPV18; NPV20].
Este resultado, en particular nos proporciona una interpretación algebraica de la distancia mínima de códigos Reed-Muller, y así como esta, podemos obtener más interpretaciones de los parámetros y propiedades de códigos, usando ideas y herramientas algebraicas muy poderosas.
El desarrollo de estas ideas (con poca formalidad) en este documento, es una invitación para interesarse en estudiar estos tópicos que se encuentran entre el álgebra conmutativa y la teoría de códigos, dos áreas de las matemáticas que en la actualidad son muy fructíferas en México.
