Preliminary version February 28, 2000

TOR VERGATA

II Università degli Studi di Roma

Algebraic curves and coding theory. Abuja 1990

René Schoof

Dipartimento di Matematica 2a Università di Roma “Tor Vergata” I-00133 Roma ITALY

Email: schoof@fwi.uva.nl

Abstract. These notes are an extension of lectures given at the National Mathematical Centre in Abuja, Nigeria during the summer of 1990. They contain brief introductions to algebraic coding theory, the geometry of algebraic curves and class field theory of algebraic curves. Goppa’s method to contruct codes by means of linear systems on algebraic curves over finite fields is discussed. Bombieri’s proof of the Riemann hypothesis for curves is given. In the last sections some recent results on the number of points on curves over finite fields are discussed. These include work by Drinfeld, Ihara, Oesterlé, Serre and Vlădut. Finally we prove a new lower bound for the number of rational points a curve of high genus over F_{2} can have.

Introduction. Codes are used to correct errors when transmitting messages through noisy channels such as telegraph wires and telephone cables. They have been used transmitting photographs from the planet Mars and they are present in compact discs. Their purpose is to detect and correct errors that occurred during the transmission of information. The basic idea to do this, is to add, in a structured way, redundant symbols to the messages. The receiver can then check whether the structure has been preserved after transmission. If it hasn’t, he knows that an error has occurred. If the added structure has been sufficiently rich, the receiver can, as we will see, even correct the errors.

In an appendix to these notes I’ve included an illustration of how codes can correct errors. The reader will find there three versions of a text taken from pages 6 and 7 of [34]. The first is the original (including some unintentional typing errors). The second is the text after a simulated transmission of the text trough a very noisy channel: using a random number generator 4% of the approximately 21 000 bits were flipped during transmission. We see that as a result of this the text became more or less unreadable. The third text is the text after transmission through the same noisy channel, this time using a code. We see that the text is readable again ! Only a few errors were not corrected. The code used was the so-called binary Golay code . We will describe it in more detail in section 2.

In this introduction we will only mention a few simple codes. A well-known example is the so-called “parity-check-bit”: Suppose, by way of example, that one transmits characters using 7 bits to represent them in binary. In this way one can represent 2^{7} = 128 different characters. One now encodes the 7 bits ϵ_{1} … ϵ_{7} by adding an 8th bit ϵ_{8}, the parity-check-bit, such that the sum ∑_{i=1}^{8} ϵ_{i} is congruent to 0 (mod 2). Now one transmits messages using common 8-bit bytes. The receiver checks whether the relation ∑_{i=1}^{8} ϵ_{i} ≡ 0 (mod 2) is satisfied. In this way he can detect 1-bit errors in a byte but there is not have enough information to correct them.

Another example is the so-called “repetition code”: instead of sending a bit once, just send it many times, say, five times. The receiver assumes that only a few errors have been made during transmission. He will now decode the received messages as follows: when he receives more ones than zeroes he decides that a one has been sent and vice versa. Using this code, the receiver can correct errors of at most two bits in one quintuple. There is a price to pay, however: the sender has to transmit 5 times as many bits.

These two examples illustrate the basic conflict in coding theory: on the one hand one wishes to be able to correct as many errors as possible, on the other hand, one wishes to transmit as few extra symbols as necessary. Our first example is extreme in one sense. One adds only very little redundancy, but one can merely detect certain errors. The second example is extreme in the other sense. One can correct more errors, but one has to add very many redundant bits.

Example. The ISBN-code. Many books have nowadays an International Standard Book Number. It is a 9 digit number followed by either a digit or an X. The famous Theory of Error-Correcting Codes by MacWilliams and Sloane [16] has the number 0-444-85193-3. The book Introduction to Coding Theory and Algebraic Geometry by Van Lint and Van der Geer [33] has 3-7643-2230-6. The text Algebraic Number Theory by Stewart and Tall [28] has 0-412-29690-X. The last symbol is a “parity-check” symbol. It can be computed as follows: if the first 9 digits are a_{1}a_{2} … a_{9} then the last symbol a_{10} is defined by

∑_{i=1}^{9} ia_{i} ≡ a_{10} (mod 11).

Here a_{10} is taken to be X whenever a_{10} ≡ 10 (mod 11).

C.E. Shannon showed in 1948 that good codes exist: no matter how noisy the channel is, for every ϵ > 0 there exist codes, with reasonable redundancy rate, that will correct each error with probability > 1 − ϵ. These codes are very long i.e. the redundant bits will not be computed from 7 bits as in the parity-check-code above but will depend on many, many more bits. One of the goals of coding theory is to contruct such good codes explicitly. In 1982 M.A. Tsfasman, S.G. Vlădut and Th. Zink [29] contructed a sequence of very good codes. The codes, so-called Goppa codes, violated the conjectural Gilbert-Varshamov bounds and their existence was a big surprise. They were contructed by means of certain linear systems on algebraic curves over finite fields.

In this course we discuss codes in sections 1 and 2 and algebraic curves in section 3. Both these sections are very brief and sketchy. They should not be considered as a serious introduction to the respective topics. In particular, no attention will be paid to encoding and decoding algorithms and we will use, but not prove the Riemann-Roch theorem for algebraic curves. We will discuss the Goppa-codes that can be constructed by means of algebraic curves over finite fields in section 4. It appears that curves over a finite field F_{q} that have many points over F_{q} with respect to their genus, give rise to good codes. Unfortunately, an algebraic curve cannot have too many points with respect to its genus. This issue is the subject matter of the remaining sections.

In section 5 we study ζ-functions of algebraic curves over finite fields. In section 6 we prove André Weil’s famous theorem [35]: the Riemann hypothesis for curves over finite fields. It implies certain bounds for the number of rational points on a curve. Weil’s proof appeared in 1948. We present S.A. Stepanov’s proof given by E. Bombieri [3] in Séminaire Bourbaki in 1973. Stimulated by the relations to coding theory, the estimates for the number of F_{q}-rational points implied by Weil’s theorem were reconsidered by several people in the early 1980’s. It appeared, rather unexpectedly, that the estimates were not best possible. In section 7 we will prove the theorem of V.G. Drinfeld and S.G. Vlădut [7] which, roughly speaking, says that the number of F_{q}-rational points on a curve of genus g over F_{q} has to be rather small with respect to g when g is very large. This indicates the limitations of the methods to construct codes with algebraic curves. Nevertheless, it is now interesting to search for curves that have many F_{q}-rational points with respect to their genus. Using class field theory, explained briefly and without proofs in section 8, we study this problem in section 9. The discussion is based on J.-P. Serre’s Collège de France course in 1983–1984. See [22,23,24,25]. Section 9 contains the only new result in these notes: the existence of algebraic curves X of arbitrary high genus g over F_{2}, for which the ratio #X(F_{2})/g is at least 2/9; see [19].

1. Coding Theory: The Hamming code. In this section and the next we will briefly outline the basic principles of coding theory. This should not be considered as a thorough introduction to the subject. We will only mention a few codes as examples or because of their relations to certain Goppa codes that will be studied in section 4. The reader who wishes to obtain a more complete knowledge of coding theory should consult more extensive texts like the book by MacWilliams and Sloane [16], the one by Van Lint [32] or the book by Tsfasman and Vlădut [30], which will be translated into English soon. For an informal historical introduction to coding theory see [6].

We will discuss one special code in detail: the [7,4,3]-Hamming code. We will explain in detail how to use this code: how to encode and how to decode. We begin by introducing some basic notions in coding theory.

The messages will be transmitted using an alphabet. In practice, this alphabet will often consist of the two bits 0 and 1. We will, more generally, consider alphabets that are finite fields. We write F_{q} for a field with q elements. The alphabet {0, 1} corresponds to the field F_{2}. Codes over this field are called binary codes . When transmitting, the entire message will be split into blocks of fixed length and each block will be encoded i.e. each block will be provided with certain redundant letters of the alphabet. In other words, encoding is an injective map E

F_{q}^{k} ⟶^{E} F_{q}^{n}

where k is the length of the blocks and n ≥ k is the length of an encoded block. We will call the image of E the code C. Its elements are called code words or simply words . The integer n is called the length of the code. The code words are the ones being transmitted.

When no errors occur during transmission, the receiver will receive a code word and, knowing the map E, he can recover the k bits of the original block. If however, the receiver encounters a word v ∉ C, then an error has occurred and he will assume that the error made is small i.e. he will look for a word ṽ ∈ C which resembles v in the sense that ṽ and v are different in only a few coordinates. The whole process is very similar to the way we ourselves detect and correct printing errors in a text: the word immediaxely is not an English word, but it is very close to the English word immediately. It differs in one place only. When we encounter the word immediaxely in a text, we “correct” the error by assuming that a small error has been made and that immediately was meant.

This leads to the notion of distance in F_{q}^{n}: For v ∈ F_{q}^{n} we define the weight |v| of a word v by

|v| = the number of non-zero coordinates of v.

The Hamming distance between two vectors v and w in F_{q}^{n} is simply |v − w|. A very important invariant of a code is the minimal distance d: it is the minimal Hamming distance between distinct words in the code C. Since the Hamming distance satisfies the triangle inequality, every “ball” of radius less than d/2 contains at most one code word. Therefore one can, in principle, correct upto [(d − 1)/2] errors in each word.

Clearly, the map E should be injective. We will only consider codes where the map E is also linear. This gives rise to the class of so-called linear codes. The linearity of C implies that

d = min_{v≠0}{|v|: v ∈ C}.

Recapitulating we have

Definition (1.1). A linear code C over an alphabet F_{q} is an F_{q}-linear subspace of F_{q}^{n}. The dimension k of C is the dimension of C as an F_{q}-vector space and the minimal distance d of C is d = min_{v≠0}{|v|: v ∈ C}.

A code C with the parameters n, k and d, is called a [n, k, d]-code. There are certain restrictions on the possible values of k and d. We mention a very easy one.

Proposition (1.2). (The Singleton bound) For every linear [n, k, d]-code one has the inequality k + d ≤ n + 1.

Proof. Since the code has dimension k, there exists a codeword with at least k − 1 coordinates equal to 0. This word has weight at most n − (k − 1). Therefore d ≤ n + 1 − k as required.

Example (1.3). The parity-check code is just {v = (v_{1}, …, v_{n}): ∑_{i} v_{i} = 0} ⊂ F_{q}^{n}. It is a [n, n−1, 2]-code. The repetition code is the subspace of F_{q}-multiples of the vector (1, 1, …, 1) ∈ F_{q}^{n}. It is a [n, 1, n]-code.

Example (1.4). The code that we used to encode and decode the text in the appendix was the binary Golay code. We will describe this code in more detail in section 2. It is a [23, 12, 7]-code. We encoded two letters at the time by taking the 2×6 = 12 bits of their ASCII-codes as the k = 12 information symbols. Using the Golay code, one can correct upto 3 errors in each 23-bit word.

One could view the ISBN-code from the introduction as a subset of F_{11}^{10}. It is not a linear code, however, since the first 9 coordinates of the code words are only in {0, 1, …, 9} which is not a full set of representatives for F_{11} in Z. One could say that it is a [10, 9, 2]-code over F_{11} not all of which code words are used.

The rest of this section will be devoted to the [7, 4, 3]-Hamming code H. It is the binary code in F_{2}^{7} generated by the four vectors

( \begin{matrix}1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix} ) , ( \begin{matrix}0 \\ 1 \\ 0 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix} ) , ( \begin{matrix}0 \\ 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \end{matrix} ) , ( \begin{matrix}0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 1 \\ 1 \end{matrix} ) .

Equivalently, it is the 4-dimensional subspace of F_{2}^{7} given by the linear equations

( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \\ x_{6} \\ x_{7} \end{matrix} ) = 0.

Here is a complete list of all 16 code words:

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
0 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1
0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1

When using this code, we let the first 4 coordinates contain the information bits. We’ll transmit the unique vector v ∈ H which has its first 4 coordinates x_{1}, …, x_{4} equal to the 4 information bits. It is easy to find v by means of a matrix multiplication:

v = ( \begin{matrix}1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{matrix} ) = ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{2} + x_{3} + x_{4} \\ x_{1} + x_{3} + x_{4} \\ x_{1} + x_{2} + x_{4} \end{matrix} ) .

Now v will be transmitted and a, possibly erronous, vector ṽ is received. We must decode ṽ by looking for a vector w ∈ C nearest to ṽ and “hope” that w is indeed the message sent. In general this is a very difficult problam, but here it can be done as follows: the vector ṽ is in some coset C′ of the code H. We look for a vector v′ ∈ C′ of minimal weight. The vector w = ṽ − v′ is now in C and as close as possible to ṽ. We will assume that w is the original message.

How to find vectors of small weight in the cosets of C? For our small Hamming-code H this is very easy. By inspecting the 16 vectors in C given above one sees that the minimal distance d is equal to 3. This implies at once that the 7 basis vectors e_{1}, … e_{7} are each in a different non-trivial coset of C. It so happens that there are precisely 2^{3} − 1 = 7 non-trivial cosets of H. So each basis vector e_{i} is contained in precisely one coset C_{i} of H. To decode an erronous ṽ we must decide in which coset C_{i} it is. This can be done by means of the following elegant trick: Consider the matrix

A = ( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} );

it is the matrix of equations for the code H given above. So C = ker(A) and A is constant on cosets of C. Observe now that the column vectors of A can be viewed as the numbers “1” upto “7” written in binary: we see that Ae_{i} =“i”. Now the decoding recipee is clear: apply A to ṽ. You will find a vector “i” where 0 ≤ i ≤ 7. If i = 0 the vector ṽ is in C and probably no error has been made. If i ≠ 0 then ṽ is in the same coset as e_{i} and you should take, in the above notation, v′ = e_{i}. In other words: an error has been detected in the i-th coordinate. Change the bit there.

Exercises.

(1.A) Find the parameters n, k, and d of the code {(0, 0, 0, 0), (0, 0, 1, 1), (1, 1, 0, 0), (1, 1, 1, 1)} ⊂ F_{2}^{4}. (1.B) Let < v, w > denote the usual scalar product on the vector space F_{q}^{n}: For v = (v_{i})_{i} and w = (w_{i})_{i}

one has < v, w >= ∑_{i=1}^{n} v_{i}w_{i}. By V^{⊥} we denote the dual of a linear subspace V of F_{q}^{n}: that is V^{⊥} = {v ∈ F_{q}^{n}: < v, w >= 0 for all w in V }. Show that (V^{⊥})^{⊥} = V. Show that the dual of a code is again a code. What can you say about its parameters ? Show that the parity-check code and the repetition codes are dual to one another.

(1.C) Suppose that F_{q} is a subfield of F_{r} and suppose that C ⊂ F_{r}^{n} is a code over F_{r}. Show that C′ = F_{q}^{n} ∩C is a code over F_{q}. The code C′ is called the restriction of C to F_{q}. What can you say about its parameters?

(1.D) Show that the weights of the code words of a self-dual binary code C are even. Suppose that this code C is generated by v_{1}, …, v_{m}. Show that if |v_{i}| ≡ 0 (mod 4) for 1 ≤ i ≤ m then |x| ≡ 0 (mod 4) for every code word x.

1.E) Use the Hamming code and encode the the vectors (0, 1, 1, 0) and (1, 1, 1, 0). Decode the following words: (0, 0, 1, 1, 1, 1, 1) and (1, 0, 1, 0, 0, 0, 0). Which are the weights that occur in the Hamming code H? Which weights and with which frequencies occur in the cosets of H? What are the parameters of the even-weight subcode of H?

(1.F) Construct an extended Hamming code H′ by adding a parity-check bit to the words of H. What are

