arxiv: 2605.11465 · v1 · submitted 2026-05-12 · 💻 cs.IT · math.IT

Recognition: 2 theorem links

· Lean Theorem

Beyond Polynomials: Optimal Locally Recoverable Codes from Good Rational Functions

Hengfeng Liu , Sihem Mesnager , Chunming Tang , Xuemin Zheng

Authors on Pith no claims yet

Pith reviewed 2026-05-13 02:00 UTC · model grok-4.3

classification 💻 cs.IT math.IT

keywords locally recoverable codesoptimal LRCsgood rational functionsalgebraic function fieldsGalois theoryTamo-Barg constructionrational functionsdistributed storage

0 comments

The pith

Good rational functions enable infinite families of optimal locally recoverable codes with better parameters than good polynomials.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper introduces good rational functions as a direct generalization of the good polynomials used in the Tamo-Barg construction of locally recoverable codes. It embeds the quality measure for these functions into algebraic function field theory, then applies Galois theory to count the totally split rational places they produce. From this counting the authors derive explicit infinite families that achieve optimal LRC parameters superior to those obtainable from polynomials of the same degree. A sympathetic reader cares because the new codes support local recovery of erased symbols with less overall redundancy, which directly reduces storage overhead in distributed systems. The work supplies a unified framework that replaces the polynomial restriction with a broader rational-function setting.

Core claim

By defining good rational functions through the Galois-theoretic count of totally split rational places in their function fields, the authors construct explicit families that outperform all good polynomials of equal degree; these families in turn produce infinite optimal LRCs whose locality and distance parameters improve on the classical Tamo-Barg bounds.

What carries the argument

Good rational functions, whose quality is measured by the number of totally split rational places they induce, which directly determines the locality parameter of the resulting code.

If this is right

Infinite families of optimal LRCs exist with locality-distance trade-offs unavailable from polynomials.
The same degree now yields strictly more totally split places than any good polynomial.
A single Galois-theoretic framework covers both polynomial and rational cases.
Explicit constructions are available for any sufficiently large length satisfying the new bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same counting technique might be applied to construct LRCs with multiple disjoint recovery sets.
Higher-genus function fields could produce further parameter gains once the split-place formulas are extended.
The rational-function codes may admit efficient encoding and decoding algorithms that exploit the underlying rational map.

Load-bearing premise

The Galois-theoretic count of totally split rational places for a given rational function translates without hidden degree or genus constraints into the locality and minimum-distance parameters of an optimal LRC.

What would settle it

An explicit rational function of degree d whose associated code fails to recover from the predicted number of erasures or whose minimum distance falls short of the optimal LRC bound.

