Ivan Pogildiakov

ON THE LINEAR BOUNDS ON GENERA OF POINTLESS HYPERELLIPTIC CURVES

research documents, whether they are published or not. The documents may come

Introduction

Given a prime power q = p n it is natural to ask whether a non-singular curve over the finite field F q having no rational points exists. For example, if p > 3, then the Fermat curve X q-1 + Y q-1 + Z q-1 = 0 serves an example of such a curve, since α q-1 ∈ {0, 1} for every α in F q . A positive answer to this question in the case of arbitrary characteristic follows from a result due to N. Anbar and H. Stichtenoth [START_REF] Anbar | Curves of Every Genus With a Prescribed Number of Rational Points[END_REF]Theorem 1.2]. They show that, given q and a non-negative number N , there is a suitable function field defining a smooth curve over F q of large genus having exactly N rational points. Thus, given q, it is natural to ask what genus a pointless curve over F q may have.

Let C be an irreducible non-singular projective (we will omit these words further) genus g curve defined over F q . Denote by N k (C) the number of rational points of C ⊗ Fq F q k . The curve C can not have too many or too few rational points. More precisely, the Hasse-Weil-Serre bound on N k (C) holds :

q k + 1 -g 2q k/2 ≤ N k (C) ≤ q k + 1 + g 2q k/2 .
Therefore, if a curve C has no points over F q k , i.e. N k (C) = 0, then the lower bound implies a restriction on the genus :

(1.1) g ≥ (q k + 1)/ 2q k/2 .

Hence the following question arises.

Question 1.1. Given a prime power q and an integer g satisfying (1.1), does there exist a non-singular genus g curve over F q having no F q k -points?

A complete answer to this question seems to be very difficult to obtain. It is directly related to the question about the attainability of the lower Hasse-Weil-Serre bound, becoming especially difficult, when the lower bound is non-positive but close to zero.

In this paper we study the following special version of Question 1.1.

1 Question 1.2. Given a prime power q, what is the minimal number g min q such that for any g ≥ g min q there is a non-singular pointless genus g curve over F q ?

We restrict our consideration of these questions to hyperelliptic curves. Note that for these curves there are several known improvements of the Hasse-Weil-Serre bounds. They are mostly based on Stepanov's method. One of these improvements belongs to H. M. Stark. Applying one of his estimates on the number of rational points on a hyperelliptic curve to the case g = 2 and q = 13, he showed that every genus two curve C over F 13 has N 1 (C) ≥ 2 [7, p. 288] (note that if a genus 2 curve over F q has no rational points, then the inequality (1.1) implies that q ≤ 13). This fact probably initiated the study of Question 1.1.

There are several known approaches to Question 1.1. Each of them involves different methods and constructions. One can identify three main directions : when q is fixed, when g is fixed, and when q and g both vary.

The asymptotic behavior of the minimal degree of smooth plane curves over F q having no rational points when q → ∞ was studied by S. Yekhanin in [START_REF] Yekhanin | A Note on Plane Pointless Curves[END_REF]. For a field F q of characteristic p > 3 a sequence of pointless non-singular plane curves over F q 4 k+1 of genus g k such that log q 4 k+1 g k tends to 2/3 was constructed. Namely, he showed that the Fermat curves

X d k + Y d k + Z d k = 1,
where d k = 2 k+1 (q 2 -1) k i=1 (q 4 i + 1), have no points over F q 4 k+1 . Aside from the trivial case of genus one, the question is completely resolved only in the genus two, three and four cases. As we mentioned above, the genus two case was treated by H. M. Stark in [START_REF] Stark | On the Riemann Hypothesis in Hyperelliptic Function Fields, Analytic number theory[END_REF], where he modified Stepanov's method to estimate the number of rational points on hyperelliptic curves over F p . Later on, as a by-product of their research concerning abelian surfaces, D. Maisner and E. Nart listed in [START_REF] Maisner | Abelian Surfaces over Finite Fields as Jacobians, With an appendix[END_REF]Table 4] all the pointless genus two curves over F q , q < 13, up to isomorphism over F q . The genus three and four cases were investigated in detail by E. W. Howe, K. E. Lauter and J. Top in [START_REF] Howe | Pointless Curves of Genus Three and Four, Arithmetic, geometry and coding theory[END_REF]. For g equal to 3 or 4 and every q, they either provide an example of a pointless genus g curve over F q , or prove by various methods that such a curve does not exist. Question 1.1 still remains open if the genus is greater than 4.

The case when q is fixed has been studied more extensively. It can be subdivided into at least two problems.

The first one is to estimate the minimal genus of a curve over F q having no points of degree n > 0 or less. It was proven by P. Clark and N. Elkies (a citation can be found in [4, p. 127]), that for every prime p there is a constant C p such that for every integer n > 0 there is a curve over F p of genus at most C p np n that has no points of degree n or less.

