Everett W. Howe and Kristin E. Lauter: Improved upper bounds for the number of points on curves over finite fields, Ann. Inst. Fourier (Grenoble) 53 (2003) 1677–1737, MR 2005c:11079, Zbl 1065.11043. Corrigendum, Ann. Inst. Fourier (Grenoble) 57 (2007) 1019–1021,

(A corrected preprint and an official version with a correction are available online.)

Important note: There is a mistake in Section 7 of the original version of this paper. A correction can be found here. The correction has been incorporated into the arXiv version of the paper.

We give new arguments that improve the known upper bounds on the maximal number Nq(g) of rational points of a curve of genus g over a finite field Fq, for a number of pairs (q,g). Given a pair (q,g) and an integer N, we determine the possible zeta functions of genus-g curves over Fq with N points, and then deduce properties of the curves from their zeta functions. In many cases we can show that a genus-g curve over Fq with N points must have a low-degree map to another curve over Fq, and often this is enough to give us a contradiction. In particular, we are able to provide eight previously unknown values of Nq(g), namely: N4(5) = 17, N4(10) = 27, N8(9) = 45, N16(4) = 45, N128(4) = 215, N3(6) = 14, N9(10) = 54, and N27(4) = 64. Our arguments also allow us to give a non-computer-intensive proof of the recent result of Savitt that there are no genus-4 curves over F8 having exactly 27 rational points. Furthermore, we show that there is an infinite sequence of q's such that for every g with 0 < g < log2 q, the difference between the Weil-Serre bound on Nq(g) and the actual value of Nq(g) is at least g/2.

To prove these results we make use of a number of Magma programs, which we provide below. Be warned that they have not been optimized. Also, the programs may not work on versions of Magma earlier than 2.8.

• CheckQGN.magma. Given a field size q, a genus g, and a number N, this program will (eventually) list all of the possible real Weil polynomials of a genus-g curve over Fq having N points. UPDATED ON 25 FEBRUARY 2007 to correct an error. (See the changelog in the file for an explanation.) Fortunately, the error did not result in any mistakes in the published paper.
• DeficientPolynomialList.magma. This file contains data that is used in the program CheckQGN.magma.
• Smyth.magma. This program allows us to recreate the tables that occur in a paper of Smyth.
The following programs were updated on 5 February 2004:
• 3-6-15.magma. This is the program we used to show that there are no genus-6 curves over F3 having exactly 15 points.
• 27-4-66.magma. This is the program we used to show that there are no genus-4 curves over F27 having exactly 66 points.
• 27-4-65.magma. This is the program we used to show that there are no genus-4 curves over F27 having exactly 65 points.
• 32-4-75.magma. This is the program we used to show that there are no genus-4 curves over F32 having exactly 75 points.

Our paper refers to the van der Geer-van der Vlugt tables of curves with many points. The version of their paper that we use is dated 18 January 2002, and we include a gzipped version of it here for reference. The current version can be found on Gerard van der Geer's web page.