Curve-lifted codes for local recovery using lines

Algebraic geometry codes were introduced in the 1980s [7] and quickly received attention due to the existence of sequences with parameters exceeding the Gilbert-Varshamov bound [19]. These codes are defined by evaluating functions on a smooth projective curve over a finite field at rational points, a construction that is quite flexible allowing for customizations or variants that achieve particular goals. In [2], it was demonstrated how coverings of curves yield locally recoverable codes (also known as LRCs or codes with locality). A code C of length n is said to be locally recoverable if there exist recovery sets \(R_1, \dots , R_n\) such that for every codeword coordinate i, the \(i^{th}\) coordinate \(c_i\) of any codeword \(c \in C\) may be recovered from the codeword symbols \(c\mid _{R_i}\). In this case, the code C is said to have locality R relative to the recovery sets \(R_1, \dots , R_n\), where R is the cardinality of the largest \(R_i\). When the context is clear, we may say that a code C has locality R to mean there exists a recovery set for each coordinate of cardinality at most R. Hence, as we will see a code may have various localities. A code has availability t if each coordinate has t disjoint recovery sets and is called a code with availability if \(t>1\).

Locally recoverable codes, whose study originated in [6, 17], are studied due to their applicability in settings such as distributed storage where vast amounts of data are stored across many servers which may be temporarily offline (and is modeled as an erasure). To limit network traffic involved in recovery, it is desirable that each coordinate (or server) can be recovered using information from a small subset of all other coordinates (or the rest of the network). Moreover, it is useful to have multiple ways in which information can be recovered, so that if a coordinate is lost, the ability to recover does not depend on the availability of some other coordinate which might also be lost.

Algebraic geometry codes can be adapted to define locally recoverable codes, as noted in [2, 9]. In this paper, we define curve-lifted codes, a generalization of the Hermitian-lifted codes [11], for a projective curve \({\mathcal {X}}\) over a finite field \(\mathbb {F}_q\). Curve-lifted codes are evaluation codes in which codewords are determined by evaluating particular functions at affine points on the curve. The functions to evaluate depend on what we will refer to as an intersection number: given a curve \({\mathcal {X}}\) and a collection of lines \({\mathbb {L}}\), the intersection number of the curve relative to \({\mathbb {L}}\) isCodewords arise from the evaluation of rational functions f on X that restrict to low-degree polynomials on \(\left( L \cap {\mathcal {X}} \right) \left( \mathbb {F}_q \right) \). Recovery sets for a position associated with a point P consist of collections of other points of intersection between a line through P and \({\mathcal {X}}\). The parameters of such codes depend on the collection \({\mathbb {L}}\) of lines selected and the number of \(\mathbb {F}_q\)-rational points that lie on both the curve \({\mathcal {X}}\) and a line \(L \in {\mathbb {L}}\). When \({\mathbb {L}}\) is the set of all lines in affine space over \(\mathbb {F}_q\), we refer to the intersection number of the curve relative to \({\mathbb {L}}\) as the intersection number of the curve.

Intersection numbers of particular curves can be challenging to determine. We demonstrate progress in this direction for the norm-trace curve which is defined byover the field \(\mathbb {F}_{q^r}\) with \(q^r\) elements. Taking \(r=2\) gives the Hermitian curve \({\mathcal {X}}_{q,2}: y^q+y=x^{q+1}\) over \(\mathbb {F}_{q^2}\). This allows us to give important instances of the curve-lifted construction, resulting in norm-trace-lifted codes.

Curve-lifted codes and norm-trace-lifted codes are strongly inspired by Hermitian-lifted codes. We note some key distinctions between the binary Hermitian case (\(r=2\)) and the more general norm-trace one in which \(r>2\). Much of the effort in studying the Hermitian case is devoted to finding enough functions to get a positive rate. It should be mentioned that lifted codes are not traditional algebraic geometry codes; while the codewords are of a similar form, obtained by evaluating functions at rational points, the space of functions is not the Riemann-Roch space of a divisor on the curve. Curve-lifted codes are motivated by but should not to be confused with lifted Reed-Solomon codes [8]. Reed-Solomon codes are formed from evaluating polynomials of bounded degree at points on the projective line \({\mathbb {P}}\). It is for this reason that codes defined from positive genus curves, such as the norm-trace curve, can provide codes of same length over smaller fields than Reed-Solomon codes. Lifted Reed-Solomon codes are defined by evaluating multivariate polynomials that restrict to low-degree polynomials on lines. While one may consider a curve-lifted construction relative to \({\mathbb {P}}\), it does not yield interesting locally recoverable codes with large availability. Indeed, recovery sets for a position associated with a point P are found by taking lines through P and determining the other evaluation points that lie on L. However, the only line for which \(\mid L \cap {\mathbb {P}} \mid \ge 2\) is \(L\,=\,{\mathbb {P}}\).

