YET MORE PROJECTIVE CURVES OVER 𝔽_{2}

CHRIS LOMONT

Abstract. All plane curves of degree less than 7 with coefficients in 𝔽_{2} are examined for curves with a large number of 𝔽_{q} rational points on their smooth model, for q = 2^{m}, m = 3, 4, ..., 11. Known lower bounds are improved, and new curves are found meeting or close to Serre’s, Lauter’s, and Ihara’s upper bounds for the maximal number of 𝔽_{q} rational points on a curve of genus g.

1. Introduction

Let 𝔽_{q} denote the finite field with q elements. All absolutely irreducible homogeneous polynomials f ∈ 𝔽_{2}[x, y, z] of degree less than 7 are examined for those with a large number of 𝔽_{q} rational points, q = 2^{m}, m = 3, 4, 5, ..., 11, extending the results in [10]. A brute force search obtained all rational points for each polynomial of a given degree. The resulting list of polynomials with many rational points, perhaps with singularities, were then studied to determine if resolving singularities would add more rational points on the smooth model. The result is an exhaustive search of all curves resulting from desingularizing a homogeneous polynomial of degree less than 7 in 𝔽_{2}[x, y, z].

The rest of the paper is laid out as follows: first known bounds on the maximal number of 𝔽_{q} rational points of a genus g curve are recalled, along with some theorems that speed up the computations. Then the computation is described in some detail. A listing of the best found polynomials is given for each genus, allowing checking (by computer unless one has a lot of time!) the claimed number of rational points on each curve.. Finally the new lower bounds are listed in a table for each 𝔽_{q} and genus combination.

2. Genus Bounds and Irreducibility Tests

Let f ∈ 𝔽_{2}[x, y, z] be an absolutely irreducible homogeneous polynomial; f defines a projective plane curve C. Let C̃ be the smooth model, and g its genus. Some bounds on the genus can be deduced from knowing the number of 𝔽_{q} rational points in the plane and the number of singularities in the plane. N_{q}(g) is the maximum number of 𝔽_{q}-rational points on a smooth curve of genus g over 𝔽_{q}. Serre’s bound [13] on N_{q}(g) is

|N_{q}(g) − (q + 1)| ≤ g⌊2\sqrt{q}⌋

where ⌊α⌋ is the integral part of α. This gives

N_{q}(g) ≤ (q + 1) + g⌊2\sqrt{q}⌋

so if there is an integer g_{0} such that

q + 1 + g_{0}⌊2\sqrt{q}⌋ < p

where p is the point count on the particular curve C in question, then g_{0} < g. If the number of singularities is r, and the degree of the polynomial f is d, then

g ≤ \frac{(d − 1)(d − 2)}{2} − r

To get an estimate of the total number of points possible on the smooth model C̃ resulting from blowing up singularities the following estimate was used.

Theorem 1. Let C ⊆ ℙ^{2} be a plane curve of degree d with singularities P_{1}, P_{2}, ..., P_{r}, with multiplicities m_{1}, m_{2}, ..., m_{r}, for r ≥ 2. Then ∑_{i=1}^{r} m_{i} ≤ ⌊\frac{d}{2}⌋r + 1 if d is odd, and ∑_{i=1}^{r} m_{i} ≤ ⌊\frac{d}{2}⌋r if d is even.

So the number of points obtained from blowing up singularities is bounded above by ⌊\frac{d}{2}⌋r + 1.

Proof. By Bezout’s theorem, a line through any 2 singularities P_{i} and P_{j} implies m_{i} + m_{j} ≤ d. Thus at most one singularity can have multiplicity > d/2, and the result follows. □

More details on resolution of curve singularities can be found in [3] and [15].

To test for absolute irreducibility the following was used [12]:

Definition 1. Let k be a field. The polynomial f ∈ k[x_{1}, x_{2}, ..., x_{n}] has a simple solution at a point P ∈ k^{n} if f ∈ I(P)⧹I(P)^{2}, with I(P) being the ideal of polynomials vanishing at P.

Theorem 2. If f ∈ k[x_{1}, x_{2}, ..., x_{n}] is irreducible over the perfect field k and has a simple solution in k^{n}, then f is absolutely irreducible.

Proof. Since f is irreducible over k, its absolutely irreducible factors are conjugate over k. If P ∈ k^{n} is a root of one of the factors, it must be a root of the others. But P only vanishes to order 1, thus f has one factor, and is absolutely irreducible. □

The number of 𝔽_{q} points on a plane curve can be computed directly by brute force, as can lower bounds on the number of singularities, and then the above inequalities can be used to obtain bounds on the genus. So given a polynomial f, the number of rational points computed on it, and the number of singularities found, upper and lower bounds on the possible genus are obtained, which speeds up the search by removing curves early in the computation that have uninteresting combinations of genus and rational point count.

