## 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).

## Additional Information

**Pieter Rozenhart**- Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
- Email: pmrozenh@alumni.uwaterloo.ca
**Michael Jacobson Jr.**- Affiliation: Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
- Email: jacobs@cpsc.ucalgary.ca
**Renate Scheidler**- Affiliation: Department of Mathematics and Statistics, University of Calgary, 2500 University Drive NW, Calgary, Alberta, T2N 1N4, Canada
- MR Author ID: 308756
- ORCID: 0000-0001-7164-8769
- Email: rscheidl@math.ucalgary.ca
- Received by editor(s): April 27, 2010
- Received by editor(s) in revised form: May 30, 2011
- Published electronically: March 14, 2012
- © Copyright 2012
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Math. Comp.
**81**(2012), 2335-2359 - MSC (2010): Primary 11Y40, 11R16; Secondary 11R58
- DOI: https://doi.org/10.1090/S0025-5718-2012-02591-9
- MathSciNet review: 2945159