Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

Resumen Técnico: Más allá de los polinomios: Códigos Óptimos Localmente Recuperables a partir de Funciones Racionales Bona

Enunciado del Problema
Los códigos localmente recuperables (LRCs) son esenciales para sistemas de almacenamiento distribuido y en la nube, donde la capacidad de recuperar una única coordenada borrada accediendo a un pequeño número de otras coordenadas (localidad $r$) es crítica. El límite fundamental sobre los parámetros de un LRC $(n, k, r)$ es el límite de tipo Singleton: $d \le n - k - \lceil k/r \rceil + 2$. Los códigos que cumplen este límite se denominan "óptimos".

El paradigma de construcción dominante para LRCs óptimos, introducido por Tamo y Barg, se basa en "polinomios bona". Un polinomio $f \in \mathbb{F}_q[X]$ es $(r, l)$-bono si tiene grado $r+1$ y es constante en $l$ subconjuntos disjuntos de tamaño $r+1$. El número de tales subconjuntos, $l$, determina la longitud del código $n = (r+1)l$. Sin embargo, la construcción de polinomios bona con $l$ grande está restringida por las propiedades aritméticas del cuerpo finito y la estructura del grupo de Galois asociado al polinomio (específicamente, el grupo de monodromía aritmética). Para polinomios de grado $r+1$, el grupo de Galois suele ser grande (acercándose al grupo simétrico $S_{r+1}$), lo que limita el número de lugares racionales totalmente descompuestos y, en consecuencia, la longitud de código alcanzable.

Metodología
Este artículo propone una generalización del marco de Tamo-Barg reemplazando los polinomios bona por funciones racionales bona. La metodología integra la teoría de cuerpos de funciones algebraicas y la teoría de Galois para analizar y construir estas funciones.

1. Definición de Funciones Racionales Bona: Los autores definen una función racional $h(x) \in \mathbb{F}_q(x)$ como $(r, l)$-bona si tiene grado $r+1$ y es constante en $l$ subconjuntos disjuntos de la recta proyectiva $\mathbb{P}^1(\mathbb{F}_q)$, cada uno de tamaño $r+1$.
2. Inmersión en Cuerpos de Funciones: El problema de maximizar $l$ se incrusta en la teoría de cuerpos de funciones algebraicas. Específicamente, $l$ corresponde al número de lugares racionales totalmente descompuestos, denotado $\#T^1_{split}(h)$, en la extensión $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$.
3. Análisis Teórico-Galoisiano: Los autores analizan el comportamiento de descomposición de los lugares considerando el cierre de Galois $M_h$ de la extensión. Derivan una fórmula para $\#T^1_{split}(h)$ utilizando la función Zeta y las series L de Artin, mostrando que:
   $$\#T^1_{split}(h) \approx \frac{q}{\#G_h}$$
   donde $G_h$ es el grupo de Galois de la extensión.
4. Estrategia de Optimización: A diferencia de los polinomios, donde el grupo de Galois suele ser grande, los autores se centran en construir funciones racionales donde la extensión $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$ es en sí misma una extensión de Galois con un tamaño de grupo de Galois mínimo ($\#G_h = r+1$). Esto se logra utilizando subgrupos del grupo de automorfismos del cuerpo de funciones racionales, $\text{PGL}(2, q)$.
5. Construcción Explícita: El artículo construye familias explícitas de funciones racionales bona utilizando subgrupos cíclicos de $\text{PGL}(2, q)$. Para una transformación $\phi \in \text{PGL}(2, q)$ de orden $r+1$, se demuestra que la función $h(x) = \sum_{i=0}^r \phi^i(x)$ genera una extensión de Galois con las propiedades deseadas.

Contribuciones y Resultados Clave

• Marco Unificado: El artículo establece un marco unificado para construir LRCs óptimos basados en funciones racionales bona, extendiendo el paradigma de Tamo-Barg.
• Límites Cuantitativos: Utilizando el límite de Hasse-Weil y la fórmula de Riemann-Hurwitz, los autores derivan cotas inferiores explícitas para el número de lugares racionales totalmente descompuestos. Demuestran que para una función racional bona $h$ de grado $r+1$, el parámetro $l$ satisface:
  $$l \ge \frac{q - 2\sqrt{q} + 1}{(r+1)!} - \text{términos de corrección}$$
  Sin embargo, en el caso específico de extensiones de Galois, la cota es significativamente más ajustada.
• Caracterización del Caso Galoisiano: Cuando la extensión es de Galois, los autores proporcionan una caracterización exacta de $\#T^1_{split}(h)$ basada en la estructura de órbitas de la acción del grupo de Galois sobre $\mathbb{P}^1(\mathbb{F}_q)$. Demuestran que el número de lugares totalmente descompuestos es aproximadamente $q/(r+1)$, lo cual es un factor de $(r)!$ mayor que en el caso típico de polinomios donde el tamaño del grupo es $(r+1)!$.
• Construcciones Explícitas:
  • Grado 3 ($r=2$): El artículo construye una función racional $h(x) = \frac{x^3 - 3w^2x + w^3}{x(x-w)}$. Dependiendo de $q \pmod 3$, esto produce LRCs de longitud $q$, $q-1$ o $q+1$. Específicamente, si $q \equiv 2 \pmod 3$, la longitud del código es $q+1$.
  • Grado 4 ($r=3$): Se construye una función racional $h(x) = \frac{4x^4 - 12d^2x^2 + 8d^3x - d^4}{2x(x-d)(2x-d)}$. Si $q \equiv 3 \pmod 4$, el código resultante tiene longitud $q+1$.
• Optimalidad: Los códigos construidos son óptimos, cumpliendo el límite de tipo Singleton. Crucialmente, para parámetros de localidad específicos ($r=2, 3$) y características de cuerpo, estas construcciones alcanzan la longitud de código máxima posible de $n = q+1$ (evaluación en toda la recta proyectiva), lo cual es estrictamente mayor que lo que típicamente se puede lograr con polinomios bona del mismo grado.

Significado y Afirmaciones
El artículo afirma que la introducción de funciones racionales bona representa un avance fundamental sobre el enfoque clásico basado en polinomios. El significado principal radica en la capacidad de controlar directamente el tamaño del grupo de Galois. Mientras que los polinomios bona están restringidos por grupos de monodromía grandes (a menudo $S_{r+1}$), las funciones racionales construidas mediante subgrupos de $\text{PGL}(2, q)$ pueden alcanzar el tamaño de grupo transitivo mínimo posible ($r+1$).

Esta reducción en el tamaño del grupo conduce a un aumento sustancial en el número de lugares racionales totalmente descompuestos, permitiendo así la construcción de LRCs con longitudes significativamente mayores ($n \approx q$) para la misma localidad $r$. Los autores enfatizan que su método proporciona familias infinitas de LRCs óptimos con parámetros que superan estrictamente a los que surgen de la construcción de Tamo-Barg para el mismo grado. El enfoque se presenta como una "extensión natural y poderosa" que aprovecha el marco algebraico y geométrico más rico de la recta proyectiva y las funciones racionales para superar las limitaciones inherentes a las construcciones polinómicas.