This unpublished result was reproven by C. Stirpe in her PhD thesis [START_REF] Stirpe | An Upper Bound for the Genus of a Curve Without Points of Small Degree[END_REF] by means of the class field theory. She showed [START_REF] Stirpe | An Upper Bound for the Genus of a Curve Without Points of Small Degree[END_REF]Corollary 4.3] that, given a degree n > n 0 place m of the rational function field F q (x), there is a ray class field extension of F q (x) with conductor m and constant field F q of genus (n -2)(q n -q) 2(q -1) , having no places of degree smaller than n. Note, the constant n 0 can be specified by [START_REF] Stirpe | An Upper Bound for the Genus of a Curve Without Points of Small Degree[END_REF]Remark 4.5] as n 0 = 6 log q (9/4) < 14. Furthermore, by taking a place m of a special form, she refined this result as follows.

Theorem 1.3 (Theorem 1.1 in [START_REF] Stirpe | An Upper Bound for the Genus of a Curve Without Points of Small Degree[END_REF]). For any prime p there is a constant C p such that for any n > 0 and for any power q of p there is a projective curve over F q of genus g ≤ C p q n without points of degree strictly smaller than n.

However, a sharper bound is proven in the general case. She obtained that, given a prime p, there is a large integer n 1 such that for any n > n 1 there is a function field over F p of genus g ≤ 1 2(p-1) p n without places of degree smaller than n. This bound was replaced by g ≤ C p q n , C p = 1 2(p-1) p n1 , for arbitrary n. The second problem is to provide a number g q such that for any g ≥ g q there is a pointless genus g curve over F q . Using Artin-Schreier extensions of function fields, N. Anbar and H. Stichtenoth showed in [1, Theorem 1.2] that for any q there are positive constants a q , defined implicitly, and b q = (p -1)(q + 2(p -1)

√ q + 3p -1)
such that for any g ≥ g q,N = a q N + b q there is a genus g curve over F q having exactly N rational points. In particular, for any g ≥ g q = g q,0 there is a pointless genus g curve over F q . In the case when q is a square the constant can be slightly improved, namely g q = 2q(p -1) + 3p 2 -2, which follows from [START_REF] Anbar | Curves of Every Genus With a Prescribed Number of Rational Points[END_REF]Remark 4.4].

We also remark that a more general result is implied by [START_REF] Anbar | Curves of Every Genus With a Prescribed Number of Rational Points[END_REF]Theorem 1.4]. Given a prime power q and a positive integer n, there is a constant g 0 such that for every g ≥ g 0 there is a curve over F q having no points of degree n or less. This differs from the results of C. Stirpe, since the bound on the genus is worse, however, the existence is valid for any g ≥ g 0 .

Finally, in the case of odd characteristic there are results due to R. Becker and D. Glass [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF] that inspired our own research in this direction. In their work an explicit construction of pointless hyperelliptic curves of a certain form defined over a finite field F q was provided. Let us discuss some of their results.

Let q be a power of an odd prime p. There are two types of existence bounds on the genus of a pointless curve over F q . The first one is implied by [2, Theorem 1.2], which can be reformulated in terms of pointless curves in the following manner.

Theorem 1.4 (Reformulation of [2, Theorem 1.2]). Let a be the least residue of g mod p. Suppose that g ≥ (p -a -1)(q -1), if a < p -1, or g ≥ (p -2a -2)(q -1)/2, if 0 ≥ a ≥ (p -3)/2. Then there exists a non-singular hyperelliptic pointless curve of genus g defined over F q .

These bounds depend on the congruence class of the genus modulo p and, in general, are non-linear. Furthermore, they showed [2, Lemma 2.2] that if a = p -1 and g ≥ (q -1)/2, then such a curve also exists. Putting the above together, one obtains the bound g min q ≤ (p -1)(q -1), which holds without any restriction on the genus. R. Becker and D. Glass also established several results of another type, providing linear existence bounds. These bounds require imposing certain restrictive conditions on the genus. For example, they proved : Theorem 1.5 ([2, Corollary 2.5]). Let q be a power of a prime p > 2. For a given g ≥ q-1 2 , set d = gcd(2g + 2, q -1). If (2g + 2) d ≡ (2g + 3) d mod p, then there exists a hyperelliptic curve over F q of genus g with no rational points.

Moreover, in the case of prime q this theorem can be simplified as follows. Suppose g is an integer such that g ≥ (p -3)/2 and g + 1 is prime to (p -1)/2. It results from [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]Theorem 1.3] that there is a non-singular pointless genus g curve over F p .

However, no linear bound without any restriction on g was previously known, unless q is a Sophie Germain prime.

In this paper we provide a linear existence bound on the genus of a non-singular pointless curve defined over a fixed finite field F q with no additional assumptions. Our main result is the following theorem : Theorem 1.6. Let q be a prime power. Set

g q = max q-3 2 , 2 , q is odd, max {q -1, 2}, q is even.
Suppose that g ≥ g q . Then there is a smooth genus g hyperelliptic curve over F q having no F q -points.

This result is stronger than that of R. Becker and D. Glass [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF], since it provides unconditional bounds, which depend linearly on q. Furthermore, it covers the case of even characteristic.

We finish this introduction with a brief discussion of Question 1.2. It can be completely answered for small values of q. We know that a pointless genus 2 curve over F q exists if and only if q < 13. It is also known that for q ≤ 13 there are pointless curves over F q of genus 3 and of genus 4. As a corollary of Theorem 1.6, for an arbitrary q we have the bound

g min q ≤ g q =      2, q = 2, 3, 5, 7, q -1,
q is even, q ≥ 4, (q -3)/2, q is odd, q ≥ 9.

