Cyclotomic function fields, Artin-Frobenius automorphisms, and list error correction with optimal rate (Q983514)

Recently in [IEEE Trans. Inf. Theory 54, No. 1, 135--150 (2008; Zbl 1205.94125)], \textit{V. Guruswami} and \textit{A. Rudra} constructed the folded Reed-Solomon codes for list decoding, which achieve the information theoretically best possible trade-off between the rate and the fraction of errors corrected. The alphabet size of these folded Reed-Solomon codes is polynomial in the block length. This paper constructs new folded algebraic-geometric codes with an alphabet size that is polylogarithmic in the block length, utilizing the Artin-Frobenius automorphism at primes in cyclic cyclotomic function fields. The authors first show how the folded Reed-Solomon codes can be viewed as constructed from the simplest cyclotomic function field \(\mathbb{F}_q(t)(\lambda_{t})\) over \(\mathbb{F}_q(t)\), where \(\lambda_{t}\) is a primitive \(t\)-torsion point for the Carlitz module. Then the authors consider a subfield \(E\) of a general cyclic cyclotomic function field \(K=\mathbb{F}_q(t)(\lambda_{m})\) for an irreducible polynomial \(m\in\mathbb{F}_q[t]\) of degree \(d>1\), where many degree one places split completely in \(E/\mathbb{F}_q(t)\). This method follows the work of \textit{H.-G. Quebbemann} in [IEEE Trans. Inf. Theory 34, 1317--1320 (1988; Zbl 0665.94014)] and the work of \textit{H. Niederreiter} and \textit{C. Xing} in [Acta Arith. 75, 383--396 (1996; Zbl 0877.11065) and Acta Arith. 79, 59--76 (1997; Zbl 0891.11057)]. Next the authors construct the cyclotomic algebraic-geometric codes based on the function field \(E\). Similar to the folded Reed-Solomon codes case, the authors give the folding scheme and the list decoding algorithm. Finally the authors describe the construction of the capacity-achieving list-decodable codes, i.e. codes of rate \(0<R<1\) which correct a fraction \(1-R-\varepsilon\) of errors, whose alphabet size is polylogarithm in the block length.