Optimal Rate List Decoding over Bounded Alphabets Using Algebraic-geometric Codes

The first approach is to use suitable automorphisms of function fields to fold the code. This approach was used for Reed–Solomon codes in Reference [14] and for cyclotomic function field in Reference [10], though this was done using the original approach in Reference [14], where the messages to be list decoded were pinned down to the roots of a higher degree polynomial over a large residue field. As mentioned earlier, effecting this “non-linear” approach in References [10, 14] with automorphisms of more general function fields seems intricate at best. In this work, we employ the linear-algebraic list-decoding method of Reference [17]. However, the correct generalization of the linear-algebraic list-decoding approach to the function field case is also not obvious. One of the main algebraic insights in this work is noting that a possible way to generalize the linear-algebraic approach to codes based on algebraic function fields is to rely on the local power series expansion of functions from the message space at a suitable rational point. (The case for Reed–Solomon codes being the expansion around 0, which is a finite polynomial form.)

Working with a suitable automorphism that has a “diagonal” action on the local expansion lets us extend the linear-algebraic decoding method to AG codes (here by a “diagonal” action, we mean that this action gives rise to equations on coefficients of a polynomial that are diagonal when put in matrix form). Implementing this for specific AG codes requires an explicit specification of a basis for an associated message (Riemann–Roch) space and the efficient computation of the local expansion of the basis elements at a special rational point on the curve. We show how to do this for two towers of function fields: the Hermitian tower [29] and the asymptotically optimal Garcia–Stichtenoth tower [6, 7]. The former tower is quite simple to handle—it has an easily written down explicit basis, and we show how to compute the local expansion of functions around the point with all zero coordinates. However, the Hermitian tower does not have bounded ratio of the genus to number of rational points and so does not give constant alphabet codes (we can get codes over an alphabet size that is polylogarithmic in the block length though). Explicit bases for Riemann–Roch spaces of the Garcia–Stichtenoth tower were constructed in Reference [30]. Regarding local expansions, one major difference is that we work with local expansion of functions at the point at infinity, which is fully “ramified” in the tower. For both these towers, we find and work with a nice automorphism that acts diagonally on the local expansion and use it for folding the codes and decoding them by solving a linear system.

The second approach is to work with “usual” algebraic-geometric codes, based on evaluating functions from a Riemann–Roch space at some rational places, except we use a constant field extension of the function field for the function space but restrict ourselves to evaluating at rational places over the original base field. Let us give a brief idea why restricting evaluation points to a subfield enables correcting more errors. The idea behind list-decoding results for folded RS (or derivative) codes in References [14, 17] is that the encoding of a message polynomial \(f \in \mathbb {F}_Q[X]\) includes the values of \(f\) and closely related polynomials at the evaluation points. Given a string not too far from the encoding of \(f\), one can use this property together with the “interpolation method” to find an algebraic condition that \(f\) (and its closely related polynomials) must satisfy, e.g., \(A_0(X) + A_1(X) f(X) + A_2(X) f^q(X) + \cdots + A_s(X) f^{q^{s-1}}(X)\equiv 0\pmod {x^{q-1}-\gamma }\) in the case of folded Reed–Solomon codes [14] (here \(\gamma\) is a primitive element of \(\mathbb {F}_q\), and the \(A_0,A_1,\dots ,A_s\) are low-degree polynomials found by the decoder). The solutions \(f(X)\) to this equation form an affine space, which can be efficiently found (and later pruned for list-size reduction when we pre-code messages into a subspace-evasive set).

For Reed–Solomon codes as in Definition 6, the encoding only includes the values of \(f\) at \(\alpha _1,\alpha _2,\dots ,\alpha _n\). But since \(\alpha _i \in \mathbb {F}_q\), we have \(f(\alpha _i)^q = f^\sigma (\alpha _i)\), where \(f^\sigma\) is the polynomial obtained by the action of the Frobenius automorphism that maps \(y \mapsto y^q\) on \(f\) (formally, \(f^\sigma (X) = \sum _{j=0}^{k-1} f_j^q X^j\) if \(f(X) = \sum _{j=0}^{k-1} f_j X^j\)). Thus the decoder can “manufacture” the values of \(f^\sigma\) (and similarly \(f^{\sigma ^2}, f^{\sigma ^3}\), etc.) at the \(\alpha _i\). Applying the above approach then enables finding a relation \(A_0(X) + A_1(X) f(X) + A_2(X) f^\sigma (X) + \cdots + A_s(X) f^{\sigma ^{s-1}}(X)=0\), which is again an \(\mathbb {F}_q\)-linear condition on \(f\) that can be used to solve for \(f\). We remark here that this approach can also be applied effectively to linearized polynomials and can be used to construct variants of Gabidulin codes that are list-decodable up to the optimal \(1-R\) fraction of errors (where \(R\) is the rate) in the rank metric [18].

To extend this idea to algebraic-geometric codes, we work with constant extensions \(\mathbb {F}_{q^m} \cdot F\) of algebraic function fields \(F/\mathbb {F}_q\). The messages belong to a Riemann–Roch space over \({\mathbb {F}_{q^m}}\), but they are encoded via their evaluations at \(\mathbb {F}_q\)-rational points. For decoding, we recover the message function \(f\) in terms of the coefficients of its local expansion at some rational point \(P\). (The Reed–Solomon setting is a special case when \(F =\mathbb {F}_q(X)\), and \(P\) is 0, i.e., the zero of \(X\).) To get the best tradeoffs, we use AG codes based on a tower of function fields due to Garcia and Stichtenoth [6, 7] that achieve the optimal tradeoff between the number of \(\mathbb {F}_q\)-rational points and the genus. For this case, we recover messages in terms of their local expansion around the point at infinity \({P_{\infty }}\), which is also used to define the Riemann–Roch space of messages. So we treat this setting separately (Section 8.3) after describing the framework for general AG codes first.

