Pith. sign in

REVIEW 2 major objections 4 minor 28 references

Constructive asymptotic bounds of locally repairable codes via function fields

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For every prime power q and every locality r, this paper constructs linear locally repairable codes meeting a TVZ-type asymptotic rate–distance bound, with no restriction on alphabet or locality.

desk verdict A novel local-expansion route to asymptotic LRCs, but a false rank assumption at the center leaves the main bounds unproven. read the letter →

arxiv 1908.01471 v1 pith:GGMLN5T4 submitted 2019-08-05 cs.IT math.IT

Liming Ma , Chaoping Xing This is my paper · ORCID
classification cs.ITmath.IT MSC 94B2794B6511G2014H05
keywords locallyrepairablecodesasymptoticboundsfunctionfieldslocalexpansionsIhara'sconstantTsfasman–Vladut–ZinkboundGilbert–Varshamovfinite
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Locally repairable codes are storage codes in which each erased coordinate can be recovered from at most r others, and this paper studies the best possible trade-off between code rate and relative distance as the block length grows. The paper gives an explicit construction, valid over every finite field and for every fixed locality r, that realizes a Tsfasman–Vladut–Zink-type asymptotic bound: the rate R and relative distance δ satisfy $R > \frac{r}{r+1} - \frac{r}{r+1}\frac{1}{A(q)} - \delta$, where $A(q)$ is the maximal asymptotic ratio of rational places to genus over $\mathbb{F}_q$. Earlier curve-based constructions required the alphabet size to be a square and imposed divisibility conditions on r; the claimed advantage here is that both restrictions disappear. Over non-prime finite fields with sufficiently large alphabet, the resulting bound is shown to exceed the asymptotic Gilbert–Varshamov bound for locally repairable codes, and a separate variant over prime fields gives an explicit but weaker bound.

What carries the argument

The central object is the local expansion matrix $A$ (equation (15)): for a basis of $L((2g-1)P_\infty)$ with pole numbers $n_j$, the columns record the coefficients $c_{i,j}$ in the local expansions $f_j = \pi^{-2g+1}\sum_{i\ge 0} c_{i,j}\pi^i$ at a rational place $P_\infty$. The construction hinges on the 'without loss of generality' claim that the $g\times g$ submatrix $A_1$ of the first $g$ rows has rank $g$; this lets one solve $A_1 x^T = (b_0,\dots,b_{g-1})^T$ for each auxiliary function $g_{ij}$, so that the adjusted functions $f_{ij} = g_{ij} - \sum_w \alpha_{w,ij} f_w$ have expansions starting at $\pi^g$. The blocks $D_i$ of coefficients $a_{p,ij}$ ($p = g,\dots,2g-1+t$) form the lower part of the parity-check matrix $H$; the all-one and identity blocks at the top ensure that any single erased coordinate can be recovered from the other r coordinates in its block, i.e. locality r. Taking a tower of function fields with $N(F_i)/g(F_i) \to A(q)$ and letting t grow proportionally to n converts the rank condition on $H$ into the asymptotic rate–distance trade-off.

What would settle it

Take a basis of $L((2g-1)P_\infty)$ that contains the constant function 1; since 1 has a zero in every row of $A$ before row $2g-1$, the $g\times g$ submatrix $A_1$ formed by rows $0,\dots,g-1$ has a zero column and rank at most $g-1$. This contradicts the assumed full-rank step and shows the linear system $A_1 x^T = (b_0,\dots,b_{g-1})^T$ that defines the adjusted functions is not always solvable.

Watch

Extended reading notes

Core claim

The paper's central discovery is that the local expansions of functions at a single rational place can be turned directly into parity-check matrices of locally repairable codes. Starting with an $\mathbb{F}_q$-basis $\{f_1,\dots,f_g\}$ of the Riemann–Roch space $L((2g-1)P_\infty)$, each basis element has a local expansion $f_j = \pi^{-2g+1}\sum_{i\ge 0} c_{i,j}\pi^i$ at a rational place $P_\infty$. The paper labels the basis so that the $g\times g$ matrix $A_1$ of the first $g$ coefficients $c_{i,j}$ has full rank; for each auxiliary function $g_{ij}$ with a simple pole at a chosen repair position $P_{ij}$, it then solves $A_1 x^T = (b_0,\dots,b_{g-1})^T$ and forms $f_{ij} = g_{ij} - \sum_w \alpha_{w,ij} f_w$, so that the local expansion of $f_{ij}$ starts at $\pi^g$. The coefficients $a_{p,ij}$ for $p=g,\dots,2g-1+t$ fill the lower blocks of a parity-check matrix whose upper blocks force locality r. Proving that any t columns of this matrix are independent gives $d > t+1$, and passing to a tower of function fields with $N(F_i)/g(F_i) \to A(q)$ yields the asymptotic inequality of Theorem 1.1. For square alphabets the tower can be taken explicit; for $q = p^{2m+1}$ the paper uses the explicit towers of [4]; for prime alphabets, places of higher degree replace the rational repair places and produce the bound of Theorem 1.4.

