Codes on Drinfeld modular curves (Q4485871)

The authors drastically improve an old estimate of the computational complexity of constructing algebraic-geometric codes based on Drinfeld modular curves. \textit{Y. Manin} and \textit{S. Vladut} [J. Sov. Math. 30, 2611-2643 (1985); translation from Itogi Nauki Tekh., Ser. Sovrem. Probl. Mat. 25, 209-257 (1984; Zbl 0629.94013)] give an algorithm to construct good families of codes using a family of Drinfeld modular curves. To do so, they use a plane model \(C_1(I)\) of the reduction \(\text{mod }T\) of the Drinfeld modular curve \(X_1(I)\), \(I\) a prime ideal in the polynomial ring \(F_q(T)\), \(F_q\) a finite field. The algorithm constructs the generator matrix of a Goppa code \(C_L(P, G)\), with \(P\), \(G\) appropriate divisors, defined over \(F_{q^2}\). The algorithm has complexity \(O(n^{32})\), \(n\) being the length of the code. In his doctoral thesis [Plane models of Drinfeld modular curves, Thesis, U. Complutense, Madrid (1996)], \textit{B. Lopez} obtains the estimate \(O(n^{17})\), and the present paper improves this estimate to \(O(n^{12})\). In section 1 the paper refers to B. Lopez [Thesis] and to \textit{M. Tsfasman} and \textit{S. Vladut} [Algebraic-geometric codes, in Math. Appl. Soviet Ser. 58, Kluwer (1991; Zbl 0727.94007)] for the main results about \(C_1(I)\), section 2 recalls the Brill-Noether algorithm used to construct a set of generators of the vector space \(L(G)\), and section 3 recalls the Manin-Vladut construction and describes the authors' algorithm. Finally, we point out a minor problem that can make the reading of the paper harder: while the results (propositions, lemmas and remarks) are numbered with two numbers (section result) they are quoted using a consecutive numbering (for instance proposition 7 must be understood as proposition 2.2). For the entire collection see [Zbl 0930.00089].