The first approach follows along the lines of Reference [17], and we only encode messages in a subspace-evasive set, which has small intersection with low-dimensional subspaces. Implementing this in our case, however, leads to several problems. First, since the subspace we like to avoid intersecting much has large dimension, the list-size bound will be linear in the code length and not a constant like in our final result (by “a constant,” we mean that the list size is independent of the code length and dependent on \(\varepsilon\)). More severely, we cannot go over the elements of this subspace to prune the list as that would take exponential time. To solve the latter problem, we observe that the subspace has a special “periodic” structure and exploit this to show the existence of large h.s.e. subsets that have small intersection with the projection of the subspace on certain prefixes. Isolating the periodic property of the subspaces, and formulating the right notion of evasiveness w.r.t. to such subspaces, is an important aspect of this work.

We also give a construction of good h.s.e. sets using limited wise independent sample spaces, in a manner enabling the efficient iterative computation of the final list of intersecting elements. Further, our construction allows for efficient indexing into the h.s.e. set, which leads to an efficient encoding algorithm for our code. As a further ingredient, we note that the number of possible subspaces that arise in the decoding is much smaller than the total number of possibilities. Using this together with an added trick in the h.s.e. set construction, we are able to reduce the list size to a constant.

The approach based on h.s.e. sets leads to excellent list size; however, we only know randomized constructions of h.s.e. sets with the required properties. Our second approach to prune the subspace of possible solutions is based on subspace designs and leads to deterministic subcode constructions. More precisely speaking, the coefficients \(f_0,f_1,\dots ,f_{k-1}\) of the message polynomial (which belong to the extension field \(\mathbb {F}_{q^m}\)) are pinned down by the linear-algebraic list decoder to a periodic subspace with the property that there is an \(\mathbb {F}_q\)-subspace \(W \subset \mathbb {F}_{q^m}\) such that once \(f_0,f_1,\dots ,f_{i-1}\) are fixed, \(f_i\) belongs to a coset of \(W\). Our idea then is to restrict \(f_i\) to belong to a subspace \(H_i\), where \(H_1,H_2,\dots ,H_k\) are a collection of subspaces in \(\mathbb {F}_q^m\) such that for any \(s\)-dimensional subspace \(W \subset \mathbb {F}_q^m\), only a small number of them have non-trivial intersection with \(W\). More precisely, we require that \(\sum _{i=1}^k \dim (W \cap H_i)\) is small. We call such a collection \(\lbrace H_i\rbrace _{i=1}^k\) as a subspace design in \(\mathbb {F}_q^m\). We feel that the concept of subspace designs is interesting in its own right and view the introduction of this notion in Section 10 as a key contribution in this work. Indeed, subsequent work by Forbes and Guruswami [5] highlighted the central role played by subspace designs in “linear-algebraic pseudorandomness” and in particular how they lead to rank condensers and dimension expanders.

A simple probabilistic argument shows that, with high probability, any \(q^{\Omega (\varepsilon m)}\) subspaces of dimension \((1-\varepsilon) m\) that are randomly chosen have small total intersection with every \(s\)-dimensional \(W\). This construction can also be derandomized, though the construction complexity of the resulting codes becomes quasi-polynomial with this approach for the parameter choices needed in the construction.

Fortunately, in a follow-up to Reference [20], Guruswami and Kopparty gave explicit constructions of subspace designs with parameters nearly matching the random constructions [12]. One can pre-code with this subspace design to get explicit list-decodable sub-codes of Reed–Solomon codes whose evaluation points are in a subfield (Section 11.2.1). However, this construction inherits the large field size of Reed–Solomon codes.

For explicit subcodes of algebraic-geometric codes using subspace designs we need additional ideas. The dimension \(k\) in the case of AG codes is much larger than the alphabet size \(q^m\) (in fact that is the whole point of generalizing to AG codes). So we cannot have a subspace design in \(\mathbb {F}_q^m\) with \(k\) subspaces. We therefore use several “layers” of subspace designs in a cascaded fashion (Section 10.4)—the first one in \(\mathbb {F}_q^m\), the next one in \(\mathbb {F}_q^{m_1}\) for \(m_1 \gg q^{\sqrt {m}}\), the third one in \(\mathbb {F}_q^{m_2}\) for \(m_2 \gg q^{\sqrt {m_1}}\), and so on. Since the \(m_i\)’s increase exponentially, we only need about \(\log ^* k\) levels of subspace designs. Each level incurs about a factor \(1/\varepsilon\) increase in the dimension of the “periodic subspace” (\(W\) when we begin) at the corresponding scale. With a careful technical argument and choice of parameters, we are able to obtain the bounds of Theorem 1.1(ii).

