Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

Résumé technique : Au-delà des polynômes : Codes localement réparables optimaux à partir de bonnes fonctions rationnelles

Énoncé du problème
Les codes localement réparables (LRC) sont essentiels pour les systèmes de stockage distribué et cloud, où la capacité de récupérer une seule coordonnée effacée en accédant à un petit nombre d'autres coordonnées (localité $r$) est critique. La limite fondamentale sur les paramètres d'un LRC $(n, k, r)$ est la borne de type Singleton : $d \le n - k - \lceil k/r \rceil + 2$. Les codes satisfaisant cette borne sont qualifiés d'« optimaux ».

Le paradigme de construction dominant pour les LRC optimaux, introduit par Tamo et Barg, repose sur les « bons polynômes ». Un polynôme $f \in \mathbb{F}_q[X]$ est $(r, l)$-bon s'il est de degré $r+1$ et constant sur $l$ sous-ensembles disjoints de taille $r+1$. Le nombre de tels sous-ensembles, $l$, détermine la longueur du code $n = (r+1)l$. Cependant, la construction de bons polynômes avec un $l$ élevé est contrainte par les propriétés arithmétiques du corps fini et la structure du groupe de Galois associé au polynôme (spécifiquement, le groupe de monodromie arithmétique). Pour les polynômes de degré $r+1$, le groupe de Galois est souvent grand (approchant le groupe symétrique $S_{r+1}$), ce qui limite le nombre de places rationnelles totalement décomposées et, par conséquent, la longueur de code réalisable.

Méthodologie
Cet article propose une généralisation du cadre Tamo-Barg en remplaçant les bons polynômes par des bonnes fonctions rationnelles. La méthodologie intègre la théorie des corps de fonctions algébriques et la théorie de Galois pour analyser et construire ces fonctions.

1. Définition des bonnes fonctions rationnelles : Les auteurs définissent une fonction rationnelle $h(x) \in \mathbb{F}_q(x)$ comme étant $(r, l)$-bonne si elle est de degré $r+1$ et constante sur $l$ sous-ensembles disjoints de la droite projective $\mathbb{P}^1(\mathbb{F}_q)$, chacun de taille $r+1$.
2. Immersion dans la théorie des corps de fonctions : Le problème de la maximisation de $l$ est intégré dans la théorie des corps de fonctions algébriques. Spécifiquement, $l$ correspond au nombre de places rationnelles totalement décomposées, noté $\#T^1_{split}(h)$, dans l'extension $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$.
3. Analyse théorique de Galois : Les auteurs analysent le comportement de décomposition des places en considérant la clôture galoisienne $M_h$ de l'extension. Ils dérivent une formule pour $\#T^1_{split}(h)$ utilisant la fonction zêta et les séries L d'Artin, montrant que :
   $$\#T^1_{split}(h) \approx \frac{q}{\#G_h}$$
   où $G_h$ est le groupe de Galois de l'extension.
4. Stratégie d'optimisation : Contrairement aux polynômes, où le groupe de Galois est souvent grand, les auteurs se concentrent sur la construction de fonctions rationnelles pour lesquelles l'extension $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$ est elle-même une extension galoisienne avec une taille minimale de groupe de Galois ($\#G_h = r+1$). Cela est réalisé en utilisant des sous-groupes du groupe d'automorphismes du corps de fonctions rationnelles, $\text{PGL}(2, q)$.
5. Construction explicite : L'article construit des familles explicites de bonnes fonctions rationnelles en utilisant des sous-groupes cycliques de $\text{PGL}(2, q)$. Pour une transformation $\phi \in \text{PGL}(2, q)$ d'ordre $r+1$, la fonction $h(x) = \sum_{i=0}^r \phi^i(x)$ est montrée comme générant une extension galoisienne avec les propriétés désirées.

Contributions et résultats clés

• Cadre unifié : L'article établit un cadre unifié pour la construction de LRC optimaux basés sur des fonctions rationnelles bonnes, étendant le paradigme Tamo-Barg.
• Bornes quantitatives : En utilisant la borne de Hasse-Weil et la formule de Riemann-Hurwitz, les auteurs dérivent des bornes inférieures explicites pour le nombre de places rationnelles totalement décomposées. Ils prouvent que pour une bonne fonction rationnelle $h$ de degré $r+1$, le paramètre $l$ satisfait :
  $$l \ge \frac{q - 2\sqrt{q} + 1}{(r+1)!} - \text{termes de correction}$$
  Cependant, dans le cas spécifique des extensions galoisiennes, la borne est significativement plus serrée.
• Caractérisation du cas galoisien : Lorsque l'extension est galoisienne, les auteurs fournissent une caractérisation exacte de $\#T^1_{split}(h)$ basée sur la structure des orbites de l'action du groupe de Galois sur $\mathbb{P}^1(\mathbb{F}_q)$. Ils montrent que le nombre de places totalement décomposées est approximativement $q/(r+1)$, ce qui est un facteur de $(r)!$ plus grand que le cas polynômial typique où la taille du groupe est $(r+1)!$.
• Constructions explicites :
  • Degré 3 ($r=2$) : L'article construit une fonction rationnelle $h(x) = \frac{x^3 - 3w^2x + w^3}{x(x-w)}$. Selon $q \pmod 3$, cela produit des LRC de longueur $q$, $q-1$ ou $q+1$. Spécifiquement, si $q \equiv 2 \pmod 3$, la longueur du code est $q+1$.
  • Degré 4 ($r=3$) : Une fonction rationnelle $h(x) = \frac{4x^4 - 12d^2x^2 + 8d^3x - d^4}{2x(x-d)(2x-d)}$ est construite. Si $q \equiv 3 \pmod 4$, le code résultant a une longueur $q+1$.
• Optimalité : Les codes construits sont optimaux, satisfaisant la borne de type Singleton. Crucialement, pour des paramètres de localité spécifiques ($r=2, 3$) et des caractéristiques de corps, ces constructions atteignent la longueur de code maximale possible de $n = q+1$ (évaluation sur toute la droite projective), ce qui est strictement supérieur à ce qui est généralement réalisable avec des bons polynômes du même degré.

Signification et affirmations
L'article affirme que l'introduction des bonnes fonctions rationnelles représente une avancée fondamentale par rapport à l'approche classique basée sur les polynômes. La signification principale réside dans la capacité à contrôler directement la taille du groupe de Galois. Alors que les bons polynômes sont contraints par de grands groupes de monodromie (souvent $S_{r+1}$), les fonctions rationnelles construites via des sous-groupes de $\text{PGL}(2, q)$ peuvent atteindre la taille minimale possible d'un groupe transitif ($r+1$).

Cette réduction de la taille du groupe conduit à une augmentation substantielle du nombre de places rationnelles totalement décomposées, permettant ainsi la construction de LRC avec des longueurs significativement plus grandes ($n \approx q$) pour la même localité $r$. Les auteurs soulignent que leur méthode fournit des familles infinies de LRC optimaux avec des paramètres surpassant strictement ceux issus de la construction Tamo-Barg pour le même degré. L'approche est présentée comme une « extension naturelle et puissante » qui exploite le cadre algébrique et géométrique plus riche de la droite projective et des fonctions rationnelles pour surmonter les limitations inhérentes aux constructions polynomiales.