the parameters of the new code ? Show that it is self-dual. Determine the weight distribution of H′. (1.G) The Hamming ball B(v, r) with center v and radius r is the collection of vectors w ∈ F_{q}^{n} with |w−v| ≤ r.

What is the cardinality of B(v, r)? A code C ⊂ F_{q}^{n} is called perfect if there is an integer r such that F_{q}^{n}is the disjoint union of the Hamming balls B(c, r) with c ∈ C. Show that the Hamming code is perfect. Are the parity-check codes or the repetition codes perfect?

(1.H) Let V = F_{2}^{23}. Calculate the cardinalities of the Hamming balls B(0, k) for 1 ≤ k ≤ 23. Show that the binary [23, 12, 7]-Golay code is perfect.

2. Coding Theory: Cyclic Codes.

In this section we will discuss the important class of cyclic codes. We will study generalized Hamming codes, BCH-codes and quadratic resisue codes.

Definition (2.1). A cyclic code is an ideal in F_{q}[X]/(X^{n} −1). The F_{q}-basis for this ring is formed by the monomials 1, X, …, X^{n−1}.

Examples. The ideal generated by X − 1 consists of the poynomials f with f(1) = 0. We see that this is the parity-check code. The other extreme, the ideal generated by (X^{n} − 1)/(X − 1) consists of the scalar multiples of the polynomial 1 + X + X^{2} + … + X^{n−1}. This is clearly the repetition code.

Cyclic codes are called cyclic because whenever f(X) is in the code, so is Xf(X). Looking at the coefficients of f, we see that this means that whenever a vector is in a cyclic code, so are all its cyclic shifts. Next we introduce binary Hamming codes. For non-binary Hamming codes see Exercise 2.A.

For f ≥ 1 let α denote a generator of the cyclic group F_{2^{f}}^{∗} and let ϕ(X) ∈ F_{2}[X] denote its minimal polynomial. The ideal generated by ϕ(X) in the ring F_{2}[X]/(X^{2^{f} −1} − 1) is called a (binary) Hamming code .

Let H be a Hamming code. Since α has order 2^{f} − 1 in the multiplicative group, there are no non-zero words of weight 2 or less in a Hamming code. We conclude that the minimal distance d is at least 3. On the other hand, the Hamming balls (see Ex.1.F) of radius 1 and center in H are disjoint, they each contain 2^{f} vectors and there are 2^{2^{f} −f} of them. By counting we see that these balls cover the vector space F_{2}[X]/(X^{2^{f} −1} − 1). We conclude that the minimal distance is actually equal to 3. The Hamming codes are [2^{f} − 1, 2^{f} − f − 1, 3]-codes. They are perfect (see Ex.1.F). One recovers the Hamming code of section 1 as the ideal generated by the polynomial X^{3} + X + 1 in F_{2}[X]/(X^{7} − 1). It is the case with f = 3. To see that the codes coincide it suffices to permute the first, second and fourth coordinates of the code of section 1. A vector (a_{1}, a_{2}, …, a_{7}) then corresponds to the polynomial a_{1}X^{6} + a_{2}X^{5} + … + a_{7}.

Next we study BCH-codes over arbitrary base fields F_{q}. BCH-codes were invented by Bose, Ray-Chaudhuri and Hocquenghem in 1959. These codes come with a designed distance t: Let n be a positive integer and let α ∈ \overline{F}_{q} have order n. The ideal I ⊂ F_{q}[X]/(X^{n} − 1) consisting of the polynomials f(X) for which f(α^{b}) = f(α^{b+1}) = … = f(α^{b+t−2}) = 0 for some b is a called a BCH-code of designed distance t.

The ideal I is, of course, generated by the lowest common multiple of the minimum polynomials of α^{b}, α^{b+1}, …, α^{b+t−2}.

Proposition (2.2). A BCH-code with designed distance t has minimal distance d ≥ t.

Proof. Suppose f(X) is a code word of weight less than t. Suppose a_{i_{1}}, a_{i_{2}}, … a_{i_{t−1}} are its only possibly non-zero-coefficients. Substituting α^{b}, α^{b+1}, …, α^{b+t−2} into f we find a system of linear equations:

( \begin{matrix}α^{i_{1}b} & … & α^{i_{t−1}b} \\ α^{i_{1}(b+1)} & … & α^{i_{t−1}(b+1)} \\ . & & . \\ . & & . \\ . & & . \\ α^{i_{1}(b+t−1)} & … & α^{i_{t−1}(b+t−1)} \end{matrix} ) ( \begin{matrix}a_{i_{1}} \\ a_{i_{2}} \\ . \\ . \\ . \\ a_{i_{t−1}} \end{matrix} ) = 0.

It is easily seen that this matrix is equal to α^{(i_{1}+i_{2}+...+i_{t−1})b} times an invertible Vandermonde matrix. This implies that the matrix is non-singular and we conclude that a_{i_{1}} = a_{i_{2}} = … = a_{i_{t−1}} = 0 and hence that f = 0 as required.

Since every f(X) ∈ F_{2}[X] for which f(α) = 0 also satisfies f(α^{2}) = 0 we see that binary BCH-codes automatically have minimum distance at least 3. Binary Hamming codes are precisely the binary BCH-codes with designed distance 3. Example (2.3). Let α ∈ F_{16}^{∗} be a generator of the multiplicative group. It has order 15. Let I be the ideal in F_{2}[X]/(X^{15} − 1) generated by the product h(X) of the minimal polynomials of α and α^{3}. This is a (binary) BCH-code. Clearly h(α) = h(α^{2}) = h(α^{3}) = h(α^{4}) = 0 and we see that its designed distance is 5. The dimension of the code I is 7 = 15 − 2 × 4. This is a [15, 7, ≥ 5]-code. Using it, one can correct upto 2 errors in each code word.

Example (2.4). Consider the polynomial X^{23} − 1 ∈ F_{2}[X]. Since 2 has order 11 modulo 23, this polynomial factors as a product of X − 1 and two irreducible polynomials of degree 11. The binary Golay code is defined to be the ideal generated by one of these 11-th degree polynomials.

Example (2.5). Quadratic residue codes. Let p be a prime and let ℓ be a prime which is a square modulo p. Let α be a primitive root mod p and let Q denote the subgroups of squares in F_{p}^{∗}

q(X) = ∏_{x∈Q}(X − α^{x}) and n(X) = ∏_{x∉Q}(X − α^{x}).

We have that and that X^{p} − 1 = (X − 1)q(X)n(X) in F_{ℓ}. The ideals in F_{l}[X]/(X^{p} − 1) generated by q(X), (X − 1)q(X), n(X) or (X − 1)n(X) are the quadratic residue codes over F_{l} of length p. The binary Hamming code and the binary Golay code are examples of quadratic residue codes. Quadratic residue codes have minimum distance at least \sqrt{p} (see Exercise 2.E).

As an illustration we show that the binary Golay code, that was used in the example mentioned in the introduction, is perfect.

Proposition (2.6). The binary Golay code is a perfect [23, 11, 7]-code.

Proof. Let G denote the binary Golay code. In the notation of Example 2.4 it is the ideal generated by q(X) in F_{2}[X]/(X^{23} − 1). There are two possibilities for q(X) depending on the choice of a primitive 23-th root of unity in \overline{F}_{2}. Since the sum of all non-trivial 23-th roots of unity is equal to 1, we see that one factor of (X^{23} − 1)/(X − 1) has a X^{10}-term, while the other has not. We will take q(X) to be the factor without this term.

Let \overline{G} denote the code obtained from G by adding a parity check bit. This code has length 24 and dimension 12. It follows easily from Exercise 2.D below that \overline{G} is self-dual. One can verify that the words (∑_{i∈(F_{23}^{∗})^{2}} X^{i}, 1) and (X^{22} + … + X + 1, 1) form a basis for \overline{G}. Since there are precisely 11 non-zero squares modulo 23, these words all have weights divisible by 4. By Exercise 1.D we conclude that every word in \overline{G} has its weight divisible by 4. Therefore it follows from Exercise 2.E that the minimum distance of \overline{G} is at least 8 and we see that G itself has minimum distance at least 7. The result now follows from Exercise 1.H.

Finally we mention the so-called Reed-Solomon codes. These are BCH-codes of length q − 1 over F_{q}. So, they are ideals generated by a polynomial of the form ∏_{i=1}^{d}(X − α^{i}) where α ∈ F_{q}^{∗} is some primitive root. They have length n − d + 1 and designed distance d. By the Singleton-bound (Prop.1.2), the minimal distance is actually equal to d. Therefore the Reed-Solomon codes are [n, n − d + 1, d]-codes. Of course one should have q > 2 in order to obtain a somewhat interesting code. Reed-Solomon codes are used in compact discs.

Exercises.

(2.A) Show that the BCH-codes of length (q^{f} − 1)/(q − 1) over F_{q} and designed distance 2 do, in fact, have

minimum distance 3 and are perfect. These codes are the so-called q-ary Hamming codes. (2.B) Show that in Example 2.3 one can take h(X) = (X^{4} + X + 1)(X^{4} + X^{3} + X^{2} + X + 1). (2.C) Let α be a zero of the polynomial that generates the binary Golay code. Express the other zeroes in

terms of α. Show that Proposition 2.2 implies that the minimum distance is at least 5. (2.D) Let C be a cyclic code with generator polynomial g i.e. C = (g) ⊂ F_{q}[X]/(X^{n} − 1). Let h(X) =

(X^{n} − 1)/g(X). Show that C^{⊥} has generator polynomial X^{deg h(X)}h(X^{−1}). (2.E) Prove that the minimum distance d of a quadratic residue code of length p over F_{l} is at least \sqrt{p}

(Consider “both” codes at once). Prove that, if p ≡ 3 (mod 4), then one even has that d^{2} − d + 1 ≥ p. Show that the binary Golay code (Example 2.4) has minimum distance at least 6.

3. Algebraic Curves.

In this section we will briefly review some of the fundamental results in the theory of algebraic curves over a field. In the next section we will apply these results to curves over finite fields and construct the Goppa codes. It is therefore important to consider curves over fields that are not necessarily algebraically closed. Although in the literature many of the basic theorems on curves are formulated over an algebraically closed field, they usually hold over perfect fields as well, see [27,Lemma II.5.8.1]. We do not pretend to give a self-contained introduction to the theory of curves. This would take us too far. Very often proofs will not be given. If the reader wishes to study the theory more thoroughly, she should study other, more extensive texts, like Hartshorne’s book [12], or older books like [5,8,20,26]. There is also a proof of the Riemann-Roch theorem in [31].

A curve X over a field k is a smooth irreducible projective algebraic variety of dimension 1. Every curve can be embedded into some projective space P^{n} over k as a closed subvariety. This means that we can describe a curve as the common zero locus of a finite collection of homogeneous polynomials. By the irreducibility of X, the ideal generated by these polynomials is a prime ideal. The function field i.e. the field of rational functions on X over k will be denoted by k(X). Note that these “functions” need not be defined everywhere. They may have poles. When k = C they are precisely the meromorphic functions on X.

We will henceforth assume that k is perfect and we fix an algebraic closure k̄ of k. For any field F with k ⊂ F ⊂ k̄ we let X(F) denote the set of points on X that are defined over F i.e. they have their coordinates in F. We have, of course that X(F) ⊂ X(k̄), the set of “all” points on X.

The degree deg(P) of a point P is the degree over k of the field of definition of P. A divisor D on X is a formal sum D = ∑_{P} n_{P} P where the sum runs over the points P ∈ X(k̄) and the n_{p} ∈ Z are almost all 0. The divisors form a free abelian group Div(X). Examples of divisors are provided by the divisors of rational functions on X: for f ∈ k̄(X) we let div(f) denote the divisor ∑_{P zero of f} P − ∑_{P pole of f} P where one should count with multiplicities.

A divisor D is said to be defined over F ⊂ k̄ if it is left fixed by the Galois group Gal(k̄/F). The divisors that are defined over a subfield F of k̄ form a subgroup Div_{F} (X) of the divisor group Div(X). It is immediate that div(f) is defined over F whenever f ∈ F (X) ⊂ k̄(X). Clearly the divisors of functions form a subgroup of Div(X): the principal divisors. The quotient group is called the Picard group of X:

Pic(X) = Div(X)/{(f): f ∈ k̄(X)}

When k is a finite field, then, for a finite extension F of k inside k̄, one has that Pic_{F} (X) = Div_{F} (X)/{(f): f ∈ F (X)} is equal to the subgroup of Gal(k̄/F)-invariants of Pic(X).

The degree of a divisor D = ∑_{P} n_{P} P is given by ∑_{P} n_{P}. The degree is a homomorphism Div(X) ⟶ Z. Its kernel is denoted by Div^{0}(X). We’ll say that D ≤ D′ for two divisors D = ∑_{P} n_{P} P and D′ = ∑_{P} m_{P} P if and only if n_{P} ≤ m_{P} for all points P. Divisors D that satisfy D ≥ 0 are called effective . To distinguish a point P from the divisor determined by it, we will sometimes write (P) for this divisor.

When k is not algebraically closed, it is sometimes convenient to modify the notion of a point somewhat: a place v of a curve X is a Galois conjugacy class of points in X(k̄). The degree deg(v) of a place v is its cardinality. The divisor (v) associated to a place v is the sum of its points. It is automatically defined over k. Every divisor D that is defined over k can be written as a sum of places. One has for D = ∑_{v} n_{v}v that deg(D) = ∑_{v} n_{v}deg(v). A place is the analog of a prime ideal in number theory. They will prove convenient in our study of ζ-functions in section 5 and in section 9.

A morphism from a curve X to another curve Y is an algebraic map f which is defined everywhere. The degree deg(f) of f is defined to be the degree of the corresponding extension k(X) ↩ k(Y). Since X is non-singular, one can extend every rational map X ⟶ P^{n} to a morphism. We will use the following Theorem from Hartshorne’s book:

Theorem (3.1). Let f: X ⟶ Y be a non-constant map of curves. Let P be a point of Y. Then f^{−1}(P) is a divisor on X and its degree satisfies deg(f^{−1}(P)) = deg(f).

Proof. This is Hartshorne’s Proposition 6.9 in Chapter II of [12].

Corollary (3.2). The degree deg(div(f)) of the divisor of a function f is 0.

Proof. We can view f as a rational function X ⟶ A^{1}. Since X is smooth, it can be extended to a morphism X ⟶ P^{1}. Now we apply Theorem 3.1 to the point P = 0 and the point P = ∞. We find that the degree of the zero-divisor of f is equal to the degree of its pole-divisor. This proves the Corollary.

In other words, the subgroup of principal divisors is contained in Div^{0}(X).We will denote the quotient by Pic^{0}(X). For finite ground fields k one can show, that for every finite extension F of k inside k̄, the group Pic_{F}^{0} (X) = Div_{F}^{0} (X)/{(f): f ∈ F (X)} is equal to the Gal(k̄/F)-invariants of Pic^{0}(X).

For every divisor D of a curve X we put

L(D) = {f ∈ k(X)^{∗}: (f) ≥ −D} ∪ {0}.

These k-vectorspaces L(D) are very important. In order to discuss their properties, it is convenient to use the adèle ring A_{K} associated to K see [20].

For every place v we let O_{v} denote the completion of any of the local rings O_{P} where P is a point “of ” v. This is a discrete valuation ring. By K_{v} we denote its quotient field. The ring of adèles A_{K} is the restricted product of the fields K_{v} with respect to the O_{v}:

A_{K} = {(x_{v})_{v} : x_{v} ∈ K_{v} and x_{v} ∈ O_{v} for almost all v}.