A discrete valuation of \(F/\mathbb {F}_q\) is a map from \(F\) to \(\mathbb {Z}\cup \lbrace + \infty \rbrace\) satisfying certain properties (see Reference [32][Definition 1.19]). Then each discrete valuation \(\nu\) from \(F/\mathbb {F}_q\) to \(\mathbb {Z}\cup \lbrace + \infty \rbrace\) defines a valuation ring \(O=\lbrace f\in F:\; \nu (f)\geqslant 0\rbrace\) that is a local ring [32][Theorem 1.1.13]. The maximal ideal \(P\) of \(O\) is given by \(P=\lbrace f\in F:\; \nu (f)\gt 0\rbrace\) and it is called a place. We denote the valuation \(\nu\) and the local ring \(O\) corresponding to \(P\) by \(\nu _P\) and \(O_P\), respectively. The residue class field \(O_P/P\), denoted by \(F_P\), is a finite extension of \(\mathbb {F}_q\). The extension degree \([F_P:\mathbb {F}_q]\) is called the degree of \(P\), denoted by \(\deg (P)\). A place of degree one is called a rational place.

Let \(\mathbb {P}_F\) denote the set of places of \(F\). The divisor group, denoted by \({\rm Div}(F)\), is the free Abelian group generated by all places in \(\mathbb {P}_F\). An element \(G=\sum _{P\in \mathbb {P}_F}n_PP\) of \({\rm Div}(F)\) is called a divisor of \(F\), where \(n_P=0\) for almost all \(P\in \mathbb {P}_F\). We denote \(n_p\) by \(\nu _P(G)\). The degree of \(G\) is defined by \(\deg (G)=\sum _{P\in \mathbb {P}_F}n_P\deg (P)\). The support, denoted by \({\rm Supp }(G)\), of \(G\) is the set \(\lbrace P\in \mathbb {P}_F:\; n_P\ne 0\rbrace\). Thus, \({\rm Supp }(G)\) of a divisor \(G\) is always a finite subset of \(\mathbb {P}_F\). We say that a divisor \(G \geqslant 0\) if \(\nu _P(G) \geqslant 0\) for all \(P \in \mathbb {P}_F\).

For a nonzero function \(z\in F\), the principal divisor of \(z\) is defined to be \({\rm div}(z)=\sum _{P\in \mathbb {P}_F}\nu _P(z)P\). The principal divisor \({\rm div}(z)\) is indeed a divisor as \(z\) has only finitely many zeros and poles. The zero and pole divisors of \(z\) are defined to be \({\rm div}(z)_0=\sum _{\nu _P(z)\gt 0}\nu _P(z)P\) and \({\rm div}(z)_{\infty }=-\sum _{\nu _P(z)\lt 0}\nu _P(z)P\), respectively. Then we have \(\deg ({\rm div}(z))=0\), i.e., \(\deg ({\rm div}(z)_0)=\deg ({\rm div}(z)_\infty)\). For two functions \(f,g\in F\) and a place \(P\), we have \(\nu _P(f+g)\geqslant \min \lbrace \nu _P(f),\nu _P(g)\rbrace\), and the equality holds if \(\nu _p(f)\ne \nu _P(g)\) (note that \(\nu _P(0)=+\infty\)). This implies that \(f+g\ne 0\) if \(\nu _P(f)\ne \nu _P(g)\).

If \(F\) is the rational function field \(\mathbb {F}_q(x)\), then every discrete valuation of \(F/\mathbb {F}_q\) is given by either \(\nu _{\infty }\) or \(\nu _{p(x)}\) for an irreducible polynomial \(p(x)\), where \(\nu _{\infty }\) is defined by \(\nu _{\infty }(f/g)=\deg (g)-\deg (f)\) and \(\nu _{p(x)}(f/g)=a-b\) with \(p(x)^a||f\) and \(p(x)^b||g\) for two nonzero polynomials \(f,g\in \mathbb {F}_q[x]\). It is straightforward to verify that the degrees of places corresponding to \(\nu _{\infty }\) and \(\nu _{p(x)}\) are 1 and \(\deg (p(x))\), respectively.

One of our code constructions will be based on evaluations of functions at rational points over a subfield. For this purpose, we will work with constant field extensions over \(\mathbb {F}_{q^m}\) of a function field over a base field \(\mathbb {F}_q\). We describe these now.

Let \(F/\mathbb {F}_q\) be a function field. Fix an algebraic closure \(\bar{F}\) of \(F\). Then \(\bar{F}\) contains the algebraic closure \(\bar{\mathbb {F}}_q=\cup _{i=1}^{\infty }\mathbb {F}_{q^i}\) as well. Hence, for \(m\geqslant 1\), \(\bar{F}\) contains the extension field \(\mathbb {F}_{q^m}\) of \(\mathbb {F}_q\). The composite field \(F_m:=\mathbb {F}_{q^m}\cdot F\) is defined to be the smallest subfield of \(\bar{F}\) that contains both \(F\) and \(\mathbb {F}_{q^m}\). For a place \(P\) of \(F\) and a place \(P^{\prime }\) of \(F_m\), we say that \(P\) lies under \(P^{\prime }\) (or, equivalently, \(P^{\prime }\) lies above \(P\)), denoted by \(P|P^{\prime }\), if \(P\subseteq P^{\prime }\). Then we have the following facts (see Reference [32][Propositions 3.6.1 and 3.6.3]):

