Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions
Hengfeng Liu, Sihem Mesnager, Chunming Tang, Xuemin Zheng · 2026
Read Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions by Hengfeng Liu, Sihem Mesnager, Chunming Tang, Xuemin Zheng (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11465.txt.
Introduction
Liu and three colleagues generalize the Tamo-Barg construction of optimal locally recoverable codes, used in distributed and cloud storage. The classical construction rests on good polynomials. The team introduces good rational functions and a broader framework for optimal codes. They study attainable lengths with function field and Galois theory, counting totally split rational places. Exact formulas, sharp bounds and explicit constructions in Galois and non-Galois settings yield codes longer than good polynomials of the same degree allow.
Catalog record
| CREATOR | Hengfeng Liu, Sihem Mesnager, Chunming Tang, Xuemin Zheng |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 73488 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11465
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions Hengfeng Liu, Sihem Mesnager, Chunming Tang, Xuemin Zheng Abstract Locally recoverable codes (LRCs) have emerged as fundamental objects in modern coding theory, primarily due to their pivotal role in distributed and cloud storage systems. A major breakthrough in their construction was achieved by Tamo and Barg, who introduced the notion of good polynomials as a key structural ingredient. In this article, we propose a natural generalization of this paradigm by introducing the concept of good rational functions . Building upon this extension, we develop a unified and flexible framework for constructing optimal LRCs. To quantify the quality of a rational function, we embed the problem into the rich context of algebraic function field theory and Galois theory. This perspective allows us to extend the Galois-theoretic framework originally developed by Micheli for good polynomials. In particular, we derive structural and quantitative results on the number of totally split rational places associated with rational functions. Furthermore, we construct explicit families of good rational functions that outperform all good polynomials of the same degree. As a consequence, we obtain infinite families of optimal LRCs with improved parameters compared to those arising from the classical Tamo-Barg construction. These results highlight the intrinsic strength of our approach. 1 Introduction Let q be a prime power, and let \mathbb{F}_{q} denote the finite field with q elements. Let n,k,r be positive integers. An (n,k,r) -locally recoverable code (LRC) \mathcal{C} is defined as a k -dimensional linear subspace of \mathbb{F}_{q}^{n} with the property that any erased coordinate of a codeword c\in\mathcal{C} can be recovered by accessing at most r other coordinates. The parameter r is referred to as the locality of \mathcal{C} , and it measures the efficiency of the local repair process. In particular, smaller values of r correspond to more efficient recovery procedures, which is a key requirement in applications such as distributed storage systems. Locally recoverable codes (LRCs) have attracted significant attention due to their fundamental role in distributed and cloud storage systems, where efficient data recovery is crucial [ 1 ] , [ 10 ] , [ 24 ] , [ 28 ] . Over the past decade, LRCs have been extensively studied from both theoretical and practical perspectives, leading to a rich literature on their constructions, bounds, and structural properties [ 2 ] , [ 3 ] , [ 8 ] , [ 13 ] , [ 16 ] , [ 20 ] , [ 24 ] , [ 29 ] , [ 31 ] , as well as recent advances [ 9 ] , [ 11 ] , [ 12 ] , [ 21 ] , [ 22 ] , [ 23 ] , [ 26 ] , [ 30 ] . A fundamental limitation on the parameters of LRCs was established by Gopalan et al. [ 10 ] , who proved that the minimum distance d\left(\mathcal{C}\right) satisfies d\left(\mathcal{C}\right)\leqslant n-k-\left\lceil\frac{k}{r}\right\rceil+2. This inequality is known as the Singleton-type bound for LRCs. Codes attaining this bound are called optimal , and constructing such codes with flexible parameters remains a central challenge in coding theory. Among the various construction paradigms, a particularly influential framework was introduced by Tamo and Barg [ 28 ] , where the notion of a good polynomial plays a pivotal role. Intuitively, a polynomial is considered good if it exhibits a strong regularity property on suitably chosen subsets of \mathbb{F}_{q} . More precisely, a polynomial f\in\mathbb{F}_{q}[X] is said to be (r,l) -good ( l>0 ) if • f has degree r+1 , • there exist l disjoint subsets A_{1},\ldots,A_{l} in \mathbb{F}_{q} , with |A_{i}|=r+1 ( 1\leq i\leq l ), such that f is constant on each A_{i} . This structural property allows one to partition evaluation points into local groups, which is the key mechanism underlying locality. The Tamo–Barg construction is realized via generalized Reed–Solomon codes. For a message a\in\mathbb{F}_{q}^{k} (written as a_{ij} , where 0\leq i\leq r-1 , 0\leq j\leq\frac{k}{r}-1 ), the encoding polynomial is given by f_{a}(x)=\sum_{i=0}^{r-1}\sum_{j=0}^{\frac{k}{r}-1}a_{ij}f(x)^{j}x^{i}. The LRC is obtained by evaluating f_{a} on the set A=\bigcup_{i=1}^{\ell}A_{i} , namely, \mathcal{C}=\left\{\big(f_{a}(x):x\in A\big)\mid a\in\mathbb{F}_{q}^{k}\right\}. Such an (n,k,r) -LRC is optimal, with parameters n=(r+1)l and k=tr ( t\leq l ). In addition, [ 28 ] provided explicit constructions of good polynomials arising from additive and multiplicative subgroups of \mathbb{F}_{q} , under certain arithmetic constraints on (q,r) . In particular, r+1 must divide either q-1 or q , or be expressible as a product of divisors of these quantities. These constraints motivated further generalizations. In this direction, Liu, Mesnager, and Chen [ 17 ] proposed a broader construction method based on function composition. Moreover, Liu, Mesnager, and Tang [ 18 ] showed that good polynomials can be constructed using Dickson polynomials and their compositions, thereby enriching the available families. To construct LRCs with a wide range of lengths and dimensions, it is crucial to identify good polynomials that are constant on as many (r+1) -subsets as possible. To quantify this property, for a polynomial f\in\mathbb{F}_{q}[X] , one defines l_{f}=\#\left\{t_{0}\in\mathbb{F}_{q}\mid f-t_{0}\;\text{has $\deg(f)$ distinct roots in $\mathbb{F}_{q}$}\right\}. (1) This quantity measures the number of fibers of maximal size under the map induced by f . It is immediate that l_{f}\leq q/\deg(f) . A key breakthrough in understanding this parameter was achieved by Micheli [ 24 ] , who interpreted l_{f} within the framework of algebraic function field theory. More precisely, l_{f} coincides with the number \#T^{1}_{split}(f) of totally split rational places in the global function field extension \mathbb{F}_{q}(x)/\mathbb{F}_{q}(t) defined by f(x)=t . Using a density argument, [ 24 ] derived the asymptotic estimate \#T^{1}_{split}(f)=\frac{q}{\#G_{f}}+O(\sqrt{q}), where G_{f} denotes the arithmetic monodromy group of f , that is, the Galois group of f-t over \mathbb{F}_{q}(t) . This viewpoint reveals that the construction of good polynomials is closely related to controlling the size and structure of their associated Galois groups. In Micheli’s work [ 24 ] , several classes of good polynomials of low degree were constructed, together with lower bounds on l_{f} . This line of research was further developed by Chen, Mesnager, and Zhao [ 5 ] , who completely characterized good polynomials of low degree over finite fields and determined their corresponding values of l_{f} . Subsequently, Dukes, Ferraguti, and Micheli [ 8 ] extended these results using an independent Galois-theoretic approach, determining l_{f} for all good polynomials of degree up to 5 . Building on these developments, Chen and Mesnager [ 6 ] refined the Galois-theoretic framework by characterizing polynomials with minimal Galois groups and deriving explicit formulas for l_{f} in several important cases, most notably for Dickson polynomials. These results naturally raise the question of whether broader classes of functions, beyond polynomials, can provide improved constructions of LRCs with better parameters. This question serves as one of the main motivations for the present work. 1.1 Motivations and objectives of this paper Motivated by the limitations inherent in polynomial-based constructions, we propose in this paper a natural and powerful extension of the notion of good polynomial to that of good rational function . Unlike polynomials, rational functions naturally take values on the projective line \mathbb{P}^{1}(\mathbb{F}_{q})=\mathbb{F}_{q}\cup\left\{\infty\right\} , thereby offering a richer algebraic and geometric framework. Building upon this generalized notion, we develop a novel