We let Ô denote the subring of integral adèles ∏_{v} O_{v}. One can show that the k-vector space A_{K}/(Ô+K) is finite dimensional. Its dimension g is called the genus of the curve. For any k-rational divisor D of X we let Ô(D) denote {x = (x_{v})_{v} ∈ A_{K} : v(x_{v}) ≥ −v(D) for every valuation v}. When D is the trivial divisor, then Ô(D) is just the ring Ô. The Euler characteristic χ(D) of a divisor D is defined by

χ(D) = dim_{k} L(D) + dim_{k} A_{K}/(Ô(D) + K).

Proposition (3.3). Let D be a k-rational divisor of X and let v be a k-rational place with residue class field k_{v}.

(i) There is a natural exact sequence

0 ⟶ L(D) ⟶ L(D + v) ⟶ k_{v} ⟶ A_{K}/(Ô(D) + K) ⟶ A_{K}/(Ô(D + v) + K) ⟶ 0.

(ii) χ(D + v) = χ(D) + deg v. (iii) χ(D) = deg D + 1 − g. (iv) deg D + 1 − g ≤ dim_{k} L(D) ≤ deg D + 1.

Proof. To prove (i), we observe that L(D) is contained in L(D + v). Suppose that v occurs with multiplicity m in D. Let t be a uniformizing parameter at P. We define a map L(D + v) ⟶ k_{v} as follows: Let f ∈ L(D + v). In the local ring at P we have that f = a_{−m−1}t^{−m−1} + a_{−m}t^{−m} + . . .. Now map f to its coefficient a_{−m−1} ∈ k_{v}. The next arrow is defined by sending α ∈ k_{v} to the adèle that has αt^{−m−1} at v and zero at all other places. The last arrow is the canonical one. It is straightforward to check that the sequence is exact.

Part (ii) follows immediately from (i). From (ii) we conclude that χ(D) = deg D + χ(0). Since L(0) = k and, by definition, dim_{k} A_{K}/(Ô + K) = g, it follows that χ(0) = 1 − g and (iii) follows. Since 0 ≤ dim_{k} A_{K}/(Ô(D) + K) ≤ g, part (iv) follows from (iii).

The problem of determining the dimensions of the spaces L(D) is called the Riemann-Roch problem. Note that the dimension of L(D) only depends on the divisor class of D ∈ Pic(X). We will formulate the theorem of Riemann-Roch which is an important statement about these dimensions.

For a curve X over k we define the module of rational or Kähler differentials Ω_{X} as follows: it is generated over k(X) by symbols df where f ∈ k(X) subject to the usual rules for derivations:

(i) d(f + g) = df + dg for all f, g ∈ k(X); (ii) d(fg) = fdg + gdf for all f, g ∈ k(X); (iii) da = 0 for all a ∈ k.

The module Ω_{X} is a vector space of dimension 1 over the function field k(X); see for instance [26,III.4.Thm.3]. Fix a non-zero Kähler differential ω. We are going to associate a divisor div(ω) to ω. Since the space Ω_{X} is one dimensional, for every point P of X and uniformizing parameter t at P there is a unique function g ∈ k(X) such that ω = gdt. The order of g at P depends only on ω and P and does not depend on the choice of t. Therefore we will write ord_{P} ω for it. For almost all points P it is zero. This justifies the following definition:

Definition (3.4). Let ω ∈ Ω_{X} be a Kähler differential. The divisor div(ω) associated to ω is

div(ω) = ∑_{P} ord_{P} (ω)(P).

Since Ω_{X} has dimension 1 over k(X), the divisor class κ ∈ Pic(X) does not depend on the choice of ω. This class, the canonical class , is a completely intrinsically defined invariant of the curve. The divisors it contains are called canonical divisors. The degree of any canonical divisor does not depend on the divisor either. It is another invariant of the curve. Examples. Consider X = P^{1}. If t is a coordinate on P^{1}, then, because d(\frac{1}{t}) = −t^{−2}dt, we have that div(dt) = −2(∞) and that deg(κ) = −2.

Next consider a smooth cubic curve X given by the equation y^{2} = (x−e_{1})(x−e_{2})(x−e_{3}). This curve has genus 1. Writing P_{i} for the point (e_{i}, 0), one finds that div(dx) = (P_{1})+(P_{2})+(P_{3})−3(∞). This happens to be the divisor of the function y and we conclude that div(dx/y) = 0 and that deg(κ) = 0.

Theorem (3.5). (Serre duality) Let D be a divisor of the curve X and let ω be a non-trivial k-rational Kähler differential. The natural pairing

L(κ − D) × A_{K}/(Ô(D) + K) ⟶ k

given by

(f, x) ↦ ∑_{v} Res_{P} (f · x_{v} · ω)

is non-degenerate. Here the residue Res_{P} (ω′) of a differentail ω′ at a point P of a place v is the coefficient a_{−1} of an expansion ω′ = ∑_{i} a_{i}t^{i}dt in a uniformizing parameter t at P. Proof. For a proof see [20,Ch.II]. Note that it is not even clear that the residues do not depend on the choice of the local parameters!

As a consequence we obtain that

g = dim_{k} A_{K}/(Ô + K) = dim_{k} L(κ)

and we recover the usual definition of the genus g: the number of independent “holomorphic” differentials.

Theorem (3.6). (Theorem of Riemann-Roch.) Let X be a curve of genus g over k and let D be a divisor of X defined over k. We have that

dim_{k}L(D) − dim_{k}L(κ − D) = deg(D) + 1 − g.

Proof. This follows from Prop. 3.3(iii) and Theorem 3.5.

Corollary (3.7).

(i) The degree of κ is 2g − 2. (ii) If deg(D) > 2g − 2 then dim_{k}L(D) = deg(D) + 1 − g.

Proof. (i) take D ∈ κ. (ii) If deg(D) > 2g − 2 = deg(κ), then L(κ − D) = 0 by Proposition 3.3(iv). This implies the result at once.

Next we’ll see how certain divisors give rise to morphisms from X to projective spaces. Let D be a divisor on X. By |D| we denote the complete linear system associated to D, i.e. the set of effective divisors in the same divisor class as D. The projective space P(L(D)) associated to the vectorspace L(D) is in one-to-one correspondence with the set |D| via f ↦ (f) + D. A subspace of this projective space is called a linear system. A point P is called a base point of a linear system if it is in the support of all divisors in it. If a complete linear system |D| has no base points then the morphism X ⟶ P^{d−1} given by P ↦ (f_{1}(P) : …: f_{n}(P)) is well defined. Here the f_{i} are a basis for L(D) over k. The choice of the basis does not affect the isomorphism class of the morphism. Moreover, if D is a divisor defined over a finite extension F of k inside k̄ then so is the induced map to projective space.

Proposition (3.8). Let D be a K-rational divisor on a curve X. Then :

(i) The linear system |D| has no base points if and only if dim_{k}L(D − P) = dim_{k}L(D) − 1 for every point P.

(ii) Suppose that D has no base points. The map from X to projective space induced by D is a closed immersion if and only if dim_{k}L(D − P − Q) = dim_{k}L(D) − 2 for all points P and Q.

Proof. (i) Clearly the inclusion L(D − P) ↪ L(D) is an equality if and only if P is a base point of D. This proves (i). To prove (ii) we must show that the morphism from X to projective space separates points and tangents. Well, it separates points if and only if for every two distinct points P and Q of X, the point Q is not a base point of |D − P |. By (i) this is equivalent to dim_{k}L(D − P − Q) = dim_{k}L(D) − 2. The morphism separates tangents if and only if for each point P there is a divisor D′ ∈ |D| in which P occurs with multiplicity one. This just says that P is not a base point of |D − P | which by (i) is equivalent to dim_{k}L(D − 2P) = dim_{k}L(D) − 2. This proves the proposition.

Proposition (3.9). Let D be a k-rational divisor on a curve X of genus g. We have

(i) If deg(D) ≥ 2g then |D| has no base points. (ii) If deg(D) ≥ 2g + 1 then D induces a closed immersion X ↪ P^{n}.

Proof. Using Corollary 3.7 to the Theorem of Riemann-Roch one computes the dimensions of the spaces L(D), L(D − P) and L(D − P − Q). The result then follows at once from Proposition 3.8.

We will now investigate the linear system |κ|. Recall that a curve is called hyperelliptic if it admits a morphism of degree 2 to P^{1}.

Proposition (3.10). Let X be a curve over k of genus g > 0. Then the canonical system |κ| has no base points. It induces a closed immersion X ↪ P^{g−1} if and only if X is not hyperelliptic.

Proof. Since g ≠ 0, one has for every point P that L(P) = k (Ex.3.A). By Riemann-Roch we then have that dim_{k}L(κ − P) = g − 1. The first statement now follows from Proposition 3.8. To prove the second statement we consider two points P and Q on X. By Riemann-Roch we have that

dim_{k}L(P + Q) − dim_{k}L(κ − P − Q) = 3 − g.

Therefore, by Proposition 3.8, we see that the canonical system |κ| induces a closed immersion if and only if L(P + Q) = k for all points P and Q. If X is hyperelliptic and f: X ⟶ P^{1} is a morphism of degree 2, we have L(P + Q) > k whenever P and Q make up some fiber of f. On the other hand, if L(P + Q) > k we obtain a morphism of degree 2 to P^{1}. This proves the proposition.

Exercises.

(3.A) Show that a curve X has genus 0 if and only if there is a point P on X with dim_{k}L((P)) = 2. Show that a curve over a field k of genus 0 is isomorphic to P^{1} over k if and only if it has a k-rational point. Give an example of a curve of genus 0 over R which is not isomorphic to P^{1} over R.

(3.B) Show that a curve of genus 1 can be embedded in P^{2} as a smooth cubic. Fix a point P_{0} on X. Show that every divisor class of degree 0 contains a divisor of the form P − P_{0}. Use this fact to define a group structure on the set of points X(k̄) of X.

(3.C) Show that a curve of genus 2 is hyperelliptic. (3.D) Show that a curve of genus 3 is either hyperelliptic or a smooth quartic in P^{2}. Show that a curve of

genus 4 is either hyperelliptic or is a smooth curve of degree 6 in P^{3}. (In the latter case the curve is the intersection of an irreducible smooth quadric and an irreducible cubic surface. This last statement is proved in [12,IV.Ex.5.2.2].).

4. Goppa Codes. In this section we will explain how to construct codes using linear systems on curves. The basic ideas are due to the Soviet mathematician V.D. Goppa, who explained them in two papers [9,10] in 1981. See [11,30] or Lachaud’s Bourbaki talk [15] for an exposition of this work.

Let X be a curve over a finite field F_{q}. Let D be a divisor on X defined over F_{q} and let P_{1}, …, P_{n} be a collection of points in X(F_{q}) which do not occur in the divisor D. We will contruct linear codes over F_{q}. We define a map θ from the F_{q}-vectorspace L(D) to ⊕_{i=1}^{n} F_{q} by f ↦ (f(P_{1}), …, f(P_{n})). The Goppa code Γ(D, ∑_{i}(P_{i})) associated to the curve X and the divisors D and ∑_{i}(P_{i}) will be the image of θ.

We now want to estimate the parameters of this Goppa code. Its length is clearly n. Suppose the image of f ∈ L(D) has weight d. This means that f vanishes in n−d points. So by Prop.3.3(iv) we must have that deg(D) − (n − d) ≥ 0. hence d ≥ n − deg(D). This gives a lower bound for the minimum distance of the code. We will assume that the bound is positive i.e we will assume that deg(D) < n. Prop.3.3(iv) implies then at once that the kernel of θ, which is equal to L(D−∑_{i}(P_{i})) is trivial. Therefore the dimension k of the code is just dimL(D) which is at least deg(D) − g + 1 by Prop.3.3(iv). We conclude that we have the following estimates for the parameters of the code Γ(D, ∑_{i}(P_{i})):

\begin{aligned}d & ≥ n − deg(D), \\ k & ≥ deg(D) + 1 − g. \end{aligned}

Let’s work out an easy example. Consider the cubic curve given by y^{2} + y = x^{3} + x over F_{2}. It is a smooth curve of genus 1. It has 5 points over F_{2}: (0, 0), (0, 1), (1, 0), (1, 1) and the point (∞) at infinity. Since L(∞) contains only constant functions, we take D = 2(∞); then we have L(D) = {0, 1, x, x+1} and evaluating these functions in L(D) on the remaining four rational points we obtain the following Goppa code:

\begin{matrix}(0, 0) : \\ (0, 1) : \\ (1, 0) : \\ (1, 1) : \end{matrix}  ( \begin{matrix}0 \\ 0 \\ 0 \\ 0 \end{matrix} ) ( \begin{matrix}1 \\ 1 \\ 1 \\ 1 \end{matrix} ) ( \begin{matrix}0 \\ 0 \\ 1 \\ 1 \end{matrix} ) ( \begin{matrix}1 \\ 1 \\ 0 \\ 0 \end{matrix} )

a hardly impressing [4, 2, 2]-code. Using D = 3(∞) we have that L(D) is generated over by 1, x and y. It is easily seen that with this D one obtains the parity-check code.

One finds back the binary Hamming codes as follows: Let q be a power of 2. Take X = P^{1} over F_{q} and let t be a parameter on X. With D=(∞) − (0) we have that L(D) is one dimensional, generated by t. For the rational points divisor we take the formal sum of all the other points on P^{1}(F_{q}). This gives a one-dimensional code in F_{q}^{q−1}. Its elements are F_{q}-linear multiples of (1, α, α^{2}, …, α^{q−2}) where α is a generator of the multiplicative group F_{q}^{∗}. The dual of this code can easily be identified with the ideal generated by X − α in the ring F_{q}[X]/(X^{q−1} − 1). The restriction of this code (Ex.1.C) is precisely the Hamming code.

Taking X = P^{1} over F_{q} and D = r(∞) − s(0) and the sum of all other F_{q}-rational points as the rational points divisor one finds, in a similar way, the BCH-codes of length q − 1 and designed distance r − s + 2 as the restrictions of the duals of the Goppa codes.

Many of the classical codes can be viewed as Goppa codes constructed by means of certain divisors on P^{1}. One can obtain good codes by considering curves of higher genus. We present one example due to A.M. Barg, S.L. Katsman and M.A. Tsfasman [2].

Example (4.1). The Klein curve X is a smooth curve of genus 3 given by the equation x^{3}y + y^{3}z + z^{3}x = 0. It has the three points (0 : 0 : 1), (0 : 1 : 0) and (1 : 0 : 0) over F_{2}. These are the only points with xyz = 0. We will consider X over F_{8}. Let α ∈ F_{8} be a primitive element satisfying α^{3} +α +1 = 0. Suppose (x : y : z) ∈ F_{8} with xyz ≠ 0. We put z = 1, y = α^{i} and x = α^{3i}ξ. We find that ξ^{3} + ξ + 1 = 0. So ξ = α, α^{2} or α^{4} and we find 21 points. Altogether there are 24 points in X(F_{8}). Let P = (0 : 0 : 1) and take D = 10(P). We take the sum of the remaining 23 points over F_{8} as the rational points divisor. Now we estimate the parameters of this F_{8}-code: it has length 23, dimension 10 − g + 1 = 8 and minimum distance at least 23 − deg(D) = 13.

Now we apply some tricks from coding theory to get a nice code over F_{2}. Since F_{8} has dimension 3 over F_{2}, we can view the vectors in the code as 3 × 23-matrices over F_{2}. We now extend the code by adding a fourth “parity-check”-row and obtain 4 × 23-matrices. Clearly the minimum distance of this binary code is at least 2 × 13 = 26. We have constructed a binary [92, 24, ≥ 26]-code. By leaving out one bit we find a binary [91, 24, ≥ 25]-code. This beats the best known code with n = 91 and d ≥ 25 (See [16,appendix A]).

From the inequalities above and the Singleton bound it is easily seen that the parameters of a [n, k, d]-Goppa code satisfy