A divisor \(G=\sum _{P\in \mathbb {P}_F}n_PP\) of \(F\) can be viewed as the divisor \(\sum _{P\in \mathbb {P}_F}\sum _{P^{\prime }|P}n_PP^{\prime }\) of \(F_m\). We still denote this divisor of \(F_m\) by \(G\). By (iv) of the above facts, a rational place \(P\) of \(F\) continues to be a rational place \(P^{\prime }\) of \(F_m\). The valuation ring of \(P^{\prime }\) is the tensor product of \(O_P\) with \(\mathbb {F}_{q^m}\), i.e, \(O_{P^{\prime }}=O_P\otimes _{\mathbb {F}_q}\mathbb {F}_{q^m}=\lbrace \sum _{i=1}^ma_i\alpha _ix_i:\; a_i\in \mathbb {F}_q,x_i\in O_P\rbrace\), where \(\alpha _1,\dots ,\alpha _m\) is an \(\mathbb {F}_q\)-basis of \(\mathbb {F}_{q^m}\). If there is no confusion, then we still denote \(P^{\prime }\) by \(P\).

For a divisor \(G\) of \(F/\mathbb {F}_q\), we define the Riemann–Roch space associated with \(G\) bywhere \(F^*\) denotes the set of nonzero elements of \(F\). Then \(\mathcal {L}(G)\) is a finite-dimensional space over \(\mathbb {F}_q\), and its dimension \(\ell (G)\) is determined by the Riemann–Roch theorem, which giveswhere \({\mathfrak {g}}\) is the genus of \(F\) and \(W\) is a canonical divisor of degree \(2{\mathfrak {g}}-2\). Therefore, we always have that \(\ell (G)\geqslant \deg (G)+1-{\mathfrak {g}}\) and the equality holds if \(\deg (G)\geqslant 2{\mathfrak {g}}-1\) [32][Theorems 1.5.15 and 1.5.17].

Consider finite extension \(\mathbb {F}_{q^m}\) over \(\mathbb {F}_q\) and the constant extension \(F_m:=\mathbb {F}_{q^m}\cdot F\) over \(F\). As a divisor \(G\) of \(F\) can be viewed as a divisor of \(F_m\), we can consider the Riemann–Roch space in \(F_m\) given byThen it is clear that \(\mathcal {L}_m(G)\) contains \(\mathcal {L}(G)\) and \(\mathcal {L}_m(G)\) is a finite-dimensional vector space over \(\mathbb {F}_{q^m}\). Furthermore, \({\mathcal {L}}_m(G)\) is the tensor product of \({\mathcal {L}}(G)\) with \({\mathbb {F}_{q^m}}\) (see Reference [31][Proposition 5.8 of Chapter II]). This implies thatand an \(\mathbb {F}_q\)-basis of \({\mathcal {L}}(G)\) is also an \({\mathbb {F}_{q^m}}\)-basis of \({\mathcal {L}}_m(G)\).

The automorphisms of the function field \(F\) that fix \(\mathbb {F}_q\) are denoted by \({\rm Aut }(F/\mathbb {F}_q)\). For an automorphism \(\phi \in {\rm Aut }(F/\mathbb {F}_q)\) and and a function \(f\in F\), we denote by \(f^{\phi }\) the action of \(\phi\) on \(f\). For a place \(P\), define a map \(\nu _{P^\phi }\) from \(F\) to \(\mathbb {Z}\cup \lbrace + \infty \rbrace\) given by \(f\mapsto \nu _P(f^{\phi ^{-1}})\). Then one can show that \(\nu _{P^\phi }\) indeed satisfies the properties given in Reference [32][Definition 1.19], and hence it is a discrete valuation. The valuation ring \(O_{P^\phi }\) of \(\nu _{P^\phi }\) is given byand the maximal ideal of this valuation ring is \(\lbrace \phi (x):\; x\in P\rbrace\). Therefore, this maximal ideal is a place of \(F\), denoted by \(P^\phi\). Moreover, \(\phi\) induces an \(\mathbb {F}_q\)-isomorphism between the residue fields \(F_P\) and \(F_{P^\phi }\). Hence, we have \(\deg (P)=\deg (P^\phi)\).

For a function \(f\) and a rational place \(P\in \mathbb {P}_F\) with \(\nu _P(f)\geqslant 0\), we denote by \(f(P)\) the residue class of \(f\) in the residue class field \(F_P\) at \(P\). If \(\nu _P(f)\geqslant 0\) and \(\nu _{P^{\phi }}(f)\geqslant 0\), then one has that \(\nu _P(f^{\phi ^{-1}})\geqslant 0\). Furthermore, there is an \(\mathbb {F}_q\)-isomorphism between \(O_P\) and \(O_{P^\phi }\) given by \(f\mapsto f^\phi\). This induces the identity map between \(F_P=\mathbb {F}_q\) and \(F_{P^\phi }=\mathbb {F}_q\). Hence, \(f(P)=f^\phi (P^\phi)\). Replacing \(f\) by \(f^{\phi ^{-1}}\) gives \(f(P^{\phi })=f^{\phi ^{-1}}(P)\).

For a divisor \(G=\sum _{P\in \mathbb {P}_F}m_PP\) we denote by \(G^{\phi }\) the divisor \(\sum _{P\in \mathbb {P}_F}m_PP^{\phi }\). Therefore, we have