read the original 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 \emph{good polynomials} as a key structural ingredient. In this article, we propose a natural generalization of this paradigm by introducing the concept of \emph{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Extending to good rational functions yields better LRC parameters than polynomials via Galois counting, though the effect of poles on the final codes needs explicit verification.

read the letter

The main takeaway is that this work generalizes good polynomials to good rational functions for optimal LRC constructions and produces infinite families with improved parameters over Tamo-Barg. The extension of the Galois framework for counting split places is the technical step that enables the better counts. What the paper does well is lay out a unified algebraic approach using function fields. The explicit constructions of rational functions that have more totally split places than polynomials of equal degree are a concrete advance. This stays faithful to the prior literature while pushing the parameters forward. The soft spots center on the practical translation from the Galois counts to the code parameters. Rational functions have poles that cannot be used in the evaluation set, and the paper must show how these are excluded without reducing the length or locality below what is needed for the claimed optimality. The abstract states that the families outperform the polynomial case, so the constructions presumably account for this, but the details on the resulting (n, k, d, r) and the proof that the Singleton-type bound for LRCs is still met would be the place to look. If those checks pass, the concern is not major. This paper is for coding theorists who work on explicit constructions of locally recoverable codes, particularly those using algebraic geometry or Galois theory. Readers interested in new families beyond the polynomial method will find the most direct value here. It deserves a serious referee. The claims are specific, the method builds on solid prior results, and the potential improvement is worth checking. I recommend sending it to peer review with instructions to the referees to examine the handling of poles and the explicit parameter improvements.

Referee Report

2 major / 2 minor

Summary. The paper introduces the concept of good rational functions as a generalization of good polynomials from the Tamo-Barg construction. By embedding the problem in algebraic function field theory and extending Micheli's Galois-theoretic framework, the authors derive structural and quantitative results on the number of totally split rational places for rational functions, construct explicit families outperforming polynomials of equal degree, and obtain infinite families of optimal LRCs with improved parameters.

Significance. If the explicit constructions and Galois counts translate directly into (n,k,d,r) tuples that meet the LRC Singleton bound with strictly better parameters than Tamo-Barg (after any pole adjustments), this would provide a meaningful extension of algebraic LRC constructions, offering greater flexibility for distributed storage applications and highlighting the utility of rational functions over polynomials.

major comments (2)

[Constructions and main results] The central claim of improved parameters for infinite families requires explicit verification that the Galois count of totally split places for f = p/q yields optimal LRC parameters without effective reduction in n or r due to pole exclusion from the evaluation set or recovery partitions. This mapping is load-bearing for the improvement over Tamo-Barg and must be shown in the constructions (e.g., via concrete (n,k,d,r) tables or formulas).
[Galois-theoretic analysis] The quantitative Galois results extending Micheli must be shown to produce LRCs achieving the optimal distance bound; any degree limitations or constraints on the support of the rational function that could force lower locality r than the raw split count should be quantified and demonstrated not to negate the claimed improvement.

minor comments (2)

[Preliminaries] Clarify the precise definition of a 'good rational function' and how it reduces to the polynomial case when the denominator is constant.
[Examples and comparisons] Add explicit parameter comparisons (e.g., tables or asymptotic expressions) between the new rational-function LRCs and Tamo-Barg polynomials of matching degree to substantiate the 'outperform' claim.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. The points raised help clarify the presentation of our constructions and the mapping from Galois counts to LRC parameters. We address each major comment below and will revise the manuscript accordingly to strengthen the explicit verification.

read point-by-point responses

Referee: [Constructions and main results] The central claim of improved parameters for infinite families requires explicit verification that the Galois count of totally split places for f = p/q yields optimal LRC parameters without effective reduction in n or r due to pole exclusion from the evaluation set or recovery partitions. This mapping is load-bearing for the improvement over Tamo-Barg and must be shown in the constructions (e.g., via concrete (n,k,d,r) tables or formulas).

Authors: We agree that making the parameter mapping fully explicit strengthens the central claim. In Section 4, we construct explicit infinite families of good rational functions f = p/q by choosing p and q of controlled degrees with poles placed outside the evaluation set. The Galois-theoretic count from the extended Micheli framework directly gives the number of totally split places, which we use as the evaluation points to define n. The locality r is set by the degree of p (or the ramification structure), and the recovery sets are formed from the fibers of f without overlap from excluded poles. Because the number of poles is finite and small relative to the split count, we can always select a large enough subset of split places that avoids all poles while preserving the full split cardinality for the bound. This ensures no reduction in effective n or r. To address the request for concrete verification, we will add a new table in the revised manuscript listing explicit (n, k, d, r) tuples for the first several members of each family, together with the corresponding Tamo-Barg parameters from good polynomials of equal degree, confirming the strict improvement. revision: yes
Referee: [Galois-theoretic analysis] The quantitative Galois results extending Micheli must be shown to produce LRCs achieving the optimal distance bound; any degree limitations or constraints on the support of the rational function that could force lower locality r than the raw split count should be quantified and demonstrated not to negate the claimed improvement.

Authors: The quantitative results in Section 3 extend Micheli's Galois counting to rational functions by analyzing the Galois closure of the function field extension K(x)/K(f) and bounding the number of totally split rational places via the fixed-point formula on the Galois group action. We prove that this count is at least (deg(f) - 1) times a positive density factor determined by the group order, which is sufficient to meet the LRC Singleton bound with equality when the evaluation set is taken from these places. Regarding possible degree limitations or support constraints: the rational functions in our families are chosen with simple poles and numerator degree d such that the ramification is tame and the support (zeros and poles) has size O(d), which is negligible compared with the exponential growth of the split count. We quantify this in the proof of Theorem 3.4 by showing that the effective locality r equals the raw degree parameter minus at most a constant independent of the field size; the constant does not reduce r below the value needed for optimality. Thus the claimed improvement over Tamo-Barg is preserved. We will add a short clarifying paragraph after the statement of the main counting theorem that explicitly bounds the support size and confirms it does not force a lower r in the constructed families. revision: partial

Circularity Check

0 steps flagged

No circularity; derivation extends external Galois framework to rational functions with independent algebraic constructions

full rationale

The paper generalizes Tamo-Barg good polynomials to good rational functions by embedding the problem in algebraic function field theory and extending Micheli's Galois-theoretic counting of totally split places. It derives new structural and quantitative results on rational places, constructs explicit families outperforming polynomials of equal degree, and obtains improved LRC parameters. None of these steps reduce by definition or fitting to the claimed output; the counting arguments and explicit constructions are self-contained algebraic derivations independent of the final (n,k,d,r) tuples. No self-citation load-bearing, no fitted inputs renamed as predictions, and no ansatz smuggled via prior self-work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the applicability of algebraic function field theory and Galois theory to rational functions for counting totally split places, plus the existence of explicit good rational functions of given degree.

axioms (1)

standard math Standard results from algebraic function field theory and Galois theory extend to rational functions and allow quantitative control over the number of totally split rational places.
The abstract states that the problem is embedded in this theory to derive structural and quantitative results.

pith-pipeline@v0.9.0 · 5513 in / 1121 out tokens · 48106 ms · 2026-05-13T02:00:44.903714+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We derive structural and quantitative results on the number of totally split rational places associated with rational functions... extend the Galois-theoretic framework originally developed by Micheli for good polynomials (Theorem 4.5, Corollary 5.2).
IndisputableMonolith/Foundation/ArithmeticFromLogic.lean LogicNat.equivNat unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

h(x) is (r,l)-good if deg(h)=r+1 and there exist l disjoint (r+1)-subsets on which h is constant (Definition 3.1).

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

[1]

Locally recoverable codes on algebraic curves,

A. Barg, I. Tamo, and S. Vladut, “Locally recoverable codes on algebraic curves,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), 2015, pp. 1252–1256