Load-bearing premise

Everything hangs on the 'without loss of generality' assumption that the first $g$ expansion coefficients of the chosen basis functions are linearly independent, so the linear system used to adjust each auxiliary function has a solution; if that system is singular, the functions carrying both locality and distance are not guaranteed.

Editorial extensions

If this is right

  • For q a square, the construction gives explicit q-ary locally repairable codes with arbitrary locality r and $R > \frac{r}{r+1} - \frac{r}{r+1}\frac{1}{\sqrt{q}-1} - \delta$.
  • For $q = p^{2m+1}$, it gives explicit codes with $R > \frac{r}{r+1} - \frac{1}{2}\left(\frac{1}{p^m-1} + \frac{1}{p^{m+1}-1}\right)\frac{r}{r+1} - \delta$.
  • For non-prime fields with q large and $r \ge c \log_2 q$ for any $c > 1$, the new bound exceeds the asymptotic Gilbert–Varshamov bound for locally repairable codes.
  • For prime q, the same local-expansion method applied to places of high degree yields an explicit family with $R > \frac{r}{r+1} - \frac{b}{r+1}\frac{1}{q^{e/2}-1} - e\delta$, for $b = r$, $r+1$, or $r+2$ according to parity, although the paper notes this bound does not beat the Gilbert–Varshamov-type bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: the parity-check template with the same structure of one identity block and one local-expansion block per repair group should also produce codes with availability, by adding several independently scaled copies of a block column, at the price of a lower rate; the paper does not pursue this.
  • Editorial inference: since the construction depends only on the ratio of rational places to genus and not on the automorphism group, any explicit tower of function fields with a good limit $A(q)$ should plug into Theorem 1.1, so improvements in explicit towers would automatically improve the claimed rate bound.
  • Editorial inference: a natural testable extension is to enforce higher-order zeros at the other repair positions, which would trade rate for larger minimum distance or additional locality properties; the paper leaves this trade-off open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes an explicit asymptotic construction of q-ary linear locally repairable codes with arbitrary locality r, using local expansions of functions from Riemann-Roch spaces at a rational place P∞. The main result, Theorem 1.1, claims a Tsfasman-Vladut-Zink type lower bound R > r/(r+1) - (r/(r+1))/A(q) - δ for any prime power q and any locality r, with explicit versions for square and odd-power prime fields in Corollary 1.2, and a separate construction over prime fields in Theorem 1.4. The construction forms a parity-check matrix whose columns are coefficients of local expansions of functions f_ij, obtained by subtracting from each g_ij a linear combination of a basis of L((2g-1)P∞) to eliminate the first g local-expansion coefficients. The claimed distance bound depends on this elimination step.

Significance. If the main theorem were correct, the paper would be a substantial contribution: it would give locally repairable codes with no restrictions on alphabet size or locality, improve on earlier automorphism-group constructions for square alphabets, and exceed the Gilbert-Varshamov type bound for non-prime fields with large alphabet in some regimes. The paper is self-contained, uses standard function-field theory, and makes explicit comparisons with prior bounds. However, the central algebraic step on which the entire construction rests is invalid. Because the claimed rank of the first g rows of the local-expansion matrix is impossible, the functions f_ij with the required vanishing coefficients are not guaranteed to exist, and the distance proof collapses. The significance is therefore conditional, and the results as stated are not established.