Next we consider the constant extension \(F_m=\mathbb {F}_{q^m}\cdot F\). Let \(\sigma\) be the Frobenius automorphism \(\mathbb {F}_{q^m}/\mathbb {F}_q\), i.e., \(\sigma (\alpha)=\alpha ^q\) for any \(\alpha \in \mathbb {F}_{q^m}\). Then \(\sigma\) can be extended to an automorphism of \({\rm Aut }(F_m/F)\) given by \(\sigma (f)=f\) for any \(f\in F\) and \(\sigma (\alpha)=\alpha ^q\) for any \(\alpha \in \mathbb {F}_{q^m}\). If \(P\) is a rational place of \(F\), then \(P\) remains to be a rational place \(P^{\prime }\) of \(F_m\) and hence \(\sigma (O_{P^{\prime }})=\sigma (O_P\otimes _{\mathbb {F}_q}\mathbb {F}_{q^m})=O_P\otimes _{\mathbb {F}_q}\mathbb {F}_{q^m}=O_{P^{\prime }}\). Thus, we have \((P^{\prime })^\sigma =P^{\prime }\).

The function field \(F_e\) has \(r^{e+1}+1\) rational places. One of these is the “point at infinity,” which is the unique pole \({P_{\infty }}\) of \(x_1\) (and is fully ramified). The other \(r^{e+1}\) come from the rational places lying over the unique zero \(P_\alpha\) of \(x_1-\alpha\) for each \(\alpha \in \mathbb {F}_q\). Note that for every \(\alpha \in \mathbb {F}_q\), \(P_\alpha\) splits completely in \(F_e\), i.e., there are \(r^{e-1}\) rational places lying over \(P_\alpha\). Intuitively, one can think of the rational places of \(F_e\) (besides \({P_{\infty }}\)) as being given by \(e\)-tuples \((\alpha _1,\alpha _2,\dots ,\alpha _e)\in \mathbb {F}_q^e\) that satisfy \(\alpha _{i+1}^r+\alpha _{i+1}=\alpha _i^{r+1}\) for \(i=1,2,\dots ,e-1\). For each value of \(\alpha \in \mathbb {F}_q\), there are precisely \(r\) solutions to \(\beta \in \mathbb {F}_q\) satisfying \(\beta ^r + \beta = \alpha ^{r+1}\), so the number of such \(e\)-tuples is \(r^{e+1}\) (\(q=r^2\) choices for \(\alpha _1\), and then \(r\) choices for each successive \(\alpha _i\), \(2 \leqslant i \leqslant e\)).

For an integer \(l\), we consider the Riemann–Roch space defined byBy the Riemann–Roch theorem, its dimension \(\ell (l{P_{\infty }})\) is at least \(l-{\mathfrak {g}}_e+1\), and, furthermore,where \({\mathfrak {g}}_e\) is the genus of the function field \(F_e\) given by Equation (6).

A basis over \(\mathbb {F}_q\) of \({\mathcal {L}}(l{P_{\infty }})\) can be explicitly constructed as follows:

We stress that evaluating elements of \({\mathcal {L}}(l{P_{\infty }})\) at the rational places of \(F_e\) (other than \({P_{\infty }}\)) is easy: We simply have to evaluate a linear combination of the monomials allowed in Equation (5) at the tuples \((\alpha _1,\alpha _2,\dots ,\alpha _e)\in \mathbb {F}_q^e\) mentioned above. In other words, it is just evaluating an \(e\)-variate polynomial at a specific subset of \(r^{e+1}\) points of \(\mathbb {F}_q^e\), and can be accomplished in polynomial time.

The genus \({\mathfrak {g}}_e\) of the function field \(F_e\) is given bywhere the second and the last inequalities used, \({e\choose i}\leqslant e^i\) and \(r \geqslant 2e\), respectively, while the first inequality used the following:

Let \(\gamma\) be a primitive element of \(\mathbb {F}_q\). Then for \(i\geqslant 1\), one has \(\gamma ^{r(r+1)^{i}}=\gamma ^{(r^2+r)(r+1)^{i-1}}=\gamma ^{(1+r)(r+1)^{i-1}}=\gamma ^{(r+1)^{i}}\). Consider the automorphism \(\sigma \in {\rm Aut}(F_e/\mathbb {F}_q)\) defined byIndeed, \(\sigma\) defines an automorphism \(\sigma \in {\rm Aut}(F_e/\mathbb {F}_q)\), since after the action of \(\sigma\) Equation (4) becomes \((\gamma ^{(r+1)^{i}}x_{i+1})^r+\gamma ^{(r+1)^{i}}x_{i+1}=(\gamma ^{(r+1)^{i-1}}x_i)^{r+1}\), i.e., \(x_{i+1}^r+x_{i+1}=x_i^{r+1}\) by cancelling \(\gamma ^{(r+1)^{i}}\) in both the sides. The order of \(\sigma\) is \(q-1\), and, furthermore, we have the following facts:

The function field \(K_e\) has at least \(r^{e-1}(r^2-r)+1\) rational places. One of these is the “point at infinity,” which is the unique pole \({P_{\infty }}\) of \(x_1\) (and is fully ramified). The other \(r^{e-1}(r^2-r)\) come from the rational places lying over the unique zero of \(x_1-\alpha\) for each \(\alpha \in \mathbb {F}_q\) with \(\alpha ^r+\alpha \not=0\). Note that for every \(\alpha \in \mathbb {F}_q\) with \(\alpha ^r+\alpha \not=0\), the unique zero of \(x_1-\alpha\) splits completely in \(K_e\), i.e., there are \(r^{e-1}\) rational places lying over the zero of \(x_1-\alpha\). Let \(\mathbb {P}\) be the set of all the rational places lying over the zero of \(x_1-\alpha\) for all \(\alpha \in \mathbb {F}_q\) with \(\alpha ^r+\alpha \not=0\). Then, intuitively, one can think of the \(r^{e-1}(r^2-r)\) rational places in \(\mathbb {P}\) as being given by \(e\)-tuples \((\alpha _1,\alpha _2,\dots ,\alpha _e)\in \mathbb {F}_q^e\) that satisfy \(\alpha _{i+1}^r+\alpha _{i+1}=\frac{\alpha _i^{r}}{\alpha _i^{r-1}+1}\) for \(i=1,2,\dots ,e-1\) and \(\alpha _1^r+\alpha _1\ne 0\). For each value of \(\alpha \in \mathbb {F}_q\), there are precisely \(r\) solutions to \(\beta \in \mathbb {F}_q\) satisfying \(\beta ^r + \beta = \frac{\alpha ^{r}}{\alpha ^{r-1}+1}\), so the number of such \(e\)-tuples is \(r^{e-1}(r^2-r)\) (\(r^2-r\) choices for \(\alpha _1\), and then \(r\) choices for each successive \(\alpha _i\), \(2 \leqslant i \leqslant e\)).