3. Computation

3.1. Storing polynomials compactly. All 𝔽_{q} rational points were found on each homogeneous polynomial of degree ≤ 5 in 𝔽_{2}[x, y, z], for q = 2^{m}, m = 3, 4, ..., 11. Due to the the time requred, degree 6 homogeneous polynomials were examined only for m = 3, 4, ..., 9.

The most time consuming part was counting the number of 𝔽_{q}- rational points on each plane curve. This was done with a C program using exhaustive search. Several ideas were used to reduce the complexity at each stage. Degree 6 computations will be described; the other degrees are similar. The code was checked for correctness by comparing the degree ≤ 5 results with [10], and in the process a few curves were found that were previously overlooked.

First, each homogeneous polynomial can be represented uniquely by a 32 bit integer, using each bit to signify the presence of a certain monomial in the polynomial. In degree 6, there are \binom{6+2}{2} = 28 different monomials of the form x^{i}y^{j}z^{k} with i+j+k = 6 and 0 ≤ i, j, k. Each bit from 0 to 27 denotes the presence of a monomial, and the mapping α : {homogeneous degree 6 f ∈ 𝔽_{2}[x, y, z]} → {1, 2, ..., 2^{28} − 1} thus defined is a bijection. Thus each homogeneous polynomial f ∈ 𝔽_{2}[x, y, z] of degree 6 corresponds to a unique integer between 1 and 2^{28}−1 ≈ 268 million.

3.2. Reducing computation time. To reduce the number of polynomials searched, equivalent ones under the action of GL_{3}(𝔽_{2}) on the variables x, y, z were removed. To fit the entire degree 6 computation in memory, a bit table of 32 megabytes of RAM was used, with the position of each bit representing the number of a polynomial using the above bijection. All bits were set to 1, denoting all polynomials are still in the search space. Then the orbit of each polynomial under GL_{3}(𝔽_{2}) was removed from the bit table, and the polynomial in each orbit requiring the least computation to evaluate was written to a data file. Since the size of GL_{3}(𝔽_{2}) is 168, this was expected to give approximately a 168 fold decrease in the number of curves needing to be searched (not exactly 168 since some polynomials are invariant under some automorphisms). By using the representative of each orbit requiring the least work to evaluate, the search time was reduced significantly (see below). This trimmed the 268 million degree 6 polynomials down to 1.6 million. Also, clearly reducible polynomials, such as those with all even exponents or divisible by a variable, were removed at this point. At each stage data was saved to prevent having to rerun any step.

For speed reasons finding solutions was done by table lookup, so in each orbit the polynomial needing the fewest number of lookups was selected. By choosing the representative with the fewest number of lookups as opposed, for example, to the polynomial with the lowest value of α(f) defined above, 12 million lookups were removed from polynomials of degree 6, resulting in over 3 trillion operations removed during rational point counting.

3.3. Timing. After the C program computes all the 𝔽_{q}-rational points, the points are tested for singularities (a singularity will add an additional 𝔽_{q} rational point only if it comes from resolving a 𝔽_{q} rational singularity). The computation up to this point took about 80 hours of computer time on a Pentium III 800 MHZ. Using the bounds above on the genus and possible ranges for number of 𝔽_{q} rational points on the smooth model, the program searched all curves for those with a large number of possible 𝔽_{q} rational points for each genus and field combination, and all such curves were written out to be examined. If the genus of one of these curves was not forced to be unique using the bounds, the program KANT [6] was used to compute the genus, and this data was incorporated into the C program, and another pass was run. Due to the large number of degree 6 curves, and the length of time to compute the genus of all of them, not all degree 6 curves of genus ≤ 5 were identified. All curves of degree 6, genus ≥ 6 were identified. The C program also found simple points over 𝔽_{2} to apply the irreducibility theorem above, and then Maple V [9] was used to test for irreducibility since it has multivariable factoring algorithms over finite fields. For 12 curves of degree 6, there were no simple 𝔽_{2} points, so 𝔽_{4} simple points were used. For 2 of these curves there were no such simple 𝔽_{4} points, so 𝔽_{8} simple points were used. This turned out to suffice to check absolute irreducibility of all polynomials in this paper. The C program also found the singularity types of the 𝔽_{2} singularities for visual inspection to see if there were clearly more rational points on the smooth model. The package of [2] was not available to do a more detailed singularity analysis, thus some of the bounds below may be improved by looking for rational points over a wider class of singularities than the 𝔽_{2} singularities considered here.

The final C code can be found at [8].

4. Computational Results

