Tabulation of cubic function fields via polynomial binary cubic forms

Rozenhart, Pieter; Jr., Michael Jacobson; Scheidler, Renate

doi:10.1090/S0025-5718-2012-02591-9

Tabulation of cubic function fields via polynomial binary cubic forms
HTML articles powered by AMS MathViewer

by Pieter Rozenhart, Michael Jacobson Jr. and Renate Scheidler PDF

Math. Comp. 81 (2012), 2335-2359 Request permission

Abstract:

We present a method for tabulating all cubic function fields over $\mathbb {F}_q(t)$ whose discriminant $D$ has either odd degree or even degree and the leading coefficient of $-3D$ is a non-square in $\mathbb {F}_{q}^*$, up to a given bound $B$ on $\deg (D)$. Our method is based on a generalization of Belabas’ method for tabulating cubic number fields. The main theoretical ingredient is a generalization of a theorem of Davenport and Heilbronn to cubic function fields, along with a reduction theory for binary cubic forms that provides an efficient way to compute equivalence classes of binary cubic forms. The algorithm requires $O(B^4 q^B)$ field operations as $B \rightarrow \infty$. The algorithm, examples and numerical data for $q=5,7,11,13$ are included.

References

E. Artin, Quadratische Körper im Gebiete der höheren Kongruenzen. I, Math. Z. 19 (1924), no. 1, 153–206 (German). MR 1544651, DOI 10.1007/BF01181074
Eric Bach and Jeffrey Shallit, Algorithmic number theory. Vol. 1, Foundations of Computing Series, MIT Press, Cambridge, MA, 1996. Efficient algorithms. MR 1406794
K. Belabas, A fast algorithm to compute cubic fields, Math. Comp. 66 (1997), no. 219, 1213–1237. MR 1415795, DOI 10.1090/S0025-5718-97-00846-6
Karim Belabas, On quadratic fields with large 3-rank, Math. Comp. 73 (2004), no. 248, 2061–2074. MR 2059751, DOI 10.1090/S0025-5718-04-01632-1
W.E.H. Berwick and G.B. Mathews, On the reduction of arithmetical binary cubics which have negative discriminant, Proc. of the London Math. Soc., 10 (1912), 48–53.
Manjul Bhargava, The density of discriminants of quartic rings and fields, Ann. of Math. (2) 162 (2005), no. 2, 1031–1063. MR 2183288, DOI 10.4007/annals.2005.162.1031
Johannes Buchmann and Ulrich Vollmer, Binary quadratic forms, Algorithms and Computation in Mathematics, vol. 20, Springer, Berlin, 2007. An algorithmic approach. MR 2300780
Duncan A. Buell, Binary quadratic forms, Springer-Verlag, New York, 1989. Classical theory and modern computations. MR 1012948, DOI 10.1007/978-1-4612-4542-1
Rey Casse, Projective geometry: an introduction, Oxford University Press, Oxford, 2006. MR 2264641
Henri Cohen, Advanced topics in computational number theory, Graduate Texts in Mathematics, vol. 193, Springer-Verlag, New York, 2000. MR 1728313, DOI 10.1007/978-1-4419-8489-0
Richard Crandall and Carl Pomerance, Prime numbers, Springer-Verlag, New York, 2001. A computational perspective. MR 1821158, DOI 10.1007/978-1-4684-9316-0
J. E. Cremona, Reduction of binary cubic and quartic forms, LMS J. Comput. Math. 2 (1999), 64–94. MR 1693411, DOI 10.1112/S1461157000000073
Boris Datskovsky and David J. Wright, Density of discriminants of cubic extensions, J. Reine Angew. Math. 386 (1988), 116–138. MR 936994, DOI 10.1515/crll.1988.386.116
H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields, Bull. London Math. Soc. 1 (1969), 345–348. MR 254010, DOI 10.1112/blms/1.3.345
H. Davenport and H. Heilbronn, On the density of discriminants of cubic fields. II, Proc. Roy. Soc. London Ser. A 322 (1971), no. 1551, 405–420. MR 491593, DOI 10.1098/rspa.1971.0075
Jordan S. Ellenberg and Akshay Venkatesh, Counting extensions of function fields with bounded discriminant and specified Galois group, Geometric methods in algebra and number theory, Progr. Math., vol. 235, Birkhäuser Boston, Boston, MA, 2005, pp. 151–168. MR 2159381, DOI 10.1007/0-8176-4417-2_{7}
Jordan S. Ellenberg and Akshay Venkatesh, The number of extensions of a number field with fixed degree and bounded discriminant, Ann. of Math. (2) 163 (2006), no. 2, 723–741. MR 2199231, DOI 10.4007/annals.2006.163.723
Andreas Enge, How to distinguish hyperelliptic curves in even characteristic, Public-key cryptography and computational number theory (Warsaw, 2000) de Gruyter, Berlin, 2001, pp. 49–58. MR 1881626
J. W. P. Hirschfeld, Projective geometries over finite fields, 2nd ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1998. MR 1612570
M.J. Jacobson, Jr., Y. Lee, R. Scheidler and H. Williams, Construction of all cubic function fields of a given square-free discriminant, preprint.
E. Landquist, P. Rozenhart, R. Scheidler, J. Webster, and Q. Wu, An explicit treatment of cubic function fields with applications, Canad. J. Math. 62 (2010), no. 4, 787–807. MR 2674701, DOI 10.4153/CJM-2010-032-0
Rudolf Lidl and Harald Niederreiter, Introduction to finite fields and their applications, 1st ed., Cambridge University Press, Cambridge, 1994. MR 1294139, DOI 10.1017/CBO9781139172769
G. B. Mathews, On the reduction and classification of binary cubics which have a negative discriminant, Proc. of the London Math. Soc., 10 (1912), 128–138.
Michael Rosen, Number theory in function fields, Graduate Texts in Mathematics, vol. 210, Springer-Verlag, New York, 2002. MR 1876657, DOI 10.1007/978-1-4757-6046-0
P. Rozenhart, Fast Tabulation of Cubic Function Fields, Ph.D. Thesis, University of Calgary, 2009.
Pieter Rozenhart and Renate Scheidler, Tabulation of cubic function fields with imaginary and unusual Hessian, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 357–370. MR 2467858, DOI 10.1007/978-3-540-79456-1_{2}4
P. Rozenhart, M.J. Jacobson, Jr., and R. Scheidler, Computing quadratic function fields with high $3$-rank via cubic field tabulation, preprint.
R. Scheidler, Algorithmic aspects of cubic function fields, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 395–410. MR 2138010, DOI 10.1007/978-3-540-24847-7_{3}0
V. Shoup, NTL: A Library for Doing Number Theory, Software, 2001, see http://www.shoup.net/ntl.
Henning Stichtenoth, Algebraic function fields and codes, 2nd ed., Graduate Texts in Mathematics, vol. 254, Springer-Verlag, Berlin, 2009. MR 2464941
T. Taniguchi, Distributions of discriminants of cubic algebras, Preprint, Available from http://arxiv.org/abs/math.NT/0606109 (2006).