%plain TeX
\normalbaselineskip=1.6\normalbaselineskip\normalbaselines
\magnification=1200
\def\max{\mathop{\rm max}}
\def\min{\mathop{\rm min}}
\def\rk{\mathop{\rm rk}}
\def\uple#1{(#1_1,\ldots,#1_n)}
\def\puple#1{(#1_1:\ldots:#1_n)}
\def\pmb#1{\setbox0=\hbox{#1}%
 \kern-.025em\copy0\kern-\wd0
 \kern.05em\copy0\kern-\wd0
 \kern-.025em\raise.0433em\box0 }
\def\w{\pmb{$\omega$}}
\def\Gm{{\bf G}_m}
\def\ra{\rightarrow}
\def\Z{{\bf Z}}
\def\topn{\buildrel{p^n}\over\to} 
\def\Q{{\bf Q}}
\def\C{{\bf C}}
\def\F{{\bf F}}
\def\zmp{\Z/p\Z}
\def\O{{\cal O}}
\def\isom{\cong}
\def\Ext{\mathop{\hbox{Ext}}}
\def\mod{\mathop{\rm mod}\nolimits}
\def\Qp{{\bf Q}_p}
\def\Qpb{\bar{\bf Q}_p}
\def\Cp{{\bf C}_p}
\def\P{{\bf P}}
\def\Hom{\mathop{\rm Hom}\nolimits}
\def \H{{\cal H}}
\def \X{{\cal X}}
\def\Spec{\mathop{\rm Spec}\nolimits}
\def \bs{\bigskip}
\def\Gal{\mathop{\rm Gal}\nolimits}
\def\End{\mathop{\rm End}\nolimits}
\def\limproj{\mathop{\oalign{\hfil$\rm lim$\hfil\cr
 $\longleftarrow$\cr}}}
\def \L{\Lambda}
\def\bk{\bar{k}}
\def \ra{\rightarrow}
\def \op{\frac{1}{p}}
\def \st{\stackrel}
\def \da{\downarrow}
\def \R{{\bf Rings}}
\def \d{\delta}
\def \s{\sigma}
\def \a{\alpha}
\def \b{\beta}
\def \x{\chi}
\def \t{\tau}
\def \z{\zeta}
\def \con{\equiv }
\def \e{\epsilon}
\def \bC{\bar{C}}
\def \bX{\bar{X}}
\def \k{\kappa}
\def \bF{{\bar{\bf F}}_p}