Determining the functions to evaluate to define a curve-lifted code is a crucial task. As we will see in the norm-trace case when \(r>2\), we first bound the number of rational points of intersection between the curve \(\mathcal {X}_{q,r}\) and a line \(\mathbb {F}_{q^r}\). That is a primary contribution of this work. It pays off in that once this bound is determined, we can immediate specify enough functions which yield codewords in the norm-trace-lifted code to prove that this family of codes has positive rate even as the code length grows, for a fixed characteristic. It is an open problem to explicitly describe all functions that give rise to codewords.

This paper is organized as follows. Section 2 reviews the necessary terminology and the Hermitian-lifted codes. We define curve-lifted codes in Sect. 3 and give examples of them. The cardinalities of intersections between the norm-trace curves and lines are found in Sect. 4, laying a foundation to define an array of norm-trace-lifted codes over arbitrary fields in Sect. 5. The paper ends with a conclusion in Sect. 6.

In this section, we review notation to be used throughout the paper as well as the background on other curve-lifted codes in the literature. Throughout, we let q be a power of a prime and \(r\ge 2\) be an integer. The finite field with q elements is denoted \(\mathbb {F}_q\), and the multiplicative group of its nonzero elements is denoted \(\mathbb {F}_q^\times \). The set of nonnegative integers is denoted by \(\mathbb {N}\), and for a positive integer n, \([n]\,:=\,\{1, \dots , n\}\).

An [n, k, d] linear code C over a finite field \(\mathbb {F}_q\) is a k-dimensional \(\mathbb {F}_q\)-subspace of \(\mathbb {F}_q^n\) in which any two distinct elements (called codewords) differ in at least d coordinates. Such a code has length n, dimension k, and minimum distance d. Any \(d-1\) erasures in a received word may be recovered by accessing the remaining \(n-d+1\) coordinates. We are interested in recovering erasures by accessing a small number of coordinates. As is standard in the erasure recovery model, we assume a received word w has the form \(w \in \mathbb {F}_q^n \cup \{ ? \}\) where there exists a codeword \(c \in C\) such that \(w_i \in \{ c_i, ? \}\) for all \(i \in [n]\). All codes considered in this paper are linear, so we use the terms code and linear code interchangeably.

