Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

Technical Summary: Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

Problem Statement
Locally recoverable codes (LRCs) are essential for distributed and cloud storage systems, where the ability to recover a single erased coordinate by accessing a small number of other coordinates (locality $r$) is critical. The fundamental limit on the parameters of an $(n, k, r)$-LRC is the Singleton-type bound: $d \le n - k - \lceil k/r \rceil + 2$. Codes meeting this bound are termed "optimal."

The dominant construction paradigm for optimal LRCs, introduced by Tamo and Barg, relies on "good polynomials." A polynomial $f \in \mathbb{F}_q[X]$ is $(r, l)$-good if it has degree $r+1$ and is constant on $l$ disjoint subsets of size $r+1$. The number of such subsets, $l$, determines the code length $n = (r+1)l$. However, constructing good polynomials with large $l$ is constrained by the arithmetic properties of the finite field and the structure of the polynomial's associated Galois group (specifically, the arithmetic monodromy group). For polynomials of degree $r+1$, the Galois group is often large (approaching the symmetric group $S_{r+1}$), which limits the number of totally split rational places and, consequently, the achievable code length.

Methodology
This paper proposes a generalization of the Tamo-Barg framework by replacing good polynomials with good rational functions. The methodology integrates algebraic function field theory and Galois theory to analyze and construct these functions.

1. Definition of Good Rational Functions: The authors define a rational function $h(x) \in \mathbb{F}_q(x)$ as $(r, l)$-good if it has degree $r+1$ and is constant on $l$ disjoint subsets of the projective line $\mathbb{P}^1(\mathbb{F}_q)$, each of size $r+1$.
2. Function Field Embedding: The problem of maximizing $l$ is embedded into the theory of algebraic function fields. Specifically, $l$ corresponds to the number of totally split rational places, denoted $\#T^1_{split}(h)$, in the extension $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$.
3. Galois-Theoretic Analysis: The authors analyze the splitting behavior of places by considering the Galois closure $M_h$ of the extension. They derive a formula for $\#T^1_{split}(h)$ using the Zeta function and Artin L-series, showing that:
   $$\#T^1_{split}(h) \approx \frac{q}{\#G_h}$$
   where $G_h$ is the Galois group of the extension.
4. Optimization Strategy: Unlike polynomials, where the Galois group is often large, the authors focus on constructing rational functions where the extension $\mathbb{F}_q(x)/\mathbb{F}_q(h(x))$ is itself a Galois extension with a minimal Galois group size ($\#G_h = r+1$). This is achieved by utilizing subgroups of the automorphism group of the rational function field, $\text{PGL}(2, q)$.
5. Explicit Construction: The paper constructs explicit families of good rational functions using cyclic subgroups of $\text{PGL}(2, q)$. For a transformation $\phi \in \text{PGL}(2, q)$ of order $r+1$, the function $h(x) = \sum_{i=0}^r \phi^i(x)$ is shown to generate a Galois extension with the desired properties.

Key Contributions and Results

• Unified Framework: The paper establishes a unified framework for constructing optimal LRCs based on good rational functions, extending the Tamo-Barg paradigm.
• Quantitative Bounds: Using the Hasse-Weil bound and the Riemann-Hurwitz formula, the authors derive explicit lower bounds for the number of totally split rational places. They prove that for a good rational function $h$ of degree $r+1$, the parameter $l$ satisfies:
  $$l \ge \frac{q - 2\sqrt{q} + 1}{(r+1)!} - \text{correction terms}$$
  However, in the specific case of Galois extensions, the bound is significantly tighter.
• Galois Case Characterization: When the extension is Galois, the authors provide an exact characterization of $\#T^1_{split}(h)$ based on the orbit structure of the Galois group action on $\mathbb{P}^1(\mathbb{F}_q)$. They show that the number of totally split places is approximately $q/(r+1)$, which is a factor of $(r)!$ larger than the typical polynomial case where the group size is $(r+1)!$.
• Explicit Constructions:
  • Degree 3 ($r=2$): The paper constructs a rational function $h(x) = \frac{x^3 - 3w^2x + w^3}{x(x-w)}$. Depending on $q \pmod 3$, this yields LRCs of length $q$, $q-1$, or $q+1$. Specifically, if $q \equiv 2 \pmod 3$, the code length is $q+1$.
  • Degree 4 ($r=3$): A rational function $h(x) = \frac{4x^4 - 12d^2x^2 + 8d^3x - d^4}{2x(x-d)(2x-d)}$ is constructed. If $q \equiv 3 \pmod 4$, the resulting code has length $q+1$.
• Optimality: The constructed codes are optimal, meeting the Singleton-type bound. Crucially, for specific locality parameters ($r=2, 3$) and field characteristics, these constructions achieve the maximum possible code length of $n = q+1$ (evaluation on the entire projective line), which is strictly greater than what is typically achievable with good polynomials of the same degree.

Significance and Claims
The paper claims that the introduction of good rational functions represents a fundamental advancement over the classical polynomial-based approach. The primary significance lies in the ability to control the Galois group size directly. While good polynomials are constrained by large monodromy groups (often $S_{r+1}$), rational functions constructed via $\text{PGL}(2, q)$ subgroups can achieve the minimal possible transitive group size ($r+1$).

This reduction in group size leads to a substantial increase in the number of totally split rational places, thereby enabling the construction of LRCs with significantly longer lengths ($n \approx q$) for the same locality $r$. The authors emphasize that their method provides infinite families of optimal LRCs with parameters that strictly outperform those arising from the Tamo-Barg construction for the same degree. The approach is presented as a "natural and powerful extension" that leverages the richer algebraic and geometric framework of the projective line and rational functions to overcome the limitations inherent in polynomial constructions.