Thus, collecting all this together, we get g min q = 2 when q < 13 and q = 8, and g min 13 = 3. However, if q = 8 or q > 13, then we can obtain only the upper and the lower bounds on g min q . For example, there is a curve over F 2 of genus 4 having no points of degree 3 or less (see the table in the end of [START_REF] Stirpe | An Upper Bound for the Genus of a Curve Without Points of Small Degree[END_REF]Chapter 5]). Therefore, we have 4 ≤ g min 8 ≤ 7 and we do not know, whether a pointless curve over F 8 of genus 5 or 6 exists. In general, one can estimate the quantity g min q by means of the inequality (1.1) and the bound above.

In Section 2 we give some necessary preliminaries. In section 3 we prove our result in the case of odd characterictic in several steps by explicit constructions of suitable smooth hyperelliptic curves. In this case the idea of finding such curves is similar to the one used in [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]. However, we prove their smoothness by an alternative method, which leads to an improvement of the results in [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]. In section 4 we finish the proof of Theorem 1.6 providing an explicit construction of pointless curves over a finite field of even characteristic.

Acknowledgments. I would like to thank Prof. Alexey Zykin, my supervisor, for the support motivating me in this research, for careful reading of the earlier drafts of the paper and many helpful comments.

Preliminaries

In this section we introduce the notation and the definitions, that will be used in the rest of the paper. All necessary general information on hyperelliptic curves over finite fields can be found in [START_REF] Liu | Agebraic Geometry and Arithmetic Curves, Translated from the French by Reinie Erné[END_REF] (we will use Proposition 4.24 and Remark 4.25).

Let p be a prime and let q be a power of p. A genus g hyperelliptic curve C over the finite field F q can be defined by

y 2 + Q(x)y = P (x),
where Q(x) and P (x) are polynomials in

F q [x] satisfying 2g + 1 ≤ max{2 deg Q(x), deg P (x)} ≤ 2g + 2.
If p is odd, then one can take Q(x) = 0. In this case C is a smooth projective curve if and only if P (x) has no repeated roots in F q . In the case of even characteristic the smoothness of C is determined by a condition that Q (x) 2 P (x) + P (x) 2 and Q(x) are coprime.

The curve C is the union of two affine curves

y 2 + Q(x)y = P (x) and y 2 + x g+1 Q(1/x)y = x 2g+2 P (1/x).
The set of its rational points is the disjoint union of the set of rational points of the first affine curve and the set of rational points of the second one having x = 0. A hyperelliptic curve over F q is said to be F q k -maximal, if it has precisely 2q k + 2 points over F q k . This definition is reasonable, since a hyperelliptic curve is a degree 2 branched covering of the projective line, so that it has at most 2 different points over each point of P 1 .

We start with the following auxiliary lemma allowing us, in the case of odd characteristic, to search for F q -maximal non-singular hyperelliptic curves over F q rather than pointless ones. Lemma 2.1. A smooth F q -maximal genus g hyperelliptic curve over F q exists if and only if a smooth pointless hyperelliptic genus g curve over F q does. Proof. Let C be a smooth F q -maximal genus g hyperelliptic curve over F q . The Weil theorem implies that

Tr (F r C ) = 1 + q -N 1 (C) = -1 -q,
where Tr (F r C ) stands for the trace of the Frobenuis endomorphism of H 1 (C, Q l ).

Let C be the F q -quadratic twist of the curve C, then Tr (F r C ) = -Tr (F r C ) and

N 1 (C ) = 1 + q -Tr (F r C ) = 0.
Since the F q -quadratic twist of C is isomorphic over F q to C, the lemma is proven.

Let q be an odd prime power. In this case the method of finding pointless curves we use is similar to the one used in [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF] and is as follows. We denote by χ q (x) the quadratic character of F q . Let F (x) be a polynomial over F q such that (1) F (x) is monic and square free of degree 2g + 2, g > 1,

(2) χ q (F (x)) = 1 for any x ∈ F q . Denote by C the hyperelliptic curve over F q with an affine model y 2 = F (x). It follows from (1) that C is a non-singular curve of genus g. Since F (x) satisfies (2), we see that the number of affine F q -points of the curve is 2q. Since all the points of C at infinity satisfy y 2 = x 2g+2 F (x -1 ) with x = 0 and F (x) is monic, C has two points at infinity. Thus the curve C is F q -maximal, and by Lemma 2.1 there exists a non-singular hyperellptic curve of genus g over F q having no rational points. The main obstacle to applying the method is finding a polynomial over F q satisfying the conditions (1) and [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF].

We begin with the study of the family of hyperelliptic curves y 2 = f g,l,a (x), where

(2.1) f g,l,a (x) = x 2g+2 -x 2g+2-l(q-1) + a 2 .
We denote by L(q, g) the quantity (2g + 2)/(q -1) . Given an integer g and a an element of F q , the number of all the polynomials of the form (2.1) is precisely L(q, g). We will also need the parameter D(q, g) = gcd(2g + 2, q -1) in the next section. This family includes most of the curves considered in [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]. The polynomial f g,l,a (x), obviously, satisfies (2) when a = 0. In order to check (1), we use the following lemma as a central tool :