work page 2015
[2]

Bounds on the size of locally recoverable codes,

V . R. Cadambe and A. Mazumdar, “Bounds on the size of locally recoverable codes,” IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5787–5794, 2015

work page 2015
[3]

On optimal locally repairable codes with super-linear length,

H. Cai, Y . Miao, M. Schwartz, and X. Tang, “On optimal locally repairable codes with super-linear length,” IEEE Trans. Inf. Theory, vol. 66, no. 8, pp. 4853–4868, 2020

work page 2020
[4]

New optimal linear codes with hierarchical locality,

B. Chen, G. Zhang, and W. Li, “New optimal linear codes with hierarchical locality,” IEEE Trans. Inf. Theory, vol. 69, no. 3, pp. 1544–1550, 2022

work page 2022
[5]

Good polynomials for optimal LRC of low locality,

R. Chen, S. Mesnager, and C. Zhao, “Good polynomials for optimal LRC of low locality,” Des. Codes Cryptogr., vol. 89, no. 7, pp. 1639–1660, 2021

work page 2021
[6]

A function field approach toward good polynomials for further results on optimal LRC codes,

R. Chen and S. Mesnager, “A function field approach toward good polynomials for further results on optimal LRC codes,” Finite Fields Appl., vol. 81, p. 102028, 2022

work page 2022
[7]

L. E. Dickson,Linear Groups: With an Exposition of the Galois Field Theory. New York: Dover, 1958

work page 1958
[8]

Optimal selection for good polynomials of degree up to five,

A. Dukes, A. Ferraguti, and G. Micheli, “Optimal selection for good polynomials of degree up to five,” Des. Codes Cryptogr., vol. 90, no. 6, pp. 1427–1436, 2022

work page 2022
[9]

Bounds and constructions of singleton- optimal locally repairable codes with small localities,

W. Fang, R. Tao, F. Fu, B. Chen, and S. Xia, “Bounds and constructions of singleton- optimal locally repairable codes with small localities,” IEEE Trans. Inf. Theory, vol. 70, no. 10, pp. 6842–6856, 2024

work page 2024
[10]

On the locality of codeword symbols,

P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. 58, no. 11, pp. 6925–6934, 2012

work page 2012
[11]

Two families of linear codes with desirable properties from some functions over finite fields,

Z. Heng, X. Li, Y . Wu, and Q. Wang, “Two families of linear codes with desirable properties from some functions over finite fields,” IEEE Trans. Inf. Theory, 2024

work page 2024
[12]

A family of self-orthogonal divisible codes with locality 2,

Z. Heng, M. Yang, and Y . Ming, “A family of self-orthogonal divisible codes with locality 2,” Discrete Math., vol. 348, no. 10, p. 114529, 2025

work page 2025
[13]

Construction of optimal locally repairable codes via auto- morphism groups of rational function fields,

L. Jin, L. Ma, and C. Xing, “Construction of optimal locally repairable codes via auto- morphism groups of rational function fields,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 210–221, 2020

work page 2020
[14]

Polytopes with groups of typePGL(2,q),

