Resumen de New insights into the study of flag codes
El uso de códigos flag en el contexto de la codificación de red fue introducido por Liebhold et al. en 2018 en su trabajo [54], donde esta nueva familia de códigos se presenta como generalización de los códigos de subespacio de dimensión constante, ampliamente estudiados desde su introducción en 2008 por Koetter y Kschischang (véase [45]).
Un flag es una sucesión de subespacios vectoriales encajados de un espacio finitodimensional sobre un cuerpo también finito. La secuencia de dimensiones de los subespacios del flag es su "tipo" y el número de subespacios en un flag es su "longitud". El conjunto de flags de un mismo tipo tiene estructura de espacio métrico, dotado de la llamada distancia de flags.
Un código flag de tipo constante es un conjunto no vacío de flags del mismo tipo. En particular, un código flag de longitud r=1 es un código de dimensión constante. En su trabajo pionero [54], los autores introducen esta nueva familia de códigos, establecen un canal adecuado para el envío de flags y presentan varias construcciones orbitales, es decir, códigos flag obtenidos como la órbita generada por un flag bajo la acción de un subgrupo del grupo general lineal sobre la variedad de flags correspondiente.
Para la elaboración de esta tesis, hemos abordado el estudio de los códigos flag, intentando siempre extraer relaciones entre estos y sus correspondientes códigos proyectados. Dado un código flag, sus códigos proyectados (de subespacio) son códigos de dimensión constante obtenidos por proyección de los flags del código en la dimensión correspondiente. Esta familia de códigos de subespacio se obtiene de forma natural a partir de un código flag prefijado. Sin embargo, en general, los códigos proyectados no dan una información perfecta del código flag de partida. Por ello, a lo largo de nuestros trabajos, hemos dado condiciones o hemos centrado nuestro estudio en familias que permiten obtener relaciones entre los parámetros de un código flag y los de sus códigos proyectados.
Este estudio ha dado lugar a nueve trabajos de investigación, cinco de ellos ya publicados, en los que tratamos diferentes aspectos de la teoría de códigos flag. En primer lugar, los artículos [6, 8, 9, 59] se centran en el estudio de los códigos flag de distancia óptima (ODFCs). Estos códigos presentan gran interés desde el punto de vista de la aplicabilidad, pues son los que mayor capacidad correctora de errores presentan. En primer lugar, en nuestro artículo [8], introducimos esta familia de códigos y presentamos la primera caracterización de los mismos, en términos de los códigos proyectados y de la propiedad de disyunción en códigos flag. Además, en el mismo trabajo, determinamos que aquellos ODFC que tienen un código (de dimensión constante) spread como proyectado son los de mayor cardinal. A continuación, damos una construcción sistemática y un algoritmo de decodificación para códigos ODFCs de tipo completo, es decir (1,2, ..., n-1) con n=2k y un spread de dimensión k como código proyectado.
Este estudio es posteriormente generalizado en nuestro trabajo [9] donde, para cada divisor k de n (n=ks, para algún entero positivo s>1), damos construcciones de códigos ODFCs con un código spread de dimensión k como proyectado. Esta construcción se basa en resultados clásicos de la teoría de grafos; más concretamente, sobre emparejamientos prefectos en grafos bipartitos y regulares, junto con técnicas de reducción del cuerpo.
Por otra parte, en nuestros trabajos [6, 59] planteamos la construcción orbital de estos códigos. Para ello, en primer lugar, utilizamos construcciones orbitales existentes de códigos (de subespacio) spread, bajo la acción de grupos conocidos y estudiamos en qué condiciones podemos extender dicha acción (o la de ciertos subgrupos) a los códigos flag del tipo correspondiente. En [6], abordamos este problema para la misma elección de los parámetros que en [8]. Por otra parte, en [59] damos construcciones para el caso planteado en [9]. Además, en este trabajo, presentamos una nueva caracterización de códigos ODFCs en función de, a lo sumo, dos códigos proyectados y damos también construcciones orbitales de ODFCs de máximo cardinal utilizando la acción de un grupo de Singer adecuado y un código spread parcial como proyectado.
La acción de grupos de Singer en el contexto de los códigos flag es también utilizada en nuestros trabajos [4, 5] donde trabajamos con la acción natural del grupo multiplicativo de un cuerpo finito sobre flags. Este enfoque, que generaliza las ideas desarrolladas en [25], permite obtener resultados sobre códigos flag en términos del mayor subcuerpo sobre el que todos los subespacios de un flag tienen estructura de espacio vectorial: el mejor amigo del flag (véase [4]). En este mismo trabajo, introducimos los códigos flag (orbitales cíclicos) de Galois, es decir, aquellos en los que el flag generador es una sucesión de subcuerpos encajados de un cuerpo finito prefijado. Para esta familia de códigos, determinamos el conjunto de distancias posibles y establecemos qué subgrupos del grupo de Singer permiten obtener cada una de dichas distancias. Por último, también damos condiciones necesarias sobre el vector tipo de códigos ODFCs construidos como órbitas bajo la acción de este grupo o sus subgrupos. El estudio de los códigos flag de Galois y, en particular, la buena relación entre sus posibles distancias y el conjunto de subgrupos del grupo multiplicativo de un cuerpo finito motiva el trabajo que presentamos en [5], donde trabajamos con códigos flag orbitales en los que el flag generador contiene, al menos, un subcuerpo entre sus subespacios, pero no todos ellos son cuerpo. Los llamamos códigos de Galois generalizados. En primer lugar, probamos que la presencia de cuerpos en el flag generador limita enormemente el rango de posibles distancias para un código de Galois generalizado y establecemos su conjunto de distancias potenciales. Además, al contrario de lo que ocurre con los códigos flag de Galois, mostramos que no todas las distancias potenciales son realmente alcanzables. Por último, presentamos construcciones sistemáticas de estos códigos.
La relación entre códigos flag y sus proyectados, si bien es cierto que se encuentra presente a lo largo de todos los trabajos anteriores, cobra un protagonismo evidente en [3]. En dicho trabajo presentamos la familia de los códigos flags consistentes en la que los códigos proyectados determinan de forma unívoca los parámetros del código flag de partida. Además, probamos que los ODFCs son, en particular, consistentes. También generalizamos los conceptos de código equidistante y código sunflower al contexto de los códigos flag y probamos que, bajo la condición de consistencia, estas propiedades se transfieren perfectamente de los códigos flag a sus proyectados y viceversa. Por último, presentamos un algoritmo de decodificación basado en la propiedad de consistencia.
Uno de los problemas centrales de la teoría de códigos correctores de errores es determinar cuántos mensajes distintos podemos codificar a través de códigos con una capacidad correctora prefijada. En otras palabras: fijado el valor de la distancia d, queremos saber cuál es el máximo cardinal posible de entre todos los códigos con distancia mínima d. En el contexto de los códigos flag, esta cuestión ha sido abordada por Kurz en su trabajo [47] para el tipo completo. En nuestro caso, observamos que, para poder decir algo más al respecto, necesitamos estudiar en detalle el parámetro distancia de flags. Esta distancia se define como suma de distancias de subespacio. Por ello, no solo es importante el valor numérico de la distancia mínima de un código flag sino qué sumandos intervienen a la hora de alcanzarla. Así surge el concepto de vector distancia en nuestro trabajo [7]. En primer lugar, probamos que no cualquier vector es un vector distancia y caracterizamos numéricamente aquellos vectores que sí representan configuraciones válidas de la distancia entre flags. A continuación, estudiamos cómo fluctúa la distancia a medida que forzamos a los vectores distancia a contener ceros en posiciones prefijadas. Este estudio se relaciona con nuevas nociones de disyunción de códigos flag, también introducidas en [7] , y nos permite extraer cotas superiores para el cardinal de códigos flag con un valor prefijado de la distancia para cualquier elección de los parámetros.
Por último, en nuestro trabajo [2], presentamos un enfoque combinatorio que permite relacionar el parámetro distancia de flags con diagramas de Ferrers y otros objetos provenientes de la teoría de particiones. En este caso, proponemos una representación gráfica de la distancia de flags, a través de los llamados caminos de distancia (en un soporte de distancia adecuado). Por construcción, el valor de la distancia asociado a cierto camino de distancia corresponde al número de puntos del soporte que quedan en o por debajo del camino. Resulta llamativo que la cantidad complementaria a la distancia, la codistancia, que coincide con el número de puntos del soporte que quedan por encima del camino, esconde cierta una estructura combinatoria hasta ahora desconocida. Para desentrañarla, en nuestro trabajo [2], asociamos un diagrama de Ferrers marco construido ad hoc que permite leer la codistancia o, equivalentemente, la distancia entre flags, en términos de particiones de enteros asociadas a ciertos subdiagramas de Ferrers. Este puente entre la teoría de códigos flag y la combinatoria abre la puerta al estudio de códigos desde esta nueva perspectiva. En particular, en nuestro trabajo utilizamos este nuevo “diccionario” para establecer conexiones entre los parámetros (cardinal y distancia mínima) de códigos flag y los de sus códigos proyectados, en ambas direcciones, a través de nuevos objetos combinatorios asociados a un código flag, como sus conjuntos de diagramas de Ferrers o de rectángulos de Durfee.