Lemma 2.2. A polynomial x n -x n-m + a has multiple roots if and only if n N a M -m M (n m) N -M = 0, where d = gcd(n, m), N = n/d, M = m/d.
This lemma can be regarded as a direct application of [3, Theorem 4], for example. It claims that one can compute the discriminant of a trinomial

x n + ax k + b as (-1) n(n-1)/2 b k-1 n N b N -K -(-1) N (n -k) N -K k K a N d , where d = gcd(n, k), N = n/d, K = k/d.
According to Lemma 2.2, the polynomial f g,l,a (x) satisfies (1) if and only if g > 1 and the quantity (2.2)

s g,l,a = (2g + 2) N a 2M -(-l) M (2g + 2 + l) N -M
is different from zero. Here d = gcd(2g + 2, l(q -1)), N = n/d and M = l(q -1)/d.

Remark 2.3. The last lemma immediately implies that, if q is odd, then, given an integer g ≥ g 1 q = p(q -1)/2 -1, there is a non-singular genus g curve over F p having no F q -points. This estimate is of the same order as the one in Theorem 1.4. Let us prove it now.

We want to show that there are a ∈ F * q and 1 ≤ l ≤ L(q, g) such that the curve y 2 = f g,l,a (x) is an F q -maximal smooth hyperelliptic curve over F p of genus g.

Choose an element of F * p , say a. If p | 2g + 2, then s g,l0,a = 0, when l 0 = 1. Assume that p does not divide 2g + 2. Since g ≥ g 1 q , we obtain L(q, g) ≥ p. Hence we can choose 1 ≤ l 0 ≤ L(q, g) such that l 0 ≡ -(2g + 2) mod p. It follows that s g,l0,a = 0. Thus, for any g ≥ g 1 q there is a number l 0 such that 1 ≤ l 0 ≤ L(q, g) and the polynomial f g,l0,a (x) is square free by Lemma 2.2.

It remains to apply Lemma 2.1.

We also note that this construction and some of those from the next section are related to the question of the existence of curves having no points of degree greater than one.

3. Proof of Theorem 1.6, the case of odd characteristic Along the section q stands for a power of an odd prime p. For such q the proof of Theorem 1.6 consists of several parts depending on the values of the parameters p, q, g, D(q, g), and L(q, g). We first treat the easy case, when D(q, g) > 2.

Proposition 3.1. Let g be such that g ≥ q-1 2 and D(q, g) > 2. Then there is a smooth F q -maximal hyperelliptic curve over F q of genus g of the form y 2 = f g,l,a (x).

Proof. Let us take l = 1 and suppose that for any a ∈ F * q the quantity s g,l,a is equal to zero. Then the value of a 2(q-1) D(q,g) = (-1) q-1 D(q,g) (2g + 3) 2g+2-(q-1) D(q,g)

(2g + 2) -2g+2 D(q,g)
does not depend on the choice of a. Since this identity holds for a = 1, we see that a 2(q-1)/D(q,g) is equal to 1 for every a ∈ F * q . It means that the order of every element of F * q divides 2(q -1)/D(q, g) < q -1, which is a contradiction. Hence there is some a ∈ F * q such that the polynomial f g,1,a (x) has no multiple roots and the curve y 2 = f g,1,a (x) is the desired one.

We would like to draw attention to the similarity between the following technical lemma and Theorem 1.5. Lemma 3.2. Let a ∈ F * q . Suppose that for some g ≥ max q-1 2 , 2 the quantities s g,l,a are equal to 0 for all 1 ≤ l ≤ L(q, g); then the equations (1 + lx) D(q,g) ≡ 1 mod p, 1 ≤ l ≤ L(q, g), have a common non-zero solution in F * p . Proof. Since s g,l,a = 0 for all l's, it follows from (2.2) that 2g + 2 ≡ 0 mod p, and for each l there is an identity

(2g + 2) 2g+2 d a 2 l(q-1) d ≡ (-l) l(q-1) d (2g + 2 + l) 2g+2-l(q-1) d mod p,
where d = gcd(2g + 2, l(q -1)). After rising to power d both of its sides and some evident transformation, we get

(1 + (2g + 2) -1 l) 2g+2 ≡ 1 mod p,
for each l, and since 1 + (2g + 2) -1 l is an element of F * q , it is equivalent to (1 + (2g + 2) -1 l) gcd(2g+2,q-1) = (1 + (2g + 2) -1 l) D(g,q) ≡ 1 mod p, for every 1 ≤ l ≤ L(q, g).

In the case of odd p we show below that if g ≥ max {(q -1)/2, 2}, D(q, g) = 2 or g = (q -3)/2, p > 5, then there is a non-singular F q -maximal hyperelliptic genus g curve defined over the prime field F p . The proposition below shows that if the parameter D(q, g) takes the minimal possible value and L(q, g) ≥ 2, then one can choose a suitable 1 ≤ l ≤ 2. Proposition 3.3. Let g be an integer such that g ≥ max q-1 2 , 2 , let D(q, g) = 2 and L(q, g) ≥ 2. Then there is a smooth F q -maximal hyperelliptic curve over F p of genus g of the form y 2 = f g,l,a (x).

