A formula for constructing curves over finite fields with many rational points

Kristin Lauter

                lauter@mpim-bonn.mpg.de

1 Introduction

Over the past fifteen years, mathematicians have been drawn to the problem of constructing curves over finite fields that have many rational points, largely because such curves have been shown to have important applications but also because the construction of such curves is theoretically challenging. The challenge lies in meeting the bounds on the number of points given by Oesterlé’s optimization of Weil’s explicit formulae. In this paper we prove a formula that can be used to construct curves that come close to these bounds.

In 1983, Serre indicated his method for using class field theory to construct curves over 𝔽_{2} with many rational points [8]. Since then, class field theory has been responsible for much of the progress on this problem: even families which were found via other methods can be described using Serre’s approach, thus unifying the known results under one mantle [3]. Recently, Niederreiter and Xing ([4],[5]) have made remarkable progress in this direction by varying the base field and the ramification for many 𝔽_{q}. In this paper, we complement that work by fixing the base and a place of ramification and increasing the number of points to be split. When attempting to split many points, one is confronted with the problem of computing the exponent of p of n_{k}, the order of the following quotient:

(𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗}/⟨1 − αT |α ∈ 𝔽_{q}^{∗}⟩.

Such quotients appear as the Galois group of abelian extensions of 𝔽_{q}(T) in which all but one of the places of degree one are totally split. These function fields correspond to curves with n_{k}q + 1 rational points, whose genus can be computed via the conductor-discriminant formula, based on the knowledge of the orders n_{l} for all l ≤ k.

Apart from its natural importance for constructing curves with many points, the task of computing n_{k} is interesting in itself, since it is counter-intuitive to write a degree-one polynomial as a product of powers of other degree-one polynomials. This phenomenon certainly occurs as for example in the case when q = 9, k = 5.

The value of n_{k} is in general very difficult to compute, since it seems to entail finding the relations between all the degree one polynomials in order to determine the order of the subgroup that they generate. The main result of this paper is a general formula for the order of this quotient for any choice of q = p^{f} and k.

Theorem 1 Suppose q = p^{f}, k > 1. Then

|(𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗}/⟨1 − αT |α ∈ 𝔽_{q}^{∗}⟩| = p^{∑_{i∈I} γ_{i}(f−f_{i})},

where I, H, f_{i}, and γ_{i} are as below.

The set, I, consists of the natural numbers from 1 to k − 1 which are prime to p; the set, H, is the maximal set of natural numbers from 1 to q − 1

1 ≤ ℓ_{2} ≤ ... ≤ ℓ_{r}

with the property that if ℓ_{i} ≡ ℓ_{j}p^{h} (mod q − 1), then i = j, and such that no multiple of a power of p by a positive number smaller than ℓ_{i} can be congruent to ℓ_{i} (mod q − 1). For each i in I, if i is also in H, then f_{i} is such that 𝔽_{p^{f_{i}}} is the smallest subfield of 𝔽_{q} containing α^{i}, for all α ∈ 𝔽_{q}^{∗}; if i is not in H, then f_{i} is zero. Finally, γ_{i} is the smallest integer such that ip^{γ_{i}} ≥ k.

This theorem is proved in Section 3 by transforming the multaplicative structure of this group into an additive one via the isomorphism with the additive group of the ring of generalized Witt vectors. This group can then be decomposed into a direct sum of copies of the usual p-Witt vectors. The subgroup generated by the degree one polynomials is transformed by this isomorphism into the subgroup generated by the image of the Teichmüller lifts of the elements {α ∈ 𝔽_{q}^{∗}}. This subgroup and its order are computed in Proposition 1 of Section 3.

For the sake of quick access for those interested primarily in implementation, Section 4 is included as a self-contained algorithm for computing n_{k} given any q = p^{f} and k. It follows directly from the main theorem and definitions.

In Section 5, we derive from Theorem 1 expressions for n_{k} in terms of q for certain special cases of k, which arise from the examples of irreducible Deligne-Lusztig curves, The three Deligne-Lusztig families of irreducible curves, Hermitian, Suzuki, and Ree, are of particular interest because each member of them has the maximum number of points possible for a curve of its genus. These families can all be realized as abelian covers of the projective line with Galois group as in Theorem 1.

In Section 6, we determine the smallest k_{0} such that, for k ≥ k_{0}, the group (𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗}/⟨1 − αT |α ∈ 𝔽_{q}^{∗}⟩ is not of exponent p. When k > k_{0}, we will see that the ratio of the number of points to the genus is better than in the exponent p case which was studied in [9]. In addition, when k > k_{0}, we will observe the existence of characters of conductor k(T), k = mp + 1, for many values of m, whereas this is never the case for extensions of exponent p.

