Tabulation of cubic function fields via polynomial binary cubic forms

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^{\ast }$, up to a given bound $B$ on the degree of $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\to \infty$. The algorithm, examples and numerical data for $q=5,7,11,13$ are included.

30 pages, minor typos corrected, extra table entries added, revamped complexity analysis of the algorithm. To appear in Mathematics of Computation