For each field and genus combination polynomials are listed that result in the largest found number of rational points on the smooth model of the curve. For fields 𝔽_{q}, q = 2^{m}, m = 3, 4, .., 11, all homogeneous polynomials in 𝔽_{2}[x, y, z] of degree ≤ 5 were searched. For m = 3, 4, ...9, the search was extended to include all degree 6 homogeneous polynomials in 𝔽_{2}[x, y, z]. For genus and field combinations not listed here, see [10].

Remark: the four polynomials found in [10] of degree 4, genus 3, with 113 rational points over 𝔽_{64}, are only 2 distinct polynomials modulo the action of GL_{3}(𝔽_{2}) on the variables x, y, z.

4.1. 𝔽_{8}. A curve of genus 3 and the maximal number of smooth points, 24, is the Klein Quartic

x^{3} y + y^{3} z + x z^{3}

A genus 5 curve with 28 planar smooth points is

x^{6}+x^{5} y+x^{3} y^{3}+y^{6}+y^{5} z+y^{4} z^{2}+(x^{3} + x y^{2} + y^{3}) z^{3}+(x^{2} + x y) z^{4}+x z^{5}

Note: a reviewer remarked that a genus 5 curve is known with 29 points [1].

A genus 6 curve, with 33 planar smooth points is

x^{4} y^{2} + x^{3} y^{3} + x y^{5} + x y^{4} z + y^{4} z^{2} + (x^{2} + y^{2}) z^{4} + y z^{5}

A curve of genus 7 with 33 smooth planar points is

x^{6}+x^{5} y+x^{4} y^{2}+x^{3} y^{3}+y^{6}+y^{5} z+(x^{2} y^{2} + x y^{3} + y^{4}) z^{2}+(x^{2} y + x y^{2}) z^{3}+(x^{2} + x y + y^{2}) z^{4}

A genus 8 curve with 33 smooth planar points is

x^{5} y+x^{2} y^{4}+x y^{5}+y^{6}+(x^{4} y + x^{2} y^{3}) z+x^{3} y z^{2}+(x^{3} + x y^{2}) z^{3}+x y z^{4}+y z^{5}

Two curves of genus 9, each with 33 smooth planar points:

f_{1} = x^{5} y+x^{4} y^{2}+x^{2} y^{4}+(x^{3} y^{2} + x^{2} y^{3}) z+x^{4} z^{2}+(x y^{2} + y^{3}) z^{3}+x^{2} z^{4}+x z^{5}+z^{6}

f_{2} = x^{6}+x^{4} y^{2}+x^{3} y^{3}+x^{2} y^{4}+x^{3} y^{2} z+(x^{4} + x^{3} y + x y^{3}) z^{2}+y^{3} z^{3}+(x + y) z^{5}+z^{6} Five curves of genus 10 with 35 smooth points in the plane:

f_{1} = x^{5} y+x^{2} y^{4}+y^{6}+(x^{3} y^{2} + x y^{4} + y^{5}) z+y^{4} z^{2}+(x^{2} y + x y^{2}) z^{3}+(x^{2} + y^{2}) z^{4}+x z^{5}

f_{2} = x^{5} y+x^{4} y^{2}+x^{3} y^{3}+x y^{5}+y^{6}+x^{2} y^{3} z+(x^{4} + x^{2} y^{2} + x y^{3}) z^{2}+x^{3} z^{3}+y^{2} z^{4}+x z^{5}+z^{6} f_{3} = x^{5} y+x^{4} y^{2}+x^{2} y^{4}+(x^{4} y + y^{5}) z+(x^{4} + x y^{3}) z^{2}+x^{3} z^{3}+(x^{2} + y^{2}) z^{4}+y z^{5}+z^{6}

f_{4} = x^{5} y+x^{3} y^{3}+x^{2} y^{4}+(x^{5} + x^{2} y^{3} + y^{5}) z+(x^{2} y + y^{3}) z^{3}+x^{2} z^{4}+(x + y) z^{5}+z^{6}

f_{5} = x^{4} y^{2}+x^{2} y^{4}+x y^{5}+x^{5} z+x y^{3} z^{2}+(x^{3} + x^{2} y) z^{3}+(x^{2} + y^{2}) z^{4}+x z^{5}

4.2. 𝔽_{16}. One genus 6 curve, a Hermitian curve, with the maximal number of smooth points, 65, was found (it is known to be the unique such curve up to isomorphism):

x^{5} + y^{5} + z^{5}

Two genus 7 curves each with 57 smooth points in the plane:

f_{1} = x^{4} y^{2} + x y^{5} + y^{6} + (x^{2} y^{3} + x y^{4} + y^{5}) z + (x^{2} + x y) z^{4} + y z^{5}
f_{2} = x^{4} y^{2} + x^{2} y^{4} + y^{6} + (x^{2} y^{3} + x y^{4}) z + (x^{2} + x y) z^{4} + y z^{5}