In Section 7, we give tables of examples constructed via the formula in Theorem 1 for small values of q and k. For example, when q = 4 and k = 7, the resulting curve has genus 33 with 65 points. The Weil bound for this genus is 137, whereas the Oesterlé’s optimization of the explicit formulae show that no curve over 𝔽_{4} of this genus can have more than 66 points. This example was already in [2], found via the method of computing relations among the degree one polynomials, but that technique does not highlight the fact that this is the smallest choice of k over 𝔽_{4} for which the Galois group is not killed by 2, contrary to the case of the examples generated in [9] and the families of Deligne-Lusztig curves.

Acknowledgements: I would like to thank Hendrik Lenstra, Spencer Bloch and J.-P. Serre for their generous help and encouragement. This work was done while visiting the Max Planck Institute in Bonn, and I would like to thank the Institute for a wonderful place to work.

2 Notation

In this section we restate and reformulate the definitions from the introduction. This notation will be needed throughout the paper. Fix k > 1 and q = p^{f}. We define the following sets:

I = {i ∈ ℕ|1 ≤ i ≤ k − 1, (i, p) = 1}

Consider the action of ℤ/fℤ on ℤ/(q − 1)ℤ whereby

d ∗ i = p^{d}i

Define the set:

H = {smallest natural number from each of the distinct orbits of ℤ/(q−1)ℤ under the above action}

Now for all i ∈ I, define