As shown in Reference [30], every function of \(K_e\) with a pole only at \({P_{\infty }}\) has an expression of the formwhere \(a\geqslant 0, c_{{\bf i}}\in \mathbb {F}_q\), and for \(1\leqslant j\lt e\), \(h_j=x_j^{r-1}+1\) and \(\pi _j=h_1h_2\dots h_j\). Moreover, Shum et al. [30] present an algorithm running in time polynomial in \(l\) that outputs a basis over \(\mathbb {F}_q\) of \({\mathcal {L}}(l{P_{\infty }})\) in the above form.

We stress that evaluating elements of \({\mathcal {L}}(l{P_{\infty }})\) at the rational places of \(\mathbb {P}\) is easy: We simply have to evaluate a linear combination of the monomials allowed in Equation (8) at the tuples \((\alpha _1,\alpha _2,\dots ,\alpha _e)\in \mathbb {P}\) (note that \(h_i(P),\pi _j(P)\in \mathbb {F}_q^*\) for every \(P\in \mathbb {P}\)). In other words, it is just evaluating an \(e\)-variate polynomial at a specific subset of \(r^{e-1}(r^2-r)\) points of \(\mathbb {F}_q^e\), and can be accomplished in polynomial time.

The genus \({\mathfrak {g}}_e\) of the function field \(K_e\) is given byThus, the genus \({\mathfrak {g}}_e\) is at most \(r^e\). (Compare this with the \(e r^e\) bound for the Hermitian tower, where \(e\leqslant \frac{r}{2}=\frac{\sqrt {q}}{2}\); this smaller genus is what allows to pick \(e\) as large as we want in the Garcia–Stichtenoth tower, while keeping the field size \(q\) fixed.)

Let \(\gamma\) be a primitive element of \(\mathbb {F}_q\) and consider the automorphism \(\sigma \in {\rm Aut}(K_e/\mathbb {F}_q)\) defined byIndeed, \(\sigma\) defines an automorphism \(\sigma \in {\rm Aut}(K_e/\mathbb {F}_q)\), since after the action of \(\sigma\) Equation (7) becomes \((\gamma ^{r+1} x_{i+1})^r+\gamma ^{r+1} x_{i+1}=\frac{(\gamma ^{r+1}x_i)^{r}}{(\gamma ^{r+1}x_i)^{r-1}+1}\), i.e., \(x_{i+1}^r+x_{i+1}=\frac{x_i^{r}}{x_i^{r-1}+1}\) by cancelling \(\gamma ^{r+1}\) on both the sides (note the fact that \(\gamma ^{(r+1)r}=\gamma ^{r+1}\) and \(\gamma ^{r^2-1}=1\)). The order of \(\sigma\) is \(r-1\), and, furthermore, we have the following facts:

Let \(F/\mathbb {F}_q\) be a function field of genus \({\mathfrak {g}}\). Let \({P_{\infty }}, P_1,P_2,\dots ,P_N\) be \(N+1\) distinct \(\mathbb {F}_q\)-rational places. Let \(\sigma \in {\rm Gal}({\mathbb {F}_{q^m}}/\mathbb {F}_q)\) be the Frobenius automorphism, i.e., \(\alpha ^{\sigma }=\alpha ^q\) for all \(\alpha \in {\mathbb {F}_{q^m}}\). Then we can extend \(\sigma\) to an automorphism in \({\rm Gal}(F_m/F)\), where \(F_m\) is the constant extension \({\mathbb {F}_{q^m}}\cdot F\). Note that \(P^{\sigma }=P\) for any place of \(F\).

Consider the Goppa geometric code defined by

We have the following well-known result on the parameters of the above algebraic-geometric codes.

As with the case of folded AG codes, the decoding algorithm will recover the message function \(f\) via the coefficients of its local expansion at some place \(P\). Therefore, we will identify the message symbols with coefficients of local expansion of the function \(f\) and encode into a subcode of \(C(m;l)\).

We now present a list-decoding algorithm for the above codes. The algorithm follows the linear-algebraic list-decoding algorithm for RS codes. It is quite similar to that of folded algebraic-geometric codes. Suppose a codeword encoding \(f \in {\mathcal {L}}_m((k+2{\mathfrak {g}}-1){P_{\infty }})\) is transmitted and received as \({\bf y}=(y_1,y_2,\dots ,y_N)\).