\centerline{\bf Jacobians of curves over finite fields}
\medskip
\centerline{\bf Jos\'e Felipe Voloch}
\bs

Let $C/\F_q$ be a curve over a finite field of genus $g$ at least two.
Assume $C$ has a rational point $P_0$ and consider $C$ embedded in its
Jacobian $J$ by sending $P_0$ to $0 \in J$. So $C(\F_q) \subset J(\F_q)$
and we can consider the subgroup $G$ of $J(\F_q)$ generated by $C(\F_q)$.
If $G$ is not the whole of $J(\F_q)$ we will show that we can construct
an \'etale cover of $C$ where every $\F_q$-rational point of $C$ splits
completely into $\F_q$-rational points.
We will prove that, if $q$ is large enough compared to $g$, then $G=J(\F_q)$
and will give examples showing that this equality does not always hold and
these examples will lead to curves over finite fields with many rational points.

\proclaim Theorem. Notation as above, if $q \ge (8g-2)^2$ then $G=J(\F_q)$.

Before proving the theorem, we need a lemma.

\proclaim Lemma. Let $A$ be an abelian group and $\a$ a surjective endomorphism
of $A$. Let $G$ be a subgroup of $\ker \a$ and $\phi : A \to A/G$ the canonical
map and $\b : A/G \to A/G$ the endomorphism induced by $\a$. Finally, let
$\psi: A/G \to A$ be the unique homomorphism such that $\a = \psi \circ \phi$.
Then $\psi(\ker \b) = G$.

{\it Proof:} By construction, $\b \circ \phi = \phi \circ \a$, that is,
$\b(y) = \phi(\a(x))$ for any $x, \phi(x) = y$. Also, $\psi$ is defined
by $\psi(y) = \a(x)$ for any $x, \phi(x) = y$, that is $\a = \psi \circ \phi$.
We also have $\b = \phi \circ \psi$. Indeed, given $y \in A/G$ and 
$x, \phi(x) = y$, we have $\b(y) = \b(\phi(x)) = \phi(\a(x)) =
\phi(\psi(y))$. It follows that $\psi(\ker \b) \subset \ker \phi = G$.
On the other hand, given $x \in \ker \phi$, we can write $x = \a(y), y \in A$.
Then $\b(\phi(y)) = \phi(\a(y)) = \phi(x) = 0$, so $\phi(y) \in \ker \b$ and
therefore $x = \psi(\phi(y)) \in \psi(\ker \b)$, which proves that 
$G \subset \psi(\ker \b)$, proving the lemma.

\medskip

{\it Proof of the Theorem:} We apply the lemma with $A = J({\bar \F_q})$ and
$\a = 1-F$, where $F$ is the $\F_q$-Frobenius and $G$ the group generated
generated by $C(\F_q)$. So $J/G = B$ is an abelian variety and $\psi: B \to J$
is an isogeny of degree $n = [J(\F_q):G]$. 
Note that $\b$, as in the lemma, equals $1-F$, where $F$ 
is the $\F_q$-Frobenius on $B$, which follows since $J$ and $\phi$ are defined
over $\F_q$. Thus $\ker \b = B(\F_q)$ and, by the lemma, $\psi(\ker \b) = G$.
Let $C'$ be the pull-back of $C$ under $\psi$, so $C'$ is an \'etale cover of
$C$ of degree $n$ defined over $\F_q$. (In fact, $C'$ is the maximal \'etale
abelian cover of $C$ defined over $\F_q$ in which every rational point of
$C$ splits). Also, since $C(\F_q) \subset G =
\psi(B(\F_q))$, we get that $\psi^{-1}(C(\F_q)) \subset C' \cap B(\F_q) = C'(\F_q)$.
Therefore $\# C'(\F_q) \ge n\# C(\F_q)$. We now use the Riemann hypothesis for
curves over finite fields to estimate these cardinalities.
$\# C(\F_q) \ge q+1 -2gq^{1/2}$ and $\# C'(\F_q) \le q+1 +2g'q^{1/2}$, where
$g'$ is the genus of $C'$ and, by the Hurwitz formula $g' = n(g-1) + 1$.
Combining these inequalities we obtain
$q+1 +2(n(g-1) + 1)q^{1/2} \ge n(q+1 -2gq^{1/2})$ which gives
$n(q+1-2(2g-1)q^{1/2}) \le q+1 +2q^{1/2}$. Finally, this last inequality,
combined with the hypothesis $q \ge (8g-2)^2$, give $n < 2$, so $n=1$ and
we are done.

{\it Remark:} H. Lenstra has pointed out that, making use of the fact that
the zeta function of $C$ divides the the zeta function of $C'$ in the
above proof, one can get the improved bound $q < (4g-2)^2$ in the
conclusion of the theorem.


As mentioned above, examples where the theorem's conclusion does not
hold will give examples of curves with many rational points.

Consider the Hermitian curve 
$C: x^{q+1}+y^{q+1}=1$ over $\F_q$. As is well known, this curve attains the
upper bound given by the Riemann hypothesis over $\F_{q^2}$, namely it has
genus $g=q(q-1)/2$ and $q^3+1$ points over $\F_{q^2}$. This means that all
eigenvalues of Frobenius over $\F_{q^2}$ are equal to $-q$. Hence the
eigenvalues of Frobenius over $\F_{q^4}$ are equal to $q^2$. It follows that
$C$ has $q^4 + 1 -q(q-1)q^2 =q^3+1$ points over $\F_{q^4}$, 
that is $C(\F_{q^2})=C(\F_{q^4})$.
As for the Jacobian $J$, Frobenius acts as $-q$ over $\F_{q^2}$ so
$J(\F_{q^2})=J[q+1]$, the $q+1$-torsion. Similarly, 
$J(\F_{q^4})=J[q^2-1]$, which is bigger than the group generated by
$C(\F_{q^4})=C(\F_{q^2})$, since the latter is contained in $J(\F_{q^2})$.
For any subgroup $G$ of $J(\F_{q^4})$ containing $J(\F_{q^2})$ we can apply
the construction of the proof of the theorem and obtain an \'etale cover
of $C$ of degree $n=[J(\F_{q^4}):G]$ with at least $n(q^3+1)$ rational points
over $\F_{q^4}$ and genus $n(g-1)+1$, and we can take $n$ to be any divisor of
$(q-1)^{2g}$.

For a numerical example take $q=3$, so $g = 3$ and for any divisor 
$n$ of $2^6$ we get a curve of genus $2n+1$ over $\F_{81}$ with $28n$ rational
points. Or take $q=4$, so $g=6$ and for any divisor $n$ of $3^{12}$ we get 
a curve of genus $5n+1$ over $F_{256}$ with $65n$ rational points.
There are no known curves with more points with same parameters for the larger
values of $n$, according to the tables in [Sh]. These curves get very close
to the best-known upper bounds for the given parameters, which are obtained
by Oesterl\'e's method. For example, the case $q=3,n=64$ gives a curve
with $1792$ points over $\F_{81}$ and Oesterl\'e's bound is $1897$.
The case $q=4,n=531441$ gives a curve with $34543665$ points over $F_{256}$
and Oesterl\'e's bound is $46069115$.

Another example is the Suzuki curve $y^q-y=x^{q_0}(x^q-x)$, where
$q=2^{2m+1},q_0=2^m, m \ge 1$ (see [H]). This curve has $q^2+1$ points over
$\F_q$ and genus $g=q_0(q-1)$. The eigenvalues of Frobenius turn out to
be $2^m(-1 \pm i)$. It follows that the curve has also $q^2+1$ points over
$\F_{q^2}$, that is, $C(\F_{q})=C(\F_{q^2})$. 
The Jacobian has $(q+1+2q_0)^g$ rational points over $\F_q$
and $(q^2+1)^g$ rational points over $\F_{q^2}$. So we get by taking covers,
for any divisor $n$ of $(q+1-2q_0)^g=(q^2+1)^g/(q+1+2q_0)^g$, a curve of
genus $n(g-1)+1$ having $n(q^2+1)$ points over $\F_{q^2}$.

For a numerical example take $q=8$, so $g=14$ and for any divisor $n$ of 
$5^{14}$ we get a curve of genus $13n+1$ with $65n$ rational points
over $F_{64}$.
There are no known curves with more points with same parameters for the larger
values of $n$, according to the tables in [Sh].

A similar class of examples can be obtained from the Ree curves in characteristic 
three (see [P]).

The above examples can be used as first steps of class field towers 
(see [Sc]). Namely, we can consider, for a curve $C$ the cover $C'$
given by the construction in the theorem, then apply the same construction
to $C'$ and get a cover $C''$ and so on. This construction may stop 
($C^{(k)}=C^{(k+1)}=\cdots$) or not. It follows from [Sc], theorem 2.3, that
the sequence will not stop if, for some prime $\ell$, the $\ell$-primary 
component of $J(\F_q)/G$ has rank at least $2+2\sqrt{\#C(\F_q)}$.
With the exception of finitely many values of $q$, the Hermitian, Suzuki and
Ree curves above will lead to infinite towers. These towers are good in the
sense that $\lim \#C^{(k)}(\F_q)/g^{(k)} > 0$, where $g^{(k)}$ is the genus
of $C^{(k)}$ but not optimal in the sense that the limit attains its maximum
value of $\sqrt{q} - 1$.

We can consider more general class field towers as follows (see [Sc]). Take a 
set $S$ of rational points of $C$ and consider the cover $C'$ which
is the maximal unramified abelian extension of $C$ where the points of $S$ split
completely, take for $S'$ the pullback of $S$ on $C'$ and repeat with
$C',S'$ instead of $C,S$. The first step can be described geometrically
as follows, if $P_0 \in S$.
Take the subgroup $G_S$ of $J(\F_q)$ generated by $S$, apply the
lemma to get an isogeny $\psi: A \to J$ with $\psi(A(\F_q)) = G_S$ and
take $C'$ as the pullback of $C$ under $\psi$.
That this construction gives the maximal such extension follows from
Rosenlicht's geometric class field theory (see [Se]).
Let us call such a set $S$ saturated if for any $S_1, S \subset S_1 \subset
C(\F_q)$, if $G_S=G_{S_1}$, then $S=S_1$. For example $S=\{P_0\}$ or $C(\F_q)$
are saturated. We would like to point out the following.
If $S$ is saturated, then $S' = C'(\F_q)$.
Indeed, the points of $S'$ are rational by construction. On the
other hand, $C'(\F_q) = C' \cap A(\F_q)$ so $\psi(C'(\F_q))  \subset G_S$
and since $S$ is saturated, $\psi(C'(\F_q)) = S$, which gives the result.

In [ADH], Adleman et al. propose an algorithm for solving the discrete
logarithm problem on Jacobians of hyperelliptic curves of high genus.
In the algorithm they assume, but not prove, that the set of rational points
of the Jacobian can be generated by the image of prime divisors of small
degree (their set $G$, see [ADH], \S 6). From the theorem above, if
$q^r \ge (8g-2)^2$, then $X(\F_{q^r})$ generates $J(\F_{q^r})$ and it follows
immediately that the set of prime divisors of degree dividing $r$ generate
$J(\F_q)$.

\bigskip

{\bf Acknowledgements:}The author would like to thank J. Tate and M. Zieve
for comments and K. Lauter and V. Shabat for computing the upper bounds 
by Oesterl\'e's method mentioned above.
The author would also like to thank the TARP (grant \#ARP-006) and
the NSA (grant MDA904-97-1-0037) for financial support.

\bigskip
\centerline{\bf References.}
\bigskip
\noindent
[ADH] Adleman, L. M., DeMarrais, J. and Huang, M.-D.,
{\it A subexponential algorithm for discrete logarithms over the rational
subgroup of the Jacobians of large genus hyperelliptic curves over finite fields},
in {\it Algorithmic number theory}, Lecture Notes in Comput.
Sci., {\bf 877}, Springer, Berlin, 1994, pp. 28--40.
\medskip
\noindent
[H] Hansen, J.P., {\it Deligne-Lusztig varieties and group
codes}, Springer Lect. Notes Math. {\bf 1518}, 63--81 (1992).
\medskip
\noindent
[P] Pedersen, J.P.,{\it A function field related to the Ree group},
Springer Lect. Notes Math. {\bf 1518}, 122--131 (1992).
\medskip
\noindent
[Sc] Schoof, R.,{\it Algebraic curves over $\F_2$ with many
rational points}, J. Number Theory {\bf 41} (1992), 6--14. 
\medskip
\noindent
[Se] Serre, J.-P.,{\it Groupes alg\'ebriques et corps de classes}, Hermann,
Paris, 1959.
\medskip
\noindent
[Sh] Shabat, V., {\it Tables of curves with many points}, 
available at\hfil\break
{\tt http://turing.wins.uva.nl/{\~{ }}shabat/tables.html}
\medskip
\noindent
Dept. of Mathematics, Univ. of Texas, Austin, TX 78712, USA
\smallskip
\noindent
e-mail: voloch@math.utexas.edu



\end