Everett W. Howe and Kristin E. Lauter: New methods for bounding the number of points on curves over finite fields, pp. 173–212 in: Geometry and Arithmetic (C. Faber, G. Farkas, and R. de Jong, eds.), European Mathematical Society, 2012.

(An official version and an arXiv preprint are available.)

As usual, let Nq(g) denote the largest number of rationals points possible on a curve of genus g over a finite field Fq. Expanding upon our previous paper (“Improved upper bounds for the number of points on curves over finite fields,” Ann. Inst. Fourier (Grenoble) 53 (2003) 1677–1737; Corrigendum, 57 (2007) 1019–1021), we further improve the upper bounds on Nq(g) for a number of values of q and g.

As before, our methods involve analyzing the possible Weil polynomials for a curve over Fq with a given number N of points. Given a Weil polynomial of an isogeny class of abelian variety over Fq, we try to find reasons why the isogeny class cannot contain a Jacobian — or, if we cannot find a reason to exclude a Jacobian, we try to prove that a curve whose Jacobian lies in the given isogeny class must have special properties that allow us to efficiently search for it.

There are four main new techniques presented in this paper. First, we show that in many of the arguments in our previous paper where we made use of the resultant of two factors of a possible real Weil polynomial, we can instead use the “reduced resultant.” Second, we generalize an argument from our earlier paper that says that when q = s2, there is no curve whose real Weil polynomial is (x + t) (x + 2s)m, if t − 2s is squarefree and coprime to q; the new argument shows that there is no curve with real Weil polynomial h(x) (x + 2s)m, if h(−2s) is squarefree and coprime to q. Third, we generalize an argument from our earlier paper that provided restrictions on curves whose Jacobian are isogenous to E × A, where E is an elliptic curve and A is an abelian variety with Hom(E,A) = 0. The new argument provides similar restrictions on curves whose Jacobians are isogenous to En × A, when n is small and E is an ordinary elliptic curve. And fourth, we give a simple criterion for deciding whether the entire category of abelian varieties in a given ordinary isogeny class over a finite field can be defined over a subfield.

Van der Geer and van der Vlugt have maintained tables of the best known lower and upper bounds on Nq(g), for g ≤ 50 and q ≤ 128 that are powers of 2 and 3. Using our new methods, we are able to improve the best known upper bounds on Nq(g) for 91 of these (q,g) pairs, and we are able to provide two values of Nq(g): namely, N4(7) = 21 and N8(5) = 29. We are also able to provide restrictions on the real Weil polynomials of certain curves; for example, if there is a curve of genus 4 over F32 with 72 points, its real Weil polynomial must be (x + 11)2 (x2 + 17x + 71), and if there is a genus-8 curve over F4 with 24 points, its real Weil polynomial must be x(x + 2)4 (x + 3) (x + 4)2.

The van der Geer / van der Vlugt tables have been incorporated into an online database, www.manypoints.org, that includes the best known bounds on Nq(g) for other values of q as well.

Some of our intermediate results can be interpreted in terms of Mordell–Weil lattices of constant elliptic curves over one-dimensional function fields over finite fields. Using the Birch and Swinnerton-Dyer conjecture for such elliptic curves, we deduce lower bounds on the orders of certain Shafarevich–Tate groups.

Here are links to some of the Magma programs related to this paper:

• Most of our upper bounds on Nq(g) come directly from the routines in IsogenyClasses.magma. Results from running this program were used to populate many entries in the tables at manypoints.org.
• To show that N32(4) ≤ 72 we had to enumerate the genus-4 double covers of the elliptic curve y2 + xy = x3 + x over F32 and show that none of them has more than 72 points. Code for doing this can be found here. This code also produces examples of genus-4 curves over F32 with 71 points.
• For some of our improvements we used sharp upper bounds on the lengths of short vectors in Hermitian lattices over the rings of integers of imagainary quadratic fields of class number 1. We computed these bounds using the programs in HermitianForms.magma.