Proof. Chose any a ∈ F * p . Suppose that s g,l,a = 0 for all 1 ≤ l ≤ L(q, g). According to Lemma 3.2, there is a system of at least two equations :

(1 + x) 2 = 1, (1 + 2x) 2 = 1, . . .
which has a solution in F * p , say x 0 . It is obvious that x 0 ≡ -2 mod p is the unique solution of the first equation, but x 0 does not satisfy the second equation. It means that the system has no solutions in F * p , and s g,l,a = 0 for some l. It is clear that one can let either l = 1 or l = 2. Hence it is possible to construct a curve with desired properties, using either f g,1,a (x) or f g,2,a (x). Remark 3.4. As a direct corollary of Propositions 3.1, 3.3 and Lemma 2.1 we obtain a linear bound on the genus as follows. Suppose g ≥ max {q -2, 2}; then L(q, g) ≥ 2, so there is a smooth pointless genus g curve over F q . This refines [2, Corollary 2.9]. However, our goal is to prove a stronger bound.

The only possibility that remains to be treated is L(q, g) = 1, D(q, g) = 2. Proposition 3.5. Let g be such that g ≥ max {(q -1)/2, 2}, D(q, g) = 2, and L(q, g) = 1. Assume that at least one of the following conditions holds :

(1) q is a square, (2) q = p 2n+1 and p ≡ 1 mod 8, (3) g is not of the form p(2k+1)-5

4

, k ≥ 0.

Then there is a non-singular F q -maximal hyperelliptic curve over F p of genus g of the form y 2 = f g,l,a (x).

Proof. We want to show that under these assumptions s g,1,a ≡ 0 mod p for some a ∈ F * p . If g is such that p divides 2g + 2, then s g,1,a ≡ 0 mod p by its definition. We can therefore assume that 2g + 2 ≡ 0 mod p. In this case it follows from (2.2) that

s g,1,a = (2g + 2) N a 2M -(-1) M ((2g + 2) + 1) N -M = (2g + 2) N -(-1) M (2g + 2) N -M 1 + (2g + 2) -1 N -M ,
where N = g + 1 and M = (q -1)/2. Thus the value of a does not affect s g,1,a , i.e. s g,1,a coincides with s g,1,1 for any a ∈ F * q . Suppose that s g,1,1 is zero; then (1 + (2g + 2) -1 ) 2 ≡ 1 mod p by Lemma 3.2. This implies 2g + 2 ≡ (-2) -1 mod p. Hence, if g = p(2k+1)-5 4 for any integer k ≥ 0, then s g,1,1 = 0.

Let us assume that (1 + (2g + 2) -1 ) 2 ≡ 1 mod p. We put

S = (-1) M +1 2 N s g,1,1 = (-1) M +1 2 N (-1) N 2 -N -(-1) M 2 M -N = (-1) N +M +1 + 2 M .
It equals zero simultaneously with s g,1,1 . Also, note that N and M can not be even at the same time, since gcd(N, M ) = gcd(g + 1, (q -1)/2) = D(q, g)/2 = 1.

Consider several cases. If q is a square, then every element of F p is a quadratic residue in F q . Since M = (q -1)/2 is even, we see that N + M + 1 is even. Thus S = 2 is not equal to zero, since p > 2. Therefore, s g,1,1 = 0. Suppose q is not a square, then S depends on the congruence class of p modulo 8. It is well known that every quadratic (non) residue in F p remains one in F q . Using this fact and the fact that if M is even, then N must be odd, we find that

S = 2 (q-1)/2 -(-1) (q-1)/2 (-1) g+1 =         

2,

p ≡ 1 mod 8, -1 + (-1) g+1 , p ≡ 3 mod 8, 0, p ≡ 5 mod 8, 1 + (-1) g+1 , p ≡ 7 mod 8.

This formula immediately implies that s g,1,1 = 0 when p ≡ 1 mod 8.

Further study of curves of type (2.1) is not fruitful. We finish our proof of Theorem 1.6 in the case of odd characteristic taking into account hyperelliptic curves of different forms.

However, let us first assume that q is prime. This assumption allows to consider a special type of curves which is easier to work with. In particular, applying Lemma 2.1 to the following result, one can omit the restriction in [2, Theorem 1.3].

Theorem 3.6. Let g be an integer such that g ≥ max p-1 2 , 2 . Then there exists a non-singular F p -maximal hyperelliptic genus g curve over F p of one of the following forms :

y 2 = f g,l,a (x) or y 2 = x p+(p-1)/2 + x p-1 + x (p-3)/2 + 1.
Proof. If D(p, g) > 2 or L(q, g) > 1, then Propositions 3.1 and 3.3 can be applied. Assume that D(p, g) = 2 and L(q, g) = 1. Then

(3.1) p -1 2 ≤ g < p -2.
Let g be an integer such that g = (p(2k + 1) -5)/4 for some k ≥ 0. It follows from the formula (3.1) that k = 1, i.e. g = (3p -5)/4. Note that deg F (x) = 2g + 2. Suppose that p ≡ 5 mod 8; then the number g is not integer. Thus Proposition 3.5 can be applied.

We are left with the case p ≡ -1 mod 4. We can assume that p > 3. Consider a curve y 2 = F (x) over F p , where F (x) = x p+(p-1)/2 + x p-1 + x (p-3)/2 + 1. Let us show that F (x) has no multiple roots in F p . We first note that the following identities hold :