A curve with genus 8 with 57 smooth plane points is

x^{6} + x^{3} y^{3} + x^{2} y^{4} + x^{4} y z + x^{2} y^{2} z^{2} + (x^{3} + x^{2} y) z^{3} + (x + y) z^{5}

There are two curves of genus 9 with 57 smooth plane points, each receiving two points from blowups: f_{1} from the singularity (1 : 1 : 1) of type u^{2} + uv + v^{2} which splits over 𝔽_{16}, and f_{2} from the singularity (0 : 1 : 1) of type uv. Thus N_{16}(9) ≥ 59.

f_{1} = x^{5} y + x^{3} y^{3} + x y^{5} + (x^{5} + y^{5}) z + x^{2} y^{2} z^{2} + (x^{3} + y^{3}) z^{3} + (x + y) z^{5}
f_{2} = x^{6} + x^{5} y + x^{2} y^{4} + y^{5} z + x^{2} y^{2} z^{2} + x y^{2} z^{3} + (x^{2} + x y) z^{4} + y z^{5}

The two curves of genus 10 each with 59 plane smooth points are:

f_{1} = x^{5} y+y^{6}+(x^{2} y^{3} + y^{5}) z+(x^{4} + x^{3} y + x y^{3}) z^{2}+x y^{2} z^{3}+(x + y) z^{5}+z^{6}

f_{2} = x^{5} y+y^{6}+(x^{4} y + x y^{4} + y^{5}) z+(x^{4} + x y^{3}) z^{2}+(x^{3} + x y^{2}) z^{3}+y^{2} z^{4}+z^{6}

4.3. 𝔽_{32}. Three curves with genus 4 and 71 smooth points on the plane curve are:

f_{1} = x^{4} y + x y^{4} + y^{5} + x y^{3} z + (x y^{2} + y^{3}) z^{2} + x^{2} z^{3} + x z^{4} + z^{5}
f_{2} = x^{6} + x^{3} y^{3} + y^{6} + (x^{4} y + y^{5}) z + (x^{3} y + x^{2} y^{2}) z^{2} + (x^{3} + x^{2} y + y^{3}) z^{3} +
x^{2} z^{4} + y z^{5} + z^{6}
f_{3} = x^{6} + x^{3} y^{3} + y^{6} + (x^{5} + x^{3} y^{2} + x^{2} y^{3}) z + y^{4} z^{2} + (x^{3} + y^{3}) z^{3} + y^{2} z^{4} + x z^{5} + z^{6}

A curve with 82 smooth points in the plane and genus 5 is

x^{6} +x^{3} y^{3} +x^{2} y^{4} +y^{6} +x^{5} z +x^{3} y z^{2} +(x^{3} + x y^{2} + y^{3}) z^{3} +x^{2} z^{4} +y z^{5}

A genus 6 curve with 82 planar smooth points and 2 points above the singularity (1 : 0 : 1) of type uv (thus N_{32}(6) ≥ 84) is

x^{6} + y^{6} + (x^{4} y + x^{3} y^{2} + x y^{4}) z + x y^{2} z^{3} + (x^{2} + x y + y^{2}) z^{4}

YET MORE PROJECTIVE CURVES OVER 𝔽_{2} 7

Two genus 7 curves each with 92 planar smooth points are

f_{1} = x^{3} y^{3} + y^{6} + (x^{5} + x^{3} y^{2}) z + (x^{4} + y^{4}) z^{2} + (x^{3} + y^{3}) z^{3} + y^{2} z^{4} + x z^{5} + z^{6}
f_{2} = x^{6} + y^{6} + (x^{5} + y^{5}) z + y^{4} z^{2} + (x^{3} + y^{3}) z^{3} + x^{2} z^{4} + (x + y) z^{5}

A curve with 93 planar smooth points, genus 8, is

x y^{5} + y^{6} + (x^{5} + x^{4} y) z + y^{4} z^{2} + (x^{3} + y^{3}) z^{3} + y^{2} z^{4} + y z^{5} A genus 9 curve with 93 smooth planar points: x^{4} y^{2}+x^{3} y^{3}+(x^{5} + x^{3} y^{2} + x y^{4} + y^{5}) z+x^{2} y^{2} z^{2}+(x^{3} + y^{3}) z^{3}+x^{2} z^{4}+z^{6} Genus 10 with 103 smooth planar points: x^{6}+x^{3} y^{3}+x y^{5}+(x^{2} y^{2} + x y^{3}) z^{2}+(x^{3} + x y^{2} + y^{3}) z^{3}+x y z^{4}+(x + y) z^{5} 4.4. 𝔽_{64}. One curve had genus 4 and 118 smooth planar points:

x^{3} y^{2} + y^{5} + y^{4} z + y^{2} z^{3} + z^{5}

Two curves of genus 6 had 160 smooth planar points (which is one less than the bound of 161):

f_{1} = x^{4} y^{2} + x^{2} y^{4} + x y^{5} + y^{5} z + y^{3} z^{3} + y z^{5} + z^{6}
f_{2} = x^{6} + x^{5} z + (x^{4} + y^{4}) z^{2} + x^{3} z^{3} + y^{2} z^{4} + y z^{5}

Genus 7, 153 planar smooth points: x^{2} y^{4} + x y^{5} + y^{6} + (x^{3} y^{2} + x y^{4} + y^{5}) z + x y^{3} z^{2} + x^{2} z^{4} + x z^{5} + z^{6} Three curves had genus 8 and 159 plane smooth points, the last two of which have no rational points over 𝔽_{2}:

f_{1} = x^{3} y^{3} + y^{6} + (x^{4} y + x y^{4}) z + (x^{3} + y^{3}) z^{3} + x y z^{4}
f_{2} = x^{6} + x^{5} y + x^{3} y^{3} + x y^{5} + y^{6} + (x^{3} y^{2} + y^{5}) z + x^{3} y z^{2} + (x^{2} y + y^{3}) z^{3} +
y^{2} z^{4} + x z^{5} + z^{6}
f_{3} = x^{6} + x^{4} y^{2} + x^{3} y^{3} + x^{2} y^{4} + y^{6} + (x^{4} + x^{2} y^{2} + y^{4}) z^{2} + (x^{3} + y^{3}) z^{3} +
(x^{2} + y^{2}) z^{4} + z^{6}

There are 166 plane smooth points on this curve of genus 9:

x^{6} + x^{3} y^{3} + (x^{4} y + x^{2} y^{3}) z + (x^{3} y + x y^{3} + y^{4}) z^{2} + x^{2} z^{4} + y z^{5} Four genus 10 curves each had 171 points on their smooth model:

f_{1} = x^{6} + y^{6} + (x^{4} y + x^{2} y^{3} + x y^{4}) z + x^{3} y z^{2} + x y^{2} z^{3} + x y z^{4} + z^{6}
f_{2} = x^{6} + x^{5} y + x^{4} y^{2} + x^{3} y^{3} + x^{2} y^{4} + x y^{5} + y^{6} + (x^{4} y + x y^{4}) z + (x^{2} y + x y^{2}) z^{3} + z^{6}
f_{3} = x^{6} + x^{3} y^{3} + y^{6} + (x^{4} y + x y^{4}) z + (x^{3} + y^{3}) z^{3} + z^{6}
f_{4} = x^{6} + x^{3} y^{3} + x y^{5} + x^{3} y^{2} z + (x^{4} + x^{3} y + y^{4}) z^{2} + y^{2} z^{4} + x z^{5} + z^{6}

4.5. 𝔽_{128}. There is one degree 6 plane curve with a genus 3 smooth model, with 183 smooth plane points, and another point coming from the singularity (0 : 0 : 1) of type (u + v)(u^{2} + uv + v^{2}), which matches [10]. The curve is

x^{6} + x^{5} y + x^{4} y^{2} + x^{3} y^{3} + x^{2} y^{4} + (x^{5} + x^{4} y) z + y^{4} z^{2} + (x^{3} + y^{3}) z^{3}

A curve of genus 4 with 215 planar smooth points (2 less than the maximum possible) is

x^{2} y^{3} + x y^{4} + x^{4} z + x y^{2} z^{2} + x y z^{3} + (x + y) z^{4}

There are two curves of genus 6 with 240 planar smooth points, receiving 3 points each from singularities. f_{1} has type uv(u + v) at (0 : 1 : 0) and f_{2} has type (u + v)(u^{2} + uv + v^{2}) at (0 : 1 : 0) and type uv at (1 : 0 : 0). Thus N_{128}(6) ≥ 243.

f_{1} = x^{4} y^{2} + (x^{5} + x^{4} y + x^{2} y^{3}) z + (x^{2} y^{2} + x y^{3}) z^{2} + (x^{2} + x y + y^{2}) z^{4}
f_{2} = x^{3} y^{3} + x^{4} y z + (x^{4} + x^{3} y) z^{2} + (x^{3} + x^{2} y + y^{3}) z^{3} + z^{6}

Two genus 7 curves with 248 smooth planar points:

