Locally recoverable codes from algebraic curves with separated variables (Q2176292)

Consider a linear block code \(C\subset \mathrm{GF}(q)^n\) of length \(n\), dimension \(k\), and minimum distance \(d\) over a finite field \(\mathrm{GF}(q)\), where \(q\) is a prime power. Coordinates of a codeword \(c\in C\) are denoted \(c=(c_1,c_2,\ldots,c_n)\). We say \(i\in \{1,2,\ldots,n\}\) is \textit{locally recoverable with locality \(r\)} if there is a set \(R_i\subset \{1,2,\ldots,n\}-\{i\}\) of cardinality \(r\) with the property: for all codewords \(u,v\in C\), \(pr_i(u)=pr_i(v)\) implies \(u_i=v_i\) (where \(pr_i\) is the projection on the coordinates of \(R_i\)). For example, if \(C\) has a generator matrix in standard form then for any coordinate \(i>k\) is determined by the information bits in the first \(k\) coordinates, so we may take \(R_i=\{1,2,\dots,k\}\). The code \(C\) is called \textit{locally recoverable with locality \(r\)} if every coordinate is locally recoverable with locality at most \(r\). Locally recoverable codes (LCRs) were introduced relatively recently due to their application to cloud storage systems. The paper under review considers the question: which linear codes \(C\) are LCR codes with ``small'' \(r\)? Along with the upper bound \(r\leq k\), there is a lower bound provided by the Singleton-like inequality \[ k+d+\left\lceil \frac{k}{r}\right\rceil \leq n+2. \] MDS codes have \(r=k\). A. Barg and co-authors have introduced LRC analogues of RS codes and AG codes. This paper under review studies LRC AG codes arising from ``separated varibles'' curves defined by polynomial equations over \(\mathrm{GF}(q)\) with separated variables, \(A(y)=B(x)\). For example, an elliptic curve can be modeled by such an equation. We recall the AG code construction: Let \(X\) be a (projective, non-singular, absolutely irreducible, algebraic) curve of genus \(g\) defined over the field \(\mathrm{GF}(q)\). Let \(P = \{P_1 , \dots , P_n \} \subset X(\mathrm{GF}(q))\) be a set of \(n\) rational distinct points, \(D = P_1 + \dots + P_n\), and let \(G\) be a rational divisor with support disjoint from \(P\). The AG code \(C(P, L(G))\) is defined as \(C(P, L(G)) = ev_P (L(G))\), where \(L(G)\) is the Riemann-Roch space associated to \(G\) and \(ev_P\) is the evaluation at \(P\) map, \(ev_P (f ) = (f (P_1 ), \dots , f (P_n ))\). We can construct LRC AG codes from algebraic curves as follows: let \(X\), \(Y\) be two algebraic curves over \(\mathrm{GF}(q)\) and let \(\phi\colon X \to Y\) be a rational separable morphism of degree \(r + 1\). Take a set \(U\subset Y(\mathrm{GF}(q))\) of rational points with totally split fibres and let \(P = \phi^{-1}(U)\). By the separability of \(\phi\) there exists \(x \in \mathrm{GF}(q) (X )\) satisfying \(\mathrm{GF}(q) (X ) = \mathrm{GF}(q) (Y)(x)\). Let \[ V = \left\{ \sum_{i=1}^{r-1}\sum_{j=1}^m a_{ij} f_j x^i \mid a_{ij} \in \mathrm{GF}(q) \right\} \] where \(\{f_1 , \ldots , f_m \}\) is a basis of \(L(E)\). The LRC AG code \(C\) is defined as \(C = ev_P (V ) \subset \mathrm{GF}(q)^n\), with \(n = |P|\). The following result was previously known from the work of Barg et al. Theorem (Barg et al.): Let \(P\), \(V\) and \(r\) as above. If \(ev_P\) is injective on \(V\) then \(C \subset \mathrm{GF}(q)^n\) is a linear \([n, k, d]\) LRC code with parameters \(n = s(r + 1)\), \(k = r(E)\), \(d \geq n - \deg(E)(r + 1) - (r - 1) \deg(x)\) and locality \(r\). Theorem 3.2, one of the main results of the article under review, is a very similar theorem, but valid for the class of ``separated variables'' curves studied in this paper. However, it is much too technical to state here. There are other interesting bounds on the parameters proven in the paper. For example, the author's Theorem 5.1 provides a generalization of the Singleton-like inequality stated above. We refer to the paper itself for more precise statements. The remainder of the paper deals with decoding/recovery methods for such codes and numerous examples. See the paper itself for more precise statements of these results.