A code C of length n over \(\mathbb {F}_q\) has locality s if and only if for all \(i \in \{ 1,\dots ,n\}\), there existswhere \(|R_i| \le s\) and for all codewords \(c \in C\),for some function \(\varphi _i: \mathbb {F}_q^s \rightarrow \mathbb {F}_q\). In this case, we call C a code with locality s. The set \(R_i\) is called a recovery set for i. The set \(\overline{R_i} \,:=\, R_i \cup \{ i \}\) is called a repair group for i. A code with locality s clearly has locality \(s'\) for all \(s' \ge s\) by taking recovery sets \(S_i = R_i \cup \left\{ j_1, \dots , j_{s'-\mid R_i \mid }: j_1, \dots , j_{s'-\mid R_i \mid } \in [n] {\setminus } \overline{R_i} \right\} \) for all \(i \in [n]\). When particular recovery sets \(R_i\), \(i \in [n]\), are clear from the context, we say that C has locality \(\max \{ |R_i|: i \in [n] \}\). We say that C has availability t if there exist recovery setsfor each index \(i \in [n]\), such thatfor all \(j \ne j'\).

The codes considered in this paper are reminiscent of algebraic geometry codes, in that they are defined using rational points and functions on curves over finite fields. An algebraic geometry code C(D, G) of length n over a finite field \(\mathbb {F}\) is defined by fixing a curve \({\mathcal {X}}\) over \(\mathbb {F}\) along with divisors G and D on \({\mathcal {X}}\) so that their supports are disjoint and D is the sum of \(\mathbb {F}\)-rational points \(P_1, \dots , P_n\). Each codeword is of the form \((f(P_1), \dots , f(P_n))\) where f is a function in the Riemann-Roch space of G. If D is not specified, it is taken to be the sum of all \(\mathbb {F}\)-rational points other than those in the support of G. For example, Reed-Solomon codes are algebraic geometry codes on projective lines. The next most commonly studied algebraic geometry codes are Hermitian codes. Hermitian codes are special cases of norm-trace codes, meaning algebraic geometry codes defined on norm-trace curves. Norm-trace codes were first defined by Geil [5]. They are defined by evaluating functions from Riemann-Roch spaces at rational points onover the field \(\mathbb {F}_{q^r}\) with \(q^r\) elements; here and throughout, the norm and trace will be considered with respect to the extension \(\mathbb {F}_{q^r}/\mathbb {F}_q\), so that for any \(a \in \mathbb {F}_{q^r}\), they areNote that \({\mathcal {X}}_{q,r}\) has genusLet \({\mathcal {X}}_{q,r}(\mathbb {F}_{q^r})\) denote the set of \(\mathbb {F}_{q^r}\)-rational point on the curve \({\mathcal {X}}_{q,r}\). For each \(a \in \mathbb {F}_{q^r}\), there are \(q^{r-1}\) elements \(b \in \mathbb {F}_{q^r}\) such that \({{\,\textrm{Norm}\,}}(a)={{\,\textrm{Tr}\,}}(b)\), each giving rise to a rational point \((a,b) \in {\mathcal {X}}_{q,r}(\mathbb {F}_{q^r})\), referred to as an affine point of \( {\mathcal {X}}_{q,r}\). In addition, there is a unique point at infinity, \(P_{\infty } \in {\mathcal {X}}_{q,r}(\mathbb {F}_{q^r})\). Hence, \(\left| {\mathcal {X}}_{q,r}(\mathbb {F}_{q^r}) \right| = q^rq^{r-1}+1=q^{2r-1}+1\). Consider the vector space of functions \(V \subseteq \cup _{m=0}^{\infty } {\mathcal {L}}(mP_{\infty })\) with no poles other than at \(P_{\infty }\), where \(P_{\infty }\,:=\,(0:1:0)\) is the unique point at infinity on \(\mathcal {X}_{q,r}\). It is worth noting that the Riemann-Roch space of the divisor \(mP_{\infty }\) isWe denote the set of polynomials with coefficients in \(\mathbb {F}_{q^r}\) and indeterminates x, y of total degree at most k by \(\mathbb {F}_{q^r}[x,y]_{\le k}\). A Hermitian code is an algebraic geometry code over the Hermitian curve. For convenience, we will identify rational functions of the form \(\frac{f(x,y)}{z^{\deg f}}\) where \(f(x,y) \in \mathbb {F}[x,y]\) with the polynomial \(f(x,y) \in \mathbb {F}[x,y]\).

A Hermitian code with \(m \le q^2-1\) over \(\mathbb {F}_{q^2}\) has locality q and availability \(q^2-1\) [11]. To see this, note that each affine \(\mathbb {F}_{q^2}\)-rational point P on the Hermitian curve \({\mathcal {X}}_{q,2}\) has the property that any non- tangent line to \({\mathcal {X}}_{q,2}\) intersects the curve in \(q+1\) \(\mathbb {F}_{q^2}\)-rational points and there are \(q^2-1\) such lines. Because any function f in the Riemann-Roch space \({\mathcal {L}}(mP_{\infty })\) may be expressed as \(f(x,y)=\sum _{i=0}^{q-1} \sum _{j=0}^{\lfloor \frac{m-iq}{q+1} \rfloor } c_{ij}x^i y^j\) for some constants \(c_{ij}\), such a function restricted to a non-tangent line can be viewed as a univariate polynomial of degree at most \(q-1\). To recover an erasure at point \(P_{ab}\), one may treat the word corresponding to the \(\mathbb {F}_{q^2}\)-rational points on any line through \(P_{ab}\) as a Reed-Solomon codeword. Thus, the set of \(\mathbb {F}_{q^2}\)-rational points on any non-tangent line through \(P_{ab}\), other than \(P_{ab}\) itself, form a recovery set for the coordinate corresponding to \(P_{ab}\), demonstrating that the Hermitian code \(C(mP_{\infty }, D)\) over \(\mathbb {F}_{q^2}\) has locality q and availability \(q^2-1\). Unfortunately, the rate of these codes approaches 0 as q goes to infinity.

Lifting is a mechanism introduced to increase the rate of codes while maintaining desirable properties. Hermitian-lifted codes over binary fields were introduced in [11] and yield a family of codes with a positive lower bound on the rate as q goes to infinity. More recent work with an improved bound on the rate of Hermitian-lifted codes appears in [1].

In this section, we present curve-lifted codes, which are evaluation codes whose codewords arise from functions that restrict to low degree polynomials on a collection of lines through the curve. In the first subsection, we develop the notion and consider some examples. As we will see, intersection numbers will be a necessary ingredient, and they will be further explored in later sections. In the second subsection, we drill down to better describe the defining sets of functions for particular curves.

In this section, we determine the number of points in \(\mathcal X_{q,r}(\mathbb {F}_{q^r})\) on an intersection of a line \(L_{\alpha ,\beta }\) where \(\alpha \not =0\) and \(\alpha ,\beta \in \mathbb {F}_{q^r}\) with the norm-trace curve \({\mathcal {X}}_{q,r}\). We loosely refer to the number of such points as an intersection number. Intersection numbers will be applied in Sect. 5 to construct norm-trace-lifted codes over fields of arbitrary characteristic. In particular, they will be used to set the value B as in Proposition 3.3 and a degree bound which will define an appropriate set of functions to support local recovery with high availability and positive rate. In particular, we will find an integer B, depending only on q and r, such that for all \(L_{\alpha ,\beta }\in \mathbb L_{q^r}\),which will ultimately play a role in the sizes of the recovery sets for the norm-trace-lifted codes.

Given \(\alpha , \beta \in \mathbb {F}_{q^r}\), it will be useful to consider the polynomialor \(m_{\alpha , \beta }\) for short. DefineFirst, we observe that if \(\alpha \) and \(\alpha '\) are nonzero elements with the same norm and \(\beta \) and \(\beta '\) have the same trace, then \(n_{q,r}(\alpha ,\beta )=n_{q,r}(\alpha ',\beta ')\).

Next, we apply Lemma 4.1 to the case where \(q=2\); see also [12, Lemma 1].

For \(q \ne 2\), we observe more intricate behavior. We will use results of Moisio and Moisio-Wan, who build on work of Katz [10], to establish lower and upper bounds on \(n_{q,r}(\alpha ,\beta )\). For an integer \(r\ge 2\) and elements \(a,b\in \mathbb {F}_q\), letIn [10], Katz proves the following result on counting elements of \(\mathbb {F}_{q^r}\) with prescribed norm and trace:

We will use the following improvement to Katz’ result when \(a\not =0\), due to Moisio and Wan [14].

The previous bound is complemented by the following result of Moisio [13], which provides a bound \(N_{q,r}(a,b)\) when \(a=0\).

We now use [13, 14] to produce lower bounds on \(n_{q,r}(\alpha ,\beta )\).

We will use the bound in the previous corollary to establish families of norm-trace-lifted codes in arbitrary characteristic.

In this section, we combine the results from Sects. 3 and 4 to define and study norm-trace-lifted codes defined using the norm-trace curve \({\mathcal {X}}_{q,r}: {{\,\textrm{Tr}\,}}(y)={{\,\textrm{Norm}\,}}(x)\) over \(\mathbb {F}_{q^r}\) where q is any prime power. In light of Remark 4.8 and [11], we restrict our attention to \(r>2\). Now, having found a lower bound to take for B in Proposition 3.3 on intersection numbers as in Corollary 4.7, we may now consider codes defined by sets of rational functions that reduce on all lines to polynomials of degree at most \(B-2\). Also, because the curve itself is specified by a particular equation, we can obtain bounds on the code rates, including some that exceed the comparable Hermitian cases.

In this paper, we defined curve-lifted codes which allow for local recovery by taking as repair groups the points of intersection of the curve with lines through the evaluation points. While inspired by Hermitian-lifted codes, they may exhibit different behaviors depending on the particular defining curve. In addition, we determined bounds on the number of affine points of intersection between a norm-trace curve and a line. We then used them to define norm-trace-lifted codes over fields of arbitrary characteristic. These new codes have high availability and positive rate, bounded away from zero as the code length goes to infinity. We note that codes over fields of small characteristic provide the best asymptotic rates. The opportunity to obtain greater rate by evaluating more functions may motivate one to consider more tailored bounds for the intersection numbers.