major comments (2)
  1. [Section 3, eq. (15) and the paragraph before eq. (16)] The 'Without loss of generality' statement that the submatrix A1 consisting of the first g rows of A has rank g is false. For every basis {f_1,...,f_g} of L((2g-1)P∞), the constant function 1 belongs to this space, and in its expansion π^{-2g+1}∑ c_i π^i the first nonzero coefficient appears at i = 2g-1. Hence c_0 = ... = c_{g-1} = 0, so the constant function lies in the kernel of the projection L((2g-1)P∞) → F_q^g given by the first g expansion coefficients. This projection therefore has rank at most g-1 for every choice of basis, so no basis can make A1 have rank g. Consequently the linear system A1 x^T = (b_0,...,b_{g-1})^T need not be solvable for the chosen g_ij, and the existence of f_ij with the claimed local expansion (17) is not guaranteed. Remark 1(i) only proves that the first 2g rows have rank g, which is compatible with this obstruction.
  2. [Proposition 3.3 and Theorem 1.1] The distance proof in Proposition 3.3 relies on the step asserting that the local expansion of ∑_{i∈I}∑_{j∈S_i} λ_ij f_ij is π^{-2g+1}∑_{p=2g+t} ... π^p. This implication uses (17) and the fact that D_i records only coefficients a_{p,ij} for p ≥ g. Without (17), the selected combination may have nonzero coefficients a_g, ..., a_{2g-1+t}, so the valuation at P∞ need not exceed 1+t. The subsequent degree argument involving deg(−(1+t)P∞ + ∑∑ P_ij) = -1 then cannot be applied, and the claim d > t+1 is unsupported. Since Theorem 1.1 is derived directly from Proposition 3.3, the main asymptotic result does not follow as written. Section 4 constructs f_ij 'in the same way as in Section 3' and therefore inherits the same gap, so Theorem 1.4, Corollary 1.2, and the claimed GV-type improvements in Proposition 1.3 and the figures are also not justified.
minor comments (4)
  1. [Section 3, first paragraph after eq. (14)] The text says 'For 1 ⩽ j⩽ n, the local expansions of f_j ...' but the basis has g elements; this should read '1 ⩽ j⩽ g'.
  2. [Proposition 3.3, proof, Cases 1 and 2] In both cases the notation 'S_u \ {1, i+1}' should be 'S_u \ {1, r+1}', since f_{u,r+1} = α_u f_{u,1} is the repeated column.
  3. [Propositions 3.3 and 4.2] The word 'Riemman-Roch' is misspelled; it should be 'Riemann-Roch'.
  4. [Proof of Theorem 1.4] The line 'Let m_i b + 1 = ∑_{d|e} d·B_d(F_i)' is unclear: since the sum equals N(E_i), it appears to define m_i, but the notation should be made explicit, and the choice of disjoint effective divisors of degree b requires justification.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is self-contained given standard function-field facts and external asymptotic constants; the A1-rank WLOG gap is a correctness defect, not circularity.

full rationale

No circular derivation is present. The construction starts from standard Riemann-Roch and local-expansion facts, assembled in Lemmas 3.1 and 3.2; the parity-check matrix is explicitly defined from local expansion coefficients, and the rate/distance estimates in Proposition 3.3 are direct linear-algebra and degree arguments, not fitted parameters repackaged as predictions. The asymptotic comparison uses Ihara's constant A(q) as an external asymptotic quantity from the function-field literature, together with the Garcia-Stichtenoth tower and the Bassa-Beelen-Garcia-Stichtenoth tower, none of which are supplied by a self-citation chain. The paper's own prior works ([14], [15], [16], [17], [28]) appear only as contextual comparisons or constructions of optimal codes, not as load-bearing premises for the asymptotic bounds. The only genuine issue found in the derivation is the unproved and in fact false assertion in Section 3, 'Without loss of generality, we assume that the submatrix of A defined in (15) consisting of the first g rows has rank g': the constant function 1 lies in L((2g-1)P_infty) and its first nonzero coefficient in the normalized expansion appears at row 2g-1, so the first g rows have rank at most g-1. This breaks the solvability of A1 x^T = b and thus the claimed local-expansion form (17), and the same gap propagates to Section 4. However, this is a mathematical correctness flaw, not a circularity: the claimed bound would not reduce to its inputs by construction, by fitted-data prediction, or by self-citation. Therefore the circularity score is 0, with the correctness caveat noted separately.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No new entities are postulated. The free-parameter list is empty: A(q) is a known constant and e in Theorem 1.4 is a quantified design choice, not a number fitted to data. The axiomatic burden rests on standard function-field theory and previously established tower constructions.

assumptions (4)
  • standard math Standard algebraic function field theory, including Riemann-Roch theorem and Weierstrass gap theorem (Section 2.1, 2.2).
    Used to bound dimensions and construct bases of Riemann-Roch spaces.
  • standard math Known bounds on Ihara's constant A(q): A(q)=sqrt(q)-1 for square q (Drinfeld-Vladut, Ihara), and explicit lower bounds for odd powers (Bassa et al.) (Section 2.3).
    These external results supply the asymptotic number of rational places used in Theorem 1.1.
  • standard math Properties of the Garcia-Stichtenoth tower, including genus and number of rational places (Proposition 2.1, from [9]).
    Used to make the construction explicit for square q and in constant field extensions for prime q.
  • standard math Constant field extension counting: sum_{d|e} d B_d(F_i) = N(E_i) (Lemma 5.1.9 of Stichtenoth), used in Section 4.
    Relates places of degree dividing e in F_i to rational places after extension to F_{q^e}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Constructive asymptotic bounds of locally repairable codes via function fields." pith.science (2026). https://pith.science/paper/GGMLN5T4