f_{1} = x^{3} y^{3} + x y^{5} + y^{6} + x^{3} y^{2} z + y^{4} z^{2} + x^{3} z^{3} + (x^{2} + y^{2}) z^{4} + (x + y) z^{5}
f_{2} = x^{5} y + x^{4} y^{2} + x^{2} y^{4} + (x^{3} y^{2} + x^{2} y^{3}) z + x^{4} z^{2} + x y^{2} z^{3} + z^{6}

A curve with 266 planar smooth points, genus 8, and no 𝔽_{2} rational points is

x^{6}+x^{3} y^{3}+x^{2} y^{4}+x y^{5}+y^{6}+(x^{5} + y^{5}) z+(x^{2} y^{2} + y^{4}) z^{2}+(x^{3} + y^{3}) z^{3}+x z^{5}+z^{6}

There are 269 smooth plane points on the curves of genus 9 given by

f_{1} = x^{4} y^{2} + x y^{5} + (x^{4} + y^{4}) z^{2} + (x^{3} + y^{3}) z^{3} + x y z^{4} + x z^{5} + z^{6}
f_{2} = x^{6} + x^{3} y^{3} + x^{2} y^{4} + y^{6} + (x y^{4} + y^{5}) z + x^{2} y^{2} z^{2} + (x^{2} + x y + y^{2}) z^{4}

The smooth curve of genus 10 with 276 𝔽_{128} rational points is

x^{6} + y^{6} + x^{2} y^{3} z + (x^{4} + x^{3} y + y^{4}) z^{2} + x^{3} z^{3} + x^{2} z^{4} + x z^{5}

4.6. 𝔽_{256}. A genus 3 curve not listed in [10] with 350 smooth planar points is given by

x^{5} + x y^{4} + y^{5} + (x^{2} y^{2} + y^{4}) z + (x^{2} y + x y^{2}) z^{2} + x z^{4} + z^{5}

A curve with 399 smooth plane points and genus 5 is

x^{6} + x^{4} y^{2} + x^{5} z + (x^{2} y^{2} + y^{4}) z^{2} + (x^{2} y + x y^{2}) z^{3} + x^{2} z^{4} + y z^{5}

A genus 6 curve with 416 smooth plane points is

x^{4} y + x^{3} y^{2} + y^{4} z + (x^{3} + y^{3}) z^{2} + (x^{2} + x y) z^{3} + z^{5}

One point from the singularity (1 : 0 : 0) of type uv^{2} is added to the 442 smooth plane points on a curve of genus 7 given by

x^{3} y^{3} + x^{2} y^{4} + y^{5} z + x^{3} y z^{2} + (x y^{2} + y^{3}) z^{3} + y^{2} z^{4} + z^{6}

A curve of genus 8 with one point less than the Serre bound has 512 smooth plane points and is given by

x^{4} y^{2} + y^{5} z + x z^{5}

Two curves of genus 9, each with 474 smooth points and 2 points from singularities of type u^{2} + uv + v^{2}, which factor over 𝔽_{256}, at points (0 : 1 : 1) and (1 : 1 : 0) respectively (so N_{256}(9) ≥ 476) are

f_{1} = x^{5} y + x^{3} y^{3} + x^{2} y^{4} + x y^{5} + y^{4} z^{2} + x^{3} z^{3} + y^{2} z^{4} + x z^{5}
f_{2} = x^{6} + y^{6} + (x^{5} + y^{5}) z + x^{4} z^{2} + (x^{2} y + x y^{2}) z^{3} + x z^{5} + z^{6}

Two smooth curves of genus 10 have 537 smooth plane points:

f_{1} = x^{6} + x y^{5} + x^{4} y z + x^{2} y^{2} z^{2} + y^{3} z^{3} + x z^{5}
f_{2} = x^{6} + x^{5} y + x^{3} y^{3} + x y^{5} + y^{6} + (x^{5} + y^{5}) z + x^{2} y^{2} z^{2} + x y z^{4} + z^{6}

4.7. 𝔽_{512}. Four curves overlooked in [10] of genus 4 have 663 plane smooth points. They are

f_{1} = x^{4} y + x y^{4} + (x^{3} y + y^{4}) z + (x y + y^{2}) z^{3} + z^{5}
f_{2} = x^{4} y + x y^{4} + y^{5} + (x y^{3} + y^{4}) z + (x y^{2} + y^{3}) z^{2} + x^{2} z^{3} + x z^{4}
f_{3} = x^{4} y + x^{2} y^{3} + y^{5} + (x^{2} y^{2} + x y^{3} + y^{4}) z + (x^{3} + y^{3}) z^{2} + z^{5}
f_{4} = x^{5} + y^{5} + (x^{4} + x^{3} y + y^{4}) z + (x y^{2} + y^{3}) z^{2} + z^{5}