f_{i} = \{ \begin{matrix}0 & when i ∉ H \\ size of the orbit of i & when i ∈ H \end{matrix}

Finally, define

γ_{i} = the smallest integer such that ip^{γ_{i}} ≥ k

Note: if i ≥ k, then γ_{i} = 0.

3 Main Theorem

In this section we give the proof of the main theorem of the paper.

Proof of Theorem 1: We want to prove that n_{k} = p^{∑_{i∈I} γ_{i}(f−f_{i})}. We first note that (𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗} consists of all the polynomials of degree less than k with coefficients in 𝔽_{q} and constant term equal to one, so it has order q^{k−1}. Since it is clear that ∑_{i∈I} γ_{i} = k − 1, it suffices to show that the order of the subgroup < 1 − αT |α ∈ 𝔽_{q}^{∗} > is equal to p^{∑_{i∈I} γ_{i}f_{i}}. This is accomplished in Proposition 1 below via an isomorphism of the principal units in the power series ring in one variable over 𝔽_{q} with the additive group of the ring of generalized Witt vectors over 𝔽_{q} and the subsequent decomposition into copies of the usual p-Witt vectors of length γ_{i}.

Witt decomposition

First note that

(𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗} ≅ (1 + T 𝔽_{q}[[T]])/(1 + T^{k}𝔽_{q}[[T]]).

Now we have an isomorphism (see [1])

Λ(𝔽_{q}) := (1 + T 𝔽_{q}[[T]]) ≅ 𝕎(𝔽_{q})

where 𝕎(𝔽_{q}) is the ring of generalized Witt vectors over 𝔽_{q}. The map is given by:

E(a_{1}, a_{2}, ...) = ∏_{i}(1 − a_{i}T^{i})^{−1}

for (a_{1}, a_{2}, ...) ∈ 𝕎(𝔽_{q}). The map E^{−1} endows Λ(𝔽_{q}) with a ring structure.

We need the following decomposition of the generalized Witt vectors into a direct sum of copies of the usual p-Witt vectors. The difference between the generalized Witt vectors, denoted here by 𝕎(𝔽_{q}), and the usual p-Witt vectors, denoted here by 𝕎^{p}(𝔽_{q}), is as follows: the operations in either case are defined in terms of polynomials

W_{n}(X_{1}, X_{2}, ...) = ∑_{d|n} dX_{d}^{n/d},

but in the case of the usual p-Witt vectors, W_{n} is replaced by W_{p^{n}}, and the numbering is shifted to start with 0.

Our presentation here has been distilled from the sources ([7],p.102, and [1]):

𝕎(𝔽_{q}) ≅ ∏_{I(p)} 𝕎^{p}(𝔽_{q})

where I(p) is the set of positive integers prime to p. This isomorphism is given by the map

c⃗ → (a⃗_{i})_{i∈I(p)},

where (a⃗_{i})_{i∈I(p)} satisfies:

E(c⃗) = ∏_{i∈I(p)} P (a⃗_{i})^{−1/i}

with

P (a⃗_{i}) = ∏_{j=0}^{∞} AH(a_{ij}T^{ip^{j}})

a⃗_{i} = (a_{i0}, a_{i1}, ...), and AH(T) is the Artin-Hasse exponential:

AH(T) = ∏_{(n,p)=1}(1 − T^{n})^{μ(n)/n}

and μ is the Möbius function.

The fact that this isomorphism reduces to the following isomorphism for each k can be seen directly or can be found in [7]:

𝕎_{k−1}(𝔽_{q}) ≅ ⨁_{I} 𝕎_{γ_{i}}^{p}(𝔽_{q}) (∗)

Both the left and right hand sides indicate copies of truncated Witt vectors, on the left of length k − 1 and on the right of lengths {γ_{i}}. (The numbering of components of the Witt vectors starts with 1 on the left hand side and with 0 on the right.) Note that both sides are groups of order q^{k−1}, which is true again because

∑_{i∈I} γ_{i} = k − 1.

For our purposes we will need the images of the Teichmüller representatives of the elements of 𝔽_{q}: α ∈ 𝔽_{q} lifts to α⃗ = (α, 0, 0, ...) in 𝕎(𝔽_{q}) and

(α, 0, 0, ...) → ((α, 0, 0, ...), ..., (α^{i}, 0, 0, ...), ...)_{i∈I(p)}

under the isomorphism (*), since

E(α⃗) = ∏_{i∈I} AH((αT)^{i})^{−1/i}.

It remains to determine the order of the subgroup, N, of ⨁_{I} 𝕎_{γ_{i}}^{p}(𝔽_{q}) generated by the {α^{j}}, where < α >= 𝔽_{q}^{∗}, j = 1, ...q − 1, and

{α^{j}} = ((α^{j}, 0, 0, ...), ..., (α^{ji}, 0, 0, ...), ...)_{i∈I(p)}

(in the ith component, the vector (α^{ji}, 0, 0, ...) has length γ_{i}). Consider the projection

Π : ⨁_{I} 𝕎_{γ_{i}}^{p}(𝔽_{q}) → ⨁_{H} 𝕎_{γ_{i}}^{p}(𝔽_{q}).

Note that if some element s of H is not in I, it can only be for the reason that s ≥ k, in which case γ_{s} = 0. Now set N′ equal to the projection of N.

Proposition 1

N ≅ N′ ≅ ⨁_{H} 𝕎_{γ_{i}}^{p}(𝔽_{p^{f_{i}}})

Proof of Proposition:

First we prove the isomorphism N ≅ N′. Since N′ is obtained from N via a projection, it suffices to show that the projection is injective on N. Suppose that for any i ∈ H,

∑_{j=1}^{q−1} c_{j}(α^{ji}, 0, 0, ...) = (0, 0, 0...).

We must show that

∑_{j=1}^{q−1} c_{j}(α^{ji′}, 0, 0, ...) = (0, 0, 0...)

holds for all i′ ∈ I. For i′ ∈ I, write i′ = ip^{h}, i ∈ H. The sum,

∑_{j=1}^{q−1} c_{j}(α^{ji}, 0, 0, ...)

is a Witt vector with entries which are given by polynomials with coefficients in 𝔽_{p}. Thus the entries of the sum ∑_{j=1}^{q−1} c_{j}(α^{ji′}, 0, 0, ...) are the p^{h}-th power of the entries of ∑_{j=1}^{q−1} c_{j}(α^{ji}, 0, 0, ...), which are zero by assumption.

Next we must show that

N′ ≅ ⨁_{H} 𝕎_{γ_{i}}^{p}(𝔽_{p^{f_{i}}}).

First remark that the left hand side is contained in the right hand side because α^{i} and the subgroup it generates are contained in the subfield 𝔽_{p^{f_{i}}}. Now, a subgroup of a finite abelian p-group generates the whole group if and only if it generates the group (mod p). This is an application of Nakayama’ s lemma to the group viewed as a ℤ/p^{γ_{1}}ℤ-module. So it suffices to show that the 𝔽_{p}-span of the set {(α^{j}, ..., α^{ji}, ...)_{i∈H}}_{j=1,...q−1} is ∏_{i∈H} 𝔽_{p^{f_{i}}}. Note that the 𝔽_{p}-dimension of this product is exactly the sum of the size of the orbits of the elements of H under multiplication by p, which is exactly all the numbers {1, ..., q − 1}. Thus it suffices to show that the q − 1 elements {(α^{j}, ..., α^{ji}, ...)_{i∈H}}_{j=1,...q−1} are linearly independent over 𝔽_{p}. Suppose we have a relation:

∑_{j=1}^{q−1} c_{j}α^{ji} = 0

with c_{j} ∈ 𝔽_{p}, which holds for all i ∈ H. Then since c_{j} ∈ 𝔽_{p},

∑_{j=1}^{q−1} c_{j}α^{jip^{h}} = 0, for all h ∈ ℤ.

Since ip^{h} runs through all elements of ℤ (mod q − 1), putting a_{j} = α^{j} ∈ 𝔽_{q}, we can write

∑_{j=1}^{q−1} c_{j}a_{j}^{ν} = 0, for all ν ∈ ℤ.

Now it follows from the linear independence of characters that c_{j} = 0 for all j. □

This proposition concludes the proof of our theorem, since the order of this subgroup is seen to be p^{∑_{i∈I} γ_{i}f_{i}}.

4 Algorithm

The following algorithm gives an explicit way to compute the degree of this quotient for any k and any q = p^{f}:

Step 1 Write down the set

I = {i|1 ≤ i ≤ k − 1, (i, p) = 1}.

Step 2 For each i ∈ I, compute the number

γ_{i} := the smallest positive integer such that ip^{γ_{i}} ≥ k.

Step 3 Compute the orbits of the action of ℤ/fℤ on ℤ/(q − 1)ℤ, where the action is by multiplication by the rth power of p.

Step 4 Write down the set

H = { the smallest element from each orbit of the action in Step 3 }.

Step 5 For each i ∈ I calculate the number f_{i} via the following rule:

f_{i} = 0, if i ∉ H

f_{i} = the size of the orbit of i, if i ∈ H.

Step 6 Then the formula for the degree is:

p^{∑_{i∈I} γ_{i}(f−f_{i})}.

5 Families of Examples: Deligne-Lusztig curves

In [3], the ray class field descriptions of the Deligne-Lusztig curves are given and used to deduce results on the order of quotients of polynomial rings which are quite surprising:

Theorem 2 Let 𝔽_{q^{2}} be the finite field with q^{2} elements, q a power of a prime. Let k = q + 2. Then

|(𝔽_{q^{2}}[T]/T^{k})^{∗}/𝔽_{q^{2}}^{∗}/ < 1 − αT |α ∈ 𝔽_{q^{2}}^{∗} > | = q.

Furthermore, this quotient is trivial if k < q + 2, in which case all polynomials split completely into factors of degree one.

Theorem 3 Let 𝔽_{q} be the finite field with q = 2^{2m+1} = 2q_{0}^{2} elements. Let k = 2q_{0} + 2. Then

|(𝔽_{q}[T]/T^{k})^{∗}/𝔽_{q}^{∗}/ < 1 − αT |α ∈ 𝔽_{q}^{∗} > | = q.

Furthermore, this quotient is trivial if k < 2q_{0} +2, in which case all polynomials split completely into factors of degree one.

Theorem 3 should be modified slightly to desribe the full situation in characteristic 3. The proof of these theorems uses the existence of the Deligne-Lusztig curves, the knowledge of the filtration of the ramification groups, and the theorems of class field theory. It seems natural to try to give a more direct proof. In this section we will show how these theorems can be deduced directly from Theorem 1.

The proofs depend on the following lemma, which was pointed out to me by Hendrik Lenstra. In what follows, the notation ⌈x⌉, (resp. ⌊x⌋), will be used to denote the greatest integer greater than (resp. less than) or equal to x.

Lemma 1 Let q = p^{f}. If k < p^{⌈f/2⌉} + 2, then f_{i} = f, for all i ∈ I. When k = p^{⌈f/2⌉} + 2, then k − 1 ∈ I, and f_{k−1} = f/2 if f is even, or f_{k−1} = 0 if f is odd.

Proof: We will prove these statements in order. To show that f_{i} = f for all i in I, we must show that the orbit of i has size f, and that i is the smallest element in its orbit. Suppose that i, i′ ≤ p^{⌈f/2⌉} − 1, and

p^{h}i ≡ p^{h′}i′ (mod q − 1), h, h′ < f.

Then p^{h−h′}i ≡ i′ (mod q − 1), with h − h′ ≤ ⌊f/2⌋. Since

p^{h−h′}i ≤ p^{⌊f/2⌋}(p^{⌈f/2⌉} − 1) ≤ q − 1

and (i′, p) = 1, we conclude that h − h′ ≡ (mod f) and i = i′. This shows that each of the orbits of the elements i < p^{⌈f/2⌉} + 1, (i, p) = 1, has size f, and that no two of these elements are in the same orbit, which means exactly that f_{i} = f.

For the next claim, we assume that k = p^{⌈f/2⌉} + 2. Then k − 1 is prime to p, so it belongs to I. When f is even, we must show that the size of the orbit of k − 1 is f/2. But k − 1 = p^{f/2} + 1, and p^{f/2}˙(k − 1) ≡ (k − 1) (mod q − 1). Furthermore, this is the smallest positive power of p which could have this property. We also know that k − 1 is not in the orbit of any smaller element of I, since all other elements of its orbit are between p^{f/2} + 1 and q − 1. From this we conclude that f_{k−1} = f/2.

When f is odd, it suffices to show that k − 1 is in the orbit of a smaller number. But

k − 1 = p^{⌈f/2⌉} + 1 ≡ p^{⌈f/2⌉}(p^{⌊f/2⌋} + 1) (mod q − 1).

Since k − 1 is not in H, we conclude that f_{k−1} = 0. □

Direct proof of Theorem 2: q^{2} = p^{f}, f = 2m. By Lemma 1,

k < p^{m} + 2 = q + 2 ⇒ f_{i} = f, for all i ∈ I
⇒ p^{∑_{i∈I} γ_{i}(f−f_{i})} = 1.

If k = p^{m} + 2, then p^{⌈f/2⌉} + 1 ∈ I, and f_{p^{m}+1} = m. Since γ_{p^{m}+1} = 1, we have

p^{∑_{i∈I} γ_{i}(f−f_{i})} = p^{f−m} = q. □

Direct proof of Theorem 3: q = p^{f}, f = 2m + 1. By Lemma 1,

k < p^{⌈f/2⌉} + 2 = p^{m+1} + 2 ⇒ f_{i} = f, for all i ∈ I
⇒ p^{∑_{i∈I} γ_{i}(f−f_{i})} = 1.

If k = p^{m+1} + 2, then p^{m+1} + 1 ∈ I, and f_{p^{m+1}+1} = 0. Since γ_{p^{m+1}+1} = 1, we have

p^{∑_{i∈I} γ_{i}(f−f_{i})} = p^{f} = q. □

Note that this proof holds for any characteristic, eliminating the assumption p = 2 from Theorem 3. When p = 3, m ≥ 1, the quotient in the statement of Theorem 3 corresponds to the first stage of the Ree curve. When k is increased to 3^{m+1} + 3, we obtain the Ree curve which has the maximum number of points for its genus. The fact that the degree of the extension is q^{2} when k = 3^{m+1} + 3 can also be deduced from Theorem 1. In fact, it is a special case of the following proposition:

Proposition 2 Let q = p^{2m+1}, p > 2. If D = (p^{m+1} + i)P_{∞}, 2 ≤ i ≤ p, then the ray class field extension of 𝔽_{q}(X) obtained when the other q places of degree one are totally split has degree q^{i−1}.

Proof: Taking into consideration what has already been proved in Lemma 1, it suffices to show that f_{k_{i}−1} = 0, k_{i} = p^{m+1} + i, i = 2, ...p. In other words, that p^{m+1} + (i − 1) is in the orbit of some smaller element of I_{k_{i}}. But

p^{m+1} + i + i(q − 1) = p^{m+1} + ip^{m+1}p^{m} = p^{m+1}(1 + ip^{m})
⇒ p^{m+1} + i ≡ p^{m+1}(1 + ip^{m}) (mod q − 1).

This suffices to show that f_{k_{i}} = 0 for i = 1, ..., p − 1, since 1 + ip^{m} is prime to p and less than p^{m+1} + i + 1, so it is an element of I_{k_{i+1}}. □

From this proposition, we can produce families of curves in any characteristic which are analogous to the Deligne-Lusztig curves in characteristics 2 and 3. The following simple examples certainly have many points, but it remains to be seen whether they are optimal for their genus. Furthermore, these results also hold for m = 0, that is to say over prime fields.

Corollary 1 Let q = p^{2m+1}, p > 2. If D = (p^{m+1} + i)P_{∞}, then the ray class field extension of 𝔽_{q}(X) obtained by splitting the other q places in the base corresponds to a curve with q^{i} + 1 rational points of genus

g = \frac{1}{2}((p^{m+1} + i − 2)q^{i−1} − q^{i−2} − q^{i−3} − ... − q − p^{m+1}).

Special cases of this family when i = 2 and i = p are:

Corollary 2 Let q = p^{2m+1}, p > 2. If D = (p^{m+1} + 2)P_{∞}, then the ray class field extension of 𝔽_{q}(X) obtained by splitting the other q places in the base corresponds to a curve with q^{2} + 1 rational points of genus

g = \frac{1}{2}p^{m+1}(q − 1).

Corollary 3 Let q = p^{2m+1}, p > 2. If D = (p^{m+1} + p)P_{∞}, then the ray class field extension of 𝔽_{q}(X) obtained by splitting the other q places in the base corresponds to a curve with q^{p} + 1 rational points of genus

g = \frac{1}{2}((p^{m+1} + p − 2)q^{p−1} − q^{p−2} − q^{p−3} − ... − q − p^{m+1}).

These two cases correspond to the first and second stages of the Ree curve. The reason that the behaviour of the degree is different when i ≥ p + 1 is that multiples of p are not in I.

6 Comparison with exponent p

The quotient whose order is computed in Theorem 1 is the Galois group of the maximal abelian extension of 𝔽_{q}(T) which is

1. unramified outside (T),

2. totally split at all other places of degree one,

3. whose characters have conductor k′(T), with k′ ≤ k.

It is an abelian p-group, but it is not necessarily of exponent p (killed by p). Taking the quotient of this group by the subgroup of its pth powers, we obtain the Galois group of the maximal abelian extension of exponent p with properties (1),(2),(3). In this section, we compare the degrees of these two extensions, which we call the maximal p-extension and the maximal p-extension of exponent p.

6.1 Comparison of the degrees

First note that the degree of the maximal p-extension of exponent p is given by the formula:

p^{∑_{i∈I}(f−f_{i})}.

This follows from the proof of proposition 1, where we computed the subgroup N′ (mod p). All of the families described in Section 5 are of exponent p. In fact, we can determine exactly the smallest k for which the Galois group of the extension will not be killed by p:

Proposition 3 Let q = p. Then the degrees of the maximal p-extension and the maximal p-extension of exponent p are equal when k < (p + 1)p + 1. For k ≥ (p + 1)p + 1, the degrees differ, and the quotient in Theorem 1 is not of exponent p.

Proof: It is clear that p^{∑_{i∈I}(f−f_{i})} = p^{∑_{i∈I} γ_{i}(f−f_{i})} whenever

f_{i} ≠ f ⇒ γ_{i} = 1, for all i ∈ I.

In this case, since f_{i} = f = 1, for all i ∈ H, the only contribution to the degree in either of the formulas comes when i ∉ H. Each element of the set {1, ..., p − 1} constitutes a distinct orbit under multiplication by p (mod p − 1), so they all belong to H. The first element of I which is not in H is p + 1, and the first k for which γ_{p+1} > 1 is (p + 1)p + 1. □

When q is a power of a prime, the situation is similar. Proposition 3 is a special case of the following:

Proposition 4 When q = p^{f}, the smallest k for which the extension is not of exponent p occurs for k = p^{⌈f/2⌉+1} + p + 1.

Proof: This follows from Lemma 1 since the first i ∈ I for which f_{i} ≠ f occurs when i = p^{⌈f/2⌉+1} + 1, and it is not until k > ip that γ_{i} > 1. □

Remark 1 The maximal p-extension of exponent p corresponds to an Artin-Schreier extension of the type considered in [9], with equation

y^{q} − y = f(x)

whereas the maximal p-extension is an Artin-Schreier extension given by an equation in the Witt vectors.

6.2 Example:q=2

As an example of the difference between these two types of extensions, we consider the formulas for the degrees in terms of k when q = 2:

Proposition 5 Let K = 𝔽_{2}(X). Then the degree of L_{k}, the maximal p-extension of K of conductor D = kP_{1} in which the other two rational points of K are totally split, depends on k in the following way:

deg(L_{k}/K) = 2^{k−p−m^{∗}}

where

m^{∗} = #{ positive powers of p ≤ k − 1} = ⌊log_{p}(k − 1)⌋.

Proof: Since q = p is a prime and f = 1, the only contribution to the degree is p^{γ_{i}} for each i ∈ I − H. In this situation, H = {1}. Beginning with k = 4, which is the first time when k − 1 produces an element of I which is not in H, remark that the degree of the extension increases by a power of two for every increase of the conductor by one, except when k − 1 is a power of the prime. In fact, if k is even, then k − 1 gives a new element of I \ H, with γ_{k−1} = 1; if k is odd, then γ_{i} increases by one, for some i ∈ I: this will increase the degree by one unless i ∈ H, which in this case happens exactly when k − 1 is a power of the prime. □

Compare this with the formula for the maximal p-extension of exponent p and conductor kP_{1}:

Proposition 6 Let L_{k}^{p} denote the maximal p-extension of exponent p of K of conductor D = kP_{1} in which the other two rational points of K are totally split. If k = 2m + r, r = 0, 1, then

deg(L_{k}^{p}/K) = 2^{m−1}.

Proof: The degree increases by one power of p for each new element of I which is not in H, which are exactly all odd numbers bigger than one and less than k. □

The point of this comparison is that for a given k the degree of the maximal pextension will be roughly 2^{k−2}/(k−1), while the degree of the maximal exponent p p-extension will be roughly \sqrt{2}^{k−2}, which means that the examples of the former type will have a much better ratio of number of points to genus. For example, the extension of K with 33 rational points is obtained when k = 8, but as an exponent p extension when k = 10, so the genus of the exponent p extension is 47 instead of 39. Similarly, in the table for 𝔽_{4}, the example over 𝔽_{4} of a curve with 65 points which is not of exponent p has genus 33, whereas the curve with this same number of points which is of exponent p has genus 37. □

6.3 New characters from maximal p-extensions

We can interpret a jump in the degree of the extension when k is increased by 1 as implying the existence of new characters with conductor (k + 1)P_{1}. The formula we obtained in Theorem 1 shows that when considering the maximal p extension, one will obtain characters of conductor a multiple of p plus one in many cases, whereas this will never occur in the exponent p case. The degree of the maximal p-extension of exponent p does not change when k is increased from a multiple of p, mp, to mp + 1, since mp is not prime to p, so it is not an element of I. However, the expression for the degree of the maximal p-extension may change under these circumstances, if mp = ip^{γ_{i}}, for some i ∈ I. This is due to the fact that when k is increased to mp + 1, γ_{i} will increase by one.

7 Examples

In this section, we give tables for different q = p^{f} of curves obtained by splitting all q rational points of ℙ_{𝔽_{q}}^{1} different from a given one, P_{1}, in the ray class field of conductor D = kP_{1}, where k ≥ p^{⌈f/2⌉} + 2.

All entries in these tables are computed directly from the main theorem of this paper via the ray class field method of Serre which is detailed in [6],[3]. Some of these entries correspond to examples from [9], [5], [8], and [2]. Optimality of an example is determined relative to the Oesterle bounds. Examples not contained in previous tables in the above sources are denoted with a star (*).

7.1 characteristic 2

7.1.1 q=2

For all entries in this table, H = {1}

Table 1: Splitting q Points, D = kP_{1}, q = 2

k  degree genus  N exponent p?  Notes
k = 4  2  g = 1  5  yes  optimal (Serre)
= p + 2  k − 1 = 3 ∉ H
k = 5 2 no new element of I

γ_{1} = 3, no difference

k = 6 2^{2} g = 5 9 yes optimal (Serre)

γ_{3} = 1, γ_{5} = 1

k = 7 2^{3} g = 15 17 no optimal (Serre)

γ_{3} = 2, γ_{5} = 1

k = 8  2^{4}  g = 39 33  no  optimal (Serre)
k = 9  2^{4}  γ_{1} = 4
k = 10  2^{5}  g = 103 65  no
k = 11  2^{6}  g = 247 129  no  γ_{5} = 2

7.1.2 q=4

For all entries in this table, H = {1, 3} since the orbits modulo (q − 1) are: {1, 2} and {3}.

Table 2: Splitting q Points, D = kP_{1}, q = 4 = 2^{2}
k  degree genus  N exp p?  Notes
k = 4  2  g = 1  9  yes  optimal (Hermitian)
= p + 2  k − 1 = 3 ∈ H, f_{3} = 1
k = 5 2 no new element of I

γ_{1} = 3, no difference

k = 6 2^{3} g = 13 33 yes optimal
f_{5} = 0
k = 7 2^{4} g = 33 65 no Oesterle bound is 66
γ_{3} = 2
∗ k = 8 2^{6} g = 177 257 no f_{7} = 0

Oesterle bound 269

7.1.3 q=8 Orbits for q = 2^{3} = 8:

\begin{matrix}\{1, 2, 4\} \\ \{3, 6, 5\} \\ \{7\} \end{matrix}

H = {1, 3, 7}

Table 3: Splitting q Points, D = kP_{1}, q = 8 = 2^{3} = 2^{2m+1}

k  degree  genus  N  exp p?  Notes
k = 6  2^{3}  g = 14  65  yes  Suzuki curve (optimal)
= p^{m+1} + 2  k − 1 = p^{m+1} + 1

first time an element appears in a previous orbit

k = 7  2^{3}  γ_{3} = 2, f_{3} = 3
∗ k = 8  2^{5}  g = 86  257  yes  f_{7} = 1, Oesterle: 266

Weil: 495

k = 9  2^{5}  γ_{1} = 4, no change
∗ k = 10 2^{8} = 256 g = 982 2, 049  yes  f_{9} = 0 Oesterle: 2, 372

Weil: 5, 281

∗ k = 11 2^{11} g = 9, 046 16, 385 no γ_{5} = 2, Oesterle:19, 673

Weil: 51, 181

First k for which the extension is not of exponent p is 11.

7.2 characteristic 3

7.2.1 q=3 For all entries in this table, H = {1, 2}

Table 4: Splitting q Points, D = kP_{1}, q = 3

k  degree  genus  N  exp p?  Notes
k = 5  3  g = 3  10  yes  optimal
=p+2  k − 1 = 4 ∉ H
k = 6 3^{2} = 9  g = 15  28  yes  optimal
k = 7  3^{2}  no new element of I
k = 8  3^{3}  g = 69  82  yes Oesterle bound is 88
∗ k = 9  3^{4}  g = 258  244  yes  k − 1 ∉ H

Oesterle: 276

k = 10  3^{4}
∗ k = 11 3^{5} g = 987 730 yes k − 1 ∉ H

Oesterle: 940

∗ k = 12  3^{6}  g = 3417  2188  yes  k − 1 ∉ H
∗ k = 13  3^{7}  g = 11, 436 6, 562  no  γ_{4} = 2, 4 ∉ H
∗ k = 14  3^{8}  g = 37, 680 19, 684  no  k − 1 ∉ H
∗ k = 15  3^{9}  122, 973 59, 050  no  k − 1 ∉ H

7.2.2 q=9 Orbits for q = 3^{2} = 9:

\begin{matrix}\{1, 3\} \\ \{2, 6\} \\ \{4\} \\ \{5, 7\} \\ \{8\} \end{matrix}

H = {1, 2, 4, 5, 8}

Table 5: Splitting q Points, D = kP_{1}, q = 9 = 3^{2}
k  degree  genus  N  exp p?  Notes
k = 5  3  g = 3  28  yes  Hermitian curve
=p+2  orbit of 4 size 1
k = 6  3  orbit of 5 size f = 2
k = 7  3  I_{7} = I_{6} γ_{2} = 2
∗ k = 8  3^{3}  g = 75  244  yes  7 is in orbit of 5

Oesterle: 263

∗ k = 9 3^{4} g = 264 730 yes orbit of 8 size 1

Oesterle: 784

k = 10  3^{4}  I,H same, γ_{1} = 3
∗ k = 11  3^{6}  g = 3180  6561  yes  k > q, so k − 1 ∉ H
∗ k = 12  3^{8}  g = 32, 340  59, 049  yes  k − 1 ∉ H
∗ k = 13  3^{9}  g = 104, 511  177, 147  no  γ_{4} = 2, f_{4} = 1
∗ k = 14 3^{11} g = 1, 049, 295 1, 594, 323  no  k − 1 ∉ H

7.2.3 q=27 Orbits for q = 3^{3} = 27:

{1, 3, 9} {2, 6, 18} {4, 12, 10} {5, 15, 19} {7, 21, 11} {8, 24, 20} {13} {14, 16, 22} {17, 25, 23}

Table 6: Splitting q Points, D = kP_{1}, q = 27 = 3^{3} = 3^{2m+1}
k  degree  genus  N  exponent p?  Notes
k = 11  3^{3} = 27  g = 117  730  yes  first stage of Ree curve
= p^{m+1} + 2  k − 1 = p^{m+1} + 1

first time an element appears in a previous orbit

k = 12  3^{6} = q^{2} = 729 g = 3, 627 19, 684  yes  Ree curve
k = 13  3^{6}  I same, γ_{4} = 2
∗ k = 14  3^{8} = 6561  g = 38, 619 177, 148  yes  f_{13} = 1

References

[1] P. Cartier, Groupes formels associés aux anneaux de Witt généralisés, C.R.Acad.Sc. Paris, t.265 (10 juillet 1967), Serie A, p. 49-52.

[2] K. Lauter, Ray class field constructions of curves over finite fields with many rational points, in Algorithmic Number Theory (ed. by H. Cohen), Lecture Notes in Computer Science 1122, p.187-195. Springer, Berlin 1996.

[3] K. Lauter, Deligne-Lusztig curves as ray class fields, Preprint, 1997.

[4] H. Niederreiter and C. Xing, Modules de Drinfeld et courbes algébriques ayant beaucoup de points rationnels, C.R. Acad. Sc. Paris Sér. I Math.322 (1996), 651-654.

[5] H. Niederreiter and C. Xing, Algebraic curves over finite fields with many rational points, submitted to Proc. Number Theory Conf. (Eger, 1996), de Gruyter, Berlin.

[6] R. Schoof, Algebraic curves and coding theory, UTM 336, Univ. of Trento, 1990.

[7] J.-P. Serre, Groupes algébriques et corps de classes, Hermann Paris, 1959.

[8] J.-P. Serre, Sur le nombre des points rationnels d’une courbe algebrique sur un corps fini, C.R. Acad. Sc. Paris, t. 296, (7 mars 1983).

[9] G. van der Geer and M. van der Vlugt, How to Construct Curves over Finite Fields with Many Points, Proc. Conf. Algebraic Geometry (Cortona, 1995), to appear.

[10] E. Witt, Zyklische Körper und Algebren der Charakteristik p vom Grad p^{n}, Crelle 176 (1936) p.126-140.