F (x) + 2xF (x) = r 1 (x) = -x p-1 -2x (p-3)/2 + 1, 2F (x) -x (p-1)/2 r 1 (x) = r 2 (x) = -x (p-5)/2 (x 2 + 3).
Now, suppose that F (x) has a multiple root, say α. Then we see that α 2 = -3, since r 2 (α) = 0 and α = 0. We also obtain

-α 2 r 1 (α) = α (p+1)/2 2 + 2α (p+1)/2 + 3 = 0.
This equation implies α (p+1)/2 = -1 ± √ -2. Furthermore, we can compute α (p+1)/2 4 in two different ways :

α (p+1)/2 4 = (-1 ± √ -2) 4 = -7 ± 4 √ -2 = α 2 p+1 = 9.
Hence the equality √ -2 = 4 holds for the field F p , but this is not possible whenever p > 3. Therefore, we have a contradiction and the polynomial F (x) satisfies [START_REF] Anbar | Curves of Every Genus With a Prescribed Number of Rational Points[END_REF].

The polynomial F (x) also satisfies [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]. Indeed, for any x ∈ F * p we have

F (x) = χ p (x)x + 2 + χ p (x)x -1 = χ p (x)x -1 (1 + χ p (x)x) 2 .
Since χ p (-1) = -1, it follows that χ p (χ p (x)x -1 ) = 1 for any x ∈ F * p . Regardless of the value of χ p (x), we obtain χ p (F (x)) = 1 for any x ∈ F p .

Thus, the curve y 2 = F (x) is a non-singular F p -maximal genus g hyperelliptic curve over F p . Remark 3.7. By the same method one can show that if q is not a prime such that q ≡ -1 mod 4, then the curve y 2 = x q+(q-1)/2 + x q-1 + x (q-3)/2 + 1 is smooth and F q -maximal. However, this construction does not allow to obtain the desired bound on the genus.

In order to get the bound g ≥ max q-1 2 , 2 for odd q, we prove that if q is neither a square nor a prime and g is such that (3.2) (q -1)/2 ≤ g < q -2, gcd(2g + 2, q -1) = 2 and 2g + 2 ≡ -1/2 mod p, then there exists a non-singular genus g pointless curve over F q . Now, we concentrate our attention only on this case.

Consider the following family of hyperelliptic curves :

(3.3) y 2 = F n,b,ξ (x) = x q-1+n + b 2 x 2n -(2b 2 ξ + 1)x n + b 2 ξ 2 .
Let b, ξ ∈ F * p , χ p (ξ) = -1, and let n be an even number. Under these assumptions the polynomial F n,b,ξ (x) satisfies [START_REF] Becker | Pointless Hyperelliptic Curves[END_REF]. Indeed, we see that χ q (F n,b,ξ (x)) = 1 for any x ∈ F q , since F n,b,ξ (x) = (x q-1 -1)x n + b 2 (x n -ξ) 2 . Suppose that (1) holds for F n,b,ξ (x). Then the hyperelliptic curve (3.3) over F p is smooth F q -maximal of genus

g = (q -3 + n)/2, n is even and 0 < n < q -1, n -1, n ≥ q -1.
Recall that g must satisfy (3.2), so we have the following restrictions on n :

(3.4) n even, 0 < n < q -1, gcd(n, q -1) = 2 and n ≡ 1/2 mod p.

Let us show that for such n there are b and ξ in F p such that F n,b,ξ (x) satisfies both (1) and (2). Our proof of this fact splits into two steps depending on p.

Lemma 3.8. Suppose that p is either 3 or 5. Let n be such that n ≡ 1/2 mod p.

There are b, ξ ∈ F * p , χ p (ξ) = -1, such that F n,b,ξ (x) has no multiple roots in F p . Proof. Case p = 3. There is just one polynomial of the desired form over F p :

F (x) = F n,±1,-1 (x) = x q-1+n + x 2n + x n + 1.
Let α ∈ F p be a multiple root of F (x). Since n ≡ 2 mod 3, we have

xF (x) = x q-1+n + x 2n -x n .
Note that F (α) -αF (α) = 2α n + 1 = 0, so α n = 1. However, F (α) = α q-1+n + α 2n + α n + 1 = α q-1 = 0, so we get a contradiction. Thus F (x) is square free.

Case p = 5. One of the following polynomials is square free :

F n,1,2 (x) = x q-1+n + x 2n -1, F n,2,-2 (x) = x q-1+n -x 2n + 1.
The Theorem 4 in [START_REF] Greenfield | On the Discriminant of a Trinomial[END_REF] (see Section 2) implies that a trinomial x q-1+n ± x 2n ∓ 1 is square free if and only if

S ± = (q -1 + n) N (∓1) N -K -(-1) N (q -1 -n) N -K (2n) K (±1) N
is non-zero, where d = gcd(q -1 + n, 2n), N = (q -1 + n)/d and K = 2n/d. By the assumption on n we have n ≡ -2 mod 5 and