A genus 6 curve with 766 smooth plane points and one more point from the singularity (1 : 0 : 0) of type (u+v)(u^{2}+uv+v^{2}) (so N_{512}(6) ≥ 767) is

x^{3} y^{3} + y^{6} + (x y^{4} + y^{5}) z + (x^{2} y^{2} + y^{4}) z^{2} + x^{3} z^{3} + x y z^{4} + (x + y) z^{5}

There are 786 smooth plane points and 1 point from the singularity (1 : 0 : 0) of type uv^{2} on the genus 7 curve

x^{2} y^{4} + y^{6} + x^{3} y^{2} z + (x^{3} + x y^{2}) z^{3} + x y z^{4} + y z^{5}

A curve of genus 8 with 813 plane smooth points is

x^{2} y^{4} +y^{6} +(x^{5} + x^{2} y^{3}) z +(x^{3} y + x y^{3} + y^{4}) z^{2} +(x^{3} + x^{2} y) z^{3} +x z^{5}

A genus 9 curve with 837 smooth plane points is

x^{6} +x^{4} y^{2} +(x y^{4} + y^{5}) z +x^{2} y^{2} z^{2} +(x^{2} y + x y^{2}) z^{3} +x y z^{4} +x z^{5} +z^{6}

A smooth genus 10 plane curve with 845 plane points is

x^{5} y+x^{4} y^{2}+x^{2} y^{4}+y^{6}+(x^{2} y^{3} + y^{5}) z+(x^{3} y + y^{4}) z^{2}+x^{2} z^{4}+(x + y) z^{5} 4.8. 𝔽_{1024}. A genus 3 curve with 1211 smooth plane points is

x^{3} y + y^{3} z + y z^{3} + z^{4}

Three genus 4 curves have 1273 smooth plane points:

f_{1} = x^{3} y^{2} + y^{5} + x^{2} y z^{2} + y^{2} z^{3} + x z^{4}
f_{2} = x^{4} y + x^{2} y^{3} + y^{5} + (x^{2} y^{2} + y^{4}) z + (x^{3} + y^{3}) z^{2} + x z^{4}
f_{3} = x^{5} + x^{3} y^{2} + x^{2} y^{3} + y^{5} + y^{4} z + x y^{2} z^{2} + x^{2} z^{3}

A curve with 1343 smooth plane points, genus 5, and 2 points coming from the singularity (1 : 0 : 0) of type uv (and thus attaining the maximum possible 1345) is

x^{3} y^{2} + y^{5} + x^{3} y z + y^{3} z^{2} + z^{5}

A genus 6 curve with 1383 smooth plane points is

x^{4} y + x y^{4} + y^{5} + x^{2} y^{2} z + x y z^{3} + z^{5}

4.9. 𝔽_{2048}. Two genus 3 curves with 2293 smooth plane points, and one more coming from the singularity (0 : 1 : 0) of type (u+v)(u^{2}+uv+v^{2}) on each curve are

f_{1} = x^{4} y + x^{3} y^{2} + x^{3} y z + y^{2} z^{3} + (x + y) z^{4}
f_{2} = x^{4} y + x^{3} y^{2} + x^{3} y z + x^{3} z^{2} + y^{2} z^{3} + y z^{4}

Three curves with 2380 smooth plane points and genus 4 are

f_{1} = x^{5} + y^{5} + x^{3} y z + y^{2} z^{3} + x z^{4}
f_{2} = x^{5} + x^{4} y + (x y^{3} + y^{4}) z + x^{3} z^{2} + (x^{2} + y^{2}) z^{3} + z^{5}
f_{3} = x^{5} + x^{2} y^{3} + x y^{4} + x^{4} z + x^{3} z^{2} + (x^{2} + x y + y^{2}) z^{3} + x z^{4} + z^{5}

A genus 5 curve with 2422 smooth plane points is

x^{4} y + x^{3} y^{2} + y^{5} + x y^{2} z^{2} + (x^{2} + x y + y^{2}) z^{3}

Finally, a genus 6 curve with 2556 planar smooth points is

x^{4} y + x^{2} y^{3} + x y^{4} + y^{5} + (x^{3} y + y^{4}) z + x^{2} z^{3} + y z^{4}

4.10. Tallies. The columns headed “bound” give the Serre [13] bound, unless marked [5] as Ihara or [7] as Lauter. The columns headed “best” give the lower bounds for N_{q}(g) found above; bounds marked [10] and [13] are from those previous papers. Note in particular the reduction from the Serre [13] upper bounds using [5] and [7] has made several known curves closer to or already optimal. After this paper was initially written in 2000, improved bounds were published in [4] and incorporated in this table. These new bounds made the q = 128, g = 4 curve optimal.