1 + \frac{1 − g}{n} ≤ \frac{k}{n} + \frac{d}{n} ≤ 1 + \frac{1}{n}.

It follows that we can make good codes i.e. codes with both k/n and d/n large, when we have a curve with small g and a large number n of rational points. For this reason (and others) it is interesting to try and search for curves over finite fields that have many rational points with respect to their genus. Therefore we will in the next sections, discuss the ζ-function of a curve. We will obtain a bound on the number of rational points in terms of the genus. In the last section we will exhibit some examples of curves that have many rational points.

Exercises.

(4.A) Realize the repitition codes and parity check codes as Goppa codes on P^{1}. (4.B) Show that the curve y^{2} + y = x^{3} + x over F_{2} has genus 1 and has 25 points over F_{16} (use Prop.5.2).

Let P be one of these 25 points and let D = 13(P). We take 21 of the remaining points as the rational points divisor. Show that the corresponding Goppa code has the parameters [21, ≥ 8, ≥ 13]. Next pick an F_{2}-basis of F_{16} and add a parity-check bit to each F_{16}-coordinate. Show that the resulting binary code is a [105, ≥ 32, ≥ 26]-code. Deleting one bit gives a [104, ≥ 32, ≥ 25]-code which beats the code in [16, Appendix A].

(4.C) Let ω ∈ F_{4}^{∗} be a primitive third root of unity. Consider the curve x^{2}y + ωy^{2}z + ω̄z^{2}x = 0. Show that its genus is 1 and that it has precisely 9 rational points over F_{4}^{∗}. Let Q_{1} = (ω : 1 : 1), Q_{2} = (1 : ω : 1) and Q_{3} = (1 : 1 : ω) and let D be the divisor 2(Q_{1}) + (Q_{2}). Find a basis for L(D). (use the function x + y + ω̄z; its zero-divisor is D). For the rational points divisor we take the sum of the remaining six rational points P_{1}, …, P_{6}. Compute the F_{4}-Goppa code Γ(D, ∑_{i=1}^{6}(P_{i})). What are its parameters?

5. Curves over finite fields. In this section we will study the ζ-function ζ_{X}(s) associated to an algebraic curve X over a finite field F_{q}. We will prove that it satisfies a functional equation, similar to the one satisfied by the ordinary Riemann ζ-function. We also show that the most interesting part of the ζ-function is a polynomial in q^{−s}. The analogue of the Riemann hypothesis will be proved in the next section.

Let X be a curve over a finite field k = F_{q}. We are going to associate a meromorphic complex function to X: its ζ-function ζ_{X}(s). It will be similar to the well-known Riemann ζ-function

ζ(s) = ∑_{n=1}^{∞} \frac{1}{n^{s}} = ∏_{p prime}(1 − \frac{1}{p^{s}})^{−1}.

The sum and the product converge for s ∈ C, Re s ≥ 1. It is well-known and easy to prove that ζ(s) admits a meromorphic extension to all of C. It has only one pole. It is of order 1 at s = 1. The analogue of a prime number, or rather of the prime ideal in Z generated by it, is a place i.e. a Galois conjugacy class of points on X. Every k-rational divisor can be written as a sum of places in a unique way. The analogue of an ideal nZ ⊂ Z is an effective divisor of X which is defined over k. Therefore we put for s ∈ C, Re s ≥ 1:

ζ_{X}(s) = ∑_{D≥0} \frac{1}{ND^{s}} = ∏_{v}(1 − \frac{1}{Nv^{s}})^{−1}.

Here the product runs over the places v of X. The norm Nv of a place v is defined to be the cardinality of the field of definition of a point P in v, in other words Nv = q^{deg(v)}. Similarly we put ND = q^{deg(D)}.

We will prove certain properties of the function ζ_{X}(s). They are similar to properties enjoyed by the Riemann ζ-function. Before stating the main result, we will first, as an example, calculate the ζ-function associated to P^{1} over F_{q}. Let a_{d} denote the number of places on P^{1} of degree d. So, a_{1} = q + 1 and for d > 1 one simply has that a_{d} is equal to the number of irreducible polynomials of degree d over F_{q}. Obviously we have that ∑_{d|m} da_{d} = #P^{1}(F_{q^{m}}) = q^{m} + 1.

The ζ-function of P^{1} is given by

ζ_{P^{1}}(s) = ∏_{d≥1}(1 − q^{−sd})^{−a_{d}}.

Therefore we consider the power series ∏_{d≥1}(1 − T^{d})^{−a_{d}}. It is straightforward to verify that

log(∏_{d≥1}(1 − T^{d})^{−a_{d}}) = ∑_{m≥1} \frac{1}{m} ∑_{d|m} da_{d}T^{m} = ∑_{m≥1} \frac{q^{m} + 1}{m}T^{m}

and this easily implies that

ζ_{P^{1}}(s) = \frac{1}{(1 − q^{−s})(1 − q^{1−s})}.

We see that this ζ-function is periodic modulo 2πi/log q. Modulo the period it has only poles at s = 0 and s = 1. It satisfies ζ(1 − s) = q^{1−s}ζ(s).

For arbitrary curves X we have the expansion

ζ_{X}(s) = ∑_{n=0}^{∞} #{D ∈ Div(X): D is effective and deg(D) = n} · q^{−ns}

and therefore we put

Z_{X}(T) = ∑_{n=0}^{∞} #{D ∈ Div(X): D is effective and deg(D) = n} · T^{n} ∈ Z[[T]].

We have the following general result:

Theorem (5.1). Let X be a curve of genus g over F_{q}. Then

(i) Z_{X}(T) satisfies the functional equation:

Z_{X}(\frac{1}{qT} ) = q^{1−g}T^{2−2g}Z_{X}(T).

(ii) On has that

Z_{X}(T) = \frac{P_{X}(T)}{(1 − T)(1 − qT)}.

where P_{X}(T) ∈ Z[T] is a polynomial of degree 2g.

Proof. Let δ denote the gcd of the degrees of all divisors in Div_{k}(X) or, equivalently, of all effective divisors of X. We have that δ divides 2g − 2 = deg(κ). We write Pic^{n}(X) for the set of divisor classes of degree n and we let

Z_{X}(T) = ∑_{n=0}^{∞} #{D ∈ Div(X): D is effective and deg(D) = n} · T^{n} = ∑_{n=0}^{∞} b_{n}T^{n}.

Clearly

b_{n} = ∑_{D∈Pic^{n}(X)} \frac{q^{dimL(D)} − 1}{q − 1}.

Now either Pic^{n}(X) is empty or it is in one-to-one correspondence to Pic^{0}(X) via D ↦ D − D_{0} for some fixed D_{0} ∈ Pic^{n}(X). Since there are effective divisors D with L(D) > 0 it follows from the above formula for b_{n} that every Pic^{n}(X) is finite. We put

h = #Pic^{0}(X).

By Cor. 3.7 to the Riemann-Roch theorem we have for divisors D with deg(D) = n > 2g − 2 that dim_{F_{q}}L(D) = n + 1 − g. It follows that for n a multiple of δ we have that

b_{n} = h\frac{q^{n+1−g} − 1}{q − 1}.

So

Z_{X}(T) = ∑_{n=0}^{2g−2} b_{n}T^{n} + ∑_{n>(2g−2)/δ} h\frac{q^{nδ+1−g} − 1}{q − 1}T^{δn}.

It is easy to sum the geometric series. One finds

Z_{X}(T) = ∑_{n=0}^{2g−2} b_{n}T^{n} + (\frac{q^{g−1+δ}T^{2g−2+δ}}{1 − (qT)^{δ}} − \frac{T^{2g−2+δ}}{1 − T^{δ}})\frac{h}{q − 1}.

So, Z_{X}(T) is a rational function. It has poles of order 1 at T^{δ} = 1 and at T^{δ} = q^{−δ}. Using the product expansion of the ζ-function it is very easy to show that for every positive integer m one has the relation

Z_{X/F_{q^{m}}} (T^{m}) = ∏_{ζ^{m}=1} Z_{X/F_{q}}(ζT)

where the product runs over all m-th roots of unity ζ. We apply this with m = δ. Since Z_{X}(T) = ∑_{n} b_{nδ}T^{nδ} we have that Z_{X}(T) = Z_{X}(ζT) and hence Z_{X/F_{q^{δ}}} (T^{δ}) = Z_{X/F_{q}}(T)^{δ}. Since Z_{X/F_{q^{δ}}} has only poles of order 1, we conclude that δ = 1. We now have

Z_{X}(T) = ∑_{{D∈Pic(X) \atop 0≤deg(D)≤2g−2}} \frac{q^{dimL(D)} − 1}{q − 1}T^{deg(D)} − \frac{h}{q − 1}(\frac{T^{2g−1}}{1 − T} − \frac{q^{g}T^{2g−1}}{1 − qT} ) = \frac{1}{q − 1}( ∑_{n=0}^{2g−2} T^{n} ∑_{deg(D)=n} q^{dimL(D)} + h(q^{1−g} \frac{(qT)^{2g−1}}{1 − qT} − \frac{1}{1 − T} )) .

The functional equation in (i) now follows at once from the theorem of Riemann-Roch. Part (ii) is obvious from the explicit expression for Z_{X}(T) above. This proves the theorem.

To a curve of genus g over F_{q} we now associate 2g complex numbers ϕ_{i}: the reciprocal zeroes of the polynomial P_{X}(T): we have that P_{X}(T) = ∏_{i=1}^{2g}(1 − ϕ_{i}T). It follows easily from the above theorem that we can order the ϕ_{i} in such a way that ϕ_{g+i} = q/ϕ_{i} for 1 ≤ i ≤ g.

Proposition (5.2). Let X be a curve of genus g over F_{q}. Let the ϕ_{i} ∈ C be as introduced above. We have for every positive integer m that

P_{X/F_{q^{m}}} (T) = ∏_{i=1}^{2g}(1 − ϕ_{i}^{m}T)

and

#X(F_{q^{m}}) = q^{m} + 1 − ∑_{i=1}^{2g} ϕ_{i}^{m}.

Proof. The first formula follows at once from the relation

Z_{X/F_{q^{m}}} (T^{m}) = ∏_{ζ^{m}=1} Z_{X/F_{q}}(ζT)

where the product runs over all m-th roots of unity. We apply this with m = δ that we used in the proof above. The second formula follows by inspection of the linear coefficient of Z_{X}(T) and the theorem above. This proves the proposition.

Exercises.

(5.A) Prove that h = #Pic^{0}(X) = ∏_{i=1}^{2g}(1 − ϕ_{i}) = P_{X}(1). (5.B) Compute the number of points on the curve x^{3} + y^{3} + z^{3} = 0 over every finite extension of F_{2}. (5.C) Compute the ζ-function of the Klein curve x^{3}y +y^{3}z +z^{3}x = 0 over F_{2}. (Use the example in section 4) (5.D) Compute the ζ-function of the hyperelliptic curve given by y^{2} + y = x^{5} + 1 over F_{2}.

6. Weil’s Theorem. We will prove the analogue of the Riemann hypothesis for ζ-functions associated to curves over finite fields. This was first proved by André Weil [35], who published his proof in 1948. This result and the program started by Weil to generalize it, has had a profound influence on the development of algebraic geometry in the second half of this century. It stimulated Grothendieck to develop his powerful theory of schemes. Using these techniques, a generalization of Weil’s Theorem was proved in 1973 by Deligne. The classical Riemann hypothesis remains unproven, however.

Let X be a curve over F_{q} of genus g. Let p denote the characteristic of F_{q}. Let ϕ_{i} for i = 1, 2, …, 2g denote the reciprocal zeroes of the polynomial Z_{X}(T) introduced in Theorem 5.1. Our proof follows Bombieri’s exposé [3] of Stepanov’s proof. The idea is to construct a rational function f on X that vanishes to high order m at the F_{q}-rational points of X except possibly one but whose number of poles can be bounded. By Cor. 3.2 we will then have that