Given such a received word, we will interpolate a nonzero linear polynomial over \(F_m\),where \(A_i \in {\mathcal {L}}_m(D{P_{\infty }})\) for \(i=1,2,\dots ,s\) and \(A_0\in {\mathcal {L}}_m((D+k+2{\mathfrak {g}}-1){P_{\infty }})\) with the degree parameter \(D\) chosen to beIf we fix a basis of \({\mathcal {L}}_m(D{P_{\infty }})\) and extend it to a basis of \({\mathcal {L}}_m((D+k+2{\mathfrak {g}}-1){P_{\infty }})\), then the degrees of freedom of \(A_0\) is at least \(D+k+{\mathfrak {g}}\) and the degrees of freedom of \(A_i\) is at least \(D-{\mathfrak {g}}+1\) for \(i\geqslant 1\). Thus, the total degrees of freedom in the polynomial \(Q\) equalsfor the above choice (30) of \(D\). The interpolation requirements on \(Q \in F_m[Y_1,\dots ,Y_s]\) are the following:for \(i=1,2,\dots ,N\). Thus, we have a total of \(N\) equations to satisfy. Since this number is less than the number of freedoms in \(Q\), we can conclude that a nonzero linear function \(Q \in F_m[Y_1,\dots ,Y_s]\) of the form (29) satisfying the interpolation conditions (32) can be found by solving a homogeneous linear system over \({\mathbb {F}_{q^m}}\) with at most \(N\) constraints and at least \(s(D-{\mathfrak {g}}+1)+D+k+{\mathfrak {g}}\) variables.

The following lemma gives the algebraic condition that the message functions \(f \in {\mathcal {L}}_m((k+2{\mathfrak {g}}-1){P_{\infty }})\) we are interested in list decoding must satisfy.

Decoding. Recall that the first \(k\) coefficients of the local expansion of \(f \in {\mathcal {L}}_m(l P_\infty)\) around \(P\) is precisely the message that was encoded in the code \(\widetilde{C}(m;k)\) of Definition 9.

Therefore, combining Lemmas 7.7 and 7.8, and recalling the choice of \(D\) in Equation (30), we can conclude the following result about list-decodability of our code construction.

Instead of encoding arbitrary \({\mathbf {f}} \in \mathbb {F}_q^k\) by the folded Hermitian code (Definition 11), we can restrict the messages \({\mathbf {f}}\) to belong to the range of our h.s.e. set, so that the affine space of solutions guaranteed by Lemma 7.4 can be efficiently pruned to a small list. The formal claim is below.

Choosing parameters. . Let \(\varepsilon \gt 0\) be a small positive constant, and a family of codes of length \(N\) (assumed large enough) and rate \(R\in (0,1)\) is sought. Pick \(n\) to be a growing parameter.

By picking \(s = \Theta (1/\varepsilon)\), \(m = \Theta (1/\varepsilon ^2)\), \(r = \lfloor \log n \rfloor\), \(e = \lceil \frac{\log n}{\log \log n} \rceil\), \(\zeta = (\log n \log \log n)^{-1}\), \(N = \lfloor \frac{(r^2-1)r^e}{m}\rfloor\), and \(k\) proportional to \(Nm\) in Theorem 11.1, we can conclude the following.

Our promised main result (Theorem 1.1) achieves better parameters than the above, namely an alphabet size of \(\exp (\tilde{O}(1/\varepsilon ^2))\) and list size of \(O(1/(R\varepsilon))\). This is based on the Garcia–Stichtenoth tower and is described next.

Similarly to Section 11.1.1, we now show how to pre-code the messages of the FGS code with a h.s.e. subset. Here we will work with a base field \(\mathbb {F}_q\) whose size is fixed and independent of the code dimension \(k\), which will lead both to constant alphabet size and constant list size. To accommodate the requirement that \(k \leqslant q^{O(\zeta \Delta)}\), we work with a larger “period” size for the h.s.e. sets to evade. Recall Observation 3.2, which implies that if \(H\) is an \((s,\Delta ,b)\)-ultra periodic subspace of \(\mathbb {F}_q^k\) for \(k=b\Delta\), then \(H\) is also \((su,\Delta u, b/u)\)-periodic for every integer \(u\geqslant 1\) with \(u|b\). Thus we can scale up the period size using the ultra-periodicity of the subspace guaranteed by the decoder of Theorem 8.6. Following Remark 1, we actually only need a weaker property to prune via h.s.e. sets, which can also be ensured without ultra-periodicity. But since we have the stronger property available, we make use of it (this is also for sake of uniformity with the pruning based on subspace designs of Section 11.2, which can also be applied to the FGS code).

As in the Hermitian case, instead of encoding arbitrary \({\mathbf {f}} \in \mathbb {F}_q^k\) by the folded Garcia–Stichtenoth code, we will restrict the messages \({\mathbf {f}}\) to belong to the range of our h.s.e. set. This will ensure that the affine space of solutions can be efficiently pruned to a small list.

Choosing parameters. . Finally, all that is left to be done is to pick parameters to show how the above can lead to optimal rate list-decodable codes over a constant-sized alphabet that further achieve very good list size.

Let \(\varepsilon \gt 0\) be a small positive constant, and a family of codes of length \(N\) (assumed large enough) and rate \(R\in (0,1)\) is sought. Pick \(n\) to be a growing parameter.