S + = 2 N (-1) N -K -(-1) N = (-1) N -K (2 N -(-1) K ), S -= 2 N -1.
Suppose S -equals zero. Then, since p = 5, we see that 4 divides N . Note that gcd(N, K) = 1, thus K is odd. Hence S + = 0 and the lemma is proven. Proposition 3.9. Let q be not a square. Let g be an integer satisfying (3.2). Then there exists a non-singular F q -maximal hyperelliptic curve over F p of genus g of the form y 2 = F n,b,ξ (x).

Proof. Take an integer n satisfying (3.4) such that q -1 + n = 2g + 2. Take b, ξ ∈ F * p , χ p (ξ) = -1. As we showed above, the polynomial F n,b,ξ (x) satisfies (2). Our goal is to prove that b can be chosen in a manner that F n,b,ξ (x) is a square free polynomial, i.e. satisfies [START_REF] Anbar | Curves of Every Genus With a Prescribed Number of Rational Points[END_REF]. According to Lemma 3.8, we can assume that p > 5.

Let α ∈ F q be a multiple root of F n,b,ξ (x) = x q-1+n + b 2 x 2n -(2b 2 ξ + 1)x n + b 2 ξ 2 . Then α is a root of the following polynomials (recall that n ≡ 1/2 mod p) :

-2xF n,b,ξ (x) = x q-1+n -2b 2 x 2n + (2b 2 ξ + 1)x n , r(x) = F n,b,ξ (x) + 2xF n,b,ξ (x) = 3b 2 x 2n -2(2b 2 ξ + 1)x n + b 2 ξ 2 .
By evident computations we have

α n = 2b 2 ξ + 1 ± b 4 ξ 2 + 4b 2 ξ + 1 3b 2 , (3.5) α q-1 = 2b 2 α n -(2b 2 ξ + 1) = - 1 3 (2b 2 ξ + 1) ± 2 3 b 4 ξ 2 + 4b 2 ξ + 1. (3.6)
Let us show that b can be chosen inside F * p in the way that

χ p (b 4 ξ 2 + 4b 2 ξ + 1) = 1.
We need to show that there is such s in

α n = (2t + 1) ± s 3b 2 , α q-1 = -(2t + 1) ± 2s 3 .
are elements of F p . It easily follows that α gcd(n,q-1) = α gcd(2g+2,q-1) = α 2 is in F * p , and α q-1 = (α 2 ) (q-1)/2 = ±1. Taking into account (3.7) and (3.8) we obtain 4s 2 = ((2t + 1) + 3α q-1 ) 2 = ((2t + 1) ± 3) 2 = 4t 2 + 4t + 10 ± (12t + 6).

By the assumption (b, s) is a solution of (3.7), so that 4s 2 = 4t 2 + 4t + 10 ± (12t + 6) = 4t 2 + 16t + 4.

It follows that either 12 ≡ 0 mod p or -24t ≡ 0 mod p. Thus we get a contradiction, since p > 5 and b ∈ F * p .

The last ingredient in the case of odd q is the following result which refines [2, Lemma 2.1]. Proposition 3.10. Let q > 5. There is an F q -maximal non-singular curve over F q of genus q-3 2 of the form

y 2 = x q-1 + 2 α -β α + β x q-1 2 + 1,
where α, β ∈ F * q such that χ q (α) = χ q (β) = χ q (α + β) = 1. Proof. It is easy to see that if q > 5, then there are three non-zero quadratic residues α, β, γ in F q such that γ = α + β. Indeed, let γ = δ 2 , δ ∈ F * q . It is well known that the curve x 2 + y 2 = γ has q + 1 ≥ 8 rational points over F q . In particular, it has two points at infinity, and four affine points (±δ, 0) and (0, ±δ). Therefore, the curve has at least two affine points (a, b) such that ab = 0. Thus, there are α, β

∈ F * q 2 such that α + β = γ. Let F (x) = α γ (x q-1 2 + 1) 2 + β γ (x q-1 2 -1) 2 .
It is easy to see that the conditions (1) and ( 2) hold for this polynomial. Indeed, we have

F (x) = x q-1 2 2 + 2 α -β γ x q-1 2 + 1.
It has a repeated root if and only if α-β α+β = ±1. Therefore, F (x) satisfies (1), since α and β are both non-zero. For any a ∈ F * q we see that F (a) is either 4α/γ or 4β/γ, which are both non-zero quadratic residues. Therefore, χ q (F (a)) = 1 for any a ∈ F q , so that (2) holds.

As a consequence, if q > 5, then a hyperelliptic curve y 2 = F (x) over F q is a smooth F q -maximal curve of genus q-3 2 . Hence the result.

Remark 3.11. Using the same arguments, one can prove that if p > 5 and q = p n , then there are α, β, γ in F * p such that γ = α + β and χ p (α) = χ p (β) = χ p (γ) = 1. Define F (x) as in the last proposition. Then the curve y 2 = F (x) is defined over F p , has no singular points and is F q -maximal. This construction gives an F q -maximal curve defined over the prime field F p , however, it requires the restriction p > 5 on the characteristic of the field F q . Now, if q is odd, then Propositions 3.1, 3.3, 3.5, 3.9 and 3.10 imply that for any g ≥ g q (with the constant g q defined in the statement of Theorem 1.6) there exists a non-singular F q -maximal genus g hyperelliptic curve over F q . In order to finish the proof of Theorem 1.6 in the case of odd characteristic, one applies Lemma 2.1.