D. Leemans and E. Schulte, “Polytopes with groups of typePGL(2,q),” Ars Math. Con- temp., vol. 2, no. 2, pp. 163–171, 2009

work page 2009
[15]

Constructions of near MDS codes which are optimal locally recover- able codes,

X. Li and Z. Heng, “Constructions of near MDS codes which are optimal locally recover- able codes,” Finite Fields Appl., vol. 88, p. 102184, 2023

work page 2023
[16]

Optimal locally repairable codes via elliptic curves,

X. Li, L. Ma, and C. Xing, “Optimal locally repairable codes via elliptic curves,” IEEE Trans. Inf. Theory, vol. 65, no. 1, pp. 108–117, 2019. 29

work page 2019
[17]

New constructions of optimal locally recoverable codes via good polynomials,

J. Liu, S. Mesnager, and L. Chen, “New constructions of optimal locally recoverable codes via good polynomials,” IEEE Trans. Inf. Theory, vol. 64, no. 2, pp. 889–899, 2018

work page 2018
[18]

Constructions of optimal locally recoverable codes via Dickson polynomials,

J. Liu, S. Mesnager, and D. Tang, “Constructions of optimal locally recoverable codes via Dickson polynomials,” Des. Codes Cryptogr., vol. 88, no. 9, pp. 1759–1780, 2020

work page 2020
[19]

Optimal cyclic codes with hierarchical locality,

G. Luo and X. Cao, “Optimal cyclic codes with hierarchical locality,” IEEE Trans. Com- mun., vol. 68, no. 6, pp. 3302–3310, 2020

work page 2020
[20]

Constructions of optimal binary locally recoverable codes via a general construction of linear codes,

G. Luo and X. Cao, “Constructions of optimal binary locally recoverable codes via a general construction of linear codes,” IEEE Trans. Commun., vol. 69, no. 8, pp. 4987–4997, 2021

work page 2021
[21]

Three new constructions of optimal locally repairable codes from matrix-product codes,

G. Luo, M. F. Ezerman, and S. Ling, “Three new constructions of optimal locally repairable codes from matrix-product codes,” IEEE Trans. Inf. Theory, vol. 69, no. 1, pp. 75–85, 2023

work page 2023
[22]

Bounds and constructions of quantum locally recoverable codes from quantum CSS codes,

G. Luo, B. Chen, M. F. Ezerman, and S. Ling, “Bounds and constructions of quantum locally recoverable codes from quantum CSS codes,” IEEE Trans. Inf. Theory, vol. 71, pp. 1794–1802, 2025

work page 2025
[23]

The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally recoverable codes,

L. Ma and C. Xing, “The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally recoverable codes,” J. Combin. Theory Ser. A, vol. 193, p. 105686, 2023

work page 2023
[24]

Constructions of locally recoverable codes which are optimal,

G. Micheli, “Constructions of locally recoverable codes which are optimal,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 167–175, 2020

work page 2020
[25]

Rosen,Number Theory in Function Fields

M. Rosen,Number Theory in Function Fields. Springer, 2013

work page 2013
[26]

Quantum locally recoverable codes via good poly- nomials,

S. Sharma, V . Ramkumar, and I. Tamo, “Quantum locally recoverable codes via good poly- nomials,” IEEE J. Sel. Areas Inf. Theory, 2025

work page 2025
[27]

Stichtenoth,Algebraic Function Fields and Codes

H. Stichtenoth,Algebraic Function Fields and Codes. Springer, 2009

work page 2009
[28]

A family of optimal locally recoverable codes,

I. Tamo and A. Barg, “A family of optimal locally recoverable codes,” IEEE Trans. Inf. Theory, vol. 60, no. 8, pp. 4661–4676, 2014

work page 2014
[29]

Optimal locally repairable codes and connections to matroid theory,

I. Tamo, D. S. Papailiopoulos, and A. G. Dimakis, “Optimal locally repairable codes and connections to matroid theory,” IEEE Trans. Inf. Theory, vol. 62, no. 12, pp. 6661–6671, 2016

work page 2016
[30]

The minimum locality of linear codes,

P. Tan, C. Fan, C. Ding, C. Tang, and Z. Zhou, “The minimum locality of linear codes,” Des. Codes Cryptogr., vol. 91, no. 1, pp. 83–114, 2023

work page 2023
[31]

Construction of optimal(r,δ)-locally recoverable codes and connec- tion with graph theory,

C. Xing and C. Yuan, “Construction of optimal(r,δ)-locally recoverable codes and connec- tion with graph theory,” IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4320–4328, 2022. 30

work page 2022