@misc{pith2026190801471,
  author       = {Pith},
  title        = {Pith review of: Constructive asymptotic bounds of locally repairable codes via function fields},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GGMLN5T4}},
  note         = {Machine review of arXiv:1908.01471}
}
read the original abstract

Locally repairable codes have been investigated extensively in recent years due to practical applications in distributed and cloud storage systems. However, there are few asymptotical constructions of locally repairable codes in the literature. In this paper, we provide an explicit asymptotic construction of locally repairable codes over arbitrary finite fields from local expansions of functions at a rational place. This construction gives a Tsfasman-Vladut-Zink type bound for locally repairable codes. Its main advantage is that there are no constraints on both locality and alphabet size. Furthermore, we show that the Gilbert-Varshamov type bound on locally repairable codes over non-prime finite fields can be exceeded for sufficiently large alphabet size.

Figures

Figures reproduced from arXiv: 1908.01471 by the authors.

Figure 1
Figure 1. r = 63, q = 212 (ii) If q is an odd power of prime, i.e., q = p 2m+1 with m > 1, then there exists an explicit family of q-ary linear locally repairable codes with locality r whose rate R and relative distance δ satisfy (11) R > r r + 1 − 1 2  1 pm − 1 + 1 pm+1 − 1  r r + 1 − δ. Proof. If q is a square, then the Garcia-Stichtenoth tower is the well-known explicit tower of function fields such that A(q) = √q − 1 fr… view at source ↗
Figure 2
Figure 2. r = 64, q = 212 [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. r = 64, q = 213 the asymptotic Gilbert-Varshamov bound (5) of locally repairable codes for r = 64, q = 2 13 as well. There are no constraints on locality r in Theorem 1.1 compared with the bounds given in [3, 16]. The figure 4 shows that the bound (10) given in Corollary 1.2 can exceed the asymptotic Gilbert-Varshamov bound of locally repairable codes given for many localities for δ = 0.5, q = 212 . Furthermore, we … view at source ↗
Figures from the paper (2 more)
Figure 4
Figure 4. Figure 4: δ = 0.5, q = 212 Explicit asymptotically good towers of function fields over Fq are of great interest for coding theory, since they can be applied to construct asymptotically good families of linear codes over Fq. But there doesn’t exist explicit towers of function fie…
Figure 5
Figure 5. Figure 5: r = 11, q = 2 1.4. Organization. This paper is organized as follows. In Section 2, we introduce some preliminaries on function fields including Riemann-Roch space, local expansion, Ihara’s constant A(q) and Garcia-Stichtenoth tower. In Section 3, we present our asympto…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 26 canonical work pages

  1. [1]

    Aaltonen, Linear programming bounds for tree codes, IEEE Trans

    M. Aaltonen, Linear programming bounds for tree codes, IEEE Trans. Inf. Theory, vol. 25, no. 1, pp. 85–90, Jan. 1979

    work page 1979

  2. [2]

    A. Barg, K. Haymaker, E. Howe, G. Matthews, and A. Vrilly-Alvarado, Locally recoverable codes from algebraic curves and surfaces, in Algebraic Geometry for Coding Theory and Cryptography , E.W. Howe, K.E. Lauter, and J.L. Walker, Editors, Springer, 2017, pp. 95–126

    work page 2017

  3. [3]

    A. Barg, I. Tamo, and S. Vl˘ adut ¸,Locally recoverable codes on algebraic curves, IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4928–4939, Aug. 2017

    work page 2017

  4. [4]

    Bassa, P

    A. Bassa, P. Beelen, A. Garcia and H. Stichtenoth, Towers of function fields over non-prime finite fields, Mosc. Math. J. 15(2015), 1–29

    work page 2015

  5. [5]

    Cadambe and A

    V. Cadambe and A. Mazumda, Bounds on the size of locally recoverable codes, IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5787–5794, Nov. 2015. 18 LIMING MA AND CHAOPING XING

    work page 2015

  6. [6]

    Drinfeld and S.G

    V.G. Drinfeld and S.G. Vladut, Number of points of an algebraic curve , Funct. Anal. 17(1983), 53–54

    work page 1983

  7. [7]

    Forbes and S

    M. Forbes and S. Yekhanin, On the locality of codeword symbols in non-linear codes, Discrete Math. vol. 324, no. 6, pp. 78–84, 2014

    work page 2014

  8. [8]

    Garcia and H

    A. Garcia and H. Stichtenoth, A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vladut bound , Invent. Math. 121(1995), 211–222

    work page 1995

Show all 28 references
  1. [9]

    Garcia and H

    A. Garcia and H. Stichtenoth, On the asymptotic behavior of some towers of function fields over finite fields, J. Number Theory 61(1996), 248–273

    1996

  2. [10]

    Gopalan, C

    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, Nov. 2012

    2012

  3. [11]

    Guruswami, C

    V. Guruswami, C. Xing and C. Yuan, How long can optimal locally repairable codes be? IEEE Trans. Inform. Theory 65, no. 6, Jun. 2019, 36623670

    2019

  4. [12]

    Ihara, Some remarks on the number of rational points of algebraic curves over finite fields , J

    Y. Ihara, Some remarks on the number of rational points of algebraic curves over finite fields , J. Fac. Sci. Univ. Tokyo 28(1981), 721–724

    1981

  5. [13]

    Jin, Explicit Construction of Optimal Locally Recoverable Codes of Distance 5 and 6 via Binary Constant Weight Codes , IEEE Trans

    L. Jin, Explicit Construction of Optimal Locally Recoverable Codes of Distance 5 and 6 via Binary Constant Weight Codes , IEEE Trans. Inf. Theory, vol. 65, no. 8, Aug 2019, 4658–4663

    2019

  6. [14]

    L. Jin, L. Ma and C. Xing, Construction of optimal locally repairable codes via automorphism groups of rational function fields , arXiv:1710.09638

    arXiv

  7. [15]

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

    2019

  8. [16]

    X. Li, L. Ma and C. Xing, Construction of asymptotically good locally repairable codes via auto- morphism groups of function fields , IEEE Trans. Inf. Theory, Doi: 10.1109/TIT.2019.2923609

    2019

  9. [17]

    Y. Luo, C. Xing and C. Yuan, Optimal locally repairable codes of distance 3 and 4 via cyclic codes, IEEE Trans. Inform. Theory, vol. 65, vol. 2, Feb. 2019, 1048–1053

    2019

  10. [18]

    Niederreiter and C.P

    H. Niederreiter and C.P. Xing, Rational Points on Curves over Finite Fields: Theory and Appli- cations, LMS 285, Cambridge, 2001

    2001

  11. [19]

    D. S. Papailiopoulos and A.G. Dimakis, Locally repairable codes, IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 5843–5855, 2014

    2014

  12. [20]

    Prakash, G.M

    N. Prakash, G.M. Kamath, V. Lalitha and P.V. Kumar, Optimal linear codes with a local-error- correction property, Proc. 2012 IEEE Int. Symp. Inform. Theory, 2012, 2776–2780

    2012

  13. [21]

    Silberstein, A.S

    N. Silberstein, A.S. Rawat, O.O. Koyluoglu and S. Vichwanath, Optimal locally repairable codes via rank-matric codes, Proc. IEEE Int. Symp. Inf. Theory, 2013, 1819–1823

    2013

  14. [22]

    Stichtenoth, Algebraic Function Fields and Codes , Graduate Texts in Mathematics 254, Springer Verlag, 2009

    H. Stichtenoth, Algebraic Function Fields and Codes , Graduate Texts in Mathematics 254, Springer Verlag, 2009

    2009

  15. [23]

    Tamo and A

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

    2014

  16. [24]

    I. Tamo, A. Barg and A. Frolov, Bounds on the parameters of locally recoverable codes , IEEE Trans. Inf. Theory, vol. 62, no. 6, 3070–3083, 2016

    2016

  17. [25]

    Tamo, D.S

    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, Dec. 2016, 6661–6671

    2016

  18. [26]

    Tsfasman, S.G

    M.A. Tsfasman, S.G. Vladut and T. Zink, Modular curves, Shimura curves and Goppa codes better than the Varshamov-Gilbert bound , Math. Nachr. 109(1982), 21–28

    1982

  19. [27]

    C. Xing, H. Niederreiter and K.Y. Lam, Constructions of algebraic-geometry codes, IEEE Trans. Inf. Theory, vol. 45, no. 4, pp 1186–1193, May 1999

    1999

  20. [28]

    Xing and C

    C. Xing and C. Yuan, Construction of optimal locally recoverable codes and connection with hypergraph, arXiv:1811.09142. ASYMPTOTIC CONSTRUCTION OF LRC 19 School of Mathematical Sciences, Yangzhou University, Yangzhou, China 225002 E-mail address : lmma@yzu.edu.cn School of El...

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.