Proof of Theorem 1.6, the case of even characteristic

Finally, it remains to prove the result in the case when q is even. The existence of pointless curves over F 2 is already known. It follows from the part (i) of Proposition 4.1 in [START_REF] Stichtenoth | Curves with a Prescribed Number of Rational Points[END_REF] that for every g ≥ 2 there is a pointless smooth genus g curve over F 2 . In other cases, when q is even and q > 2, we have the following result. Proposition 4.1. Let q = 2 n , q > 2. For every g ≥ q -1 there is a pointless non-singular genus g curve over F q of the form y 2 + a(x g+1 + x g+1-(q-1) + c)y = b(x 2g+2 + x 2g+2-2(q-1) + d) for some a, b, c, d ∈ F * q .

Proof. Let C be the projective curve defined by the affine equation

y 2 + af (x)y = bh(x),
where a, b ∈ F * q and f (x) = x g+1 + x g+1-(q-1) + c, h(x) = x 2g+2 + x 2g+2-2(q-1) + d.

Recall that a curve y 2 + Q(x)y = P (x) over a finite field of characteristic 2 is non-singular (as a projective curve) if only and only if the polynomials Q(x) and R(x) = Q (x) 2 P (x) + P (x) 2 are coprime (see Section 2).

Assume that c, d in F * q are such that c 2 = d. Then it is easy to see that the curve C is smooth. Indeed, we have R(x) = a 2 bf (x) 2 h(x) + b 2 h (x) 2 . Note that h (x) = 0 and f (x) is a monomial, which is obviously prime to f (x). Thus we have gcd(R(x), af (x)) = gcd(h(x), f (x)). Since h(x) = f (x) 2 + c 2 + d, where c 2 + d = 0 (by the assumption), we see that f (x) and h(x) are coprime. Hence gcd(R(x), af (x)) = 1, so that C is a smooth curve of genus g over F q .

Remark that the choice of a and b does not affect the smoothness of the curve C. We can therefore use this fact to obtain a pointless curve.

As it was explained in Section 2, the curve C is the union of two affine curves y 2 + af (x)y = bh(x) and y 2 + ax g+1 f (1/x) = bx 2g+2 h(1/x).

The set of rational points of the curve C is the disjoint union of the set of rational points of the first affine curve and the set of rational points of the second one having x = 0. Hence any rational point of C corresponds to a solution of either y 2 + acy + bd = 0 or y 2 + ay + b = 0 over F q . These equations are, obviously, equivalent to y 2 + y + bd(ac) -2 = 0 and y 2 + y + ba -2 = 0 respectively. Recall that by the Hilbert'90 theorem the equation y 2 + y + α = 0 has no solutions in F q if and only if Tr Fq/F2 α = 1. Thus, the curve C has no rational points if and only if Since q > 2, there are two distinct elements in F q , say α and β, such that Tr Fq/F2 α = Tr Fq/F2 β = 1. Let b = a 2 α and d = c 2 β α . It is clear that c 2 = d and the conditions (4.1) hold. Thus C is a smooth curve of genus g having no rational points. Now, the goal of the paper is achieved and Theorem 1.6 is proven. Remark 4.2. As we have already written, H. Stichtenoth in [8, Section 4] considered the case q = 2. He showed that for any g ≥ 2 a genus g curve over F 2

y 2 + y = x 2 + x f (x) + 1,
where f (x) ∈ F 2 [x] is an irreducible polynomial of degree g + 1, has no rational points. By slightly modifying this construction, N. Anbar reproved this result in [1, Section 5]. Motivated by this, we note that a lot of examples of pointless curves can be easily obtained by means of the Artin-Schreier curves for arbitrary q. More precisely, their constructions can be generalized almost verbatim as follows.

Let u(x) and v(x) be monic polynomials of degree n + 1 having no roots in F q . Suppose that v(x) is irreducible. Then the Artin-Schreier curve (4.2)

y q -y = u(x) v(x)
is a non-singular curve over F q . By [1, Lemma 2.1] it is has genus (q -1)n. This curve is pointless, since u(x) v(x) = 0 and x n+1 u(1/x) x n+1 v(1/x) = 0 for any x ∈ F q . This shows that for any prime power q there is a smooth pointless curve over F q of arbitrary large genus g divisible by q -1. This result is weaker than Theorem 1.6 unless q = 2 (since in that case an Artin-Schereier curve is hyperelliptic). It seems hard to obtain better results using the Artin-Schreier coverings of the projective line.

s 2 = b 4 ξ 2 + 4b 2 ξ + 1 .

 221 Since p > 5, the equation defines an elliptic curve over F p . It has two points at infinity, two points with b = 0, and no more than two points with s = 0. According to Hasse-Weil bound, the curve (3.7) has at least p + 1 -2 √ p rational points.Thus, when p > 11, this curve has at least 7 points. In the cases p = 7 or 11 one can let ξ = -1. Then the curve (3.7) has four points with b = ±1/2 and s = ±1/4. Hence, given ξ ∈ F * p such that χ p (ξ) = -1, there is an admissible value for b in F * p . Let (b, s) be a rational point of the curve (3.7) such that bs = 0. Put t = b 2 ξ. Let us remark that(3.8)