Computing Riemann-Roch spaces in algebraic function fields and related topics. (English) Zbl 1058.14071
Summary: We develop a simple and efficient algorithm to compute Riemann-Roch spaces of divisors in general algebraic function fields which does not use the Brill-Noether method of adjoints or any series expansions. The basic idea also leads to an elementary proof of the Riemann-Roch theorem. We describe the connection to the geometry of numbers of algebraic function fields and develop a notion and algorithm for divisor reduction. An important application is to compute in the divisor class group of an algebraic function field.
MSC:
| 14Q05 | Computational aspects of algebraic curves |
| 14H05 | Algebraic functions and function fields in algebraic geometry |
| 14C40 | Riemann-Roch theorems |
| 14-04 | Software, source code, etc. for problems pertaining to algebraic geometry |
References:
| [1] | Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system I: the user language, J. Symb. Comput., 24, 235-265 (1997) · Zbl 0898.68039 |
| [2] | Brill, A.; Noether, M., Über die algebraischen Functionen und ihre Anwendung in der Geometrie, Math. Ann., 7, 269-310 (1874) · JFM 06.0251.01 |
| [3] | Buchmann, J.; Lenstra, H., Approximating rings of integers in number fields, J. Theor. Nombres Bordx., 6, 221-260 (1994) · Zbl 0828.11075 |
| [4] | Campillo, A., Algebroid Curves in Positive Characteristic (1980), Springer: Springer LNM 813. Berlin · Zbl 0451.14010 |
| [5] | Chevalley, C., Introduction to the Theory of Algebraic Functions of One Variable, volume 6 of Mathematical Surveys (1951), American Mathematical Society: American Mathematical Society New York · Zbl 0045.32301 |
| [6] | Chistov, A. L., The complexity of constructing the ring of integers of a global field, Sov. Math. Dokl., 39, 597-600 (1989) · Zbl 0698.12001 |
| [7] | Coates, J., Construction of rational functions on a curve, Proc. Camb. Phil. Soc., 68, 105-123 (1970) · Zbl 0215.37302 |
| [8] | Cohen, H., A Course in Algebraic Number Theory (1996), Springer: Springer Berlin |
| [9] | Cohn, P. M., Algebraic Numbers and Algebraic Functions (1991), Chapman & Hall: Chapman & Hall London · Zbl 0754.11028 |
| [10] | Computational Algebra Group, Magma,; Computational Algebra Group, Magma, |
| [11] | Davenport, J. H., On the Integration of Algebraic Functions, LNCS (1981), Springer: Springer Berlin · Zbl 0471.14009 |
| [12] | Dedekind, R.; Weber, H., Theorie der algebraischen Functionen einer Veränderlichen, J. Reine Angew. Math., 92, 181-290 (1882) · JFM 14.0352.01 |
| [13] | C. Friedrichs, 1997; C. Friedrichs, 1997 |
| [14] | Fulton, W., Algebraic Curves (1969), Benjamin: Benjamin New York · Zbl 0181.23901 |
| [15] | Galbraith, S.; Paulus, S.; Smart, N. P., Arithmetic on superelliptic curves, Math. Comput., 71, 393-405 (2002) · Zbl 1013.11026 |
| [16] | Haché, G., Computation in algebraic function fields for effective construction of algebraic-geometric codes, (Cohen, G.et al., Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-11, Paris. LNCS (1995)), 262-278 · Zbl 0876.94047 |
| [17] | Springer, Berlin; Springer, Berlin |
| [18] | Hensel, K.; Landsberg, G., Theorie der Algebraischen Funktionen einer Variabeln und ihre Anwendung auf Algebraische Kurven und Abelsche Integrale (1902), Leipzig: Teubner · JFM 33.0427.01 |
| [19] | F. Hess, 1999; F. Hess, 1999 |
| [20] | Huang, M.-D.; Ierardi, D., Counting points on curves over finite fields, J. Symb. Comput., 25, 1-21 (1998) · Zbl 0919.11046 |
| [21] | Kant Group, KASH,; Kant Group, KASH, |
| [22] | Koch, H., Zahlentheorie (1997), Vieweg: Vieweg Braunschweig |
| [23] | Le Brigand, D.; Risler, J. J., Algorithme de Brill-Noether et codes de Goppa, Bull. Soc. Math. France, 116, 231-253 (1988) · Zbl 0721.14015 |
| [24] | Lenstra, A. K., Factoring multivariate polynomials over finite fields, J. Comput. Syst. Sci., 30, 235-248 (1985) · Zbl 0577.12013 |
| [25] | Matsumoto, R.; Miura, S., Finding a basis of a linear system with pairwise distinct discrete valuations on an algebraic curve, J. Symb. Comput., 30, 309-323 (2000) · Zbl 0966.14042 |
| [26] | Moreno, C., Algebraic Curves Over Finite Fields (1991), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0733.14025 |
| [27] | Noether, M., Rationale Ausführung der Operationen in der Theorie der algebraischen Functionen, Math. Ann., 23, 311-358 (1884) · JFM 16.0349.01 |
| [28] | Paulus, S., Lattice basis reduction in function fields, (Buhler, J., Proceedings of the Third Symposium on Algorithmic Number Theory, Portland, OR, ANTS-III, LNCS (1998)), 567-575 · Zbl 0935.11045 |
| [29] | Springer, Berlin; Springer, Berlin |
| [30] | L. Pecquet, 1999, Private communication; L. Pecquet, 1999, Private communication |
| [31] | Pohst, M. E., Computational Algebraic Number Theory (1993), Birkhäuser: Birkhäuser Basel · Zbl 0694.12002 |
| [32] | Pohst, M. E.; Schörnig, M., On integral basis reduction in global function fields, (Cohen, H., Proceedings of the Second Symposium on Algorithmic Number Theory, Talence, ANTS-II, LNCS (1996)), 273-282 · Zbl 0898.11048 |
| [33] | Springer, Berlin; Springer, Berlin |
| [34] | Pohst, M. E.; Zassenhaus, H., Algorithmic Algebraic Number Theory (1997), Cambridge University Press: Cambridge University Press Cambridge |
| [35] | Schmidt, F. K., Analytische Zahlentheorie in Körpern der Charakteristik p, Math. Zeit., 33, 1-32 (1931) · Zbl 0001.05401 |
| [36] | Schmidt, W. M., Construction and estimation of bases in function fields, J. Number Theory, 39, 181-224 (1991) · Zbl 0764.11046 |
| [37] | M. Schörnig, 1996; M. Schörnig, 1996 |
| [38] | Stichtenoth, H., Algebraic Function Fields and Codes (1993), Springer: Springer Berlin · Zbl 0816.14011 |
| [39] | van Hoeij, M., An algorithm for computing the Weierstrass normal form, (Levelt, A. H.M., Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC ’95, Montreal (1995), ACM Press: ACM Press New York), 90-95 · Zbl 0917.14034 |
| [40] | van Hoeij, M., Rational parametrizations of algebraic curves using a canonical divisor, J. Symb. Comput., 23, 209-227 (1997) · Zbl 0878.68073 |
| [41] | Volcheck, E., Computing in the Jacobian of a plane algebraic curve, (Adleman et al, L., Proceedings of the First Symposium on Algorithmic Number Theory, Ithaca, NY, ANTS-I, LNCS (1994)), 221-233 · Zbl 0826.14040 |
| [42] | Springer, Berlin; Springer, Berlin |
| [43] | E. Volcheck, 1995, Addition in the Jacobian of a curve over a finite field. Computational Number Theory (Oberwolfach), conference manuscript; E. Volcheck, 1995, Addition in the Jacobian of a curve over a finite field. Computational Number Theory (Oberwolfach), conference manuscript |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