m(#X(F_{q}) − 1) ≤ #{ zeroes of f } = #{ poles of f }

which implies a bound on #X(F_{q}). Using the functional equation we can then prove that |ϕ_{i}| = \sqrt{q} which is easily seen to be equivalent to the analogue of the Riemann hypothesis.

We let π: X ⟶ X denote the Frobenius morphism which for the function fields is just the inclusion k(X) ↩ k(X)^{q} ≅ k(X). The Frobenius morphism acts on the points X(k̄) in a natural way: it “raises the coordinates of the points to the q-th power”. By Galois theory, the fixed points of π^{m} make up the subset X(F_{q^{m}}).

Proposition (6.1). If q is a square and q > (g + 1)^{4} then we have that

#X(F_{q}) < q + 1 + (2g + 1)\sqrt{q}.

Proof. We may assume that there is a point P in X(F_{q}). Otherwise the proposition is obvious. We will study the spaces L(m(P)) for X over k̄. For a positive integer μ we let L(k(P))^{p^{μ}} denote the space of functions f^{p^{μ}} where f ∈ L(m(P)). By L(k(P))^{π} we denote the space of functions f · π = f(X^{q}) where f ∈ L(m(P)). We first prove a lemma.

Lemma (6.2). Let n and m be two positive integers and let μ be a positive integer with np^{μ} < q. The natural homomorphism

L(n(P))^{p^{μ}} ⊗k̄ L(m(P))^{π} ⟶ L(n(P))^{p^{μ}}L(m(P))^{π}

is an isomorphism.

Proof. By Prop.3.3(ii) we have that dimk̄L((ν + 1)(P)) ≤ dimk̄L(ν(P)) + 1 and we conclude that there is a k̄-basis e_{1}, e_{2}, …, e_{r} of L(m(P)) such that ord_{P} (e_{1}) < ord_{P} (e_{2}) < … < ord_{P} (e_{r}). The homomorphism in the statement of the lemma is clearly surjective. We must show it is injective i.e. we must show that whenever ∑_{i=1}^{r} g_{i}^{p^{μ}}(e_{i} · π) = 0 for certain g_{i} ∈ L(n(P)) then all the g_{i} are 0 themselves. So assume that i_{0} is the smallest integer in {1, 2, …, r} for which g_{i_{0}} ≠ 0. We have

ord_{P} (g_{i_{0}}^{p^{μ}}(e_{i} · π) = ord_{P} (− ∑_{i>i_{0}}^{r} g_{i}^{p^{μ}}(e_{i} · π))

≥ min_{i>i_{0}} ord(g_{i}^{p^{μ}}(e_{i} · π))

≥ −np^{μ} + q ord_{P} (e_{i_{0}+1})

Therefore

p^{μ}ord_{P} (g_{i_{0}}) ≥ −np^{μ} + q(ord_{P} (e_{i_{0}+1}) − ord_{P} (e_{i_{0}}))
≥ −np^{μ} + q > 0

and we see that g_{i_{0}} vanishes at P. But g_{i_{0}} being an element of L(n(P)) has no poles outside P. Therefore it must be constant and hence 0. This proves the Lemma.

Since dimk̄L(n(P))^{p^{μ}} = dimk̄L(n(P)) and dimk̄L(m(P))^{π} = dimk̄L(m(P)) we obtain, as a consequence, that

dimk̄L(n(P))^{p^{μ}}L(m(P))^{π} = dimk̄L(n(P)) × dimk̄L(m(P)).

We have a natural well-defined homomorphism L(n(P))^{p^{μ}}L(m(P))^{π} → L(n(P))^{p^{μ}} ⊗ L(m(P))^{π} → L(n(P))^{p^{μ}} ⊗L(m(P)) → L(n(P))^{p^{μ}}L(m(P)) mapping f = ∑_{i} g_{i}^{p^{μ}}(e_{i}·π) to ∑_{i} g_{i}(e_{i}·π) because the first arrow is the inverse of the isomorphism of the lemma, while the second arrow is the inverse of an obvious isomorphism. Since L(n(P))^{p^{μ}}L(m(P)) ⊂ L((np^{μ} +m)(P)) we obtain a homomorphism

θ : L(n(P))^{p^{μ}}L(m(P))^{π} ⟶ L((np^{μ} + m)(P)).

By Prop 3.3(iv) we have that dim L(n(P)) ≥ n + 1 − g and dim L(m(P)) ≥ m + 1 − g. If n and m are at least g, we have by Cor.3.7(ii) to the Riemann-Roch theorem that dim L((np^{μ} + m)(P)) = np^{μ} + m + 1 − g. Therefore we find that, whenever m, n ≥ g,

dim kerk̄(θ) ≥ dimk̄L(n(P)) × dimk̄L(m(P)) − dimk̄L((np^{μ} + m)(P))
≥ (n + 1 − g)(m + 1 − g) − (np^{μ} + m + 1 − g).

Suppose that f = ∑_{i} g_{i}^{p^{μ}}(e_{i} · π) is a function in ker(θ) and Q ∈ X(F_{q}) is a point not equal to P. We have that

f(Q) = ∑_{i} g_{i}^{p^{μ}}(Q)(e_{i} · π)(Q) = ∑_{i} g_{i}^{p^{μ}}(Q)(e_{i})(Q) = (θf)(Q) = 0.

We conclude that f vanishes at every point of X(F_{q}) except P. But, since f is a p^{μ}-th power, f has zeroes of order at least p^{μ} at these points. Therefore any f in ker(θ) has at least p^{μ}(#X(F_{q}) − 1) zeroes. Since

f ∈ L(n(P))^{p^{μ}}L(m(P))^{π} ⊂ L((np^{μ} + mq)(P))

such a function f has, on the other hand, at most np^{μ} + mq poles. We conclude that if the assumptions np^{μ} < q and n, m ≥ g are fulfilled and if ker θ > 0 i.e. if

(n + 1 − g)(m + 1 − g) > (np^{μ} + m + 1 − g)

then one has that

#X(F_{q}) ≤ n + \frac{mq}{p^{μ}} + 1.

We will choose the parameters p^{μ}, n and m as follows: p^{μ} = \sqrt{q}, m = \sqrt{q} + 2g and n = [\frac{g}{g+1} \sqrt{q}] + g + 1. Since q > (g + 1)^{4}, it is readily verified that with these choices, the assumptions are fulfilled. This proves the Proposition.

Theorem (6.3). Let X be a curve of genus g over a finite field F_{q}. Assume that q is a square and that q > (g + 1)^{4}. Then for k large enough

#X(F_{q^{k}}) = q^{k} + O(q^{k/2})

where the O-symbol depends only on X over \overline{F}_{q}.

Proof. Use any non-zero function in F_{q}(X) to construct a morphism X ⟶ P^{1}. The corresponding extension of function fields F_{q}(X) ↩ F_{q}(P^{1}) is not necessarily Galois. Let L denote the Galois closure of this extension. The field L is the function field of a smooth irreducible curve Y of genus g_{Y} over F_{q}. Let G denote Gal(L/F_{q}(P^{1})) and let H denote the subgroup Gal(L/F_{q}(X)).

Let A denote the set of unramified points P ∈ Y (F̄_{q}) whose image in P^{1} is rational over F_{q^{k}}. Since P^{1} has q^{k} + 1 rational points over F_{q^{k}}, it is immediate that

#A = #G(q^{k} + 1)#G + O(1)

where the O-symbol is due to the finitely many ramification points of the covering Y of P^{1}. It is independent of the degree k.

For every unramified point P ∈ A the point π(P) maps to the same point in P^{1} as P does. Therefore there is a unique σ ∈ G such that π(P) = σ(P). The automorphism σ is called the Frobenius substitution of P. For every σ ∈ G put

A_{σ} = {P ∈ A: π(P) = σ(P)}.

The set A is a disjoint union of the A_{σ}’s. Since q^{k} > g_{Y} for k large enough, we can argue as in the proof of Proposition 6.2, but now with P ∈ A_{σ}. We now have tha map

θ_{σ}: L(n(σ^{−1}P))^{p^{μ}}L(m(P))^{π} → L(n(σ^{−1}P))^{p^{μ}}L(m(P))^{σ} → L((np^{μ} + m)(σ^{−1}P)).

We obtain easily that

#A_{σ} ≤ q^{k} + 1 + (2g_{Y} + 1)q^{k/2}

and hence

#A = ∑_{σ∈G} #A_{σ} = (q^{k} + 1)#G + O(q^{k/2}).

Combining this with the formula for #A that we deduced above, we find that for each σ ∈ G

#A_{σ} = q^{k} + O(q^{k/2}).

By Galois theory we have that

⋃_{σ∈H} A_{σ} = {P ∈ Y: the image of P in X is rational over F_{q^{k}}}

Therefore

\begin{aligned}∑_{σ∈H} #A_{σ} & = #H#X(F_{q}) + O(1) \\ & = #Hq^{k} + O(q^{k/2}) \end{aligned}

and the result follows at once.

Theorem (6.4). (A. Weil, 1948) Let X be a curve of genus g over a finite field F_{q}. Then the reciprocal roots ϕ ∈ C of the function Z_{X}(T) satisfy

|ϕ| = \sqrt{q}.

Proof. By Proposition 5.2, it suffices to give the proof for a power of q. We will call this power q again and choose it so large that the condition of Proposition 6.1 is satisfied: q is a square exceeding (g + 1)^{4}. We deduce from these propositions that for large enough k we have that

#X(F_{q^{k}}) = q^{k} + 1 + O(q^{k/2}).

and therefore, with the usual notation, that

∑_{j=1}^{2g} ϕ_{j}^{k} = O(q^{k/2}).

This implies that the function f(z) = ∑_{i=1}^{2g}(1 − ϕ_{i}z)^{−1} has a radius of convergence at least as large as q^{−1/2}. Therefore we have that |ϕ_{i}| ≤ \sqrt{q} for 1 ≤ i ≤ 2g. The theorem now follows from the functional equation (Theorem 5.1(ii)) satisfied by Z_{X}(T): when ϕ is a reciprocal root, so is q/ϕ and it follows that |ϕ| = \sqrt{q} for all ϕ as required.

Corollary (6.5). Let X be a curve of genus g over F_{q}. Then

|q^{m} + 1 − #X(F_{q^{m}})| ≤ 2gq^{m/2}.

Proof. This is immediate from Proposition 5.2 and Theorem 6.4.

Exercises.

(6.A) Show that a curve of genus 0 over a finite field is isomorphic to P^{1}. (6.B) Show that a curve of genus 1 over a finite field always has a point rational over that field. (6.C) Prove the Riemann Hypothesis for the ζ-function ζ_{X}(s) of a curve X over a finite field: If ζ_{X}(s) = 0

then the real part of s is 1/2. (6.D) Let X be the projective curve given by y^{2} +xy = x^{3} +x over F_{2}. Show that its genus is 1 and compute

the zeroes of the ζ-function ζ_{X}(s). (6.E) Let p be a prime and let χ: F_{p}^{∗} → {±1} be the quadratic character mod p: χ(x) = 1 whenever x is a

square in F_{p}^{∗} and χ(x) = −1 otherwise. By convention we put χ(0) = 0. Show that for every A, B ∈ Z one has that | ∑_{x∈F_{p}} χ(x^{3} + Ax + B)| < 2\sqrt{p}.

(6.F) Let F_{q} be a finite extension of degree m of F_{2} and let Tr: F_{q} → F_{2} denote the Trace map: α ↦

α + α^{2} + … + α^{2^{m−1}}. Show that for every α, β ∈ F_{q} one has that ∑_{x∈F_{q}} |(−1)^{Tr(x^{3}+αx+β)}| < 2\sqrt{q}. (6.G) Using the same notation as in Exercise 6.F, let f(X) ∈ F_{q}[X] have odd degree r. Then one has that

∑_{x∈F_{q}} |(−1)^{Tr(f(x))}| < (r − 1)\sqrt{q} (6.H) Using the same notation as in Exercise 6.F, consider the map θ: F_{q} × F_{q} ⟶ V defined by θ(α, β) =

(Tr(αx + βx^{−1})_{x∈F_{q}}. Here V is the F_{2}-vectorspace with basis indexed by the elements of F_{q}. Show that θ is injective. View the image of θ as a code in V. Estimate its parameters (cf. [18]).

7. The Theorem of Drinfeld and Vlădut.

Since asymptotically good Goppa-codes can be constructed using families of curves over finite fields that have many points with respect to their genus, it was natural to try and find such curves (cf. [17]). It was soon found, rather surprisingly, that the bounds on the number of points that follow from Weil’s theorem are not sharp when the genus is very large. In this section we will prove the asymptotic estimate by Drinfeld and Vlădut [7] and mention an unpublished theorem due to Oesterlé [22] that is somewhat more precise.

Let X be a curve of genus g over F_{q}. We will be interested in the ratio #X(F_{q})/g. Curves for which this ratio is large can be used to construct good codes. First we will look a little bit at curves with small genus and then we will study the behaviour of this ratio as the finite field F_{q} is fixed and the genus tends to infinity. We will only consider the case F_{2}. It is the most interesting case for coding theory and the easiest field when one wishes to do computations.

By Exercise 6.A the only curve, upto isomorphism, of genus 0 is P^{1}. It has 3 points and the bound #X(F_{q}) ≤ q + 1 + 2g\sqrt{q} of Weil is sharp. The curve y^{2} + y = x^{3} + x is a curve of genus 1. It has been used in section 4 to construct a simple Goppa code. It has 5 points rational over F_{2}. This is best possible since the Weil-bound is 3 + 2\sqrt{2} here. Since all curves of genus 2 are hyperelliptic (Ex.3.C) they can have at most 6 points over F_{2}. This is best possible as the example y^{2} + y = (x^{2} + x)/(x^{3} + x + 1) shows. The Weil bound is not sharp; it is only 3 + 4\sqrt{2} ≈ 8.65 here. For curves of genus 3 the Weil bound is approximately 11.48. However, by Exercise 3.D a curve of genus 3 is either hyperelliptic or isomorphic to a smooth quartic curve in P^{2}. Over F_{2} the projective plane has only 7 points! So curves of genus 3 cannot have more than 7 points. This is the best possible bound: the curve

x^{3}y + y^{3}z + z^{3}x + x^{2}y^{2} + x^{2}z^{2} + y^{2}z^{2} + x^{2}yz + xy^{2}z = 0

passes through all seven rational points of P^{2}.

According to the remark in Ex.3.E a curve of genus 4 is either hyperelliptic or can be realized as the intersection of a smooth irreducible quadric and an irreducible cubic surface in P^{3}. One can show that quadrics in P^{2} can have at most 9 points over F_{2}. This is not sharp as we will see later, but it is a lot better than the Weil bound which is approximately 14.31 for curves of genus 4. The curve with affine equation

x^{2}y^{3} + x^{3}y^{2} + xy^{3} + x^{3}y + x^{2}y^{2} + x^{2} + y^{2} + 1 = 0

in P^{1} ×P^{1} passes through every point except (0, 0). This is best possible. It follows from Oesterlé’s theorem below that a curve of genus 4 over F_{2} can have at most 8 rational points.

So we see that the bounds that follow from the Riemann hypothesis are by no means sharp when the genus becomes somewhat large. Next we’ll investigate what happens when the genus becomes very large. Put

A(q) = limsup_{g→∞} \frac{#X(F_{q})}{g}.

It follows from Weil’s Theorem that

A(q) ≤ 2\sqrt{q}.

It is rather easy to improve this somewhat.

First we discuss an improvement due to Serre [24].

Theorem (7.1). For every curve X of genus g over F_{q} one has that

#X(F_{q}) ≤ q + 1 + [2\sqrt{q}]g.

Proof. We have that #X(F_{q}) = q + 1 − ∑_{i=1}^{g}(ϕ_{i} + ϕ̄_{i}) where |ϕ_{i}| = \sqrt{q} for 1 ≤ i ≤ g. Put

x_{i} = [2\sqrt{q}] + 1 + ϕ_{i} + ϕ̄_{i} for 1 ≤ i ≤ g.

By Theorem 6.4 the numbers x_{i} are totally positive algebraic integers. Therefore their product is at least 1. It follows from the arithmetic-geometric-mean inequality that

\frac{1}{g} ∑_{i=1}^{g} x_{i} ≥ (∏_{i=1}^{g} x_{i})^{1/g} ≥ 1.

So we have that ∑_{i} x_{i} ≥ g which is easily seen to imply the result.

An immediate corollary is that

A(q) ≤ [2\sqrt{q}].

A second improvement is due to Ihara [13]: Consider X also over F_{q^{2}}. We have that

#X(F_{q}) ≤ #X(F_{q^{2}}) = q^{2} + 1 − ∑_{i=1}^{g}(ϕ_{i}^{2} + ϕ̄_{i}^{2})

= q^{2} + 1 + 2qg − ∑_{i=1}^{g} t_{i}^{2}

≤ q^{2} + 1 + 2qg − \frac{1}{g}(∑_{i=1}^{g} t_{i})^{2}

where t_{i} = ϕ_{i} + ϕ̄_{i}. The last inequality is the inequality of Cauchy-Schwartz. We conclude that

#X(F_{q}) ≤ q^{2} + 1 + 2qg − \frac{1}{g}(#X(F_{q}) − q − 1)^{2}

which easily implies that

A(q) ≤ \sqrt{2q} − \frac{1}{2}.

Now we come to the best known estimate due to Drinfeld and Vlădut [7]. The proof is an extension of Ihara’s argument. It involves a consideration of all finite extensions of F_{q}. We will write a_{d} for the number of places of X of degree d. Equivalently, a_{d} is the number of points in X(\overline{F}_{q}) of degree d upto Galois conjugacy. So, we have that #X(F_{q^{m}}) = ∑_{d|m} da_{d}.

Let Ψ(T) = ∑_{n=1}^{∞} c_{n}T^{n} be a polynomial with non-negative coefficients c_{n} for which

Ψ(t) + Ψ(t̄) + 1 ≥ 0 for all t ∈ C with |t| = 1.

By Ψ_{d}(T) we denote the polynomial ∑_{n≡0 (mod d)} c_{n}T^{n}.

Theorem (7.2). Let X be a curve over F_{q} of genus g and let Ψ(T) be a polynomial as above. We have

∑_{d≥1} da_{d}Ψ_{d}(q^{−1/2}) ≤ g + Ψ(q^{1/2}) + Ψ(q^{−1/2}).

Proof. As usual, let ϕ_{j} denote the reciprocal zeroes of the function Z_{X}(T). By the Riemann hypothesis we have that ϕ_{j} = \sqrt{q}e^{iθ_{j}} with θ_{j} ∈ R. By Theorem 5.1(i) We can order the ϕ_{j} in such a way that θ_{g+j} = −θ_{j}. We have that

#X(F_{q^{n}}) = q^{n} + 1 − q^{n/2} ∑_{j=1}^{g}(e^{inθ_{j}} + e^{−inθ_{j}}).

So

0 ≤ ∑_{j=1}^{g}(Ψ(e^{inθ_{j}}) + Ψ(e^{−inθ_{j}}) + 1) = g + ∑_{j,n} c_{n}(e^{inθ_{j}} + e^{−inθ_{j}})

= g + ∑_{n≥1} q^{−n/2}c_{n}(q^{n} + 1 − #X(F_{q^{n}}))

= g + Ψ(q^{1/2}) + Ψ(q^{−1/2}) − ∑_{d≥1} ∑_{d|n} q^{−n/2}da_{d}c_{n}

and the inequality follows.

The theorem clearly implies that

(#X(F_{q}) − 1)Ψ(q^{−1/2}) ≤ g + Ψ(q^{1/2})

and therefore that

A(q) ≤ \frac{1}{Ψ(q^{−1/2})}.

We must choose our polynomial Ψ(T) = ∑_{n=1}^{∞} c_{n}T^{n} in order to get an estimate for A(q). The larger we can take the c_{n}, the better the estimate will be. However, we have that

0 ≤ \frac{1}{π} ∫_{0}^{2π}(1 + Ψ(e^{iθ}) + Ψ(−e^{iθ}))(1 − cosnθ)dθ = 1 − c_{n}

So c_{n} ≤ 1 and we cannot choose all c_{n} = 1 since they should be zero for large n. We will, instead, choose a sequence of polynomials Ψ whose coefficients approach 1 viz:

1 + Ψ(T) + Ψ(T^{−1}) = \frac{1}{N + 1}(1 + T + … + T^{N})(1 + T^{−1} + … + T^{−N})

It is easy to see that this gives a sequence of bounds on A(q), the limit of which is

A(q) ≤ \sqrt{q} − 1.

One can show that this estimate is sharp when q is a square [13,29]. The curves that meet the bound are Shimura curves. In the case q = p^{2} the Shimura curves are the modular curves X_{0}(ℓ) and the proof then briefly runs as follows:

For every supersingular j-invariant j in characteristic p, there exists over F_{p^{2}} an elliptic curve with j-invariant j whose Frobenius endomorphism can be identified with an integer. Therefore all the finite cyclic subgroups of its points are defined over F_{p^{2}}. Consider the modular curves X_{0}(ℓ) for prime ℓ ≡ 11 (mod 12) over the field F_{p^{2}}. The curve X_{0}(ℓ) parametrizes elliptic curves together with an isogeny of degree ℓ. The genus of this curves is (ℓ + 1)/12 and its degree over the j-line is (p − 1)/2 and by the above, all the points lying over the supersingular j-invariants are rational over F_{p^{2}}. Since there are roughly p/12 supersingular j-invariants in characteristic p, which are all in the field F_{p^{2}}, there are, upto a slight error due to the cusps and the j-values 0 and 1728, at least (ℓ + 1) × (p − 1)/12 rational points on X_{0}(ℓ). We see that the ratio of the number of point on X_{0}(ℓ) to its genus is approximately p − 1. It is not so difficult to check that it actually approaches p − 1 as ℓ tends to infinity.

For finite fields F_{q} for which q is not a square, much less is known. Th. Zink [37] has shown that for prime p, one has that A(p^{3}) ≥ 2(p^{2} − 1)/(p + 2). Serre [24], using an infinite class field tower of the function field of a hyperelliptic curve over F_{q} showed that there exists a positive constant c ∈ R such that A(q) > c log q. For q = 2 one can show that 2/9 ≤ A(2) ≤ \sqrt{2} − 1, so 0.222 < A(2) < 0.415. These results are proved in section 9.

It is possible to do the above estimates in such a way that one obtains information for “ finite” values of g as well. This was done by Oesterlé in 1982. We state his result without proof.

Theorem (7.3). Let X be a curve of genus g over F_{q} with L + 1 points rational over F_{q}. Then

g ≥ sup_{Ψ}\{LΨ(q^{−1/2}) − Ψ(q^{1/2})\} ≥ \frac{(L − 1)\sqrt{q}cosθ_{0} + q − L}{q + 1 − 2\sqrt{q}cosθ_{0}}

Moreover, if q ≥ 3 the second inequality is actually an equality. Here the supremum is taken over the polynomials Ψ(T) with non-negative coefficients satisfying Ψ(t)+Ψ(t̄)+1 ≥ 0 for t ∈ C, |t| = 1. The value of θ_{0} is defined as follows: Let m be the unique integer for which \sqrt{q}^{m} < L ≤ \sqrt{q}^{m+1}. Put

u = \frac{\sqrt{q}^{m+1} − L}{Ł\sqrt{q} − \sqrt{q}^{m}} ∈ [0, 1)

and let θ_{0} denote the unique solution θ = θ_{0} of the equation cos\frac{m+1}{2}θ + ucos\frac{m−1}{2}θ = 0 in the interval [\frac{π}{m+1}, \frac{π}{m}).

See Table 8.8 for the bounds one obtains from Theorem 7.3 for small values of g in the case q = 2.

Exercises.

(7.A) We use the notation of Theorem 7.2. Show that the choice c_{1} = 1/2 and c_{n} = 0 for n > 1 leads to the

Weil bound: #X(F_{q}) ≤ q + 1 + 2g\sqrt{q}. (7.B) Verify the bounds given in table 8.8. (7.C) Show that the inequality in Theorem 7.3 is equivalent to

\frac{g − 1}{L + 1} ≥ Re( \frac{1}{\sqrt{q}e^{iθ_{0}} − 1} ).

Deduce that A(q) ≤ \sqrt{q} − 1.

(7.D) (cf. [24]) Let q = 2. We will choose Ψ such that 1 + Ψ(t) + Ψ(t^{−1}) = c^{−1}(1 + d_{1}(t + t^{−1}) + … + d_{m}(t^{m} + t^{−m}))^{2} with d_{i} ≥ 0 and c = 1 + 2d_{1}^{2} + … + 2d_{m}^{2}. Show that Theorem 7.1 with m = 3 and the choice d_{1} = 1, d_{2} = 0.7 and d_{3} = 0.2 gives rise to the bound #X(F_{2}) ≤ 0.826g + 5.346. Compute which bounds it gives for 2 ≤ g ≤ 12. Compute the bound one gets with m = 5 and the choice d_{1} = 1, d_{2} = 0.8, d_{3} = 0.6, d_{4} = 0.4 and d_{5} = 0.1.

8. Class Field Theory. Following J.-P. Serre, we use class field theory over function fields [20] to construct curves that have many points with respect to their genus. Examples of rather high genus that meet the bounds of Oesterlé are presented. Most of the results in this section are due to Serre who lectured on this in October 1982 at the Collège de France [22,23,24,25]. For the cohomology theory of groups that we will use see [4,21] and see [1,14] for a cohomological approach to class field theory of number fields as well as function fields.

Let X be a curve over a finite field F_{q}. Recall that we only consider projective, absolutely irreducible non-singular curves. Let K = F_{q}(X) denote the function field of X. A place of X or K is a Gal(\overline{F}_{q}/F_{q})-conjugacy class of points in X(\overline{F}_{q}). For every place v we let O_{v} denote the completion of any of the local rings O_{P} where P is a point “of” v. This is a discrete valuation ring. By K_{v} we denote its quotient field.

The ring of adèles A_{K} is the restricted product of the fields K_{v} with respect to the O_{v}:

A_{K} = {(x_{v})_{v}: x_{v} ∈ K_{v} and x_{v} ∈ O_{v} for almost all v}.

The unit group A_{K}^{∗} is called the group of idèles of K. It contains K^{∗} as a subgroup. The quotient group C_{K} = A_{K}^{∗}/K^{∗} is called the idèle class group of K. The idèles admit a natural surjective homomorphism A_{K}^{∗} ⟶ Div(X) induced by the valuation maps. The kernel is denoted by U. It consists of the idéles that have trivial valuation at all places. The intersection of U and K^{∗} inside A_{K}^{∗} is precisely equal to F_{q}^{∗}. Writing P for the group of principal divisors and Q for the quotient U/F_{q}^{∗} it is easy to see that we have the following diagram with exact rows and columns:

0  0  0
↓  ↓  ↓
0 ⟶ F_{q}^{∗} ⟶ K^{∗} ⟶  P  ⟶ 0
↓  ↓  ↓
0 ⟶ U ⟶ A_{K}^{∗} ⟶ Div(X) ⟶ 0
↓  ↓  ↓
0 ⟶ Q ⟶ C_{K} ⟶ Pic(X) ⟶ 0
↓  ↓  ↓
0  0  0

Class field theory gives a description of the idèle class group C_{K}. It relates its open subgroups to abelian extensions of the function field K or, equivalently, to abelian coverings of the curve X. The main result is contained in the following theorem.

Theorem (8.1). Let X be a curve over F_{q} with function field K.

(i) (Artin-Reciprocity.) For every finite extension L of K with π = Gal(L/K) abelian, there are

canonical isomorphisms

Ĥ^{q}(π, C_{L}) ≅ Ĥ^{q−2}(π, Z).

(ii) (Existence Theorem.) For every subgroup of finite index M of C_{K} there exists a unique finite abelian extension L for which N(C_{L}) = M. Here N denotes the norm map from L to K.

Proof. For the proof of this theorem we refer to standard texts on class field theory [1,4,14]

Applying Theorem 8.1(i) with q = 0 to a finite extension L over K with π = Gal(L/K) abelian, one obtains the classical reciprocity map

C_{K}/N(C_{L}) ⟶^{≅} π.

A place v of K is unramified in L if and only if the unit group O_{v}^{∗} is contained in N(C_{L}). In this case we obtain a map Z ≅ K_{v}^{∗}/O_{v}^{∗} ⟶ C_{K}/N(C_{L}) ≅ π. The image of 1 is called the Frobenius element ϕ_{v} of v in π. It determines the splitting behavior of v in the extension L over K. For instance, v is totally split if and only if its Frobenius element ϕ_{v} is trivial i.e. if and only if K_{v}^{∗}/O_{v}^{∗} ⊂ N(C_{L}).

We will study some special abelian extensions of a function field K, the so-called ray class fields . Let D be an effective divisor which is defined over F_{q}. So D = ∑_{v} n_{v}v where the sum runs over the places v of K, the n_{v} are non-negative and only finitely many of them satisfy n_{v} > 0. Let U_{D} = {(x_{v})_{v} ∈ U: x_{v} ≡ 1 (mod t_{v}^{n_{v}})}; here t_{v} denotes a uniformizing element at v. The group U_{D}/F_{q}^{∗} is a subgroup of the idèle class group C_{K}. The abelian extensions of K corresponding to the finite quotients of C_{K}/U_{D} are called ray class fields. Let L be a finite extension of K and let M ⊂ C_{K} be the ray class group that corresponds to it according to Theorem 8.1.(ii). There is an effective divisor D, minimal with respect to division, such that U_{D}/F_{q}^{∗} ⊂ M. This is called the conductor of L

For D = (0) the group U_{D}/F_{q}^{∗} is just U/F_{q}^{∗} and the quotient C_{K}/U_{D} is precisely the Picard group Pic(X). For arbitrary D we have an exact sequence

0 ⟶ U/U_{D} ⟶ C_{K}/U_{D} ⟶ Pic(X) ⟶ 0.

For the first group we have the following explicit description:

U/U_{D} ≅ ⊕_{v in D} F_{q}[[t_{v}]]^{∗}/{x : x ≡ 1 (mod t_{v}^{n_{v}}).

From the exact sequence

0 ⟶ Pic^{0}(X) ⟶ Pic(X) ⟶^{deg} Z ⟶ 0

we see that for each degree n there is a ray class field corresponding to the cyclic quotient of order n of Z. This is the constant field extension F_{q^{n}}(X). In general the degree of the field of constants of a finite abelian extension L of K corresponding to M ⊂ C_{K} is equal to the index of deg(M) in Z.

Finally we mention Dirichlet characters i.e. continuous homomorphisms χ : Gal(\overline{K}/K) ⟶ C^{∗}. Here \overline{K} denotes a separable closure of K. A character χ has a finite image and the fixed field of ker χ is a cyclic extension L of K. We define the conductor of χ to be the conductor of L. We recall the following result, very useful to calculate the genus of an abelian covering.

Proposition (8.2). (Führerproduktdiskriminantformel) Let X be a curve of genus g_{X} over F_{q} and let f : Y ⟶ X be a covering of genus g_{Y}. Suppose that the corresponding extension of function fields has a finite abelian Galois group G. Then

2g_{Y} − 2 = deg(f)(2g_{X} − 2) + ∑_{χ} deg(condχ).

Here the product runs over the characters χ of G.

Proof. See [35.Ch.V].

In the remainder of this section we will use class field theory to show the existence of curves over F_{2} with certain properties.

Example (8.3). Consider P^{1} over F_{2}. Let K denotes its function field and let P be a point of degree 3 on P^{1}. Consider the ray class fields of conductor P. Since Pic(P^{1}) = Z and F_{2}^{∗} = {1}, we have an exact sequence

0 ⟶ F_{8}^{∗} ⟶ C_{K}/U_{P} ⟶ Z ⟶ 0.

Next we pick an F_{2}-rational point Q on P^{1} and we let L be the fixed field of the Frobenius element of Q and let X be the curve corresponding to it. Clearly L has degree 2^{3} − 1 = 7 over K. Its genus g is easily computed using Prop.8.5: 2g − 2 = −2 · 2 + 6 · 3. Since all the points over Q on X are rational we see that we have found a curve over F_{2} of genus 3 and at least 7 rational points. It is rather easy to see that there are, in fact, precisely 7 rational points.

Example (8.4). Let (∞) be a rational point on P^{1} over F_{2} and let 0 and 1 denote the others. Let D = 4(∞). We have an exact sequence

0 ⟶ F_{2}[[t]]^{∗}/{f: f ≡ 1 (mod t^{4})} ⟶ C_{K}/U_{D} ⟶ Z ⟶ 0.

It follows easily that, as an abelian group, C_{K}/U_{D} ≅ Z ⊕ Z/4Z ⊕ Z/2Z. Let L be the invariant field of the two Frobenius elements of the other two points 0 and 1. It is easy to see that the degree of L over the function field K of P^{1} is 2. The genus g of the curve E corresponding to L follows from 2g − 2 = −2 · 2 + 4. By construction the points 0 and 1 are split and (∞) is ramified in E over P^{1}. We have found a curve over F_{2} of genus 1 with 5 rational points.

Example (8.5). This time we use the curve E of Example 8.3 as a basis. Its genus is 1 and it has five F_{2}-rational points P_{1}, P_{2}, …, P_{5}. Its class group Pic^{0}(E) has order 5. We will only consider 2-extensions of E. Take D = 2(P_{1}) + 4(P_{2}). We have that

U/U_{D} ≅ F_{2}[[t]]/{1 (mod t^{2})} ⊕ F_{2}[[t]]/{1 (mod t^{4})}
≅ Z/2Z ⊕ Z/4Z ⊕ Z/2Z

Let L denote the fixed field of the Frobenius elements of the three other rational points P_{3}, P_{4} and P_{5}. This is a quadratic extension. The genus g of the corresponding curve is given by 2g − 2 = 0 + 6. We have found a curve over F_{2} of genus 4 with 8 points.

These examples show that one can find curves with many points with respect to their genus by means of class field theory. All examples are best possible: there do not exist curves over F_{2} of genus 1, 3 or 4 that have more points than the curves above. This follows from Oesterlé’s estimates that have been explained in the previous section. Serre used this idea to find curves over F_{2} with rather high genus and a large number of rational points. We present two of his examples. Others can be found in the exercises.

Example (8.6). (Serre) Consider P^{1} over F_{2}. Let P_{2} be the unique place of degree 2 and let P_{3} denote one of the two places of degree 3. Consider the full ray class field of conductor P_{2} + P_{3}. Let K denote the subfield in which the point ∞ of P^{1} is completely split. This field has its Galois group over P^{1} isomorphic to F_{4}^{∗} × F_{8}^{∗}. There are two characters of conductor P_{2}; they have degree 2. The six characters of conductor P_{3} have degree 3 and the 12 remaining non-trivial characters have conductors of degree 2+3=5. We conclude from Proposition 8.5 that

2g_{X} − 2 = 21(2 · 0 − 2) + 2 · 2 + 6 · 3 + 12 · 5

and hence that g_{X} = 21. Since all points on X that lie over ∞ are rational, we see that X is a curve of genus 21 with 21 rational points. This is best possible.

Example (8.7). (Serre) Let E be the curve of genus 1 and five points from Example 8.3. Let P_{1}, …, P_{5} denote the rational points on E. We will consider ray class fields of conductor k(P_{1}) and in particular the subfields in which the other points P_{2}, …, P_{5} are completely split. It is easy to see that there exists such a subfield K of conductor 12(P_{1}) and Galois group over F_{2}(E) isomorphic to Z/2Z ⊕ Z/2Z ⊕ Z/2Z. There is one character of conductor 8(P_{1}), two of conductor 10(P_{1}) and the remaining four non-trivial ones have conductor 12(P_{1}). Let X be a smooth curve with function field K. By Proposition 8.5 we have that

2g_{X} − 2 = 2(2 · 1 − 2) + 1 · 8 + 2 · 10 + 4 · 12

and hence that g_{X} = 39. The unique point on X over P_{1} is rational. Over every other point P_{i} there are precisely 8 rational points. So, the curve X has genus 39 and 1+8·4 = 33 rational points. This is the maximal possible number for a curve of genus 39.

We conclude this section with a table. In the first column we have the genus g. In the second column the bound b from Theorem 7.2 is listed: every curve of genus g over F_{2} has at most b points. In the third column one finds the maximal number n for which a curve of genus g over F_{2} with n rational points is known to exist. Most entries in the table follow from the examples or the exercises in this section. They can also be found in [22,23,24]. The entries with an asterisk were found by Serre more recently.

Table (8.8).

\begin{matrix}g & b & n & g & b & n & g & b & n & g & b & n \\ 1 & 5 & 5 & 7 & 11 & 10 & 13 & 15 & 15* & 19 & 20 & 20 \\ 2 & 6 & 6 & 8 & 11 & 11 & 14 & 16 & 15 & 20 & 21 & 19 \\ 3 & 7 & 7 & 9 & 12 & 12 & 15 & 17 & 17 & 21 & 21 & 21 \\ 4 & 8 & 8 & 10 & 13 & 12 & 16 & 18 & 16 & 22 & 22 & 21 \\ 5 & 9 & 9 & 11 & 14 & 14* & 17 & 18 & 17 & 39 & 33 & 33 \\ 6 & 10 & 10 & 12 & 15 & 14 & 18 & 19 & 18 & 50 & 40 & 40 \end{matrix}

Exercises.

(8.A) Let P_{d} be a point of degree d ≥ 2 on P^{1} over F_{2}. Show that the degree of the maximal subfield of 2-power degree inside the ray class field of conductor 2(P_{d}) in which the three rational points are split has degree 2^{d−2}. Show that the corresponding curves have genus 2 and 6 rational points for d = 3, genus 9 and 12 points for d = 4 and genus 28 and 24 points for d = 5.

(8.B) Use ray class fields of conductor k(∞) of F_{2}(P^{1}) to show that there exists curves over F_{2} of genus 5

with 9 points and of genus 17 with 17 points. (8.C) Let E be the curve of genus 1 over F_{2} from Example 8.3. Study its ray class fields of conductor k(P_{1})

where P_{1} is a rational point and show that there exist curves over F_{2} of genus 6 or 7 with 10 points, of genus 15 with 17 points. Study its ray class fields of 2-power degree of conductor 2(P_{d}) where P_{d} denotes a place of degree d. Show that there exist curves over F_{2} of genus 19 with 20 points and of genus 50 with 40 points.

(8.D) As Exercise 8.C with E replaced by a curve of genus 2 with 6 points. Show that there exist curves over F_{2} of genus 8 with 11 points, genus 9 or 10 with 12 points, of genus 22 with 21 points and of genus 26 with 24 points.

(8.E) As Exercise 8.C with E replaced by a curve of genus 3 with 7 points. Show that there exist curves over F_{2} of genus 11 with 13 points and of genus 12 or 13 with 14 points.

(8.F) Show there exist curves of genus g over F_{2} with n rational points, for the following pairs (g, n): (14,15),

(15,16), (16,16), (17,17), (18,18), (20,19) and (21,20). (8.G) (Serre [22]) Show that there is no curve over F_{2} of genus 7 with 11 points. (Hint: show that such a

curve has no “new” points over small extensions of F_{2}; use this to calculate its ζ-function and show that it factors into two polynomials that are coprime in Z[X]; show that this contradicts the irreducibility of the Θ-divisor on the Jacobian of X.)

9. Class Field Towers. In this section we show how to construct infinite class field towers of function fields; see also [4,Ch.IX]. We will use freely the main results of class field theory that have been explained in the previous section. As an application we prove Serre’s result that A(q) > c log q for some absolute constant c > 0. We will moreover show that A(2) ≥ 2/9.

The only way known to construct infinite class field towers is by means of a group theoretical result that will be proved below. Let ℓ be a prime and let G be a finite ℓ-group. We let d = dim H_{1}(G, Z/ℓZ) denote the number of generators of G and we let r = dim H_{2}(G, Z/ℓZ) denote the number of relations of G. Here the dimensions are F_{l}-dimensions. From the homology of the exact sequence 0 ⟶ Z ⟶ Z ⟶ Z/ℓZ ⟶ 0 we see that

H_{1}(G, Z)/ℓH_{1}(G, Z) ≅ H_{1}(G, Z/ℓZ)

and we have a surjective map

H_{2}(G, Z/ℓZ) ⟶ H_{1}(G, Z)[ℓ].

This shows that r ≥ d.

Theorem (9.1). (Golod and Shafarevič, 1965) Let ℓ be a prime. For every finite ℓ-group G one has that

r > \frac{1}{4}d^{2}.

Proof. Let I denote the augmentation ideal in the group ring F_{l}[G]. Since I/I^{2} ≅ H_{1}(G, Z/ℓZ) we see, using Nakayama’s lemma, that the minimal number of F_{l}[G]-generators of I is d. Let F_{d} be a free F_{l}[G]-module of rank d admitting a surjective map F_{d} ⟶ I. From the long homology sequence it is easy to see that the minimal number of F_{l}[G]-generators of the kernel of this map is precisely r. Therefore there exists an exact sequence of F_{l}[G]-modules:

F_{r} ⟶ F_{d} ⟶ I ⟶ 0

where F_{r} is free of rank r. Because d is the minimal number of generators of I the map F_{d} ⟶ I is an isomorphism modulo I. So the image of F_{r} must be contained in IF_{d}. We conclude that we have exact sequences

F_{r}/I^{k−1}F_{r} ⟶ F_{d}/I^{k}F_{d} ⟶ I/I^{k+1} ⟶ 0

for every k ≥ 1. We obtain the following inequalities for 0 ≤ t < 1:

∑_{k=1}^{∞} dim_{F_{l}}(F_{d}/I^{k}F_{d})t^{k} ≤ ∑_{k=1}^{∞} dim_{F_{l}}(I/I^{k+1})t^{k} + ∑_{k=1}^{∞} dim_{F_{l}}(F_{r}/I^{k−1}F_{r})t^{k}.

Observe that the group ring F_{l}[G] is finite, so the ideal I^{k} = 0 for k large enough. Therefore the sums converge for 0 ≤ t < 1. We define the “Poincaré polynomial” P (t) by

P (t) = ∑_{k=0}^{∞} dim_{F_{l}}(I^{k}/I^{k+1})t^{k}.

It is easy to see that for a free F_{l}[G]-module M of rank m one has that

∑_{k=0}^{∞} dim_{F_{l}}(M/I^{k+1}M)t^{k} = \frac{mP (t)}{1 − t}.

Using this, the inequality above becomes

\frac{tdP (t)}{1 − t} ≤ \frac{P (t) − 1}{1 − t} + \frac{rt^{2}P (t)}{1 − t}

for 0 ≤ t < 1 and hence we obtain

rt^{2} − dt + 1 ≥ \frac{1}{P (t)} for 0 ≤ t < 1.

Since P (t) has all its coefficients positive, we have that rt^{2} − dt + 1 > 0 for all 0 ≤ t < 1. We have already seen that r ≤ d and hence that 0 < d/2r < 1. Substituting this value for t gives the required result.

Theorem 9.1 was proved by Golod and Shafarevič in 1965. They used it to solve the “class field tower problem”. More precisely, they showed that there exist algebraic number fields that possess infinite class field towers. Their proof applies to function fields over finite fields as well. We will now study the function field case in more detail.

Let X be a curve over F_{q} and let K denote its function field. Let S denote a non-empty set of places on X. Recall that places are Galois conjugacy classes of points. The S-Hilbert class field of K is the maximal unramified abelian extension H(K) of K in which all places in S split completely. This is a finite extension K_{1} of K = K_{0} and by class field theory, the Galois group Gal(K_{1}/K_{0}) is isomorphic to Pic_{S}(X) = Pic(X)/B where B is the subgroup generated by the points in S. This can be repeated: Let S′ be the set of places of H that lie over S. Let K_{2} = H(H(K)) be the S′-Hilbert class field of K_{1} = H(K). Etcetera. In this way one obtains a sequence of fields

K = K_{0} ⊂ K_{1} ⊂ … ⊂ K_{n} ⊂ …

all unramified over K in which the places in S are totally split. This is the S-class field tower of K or X. It is said to be finite if it stabilizes i.e. if for some n one has that K_{m} = K_{n} for all m ≥ n, and infinite otherwise.

Rather than class field towers we will consider ℓ-class field towers since these are easier to handle. For a prime ℓ one defines the (ℓ, S)-class field tower of a function field K in a similar way: The (ℓ, S)-Hilbert class field of K is the maximal unramified abelian ℓ-extension H_{ℓ}(K) of K in which all places in S split completely. This is a finite extension K_{1} of K = K_{0} and by class field theory, the Galois group Gal(K_{1}/K_{0}) is isomorphic to the ℓ-part of Pic_{S}(X) = Pic(X)/B where B is the subgroup generated by the points in S. As before, one can repeat this and obtain the (ℓ, S)-class field tower of K. It is easy to see that a field K has an infinite S-class field tower whenever it has an infinite (ℓ, S)-class field tower for some prime ℓ.

We are mainly interested in infinite S-class field towers because of the following application:

Proposition (9.2). Let X be a curve of genus g over F_{q}. Let S be a set of F_{q}-rational points of X. If X has an infinite S-class field tower then

A(q) ≥ \frac{#S}{g − 1}.

Proof. There is no loss in assuming that S is not empty. Consider the curves

X = X_{0} ⟵ X_{1} ⟵ X_{2} ⟵ …

whose function fields are the layers in the infinite S-class field tower of K. Since the points in S are totally split in every covering X ⟵ X_{n}, we see that X_{n} has field of constants equal to F_{q} and that it has at least d_{n}#S points rational over F_{q}. Here d_{n} denotes the degree of X_{n} over X. Since X_{n} is unramified over X, the Hurwitz-Zeuthen formula for its genus g_{n} becomes

2g_{n} − 2 = d_{n}(2g − 2).

Since the tower is infinite, we conclude that

A(q) ≥ lim_{n→∞} \frac{d_{n}#S}{1 + d_{n}(g − 1)} = \frac{#S}{g − 1}

as required.

We will freely use the notation introduced in the previous section. Before deriving a criterion for a function field K to have an infinite (ℓ, S)-class field tower, we introduce some more notation. Let X be a curve with function field K and let S be a finite set of places on X. By O_{S} we denote the subring of K consisting of the functions that have at most poles at places in S. let O_{S}^{∗} denote its unit group. The group of S-divisors Div_{S}(X) is the subgroup of divisors with support outside S. The kernel of the canonical map A_{K}^{∗} ⟶ Div_{S}(X) will be denoted by U_{S}. Finally we let P_{S} denote the group of principal S-divisors and we let Q_{S} = U_{S}/O_{S}^{∗}. We have the following diagram with exact rows and columns:

0  0  0
↓  ↓  ↓
0 ⟶ O_{S}^{∗} ⟶ K^{∗} ⟶  P_{S}  ⟶ 0
↓  ↓  ↓
0 ⟶ U_{S} ⟶ A_{K}^{∗} ⟶ Div_{S}(X) ⟶ 0
↓  ↓  ↓
0 ⟶ Q_{S} ⟶ C_{K} ⟶ Pic_{S}(X) ⟶ 0
↓  ↓  ↓
0  0  0

For a finitely generated abelian group A and a prime number ℓ we let d_{ℓ}A denote the ℓ-rank of A, i.e. d_{ℓ}A is the F_{l}-dimension of A/ℓA.

Proposition (9.3). Let X be a curve over F_{q} and let S be a non-empty finite set of places of X. If for a prime number ℓ one has that

d_{ℓ}Pic_{S}(X) ≥ 2 + 2\sqrt{d_{ℓ}O_{S}^{∗} + 1}

then X has an infinite (ℓ, S)-class field tower.

Proof. Suppose X has a finite (ℓ, S)-class field tower. Let L denote the union of all the layers of the tower of function fields. The Galois group G = Gal(L/K) is a finite ℓ-group. Its maximal abelian quotient is the ℓ-part of Pic_{S}(X). Therefore its number of generators d satisfies

d = d_{ℓ}Pic_{S}(X).

From the exact sequence 0 ⟶ Z ⟶ Z ⟶ Z/ℓZ ⟶ 0 we obtain the exact sequence

0 ⟶ H_{2}(G, Z)/ℓH_{2}(G, Z) ⟶ H_{2}(G, Z/ℓZ) ⟶ H_{1}(G, Z)[ℓ] ⟶ 0

and the inequality

r − d ≤ d_{ℓ}H_{2}(G, Z).

Next we compute the group H_{2}(G, Z) = Ĥ^{−3}(G, Z). By class field theory we have that Ĥ^{−3}(G, Z) ≅ Ĥ^{−1}(G, C_{L}). To compute the latter group we consider the diagram above with field L and the set of places S′ of places of L over S: by the maximality of L, the ℓ-part of Pic_{S}(Y) is trivial and so are its G-cohomology groups. Since L is unramified over K the G-cohomology groups of U_{L} are zero and we find that Ĥ^{−1}(G, C_{L}) ≅ Ĥ^{−1}(G, Q_{L}) ≅ Ĥ^{0}(G, O_{S′}^{∗}). we conclude that

r − d ≤ d_{ℓ}H^{0}(G, O_{S′}^{∗}) ≤ d_{ℓ}O_{S}^{∗}.

The result now follows easily from the theorem of Golod and Shafarevič and the fact, mentioned above, that d = d_{ℓ}Pic_{S}(X).

To apply this proposition, we need to know d_{ℓ}O_{S}^{∗} and d_{ℓ}Pic_{S}(X). It is well-known that

d_{ℓ}O_{S}^{∗} = \{ \begin{matrix}#S, & if ℓ|q − 1; \\ #S − 1, & otherwise. \end{matrix}

To estimate the ℓ-rank of Pic_{S}(X) we consider only a special case:

Proposition (9.4). Let X be a curve over F_{q} with function field K. Suppose that K is a cyclic extension of degree ℓ of a field F. Let S′ denote the set of places of F over which the places in S lie and let ρ denote the number of places of F that are ramified in K. Then

(i) If

ρ ≥ 3 + d_{ℓ}O_{S′}^{∗}/(O_{S′}^{∗} ∩ NU_{S}) + 2\sqrt{d_{ℓ}O_{S}^{∗} + 1}

then K has an infinite class field tower. (ii) If

ρ ≥ \{ \begin{matrix}3 + #S′ + 2\sqrt{#S + 1}, & if ℓ|q − 1; \\ 2 + #S′ + 2\sqrt{#S}, & otherwise. \end{matrix}

then K has an infinite class field tower.

Proof. Using class field theory we obtain the following inequalities from the diagram above:

d_{ℓ}Pic_{S}(X) ≥ d_{ℓ}Ĥ^{−1}(π, Pic_{S}(X)) ≥ d_{ℓ}Ĥ^{0}(π, Q_{S}) − d_{ℓ} − Ĥ^{0}(π, C_{K})
≥ d_{ℓ}Ĥ^{0}(π, U_{S}) − d_{ℓ}O_{S′}^{∗}/(O_{S′}^{∗} ∩ NU_{S}) − d_{ℓ}Ĥ^{−2}(π, Z)
≥ ρ − d_{ℓ}O_{S′}^{∗}/(O_{S′}^{∗} ∩ NU_{S}) − 1.

The last inequality follows, because we have that U_{S} ≅ ∏_{v∉S} O_{v}^{∗} ∏_{v∈S} K_{v}^{∗} where O_{v} is the completed local ring at v and K_{v} its quotient field. Therefore, by local class field theory, d_{ℓ}H^{0}(π, U_{S}) is equal to the number of ramified places ρ of F plus the number of inert places in S′. We will neglect the latter contribution. A combination with proposition 9.3 yields (i). Part (ii) follows from this together with the estimate

d_{ℓ}O_{S′}^{∗}/(O_{S′}^{∗} ∩ NU_{S}) ≤ \{ \begin{matrix}#S′ + 1, & if ℓ|q − 1; \\ #S′; & otherwise. \end{matrix}

This proves the Proposition.

We will use this Proposition to prove some results concerning the function A(q) that was introduced in section 7.

Corollary (9.5). For every finite field F_{q} and every prime ℓ there exists a curve X over F_{q} and a set S ≠ ∅ of rational places of X such that X has an infinite (ℓ, S)-class field tower. For every finite field F_{q} one has that A(q) > 0.

Proof. Let F be F_{q}(T), the function field of P^{1}. Let K be a cylic extension of degree ℓ of F in which at least 8 places are ramified one of which is an F_{q}-rational point P. Using class field theory, it is a trivial matter to exhibit such an extension. Now take S′ = {P } and S equal to the unique point over P in K. By Proposition 9.4 the field K has an infinite (ℓ, S)-class field tower and it follows from Proposition 9.2 that A(q) > 0.

Proposition (9.6). There exists an absolute constant c > 0 such that A(q) > c log q.

Proof. Let us first suppose that q is odd. In view of Corollary 9.5 there is no loss in assuming that q is large. We let A and B be two subsets of F_{q} with the property that α − β ∈ (F_{q}^{∗})^{2} for every α ∈ A and β ∈ B. Next we let X be the hyperelliptic curve given by Y^{2} = ∏_{α∈A}(T − α). This is a curve of genus #A/2 − 1 or (#A − 1)/2. All places (T − α) of P^{1} with α ∈ A are ramified in the function field K of X. For S we choose the set of places lying over the places (T − β) with β ∈ B. Since α − β is a square for every α ∈ A and β ∈ B, the places in S are F_{q}-rational. Moreover, we have, in the notation of Proposition 9.4(i), that O_{S′}^{∗} ⊂ NU_{S} and we conclude that X admits an infinite (2, S)-class field tower when #A ≥ 3 + 2\sqrt{#B + 1}. Choosing #B as large as possible with respect to #A i.e. #B ∼ (#A)^{2}, we have in this case that

A(q) ≥ c\frac{#B}{#A} ∼ #A

for some c > 0. When q is even there is a similar argument with quadratic Artin-Schreier extsensions.

It remains to see how large A can be chosen. The following combinatorial lemma gives an estimate for this. It should be applied with Ω = F_{q} and R = {(x, y) ∈ Ω × Ω : x − y ∈ (F_{q}^{∗})^{2}}. One has that m = (q − 1)/2. It follows easily from the lemma that one can find sets A and B with a = #A ∼ log q and b = #B ∼ log^{2}q. This proves the Proposition.

Lemma (9.7). Let Ω be a finite set of cardinality ω and let R ⊂ Ω × Ω. Suppose that

#{x ∈ Ω: (x, y) ∈ R} ≥ m for all x ∈ Ω.

If

b\binom{ω}{a} ≤ ω\binom{m}{a}

then there exist two subsets A of cardinality a and B of cardinality b such that A × B ⊂ R.

Proof. Let T = {(A, y): A ⊂ Ω, #A = a, A × {y} ⊂ R}. Each fiber of the natural projection T ⟶ Ω given by (A, y) ↦ y, contains at least \binom{m}{a} elements. Therefore #T ≥ ω\binom{m}{a}.

Now let P_{a}(A) denote the collection of subsets of Ω of cardinality a and consider the other projection T ⟶ P_{a}(Ω) given by (A, y) ↦ A. Since the cardinality of P_{a}(Ω) is \binom{ω}{a}, we see that there must exist a fiber with at least

#T/\binom{ω}{a} ≥ ω\binom{m}{a}/\binom{ω}{a} ≥ b

elements. So, it suffices to take the set A corresponding to this fiber and B = {y ∈ Ω: (A, y) ∈ R}. This proves the Lemma.

Finally we restrict our attention to the field F_{2}. We know that A(2) ≤ \sqrt{2} − 1 ≈ 0.414. Here we will prove a lower bound.

Theorem (9.8). One has that

A(2) ≥ \frac{2}{9} ≈ 0.222.

Proof. We will give two proofs. The first one is due to Serre. In both proofs a curve X and a set S of places are exhibited such that the function field K of X has an infinite (2, S)-class field tower.

(i) Serre starts with a curve of genus 1 with precisely two F_{2}-rational points, e.g. Y^{2} + XY = X^{3} + X + 1. This curve has three points with field of definition equal to F_{4} and four with field of definition F_{8}. Let F denote the function field of E and let S′ be the set of two rational points on E. The unit group O_{S′}^{∗} is infinite and cyclic generated by ε say. For each of the points Q of degree 2 and 3 there exists a quadratic extension of conductor 2(Q) where ε is a local norm. Therefore there exists a quadratic extension K of F of conductor ∑_{Q} 2(Q) in which the points in S′ are totally split and for which ε ∈ NU_{S}. Here S denotes the set of places over S′. Since d_{2}O_{S}^{∗} = 3 and O_{S′}^{∗} ⊂ NU_{S}, it follows from Prop.9.4(i) that K has an infinite (2, S)-class field tower. The genus g_{X} of the corresponding smooth curve X is given by Prop.8.2.:

2g_{X} − 2 = 2(2 · 1 − 2) + 3 · 4 + 4 · 6.

So g_{X} = 19 and #S = 2#S′ = 4 and we conclude from Prop.9.2 that

A(q) ≥ \frac{4}{19 − 1} = \frac{2}{9}.

(ii) This time we start with a curve E of genus 1 and 5 rational points P_{1}, P_{2}, …, P_{5} over F_{2}. It has been constructed in section 8 as a quadratic cover of P^{1} of conductor 4(∞) in which the other two rational points (0) and (1) are split. We will make two quadratic extensions of the function field of E: F: A quadratic extension of conductor 2Q in which all points P_{1}, P_{2}, …, P_{5} split. Here Q is a

point of degree 5 of E. The curve Y corresponding to this field has genus 6 and 10 points rational over F_{2}. It has been constructed before in section 8.

F′: This field is the composite of F_{2}(E) and the following extension of the function field of P^{1}: a quadratic extension of conductor 2(0) + 2(1) in which (∞) splits. As a consequence F′ has conductor 2 ∑_{i=1}^{4} P_{i} and P_{5}, the unique place over (∞), splits. We let X denote the curve corresponding to the function field F′F. It admits a map of degree

two to Y. Now we apply Proposition 9.4(ii). For S′ we take the two points on Y over P_{5}. They are split in the covering X ⟶ Y. The remaining 8 rational points on Y lie over P_{1}, …, P_{4} and they are all ramified. We conclude that #S = 4 and that ρ = 8. Therefore

ρ = 2 + #S′ + 2\sqrt{#S}

and we see that K = F_{2}(X) has an infinite (2, S)-class field tower. The degrees of the conductors of the characters of the Galois group of X over E are 10, 8 and 18 respectively. It follows from Proposition 8.2 that the genus of X is 19. Since #S = 4 we deduce from Proposition 9.2 that A(q) ≥ 4/(19 − 1) = 2/9 as required.

Exercises.

(9.A) Let G be a finite abelian p-group with d independent generators. Show that it has precisely \binom{d+1}{2}

independent relations. (9.B) Let p be a prime. Show that the group presented as a pro-p-group as < x, y: x^{p} = 1, [x, y] = y^{p} > is a

finite p-group. It is a group with two independent generators x and y and two relations. (9.C) Let p be a prime and let G be a group of order p^{a}. Show that G has at most a independent generators

and at most \binom{a+1}{2} independent relations. (9.D) (Mennicke) Let p be a prime and let d ≥ 3 be an integer. Let G be the pro-p-group generated by

x_{1}, x_{2}, …, x_{d} with the following relations: [x_{i}, x_{i+1}] = x_{i}^{p} for 1 ≤ i ≤ d and [x_{i}, x_{j}] = 1 for all i and j for which i − j ≠ ±1. Here all indices should be taken modulo d. Show that G is a finite p-group with d generators and \binom{d}{2} relations.

(9.E) Exhibit for each prime p and each d ≤ 3 a finite abelian p-group with d generators and d relations. Show that no such group exists when d > 3. Give an example of a p-group with 4 generators and 6 relations. It is not known whether there exist finite p-groups with 4 generators and 5 relations.

(9.F) (Kostrikin) Let p be a prime and let d > 1 be an integer. Let G_{d} be the pro-p-group generated by x_{1}, x_{2}, …, x_{d} and y_{1}, y_{2}, …, y_{d} with the following relations: x_{i}^{p} = y_{i}^{p} = 1 for all 1 ≤ i ≤ d, [x_{i}, x_{j}] = [y_{i}, y_{j}] for all i ≠ j and [x_{i}, y_{j}] = 1 for all i ≠ j. Show that G_{d} is a finite p-group with 2d independent generators and at most \frac{3}{2} d(d + 1) independent relations. Conclude that for every prime p one has that 1/4 ≤ limsup_{#G,d→∞}(r/d^{2}) ≤ 3/8. Here the limit is taken over finite p-groups G with d generators and r relations. It has been shown by J. Wisliceny [36] that for p > 2 one actually has that limsup_{#G,d→∞}(r/d^{2}) = 1/4.

Bibliography

[1] Artin, E. and Tate, J.T.: Class field theory, Math. Lecture Notes, Benjamin, New York 1967.

[2] Barg, A.M., Katsman S.L. and Tsfasman, M.A.: Algebraic geometric codes from curves of small genus, Probl. of Information Transmission 23 (1987), 34–38.

[3] Bombieri, E.: Counting points on curves over finite fields (d’après Stepanov), Sém. Bourbaki 430, juin 1973.

[4] Cassels J.W.S. and Fröhlich A.: Algebraic number theory, Academic Press, London 1967.

[5] Chevalley, C.: Introduction to the theory of algebraic functions of one variable, Math. Surveys 6, AMS, New York 1951.

[6] Cusack, E.: Codes, Open University TM 361–14, Open Univ. Press, Walton Hall, Milton Keynes 1982.

[7] Drinfeld, V.G. and Vlădut, S.G.: The number of points on an algebraic curve, Funct. Anal. i Ego Pril., 17 (1983), 68–69. (=Functional Analysis 17 (1983), 53–54.)

[8] Fulton, W.:Algebraic curves, W.A.Benjamin, New York 1969.

[9] Goppa, V.D.: Codes on algebraic curves, Doklady Akad. Nauk SSSR, 259 (1981), 1289–1290. (=Soviet Math. Dokl. 24 (1981), 170–172.)

[10] Goppa, V.D.: Algebraico-geometric codes, Izvestia. Akad. Nauk SSSR, 46 (1982), 209–257. (=Math. USSR Izvestiya 21 (1983), 75–91.)

[11] Goppa, V.D.: Geometry and codes, Mathematics and its applications (Soviet Series), Kluwer Ac. Publ., Dordrecht 1988.

[12] Hartshorne, R.: Algebraic geometry, Graduate Texts in Math. 52, Springer-Verlag, Berlin 1977.

[13] Ihara, Y.: Some remarks on the number of rational points of algebraic curves over finite fields, J. Fac. Sc. Tokyo, 28 (1981), 721–724.

[14] Iyanaga, S.: The theory of numbers, North Holland Math. Lib. 8, Amsterdam 1975.

[15] Lachaud, G.: Les codes géométriques de Goppa, Sém. Bourbaki 641, Février 1985.

[16] MacWilliams F.J. and Sloane N.J.A.: The theory of error-correcting codes, North-Holland, Amsterdam 1978.

[17] Manin, Yu.I.: What is the maximum number of points on a curve over F_{2}?, J. Fac. Sci. Univ. Tokyo I A 28 (1981), 715–720.

[18] Schoof, R. and Van der Vlugt, M.: Hecke operators and the weight distributions of certain codes, To appear in J. of Comb. Theory A (1991).

[19] Schoof, R.: Algebraic curves over F_{2} with many rational points, Preprint RUU 1990.

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

[21] Serre, J.-P.: Corps locaux, Hermann, Paris 1968.

[22] Serre, J.-P.: Nombre de points sur une courbe sur un corps fini F_{q}, notes taken by M. Waldschmidt (19 pages), octobre 1982.

[23] Serre, J.-P.: Nombre de points des courbes algébriques sur F_{q}, Sém. Th. de nombres, Bordeaux exp. 22 (1982–1983).

[24] Serre, J.-P.: Sur le nombre des points rationnels d’une courbe algébrique sur un corps fini, Comptes Rendus Acad. Sci. Paris 296 (1983), 397–402.

[25] Serre, J. -P.: Résumé des cours de 1983–1984, Annuaire du Collège de France (1984), 79–83.

[26] Shafarevič, I.R.: Basic algebraic geometry, Springer-Verlag, Berlin 1977.

[27] Silverman, J.H.: The arithmetic of elliptic curves, Graduate Texts in Math. 106, Springer-Verlag, Berlin 1986.

[28] Stewart, I.N. and Tall, D.O.: Algebraic number theory, Chapman and Hall, London 1987.

[29] Tsfasman, M.A., Vlădut, S.G. and Zink, Th.: Modular curves, Shimura curves and Goppa codes better than the Varshamov-Gilbert bound, Math. Nachr. 109 (1982), 21–28.

[30] Tsfasman, M.A. and Vlădut, S.G.: Algebrogeometritskie codi, Moskou 1988.

[31] Van der Waerden, B.L.: Algebra I und II, Heidelberger Taschenbücher 12,23, Springer-Verlag, Berlin 1967,1971.

[32] Van Lint, J.H.: Introduction to coding theory, Graduate Texts in Math. 86, Springer-Verlag, Berlin 1982.

[33] Van Lint, J.H. and Van der Geer, G.: Introduction to coding theory and algebraic geometry, DMV Seminar 12, Birkhäuser Verlag, Berlin 1988.

[34] Van Wijngaarden, A. et al.: Revised report on the algorithmic language Algol 68, Springer-Verlag, Berlin 1976.

[35] Weil, A.: Sur les courbes algébriques et les variétés qui s’en déduissent, Hermann, Paris 1948.

[36] Wisliceny, J.: Zur Darstellung von pro-p-gruppen und Lieschen Algebren durch Erzeugenden und Relationen, Math. Nachr. 102 (1981), 57–78.

[37] Zink, Th.: Degeneration of Shimura surfaces and a problem in coding theory, in Budach, L.: Fundamentals of Computation Theory, Cottbus, GDR 1985. Lecture Notes in Computer Science 199, Springer-Verlag, Berlin 1986.