Let us pick \(s = \Theta (1/\varepsilon)\), \(m = \Theta (1/\varepsilon ^2)\), \(\zeta = \varepsilon /12\), \(r = \Theta (1/\varepsilon)\), \(q=r^2\), and \(e = \lceil \frac{\log n}{\log r} \rceil\), \(N = \lfloor \frac{(r-1)r^e}{m}\rfloor\), and \(k = R N m (1+\varepsilon)\). This ensures that (i) there are at least \(n=Nm\) rational places and so we get a code of length at least \(n/m=N\), (ii) the rate of the code \(C_2\) is at least \(R\), and (iii) the error fraction (41) is at least \(1-R-\varepsilon\).

The remaining part is to pick a multiple \(\Delta\) of \((r-1)\) so that the \(k \leqslant q^{\zeta \Delta /2}\) condition is met. This can be achieved by choosing \(u = \lceil \frac{\log n}{\log (1/\varepsilon)} \rceil\) and \(\Delta = (r-1) u\). With these choices, we can conclude the following, which is our main randomized code construction promised in part (i) of Theorem 1.1.

It may be instructive to recap why the Hermitian tower could not give a result like the above one. In the Hermitian case, the ratio \({\mathfrak {g}}_e/n\) of the genus to the number of rational places was about \(e/r=e/\sqrt {q}\), and thus we needed \(q \gt e^2\). Since the period \(\Delta\) was about \(q\), the running time of the decoder was bigger than \(q^{\Omega (\zeta q)}\), whereas the length of the code was at most \(q^{O(\sqrt {q})}\). This dictated the choice of \(q \approx \log ^2 n\), and then to keep the running time polynomial, we had to take \(\zeta \approx (\log n \log \log n)^{-1}\).

We begin with the case of Reed–Solomon codes as considered in Section 7.1. For a finite field \(\mathbb {F}_q\), constant \(\varepsilon \gt 0\), integers \(n,k,m,s\) satisfying \(1 \leqslant k \lt n \leqslant q\) and \(1 \leqslant s \leqslant \varepsilon m/12\), we will define subcodes of \(\mathrm{RS}^{(q,m)}[n,k]\). Below for a polynomial \(f \in \mathbb {F}_{q^m}[X]\) with \(k\) coefficients \(f_0,f_1,\dots ,f_{k-1}\), we denote by \({\mathbf {f_0}},{\mathbf {f_1}},\dots ,{\mathbf {f_{k-1}}}\) the representation of these coefficients as vectors in \(\mathbb {F}_q^m\) by fixing some \(\mathbb {F}_q\)-basis of \({\mathbb {F}_{q^m}}\).

Define the subcode \(\widehat{\mathsf {RS}}\) of \(\mathrm{RS}^{(q,m)}[n,k]\) consisting of the encodings of \(f \in \mathbb {F}_{q^m}[X]\) such that \(({\mathbf {f_0}},{\mathbf {f_1}},\dots ,{\mathbf {f_{k-1}}}) \in V\) for a subspace \(V \subseteq \mathbb {F}_q^{mk}\) guaranteed by Theorem 10.5, when applied with the parameter choicesNote that \(\widehat{\mathsf {RS}}\) is an \(\mathbb {F}_q\)-linear code over the alphabet \({\mathbb {F}_{q^m}}\) of rate \((1-\varepsilon)k/n\), and it can be constructed in deterministic \(q^{O(m^2)}\) time, or Las Vegas \(q^{O(ms)}\) time.¹²

By picking \(s = \Theta (1/\varepsilon)\) and \(m = \Theta (1/\varepsilon ^2)\) in the above construction, we can conclude the following.

We note that the above list-decoding guarantee is in fact weaker than what is achieved for folded Reed–Solomon codes in Reference [17], where the codewords were pinned down to a dimension \(O(1/\varepsilon)\) subspace. We can improve the list size above to \(\mathrm{poly}(1/\varepsilon)\) using pseudorandom subspace-evasive sets as in Reference [17] or to \(\exp (\varepsilon ^{-O(1)})\) using the explicit subspace-evasive sets from Reference [3]. The main point of the above result is not the parameters but that an explicit subcode of RS codes has optimal list-decoding radius with polynomial complexity.

We now pre-code the codes constructed in Section 8.3. For a finite field \(\mathbb {F}_q\), constant \(\varepsilon \gt 0\), and integers \(s,m\) satisfying \(1 \leqslant s \leqslant O(\varepsilon m/\log (1/\varepsilon))\) and \(m \geqslant \Omega (1/\varepsilon ^2)\), we will define subcodes of \(\mathrm{GS}^{(q,m)}[N,k]\) guaranteed by Theorem 8.8. Note that messages space of this code can be identified with \(\mathbb {F}_q^{mk}\).

Define the subcode \(\widehat{GS}\) of \(\mathrm{GS}^{(q,m)}[N,k]\) consisting of the encodings of a subspace \(U \subseteq \mathbb {F}_q^{mk}\) guaranteed by Theorem 10.8, when applied with the parameter choicesNote that \(\widehat{GS}\) is an \(\mathbb {F}_q\)-linear code over the alphabet \({\mathbb {F}_{q^m}}\) of rate \((1-\varepsilon)k/N\). Also, it can be constructed in \(\mathrm{poly}(k,m,q)\) time by virtue of the construction complexity of \(U\).

By taking \(q = \Theta (1/\varepsilon ^2)\), and choosing \(s = \Theta (1/\varepsilon)\) and \(m = \Theta (\varepsilon ^{-2} \log (1/\varepsilon))\) in the above lemma, we conclude our main result (stated informally as part (ii) of Theorem 1.1) concerning the explicit construction of codes list decodable up to the Singleton bound over fixed alphabets and very slowly growing list size.