F_{q} best 3 bound 3 best 4 bound 4 best 5 bound 5 best 6 bound 6
8 24[13] 24 25[10] 25[4]  28 30 [4] 33  35 [7]
16 38[13] 41 45[10] 45[4] 45[10] 53[4]  65  65
32 63[10] 65[7]  71  74[4]  82  85[4]  84  96[4]
64 113[10] 113  118  129 130[10] 145  160  161
128 184[10] 195  215 215 [4] 227[10] 239  243 258 [4]
256 350[10] 353 381[10] 385  399  417  416  449
512 640[10] 648  663  693 724[10] 738  767  783
1024 1211 1217 1273 1281 1345 1345 1383 1409
2048 2294 2319 2380 2409 2422 2499 2556 2589
F_{q} best 7 bound 7 best 8 bound 8 best 9 bound 9 best 10 bound 10
8  33 38 [4] 33  42[4]  33  45[4]  35  49[4]
16 57  69[4]  57  75[4]  59  81[5]  59  87[5]
32 92 107 [4] 93 118 [4] 93 128 [4] 103 139 [4]
64 153  177  159  193  166  209  171  225
128 248  283  266 302[4] 269 322 [4] 276  349
256 443  481  512  513  476  545  537  577
512 787  828  813  873  837  918  845  963

5. Conclusions

Previously known results are [10] and [13]. The bounds in this paper could possibly be strengthened by by analyzing the singularities in more detail, resulting in more known 𝔽_{q} rational points on the smooth models of the curves. Also all genus ≤ 5 curves from the degree 6 polynomials were not identified. More work could be done to compute exact parameters for these curves.

6. Comments

The techniques used here make a search over degree 7 plane curves feasible on a supercomputer, and quite possibly on a home PC. The desingularized curves can be used to construct algebraic-geometric Goppa codes [11], [14]. For example, using the genus 5 curve over 𝔽_{1024} with 1345 rational points, linear codes with parameters [n, k − 4, n − k] can be constructed for 10 ≤ n ≤ 1344 and 8 < k < n over 𝔽_{1024}. Similarly, using the genus 6 𝔽_{64} curve with 160 points, [n, k−5, n−k]-linear codes can be constructed for 12 ≤ n ≤ 159 and 10 < k < n, and the 𝔽_{256} curve of genus 8 with 512 rational points gives [n, k − 7, n − k]-linear codes for 16 ≤ n ≤ 511 and 14 < k < n (see, for example, [11]).

Thanks to the reviewer for numerous suggestions on layout and a few corrections.

References

[1] van  der  Geer/van  der  Vlugt  tables  at

http://www.science.uva.nl/ geer/

[2] G. Haché and D. Le Brigand, “Effective construction of algebraicgeometric codes”, IEEE Transactions on Information Theory, vol. 41, Nov 1995, pp. 1615-1628.

[3] R. Hartshorne, Algebraic Geometry, GTM#52, Springer-Verlag, 1977.

[4] E. Howe, K. Lauter, http://arxiv.org/abs/math.NT/0207101

[5] Y. Ihara, “Some remarks on the number of rational points of algebraic curves over finite fields”, J. Fac. Sci. Tokyo, 28, 1981, pp. 721-724.

[6] KANT, http://www.math.tu-berlin.de/algebra

[7] K. Lauter “Geometric Methods for Improving the Upper Bounds of the Number of Rational Points on Algebraic Curves over Finite Fields”, Journal of Algebraic Geometry, 10, 2001, pp. 19-36.

[8] www.math.purdue.edu/∼clomont/Math/Papers/2000/PolySolver.zip [9] MAPLE, www.maplesoft.com

[10] O. Moreno, D. Zinoviev, V. Zinoviev, “On Several New Projective Curves Over F_{2} of Genus 3, 4, and 5”, IEEE Transactions on Information Theory, vol. 41, Nov 1995, pp 1643-1648.

[11] O. Pretzel, Codes and Algebraic Curves, Oxford Science Publications, Clarendon Press, 1998.

[12] J. Ragot, http://pauillac.inria.fr/algo/seminars/sem97-98/ragot.html [13] J.-P. Serre, “Nombres de points des courbes algebriques sur F_{q}”, Sem-

inaire de Theorie des Nombres de Bordeux, expose 22, pp. 1-8, 1983.

[14] M. A. Tsfafman and S. G. Vlăduţ, Algebraic-Geometric Codes. Dordrecht/Boston/London: Kluwer, 1991.

[15] R. Walker, Algebraic Curves, Dover Publications, N.Y., 1962.

Department of Mathematics, Purdue University, West Lafayette

Indiana 47907 Email address: clomont@math.purdue.edu First written: Dec 2000, revised Apr 2002