Let ${{\bf F}_q}$ be a finite field of order ${q = p^n}$, and let ${C}$ be an absolutely irreducible smooth projective curve defined over ${{\bf F}_q}$ (and hence over the algebraic closure ${k := \overline{{\bf F}_q}}$ of that field). For instance, ${C}$ could be the projective elliptic curve

$\displaystyle C = \{ [x,y,z]: y^2 z = x^3 + ax z^2 + b z^3 \}$

in the projective plane ${{\bf P}^2 = \{ [x,y,z]: (x,y,z) \neq (0,0,0) \}}$, where ${a,b \in {\bf F}_q}$ are coefficients whose discriminant ${-16(4a^3+27b^2)}$ is non-vanishing, which is the projective version of the affine elliptic curve

$\displaystyle \{ (x,y): y^2 = x^3 + ax + b \}.$

To each such curve ${C}$ one can associate a genus ${g}$, which we will define later; for instance, elliptic curves have genus ${1}$. We can also count the cardinality ${|C({\bf F}_q)|}$ of the set ${C({\bf F}_q)}$ of ${{\bf F}_q}$-points of ${C}$. The Hasse-Weil bound relates the two:

Theorem 1 (Hasse-Weil bound) ${||C({\bf F}_q)| - q - 1| \leq 2g\sqrt{q}}$.

The usual proofs of this bound proceed by first establishing a trace formula of the form

$\displaystyle |C({\bf F}_{p^n})| = p^n - \sum_{i=1}^{2g} \alpha_i^n + 1 \ \ \ \ \ (1)$

for some complex numbers ${\alpha_1,\dots,\alpha_{2g}}$ independent of ${n}$; this is in fact a special case of the Lefschetz-Grothendieck trace formula, and can be interpreted as an assertion that the zeta function associated to the curve ${C}$ is rational. The task is then to establish a bound ${|\alpha_i| \leq \sqrt{p}}$ for all ${i=1,\dots,2g}$; this (or more precisely, the slightly stronger assertion ${|\alpha_i| = \sqrt{p}}$) is the Riemann hypothesis for such curves. This can be done either by passing to the Jacobian variety of ${C}$ and using a certain duality available on the cohomology of such varieties, known as Rosati involution; alternatively, one can pass to the product surface ${C \times C}$ and apply the Riemann-Roch theorem for that surface.

In 1969, Stepanov introduced an elementary method (a version of what is now known as the polynomial method) to count (or at least to upper bound) the quantity ${|C({\bf F}_q)|}$. The method was initially restricted to hyperelliptic curves, but was soon extended to general curves. In particular, Bombieri used this method to give a short proof of the following weaker version of the Hasse-Weil bound:

Theorem 2 (Weak Hasse-Weil bound) If ${q}$ is a perfect square, and ${q \geq (g+1)^4}$, then ${|C({\bf F}_q)| \leq q + (2g+1) \sqrt{q} + 1}$.

In fact, the bound on ${|C({\bf F}_q)|}$ can be sharpened a little bit further, as we will soon see.

Theorem 2 is only an upper bound on ${|C({\bf F}_q)|}$, but there is a Galois-theoretic trick to convert (a slight generalisation of) this upper bound to a matching lower bound, and if one then uses the trace formula (1) (and the “tensor power trick” of sending ${n}$ to infinity to control the weights ${\alpha_i}$) one can then recover the full Hasse-Weil bound. We discuss these steps below the fold.

I’ve discussed Bombieri’s proof of Theorem 2 in this previous post (in the special case of hyperelliptic curves), but now wish to present the full proof, with some minor simplifications from Bombieri’s original presentation; it is mostly elementary, with the deepest fact from algebraic geometry needed being Riemann’s inequality (a weak form of the Riemann-Roch theorem).

The first step is to reinterpret ${|C({\bf F}_q)|}$ as the number of points of intersection between two curves ${C_1,C_2}$ in the surface ${C \times C}$. Indeed, if we define the Frobenius endomorphism ${\hbox{Frob}_q}$ on any projective space by

$\displaystyle \hbox{Frob}_q( [x_0,\dots,x_n] ) := [x_0^q, \dots, x_n^q]$

then this map preserves the curve ${C}$, and the fixed points of this map are precisely the ${{\bf F}_q}$ points of ${C}$:

$\displaystyle C({\bf F}_q) = \{ z \in C: \hbox{Frob}_q(z) = z \}.$

Thus one can interpret ${|C({\bf F}_q)|}$ as the number of points of intersection between the diagonal curve

$\displaystyle \{ (z,z): z \in C \}$

and the Frobenius graph

$\displaystyle \{ (z, \hbox{Frob}_q(z)): z \in C \}$

which are copies of ${C}$ inside ${C \times C}$. But we can use the additional hypothesis that ${q}$ is a perfect square to write this more symmetrically, by taking advantage of the fact that the Frobenius map has a square root

$\displaystyle \hbox{Frob}_q = \hbox{Frob}_{\sqrt{q}}^2$

with ${\hbox{Frob}_{\sqrt{q}}}$ also preserving ${C}$. One can then also interpret ${|C({\bf F}_q)|}$ as the number of points of intersection between the curve

$\displaystyle C_1 := \{ (z, \hbox{Frob}_{\sqrt{q}}(z)): z \in C \} \ \ \ \ \ (2)$

and its transpose

$\displaystyle C_2 := \{ (\hbox{Frob}_{\sqrt{q}}(w), w): w \in C \}.$

Let ${k(C \times C)}$ be the field of rational functions on ${C \times C}$ (with coefficients in ${k}$), and define ${k(C_1)}$, ${k(C_2)}$, and ${k(C_1 \cap C_2)}$ analogously )(although ${C_1 \cap C_2}$ is likely to be disconnected, so ${k(C_1 \cap C_2)}$ will just be a ring rather than a field. We then (morally) have the commuting square

$\displaystyle \begin{array}{ccccc} && k(C \times C) && \\ & \swarrow & & \searrow & \\ k(C_1) & & & & k(C_2) \\ & \searrow & & \swarrow & \\ && k(C_1 \cap C_2) && \end{array},$

if we ignore the issue that a rational function on, say, ${C \times C}$, might blow up on all of ${C_1}$ and thus not have a well-defined restriction to ${C_1}$. We use ${\pi_1: k(C \times C) \rightarrow k(C_1)}$ and ${\pi_2: k(C \times C) \rightarrow k(C_2)}$ to denote the restriction maps. Furthermore, we have obvious isomorphisms ${\iota_1: k(C_1) \rightarrow k(C)}$, ${\iota_2: k(C_2) \rightarrow k(C)}$ coming from composing with the graphing maps ${z \mapsto (z, \hbox{Frob}_{\sqrt{q}}(z))}$ and ${w \mapsto (\hbox{Frob}_{\sqrt{q}}(w), w)}$.

The idea now is to find a rational function ${f \in k(C \times C)}$ on the surface ${C \times C}$ of controlled degree which vanishes when restricted to ${C_1}$, but is non-vanishing (and not blowing up) when restricted to ${C_2}$. On ${C_2}$, we thus get a non-zero rational function ${f \downharpoonright_{C_2}}$ of controlled degree which vanishes on ${C_1 \cap C_2}$ – which then lets us bound the cardinality of ${C_1 \cap C_2}$ in terms of the degree of ${f \downharpoonright_{C_2}}$. (In Bombieri’s original argument, one required vanishing to high order on the ${C_1}$ side, but in our presentation, we have factored out a ${\hbox{Frob}_{\sqrt{q}}}$ term which removes this high order vanishing condition.)

To find this ${f}$, we will use linear algebra. Namely, we will locate a finite-dimensional subspace ${V}$ of ${k(C \times C)}$ (consisting of certain “controlled degree” rational functions) which projects injectively to ${k(C_2)}$, but whose projection to ${k(C_1)}$ has strictly smaller dimension than ${V}$ itself. The rank-nullity theorem then forces the existence of a non-zero element ${P}$ of ${V}$ whose projection to ${k(C_1)}$ vanishes, but whose projection to ${k(C_2)}$ is non-zero.

Now we build ${V}$. Pick a ${{\bf F}_q}$ point ${P_\infty}$ of ${C}$, which we will think of as being a point at infinity. (For the purposes of proving Theorem 2, we may clearly assume that ${C({\bf F}_q)}$ is non-empty.) Thus ${P_\infty}$ is fixed by ${\hbox{Frob}_q}$. To simplify the exposition, we will also assume that ${P_\infty}$ is fixed by the square root ${\hbox{Frob}_{\sqrt{q}}}$ of ${\hbox{Frob}_q}$; in the opposite case when ${\hbox{Frob}_{\sqrt{q}}}$ has order two when acting on ${P_\infty}$, the argument is essentially the same, but all references to ${P_\infty}$ in the second factor of ${C \times C}$ need to be replaced by ${\hbox{Frob}_{\sqrt{q}} P_\infty}$ (we leave the details to the interested reader).

For any natural number ${n}$, define ${R_n}$ to be the set of rational functions ${f \in k(C)}$ which are allowed to have a pole of order up to ${n}$ at ${P_\infty}$, but have no other poles on ${C}$; note that as we are assuming ${C}$ to be smooth, it is unambiguous what a pole is (and what order it will have). (In the fancier language of divisors and Cech cohomology, we have ${R_n = H^0( C, {\mathcal O}_C(-n P_\infty) )}$.) The space ${R_n}$ is clearly a vector space over ${k}$; one can view intuitively as the space of “polynomials” on ${C}$ of “degree” at most ${n}$. When ${n=0}$, ${R_0}$ consists just of the constant functions. Indeed, if ${f \in R_0}$, then the image ${f(C)}$ of ${f}$ avoids ${\infty}$ and so lies in the affine line ${k = {\mathbf P}^1 \backslash \{\infty\}}$; but as ${C}$ is projective, the image ${f(C)}$ needs to be compact (hence closed) in ${{\mathbf P}^1}$, and must therefore be a point, giving the claim.

For higher ${n \geq 1}$, we have the easy relations

$\displaystyle \hbox{dim}(R_{n-1}) \leq \hbox{dim}(R_n) \leq \hbox{dim}(R_{n-1})+1. \ \ \ \ \ (3)$

The former inequality just comes from the trivial inclusion ${R_{n-1} \subset R_n}$. For the latter, observe that if two functions ${f, g}$ lie in ${R_n}$, so that they each have a pole of order at most ${n}$ at ${P_\infty}$, then some linear combination of these functions must have a pole of order at most ${n-1}$ at ${P_\infty}$; thus ${R_{n-1}}$ has codimension at most one in ${R_n}$, giving the claim.

From (3) and induction we see that each of the ${R_n}$ are finite dimensional, with the trivial upper bound

$\displaystyle \hbox{dim}(R_n) \leq n+1. \ \ \ \ \ (4)$

Riemann’s inequality complements this with the lower bound

$\displaystyle \hbox{dim}(R_n) \geq n+1-g, \ \ \ \ \ (5)$

thus one has ${\hbox{dim}(R_n) = \hbox{dim}(R_{n-1})+1}$ for all but at most ${g}$ exceptions (in fact, exactly ${g}$ exceptions as it turns out). This is a consequence of the Riemann-Roch theorem; it can be proven from abstract nonsense (the snake lemma) if one defines the genus ${g}$ in a non-standard fashion (as the dimension of the first Cech cohomology ${H^1(C)}$ of the structure sheaf ${{\mathcal O}_C}$ of ${C}$), but to obtain this inequality with a standard definition of ${g}$ (e.g. as the dimension of the zeroth Cech cohomolgy ${H^0(C, \Omega_C^1)}$ of the line bundle of differentials) requires the more non-trivial tool of Serre duality.

At any rate, now that we have these vector spaces ${R_n}$, we will define ${V \subset k(C \times C)}$ to be a tensor product space

$\displaystyle V = R_\ell \otimes R_m$

for some natural numbers ${\ell, m \geq 0}$ which we will optimise in later. That is to say, ${V}$ is spanned by functions of the form ${(z,w) \mapsto f(z) g(w)}$ with ${f \in R_\ell}$ and ${g \in R_m}$. This is clearly a linear subspace of ${k(C \times C)}$ of dimension ${\hbox{dim}(R_\ell) \hbox{dim}(R_m)}$, and hence by Rieman’s inequality we have

$\displaystyle \hbox{dim}(V) \geq (\ell+1-g) (m+1-g) \ \ \ \ \ (6)$

if

$\displaystyle \ell,m \geq g-1. \ \ \ \ \ (7)$

Observe that ${\iota_1 \circ \pi_1}$ maps a tensor product ${(z,w) \mapsto f(z) g(w)}$ to a function ${z \mapsto f(z) g(\hbox{Frob}_{\sqrt{q}} z)}$. If ${f \in R_\ell}$ and ${g \in R_m}$, then we see that the function ${z \mapsto f(z) g(\hbox{Frob}_{\sqrt{q}} z)}$ has a pole of order at most ${\ell+m\sqrt{q}}$ at ${P_\infty}$. We conclude that

$\displaystyle \iota_1 \circ \pi_1( V ) \subset R_{\ell + m\sqrt{q}} \ \ \ \ \ (8)$

and in particular by (4)

$\displaystyle \hbox{dim}(\pi_1(V)) \leq \ell + m \sqrt{q} + 1 \ \ \ \ \ (9)$

and similarly

$\displaystyle \hbox{dim}(\pi_2(V)) \leq \ell \sqrt{q} + m + 1. \ \ \ \ \ (10)$

We will choose ${m}$ to be a bit bigger than ${\ell}$, to make the ${\pi_2}$ image of ${V}$ smaller than that of ${\pi_1}$. From (6), (10) we see that if we have the inequality

$\displaystyle (\ell+1-g) (m+1-g) > \ell \sqrt{q}+m + 1 \ \ \ \ \ (11)$

(together with (7)) then ${\pi_2}$ cannot be injective.

On the other hand, we have the following basic fact:

Lemma 3 (Injectivity) If

$\displaystyle \ell < \sqrt{q}, \ \ \ \ \ (12)$

then ${\pi_1: V \rightarrow \pi_1(V)}$ is injective.

Proof: From (3), we can find a linear basis ${f_1,\dots,f_a}$ of ${R_\ell}$ such that each of the ${f_i}$ has a distinct order ${d_i}$ of pole at ${P_\infty}$ (somewhere between ${0}$ and ${\ell}$ inclusive). Similarly, we may find a linear basis ${g_1,\dots,g_b}$ of ${R_m}$ such that each of the ${g_j}$ has a distinct order ${e_j}$ of pole at ${P_\infty}$ (somewhere between ${0}$ and ${m}$ inclusive). The functions ${z \mapsto f_i(z) g_j(\hbox{Frob}_{\sqrt{q}} z)}$ then span ${\iota_1(\pi_1(V))}$, and the order of pole at ${P_\infty}$ is ${d_i + \sqrt{q} e_j}$. But since ${\ell < \sqrt{q}}$, these orders are all distinct, and so these functions must be linearly independent. The claim follows. $\Box$

This gives us the following bound:

Proposition 4 Let ${\ell,m}$ be natural numbers such that (7), (11), (12) hold. Then ${|C({\bf F}_q)| \leq \ell + m \sqrt{q}}$.

Proof: As ${\pi_2}$ is not injective, we can find ${f \in V}$ with ${\pi_2(f)}$ vanishing. By the above lemma, the function ${\iota_1(\pi_1(f))}$ is then non-zero, but it must also vanish on ${\iota_1(C_1 \cap C_2)}$, which has cardinality ${|C({\bf F}_q)|}$. On the other hand, by (8), ${\iota_1(\pi_1(f))}$ has a pole of order at most ${\ell+m\sqrt{q}}$ at ${P_\infty}$ and no other poles. Since the number of poles and zeroes of a rational function on a projective curve must add up to zero, the claim follows. $\Box$

If ${q \geq (g+1)^4}$, we may make the explicit choice

$\displaystyle m := \sqrt{q}+2g; \quad \ell := \lfloor \frac{g}{g+1} \sqrt{q} \rfloor + g + 1$

and a brief calculation then gives Theorem 2. In some cases one can optimise things a bit further. For instance, in the genus zero case ${g=0}$ (e.g. if ${C}$ is just the projective line ${{\mathbf P}^1}$) one may take ${\ell=1, m = \sqrt{q}}$ and conclude the absolutely sharp bound ${|C({\bf F}_q)| \leq q+1}$ in this case; in the case of the projective line ${{\mathbf P}^1}$, the function ${f}$ is in fact the very concrete function ${f(z,w) := z - w^{\sqrt{q}}}$.

Remark 1 When ${q = p^{2n+1}}$ is not a perfect square, one can try to run the above argument using the factorisation ${\hbox{Frob}_q = \hbox{Frob}_{p^n} \hbox{Frob}_{p^{n+1}}}$ instead of ${\hbox{Frob}_q = \hbox{Frob}_{\sqrt{q}} \hbox{Frob}_{\sqrt{q}}}$. This gives a weaker version of the above bound, of the shape ${|C({\bf F}_q)| \leq q + O( \sqrt{p} \sqrt{q} )}$. In the hyperelliptic case at least, one can erase this loss by working with a variant of the argument in which one requires ${f}$ to vanish to high order at ${C_1}$, rather than just to first order; see this survey article of mine for details.

One can get a “cheap” proof of Riemann’s inequality (with the “wrong” definition of the genus ${g}$) from Cech cohomology as follows. For any natural number ${n}$, let ${{\mathcal O}_C(-nP_\infty)}$ denote the sheaf on ${C}$, defined by setting the sections on any open set ${U}$ of ${C}$ to be the rational functions with no poles at ${U}$, except possibly for a pole of order up to ${n}$ at ${P_\infty}$ in the case that ${U}$ contains ${P_\infty}$. Then ${R_n}$ is the space of global sections on this sheaf, that is to say the zeroth Cech cohomology ${H^0({\mathcal O}_C(-nP_\infty))}$. On the other hand, we also have the skyscraper sheaf ${k_{P_\infty}}$ on ${C}$, defined by setting the sections on ${U}$ to be ${k}$ if ${U}$ contains ${P_\infty}$ and ${\{0\}}$ otherwise. For ${n \geq 1}$, we have an obvious short exact sequence of sheaves

$\displaystyle 0 \rightarrow {\mathcal O}_C(-(n-1)P_\infty) \rightarrow {\mathcal O}_C(-nP_\infty) \rightarrow k_{P_\infty} \rightarrow 0$

which upon taking Cech cohomology (and using the snake lemma) gives the long exact sequence

$\displaystyle 0 \rightarrow H^0({\mathcal O}_C(-(n-1)P_\infty)) \rightarrow H^0({\mathcal O}_C(-nP_\infty)) \rightarrow H^0(k_{P_\infty}) \rightarrow$

$\displaystyle H^1({\mathcal O}_C(-(n-1)P_\infty)) \rightarrow H^1({\mathcal O}_C(-nP_\infty)) \rightarrow H^1(k_{P_\infty}).$

One can compute that ${H^0(k_{P_\infty}) = k}$ and ${H^1(k_{P_\infty})=0}$, so the long exact sequence becomes

$\displaystyle 0 \rightarrow R_{n-1} \rightarrow R_n \rightarrow k \rightarrow$

$\displaystyle H^1({\mathcal O}_C(-(n-1)P_\infty)) \rightarrow H^1({\mathcal O}_C(-nP_\infty)) \rightarrow 0.$

The first part of this long exact sequence already recovers the trivial bounds (3). But it also shows that the dimensions of the spaces ${H^1({\mathcal O}_C(-nP_\infty))}$ are non-increasing, and decrease by one precisely when the left inequality in (3) is sharp. If one then makes the non-standard definition ${g := \hbox{dim}( H^1( {\mathcal O}_C ) )}$, then this decrease can occur at most ${g}$ times, and Riemann’s inequality then follows. (However, it is not immediately obvious with this definition that ${g}$ is finite; this requires some additional effort, e.g. invoking the Riemann-Hurwitz formula.) To relate this definition of ${g}$ to the more usual notions of genus requires the use of Serre duality, which will not be discussed here.

The upper bound in Theorem 2 (or more precisely, a generalisation of this bound) can be converted into a comparable lower bound, namely

Theorem 5 Let ${C}$ be an absolutely irreducible quasiprojective curve of bounded degree, defined over ${{\bf F}_q}$, and let ${q = p^n}$ be a perfect square. Then

$\displaystyle |C({\bf F}_q)| = q + O(\sqrt{q}),$

where the implied constant can depend on ${C}$ but is uniform in ${n}$ in the limit ${n \rightarrow \infty}$ (holding ${p}$ and ${C}$ fixed).

Proof: The upper bound follows from Theorem 2, after first removing all the singularities from ${C}$, normalising ${C}$ to be projective, and noting that the genus does not depend on ${n}$. (Note that removing singularities only deletes ${O(1)}$ points at most.) So the remaining task is to establish the matching lower bound. Unfortunately, the trace formula (1) is not enough by itself to convert upper bounds to lower bounds, due to the case in which all the ${\alpha_i}$ are positive, although strangely enough it can be used for the reverse task of converting lower bounds to upper bounds. Instead, we use a Galois-theoretic argument, though for (somewhat idiosyncratic) reasons, I will disguise the Galois theory by writing everything in a geometric language rather than an algebraic one.

The basic idea is to embed ${C}$ (perhaps with a bounded number of points removed) as a component of a larger (non-reducible) curve ${C'}$ for which (a) the number of “rational points” on this larger curve ${C'}$ can be counted almost exactly; and (b) an upper bound similar to Theorem 2 exists for the number of “rational points” on each of the components of ${C'}$, so that a lower bound can then be established by subtraction.

An easy instance of this trick arises in the case of hyperelliptic curves, which we will write affinely (deleting the point at infinity, by abuse of notation) as ${C = \{ (x,y): y^2 = f(x) \}}$ for some polynomial ${f}$ defined over ${{\bf F}_q}$ that is not a perfect square. We can embed this in the reducible curve

$\displaystyle C' := \{ (x,y): y^2 = f(x) \} \cup \{(x,y): y^2 = af(x) \}$

where ${a}$ is an arbitrarily chosen quadratic non-residue of ${{\bf F}_q}$. The curve ${C'}$ is the union of two curves, one of which is a dilate of the other, so they both have the same genus ${g}$, and so they each have at most ${q + O(\sqrt{q})}$ points (in the regime when ${g}$ is bounded and ${q}$ is a perfect square), thanks to Theorem 2. On the other hand, if ${f(x)}$ is non-zero, then exactly one of ${f(x)}$ and ${af(x)}$ is a quadratic residue, and so for all but a bounded number of ${x}$, there are exactly two values of ${y}$ with ${(x,y) \in C'}$, and so ${|C'({\bf F}_q)| = 2q + O(1)}$. One can then subtract the upper bound for one of the components from this estimate to obtain a matching lower bound for the other component, and in particular ${|C({\bf F}_q)| \geq q - O(\sqrt{q})}$.

In general we can proceed as follows. Let ${d}$ be the degree of ${C}$, so ${d=O(1)}$. After deleting ${O(1)}$ points from ${C}$, we can view ${C}$ as a degree ${d}$ cover of the affine line ${{\bf A}^1}$ with ${O(1)}$ many points removed, with projection map ${\pi: C \rightarrow {\bf A}^1}$. Once we do so, we can pass to the lifted curve ${\tilde C := \bigwedge^d C}$, defined as the collection of distinct ${d}$-tuples ${y_1,\dots,y_d}$ in ${C}$ that lie over the same point in ${{\bf A}^1}$, thus ${\pi(y_1)=\dots=\pi(y_d)}$. This is a degree ${d!}$ cover of (most of) ${{\bf A}^1}$, and is defined over ${{\bf F}_q}$. It also carries a free action of the permutation group ${S_d}$: if ${\sigma \in S_d}$, we define

$\displaystyle \sigma(y_1,\dots,y_d) := (y_{\sigma^{-1}(1)},\dots,y_{\sigma^{-1}(d)})$

(the inverse is there to make the action a left action; one could also work with right actions instead if desired).

The curve ${\tilde C}$ need not be absolutely irreducible, so we break it into absolutely irreducible components. The permutation group ${S_d}$ acts transitively on these components, so if we pick one of these components, say ${\tilde C_0}$, and let ${H := \{ \sigma \in S_d: \sigma \tilde C_0 = \tilde C_0 \}}$ be the stabiliser, then ${H}$ is a subgroup of ${S_d}$ (in particular, ${H=O(1)}$), and one can index the components of ${\tilde C_0}$ as ${\sigma \tilde C_0}$, as ${\sigma}$ ranges over a set of coset representatives of ${S_d/H}$. Each fibre of ${\tilde C_0}$ over a generic point of the base ${{\bf A}^1}$ is an orbit of ${H}$; since the map ${(y_1,\dots,y_d) \rightarrow y_1}$ projects ${\tilde C_0}$ to the connected curve ${C}$, we conclude that the projection of this orbit must have cardinality ${d}$. In other words, the permutation group ${H}$ is a transitive group.

Even though ${\tilde C}$ is defined over ${{\bf F}_q}$, the individual components ${\sigma \tilde C_0}$ of ${\tilde C}$ need not be. In particular, the Frobenius image ${\hbox{Frob}_q \tilde C_0}$ of ${\tilde C_0}$ might be another component of ${\tilde C_0}$, say ${\rho_q \tilde C_0}$.

Now let ${x}$ be a generic point of ${{\bf A}^1}$ defined over ${{\bf F}_q}$, then the fibre of ${\tilde C_0}$ above ${x}$ is a free ${H}$-orbit and thus has cardinality ${|H|}$ orbit. Let ${y}$ be a point in this fibre. Applying Frobenius, we see that ${\hbox{Frob}_q(y)}$ lies in the fibre of ${\rho_q \tilde C_0}$ above ${x}$, and hence

$\displaystyle \hbox{Frob}_q(y) = \rho_q \sigma y \ \ \ \ \ (13)$

for a unique ${\sigma \in H}$. Of course, if ${y \in \tilde C_0}$ does not lie over a point ${x}$ defined over ${{\bf F}_q}$, then the equation (13) cannot hold. Since there are ${q-O(1)}$ points in ${{\bf A}^1}$ with ${O(1)}$ points removed that are defined over ${{\bf F}_q}$, and each of these give rise to ${|H|}$ points in ${\tilde C_0}$, we conclude that

$\displaystyle \sum_{\sigma \in H} | \{ y \in \tilde C_0: \hbox{Frob}_q(y) = \rho_q \sigma y \} | = q |H| - O(1). \ \ \ \ \ (14)$

On the other hand, a modification of Theorem 2 shows the upper bound

$\displaystyle | \{ y \in \tilde C_0: \hbox{Frob}_q(y) = \rho_q \sigma y \} | \leq q + O(\sqrt{q}) \ \ \ \ \ (15)$

for each ${\sigma \in H}$. Strictly speaking, Theorem 2 is only directly applicable in the case when ${\rho_q \sigma}$ is the identity. However, even when ${\rho_q \sigma}$ is not the identity, one can “twist” the proof of Theorem 2 to establish the above estimate, basically by replacing the curve ${C_1}$ in (2) by a twisted variant

$\displaystyle C'_1 := \{ (\rho_q \sigma z, \hbox{Frob}_{\sqrt{q}}(z)): z \in C \}$

which is still isomorphic to ${C_1}$; we leave the details to the interested reader. If we subtract ${|H|-1}$ instances of (15) from (14), we obtain that

$\displaystyle | \{ y \in \tilde C_0: \hbox{Frob}_q(y) = \rho_q \sigma y \} | \geq q - O(\sqrt{q})$

for each ${\sigma \in H}$, which on combining with (15) gives

$\displaystyle | \{ y \in \tilde C_0: \hbox{Frob}_q(y) = \rho_q \sigma y \} | = q + O(\sqrt{q})$

for each ${\sigma \in H}$.

Next, as ${H}$ acts transtively on ${\{1,\dots,d\}}$, we see that there are ${|H|/d}$ values of ${\sigma}$ such that ${\rho_q \sigma(1) = 1}$. We conclude that

$\displaystyle | \{ (y_1,\dots,y_d) \in \tilde C_0: \hbox{Frob}_q(y_1) = y_1 \} | = \frac{|H|}{d} q + O(\sqrt{q}).$

But as ${C}$ has degree ${d}$ above ${{\bf A}^1}$, and ${\tilde C_0}$ has degree ${|H|}$, we see that for generic ${y_1}$ there are exactly ${|H|/d}$ points ${(y_1,\dots,y_d)}$ in ${\tilde C_0}$ that lie above ${y_1}$. We conclude that

$\displaystyle | \{ y_1 \in C: \hbox{Frob}_q(y_1) = y_1 \} | = q + O(\sqrt{q}),$

and the claim follows. $\Box$

Finally, if one uses the trace formula (1), then Theorem 5 implies the bounds

$\displaystyle |\alpha_i| \leq \sqrt{p} \ \ \ \ \ (16)$

for all ${i=1,\dots,2g}$, and hence Theorem 1. Indeed, if we let ${\alpha_i}$ be of maximal magnitude, thus ${|\alpha_i| \geq |\alpha_j|}$ for all ${j=1,\dots,2g}$, and an easy application of the Dirichlet approximation theorem then shows that

$\displaystyle |\sum_{j=1}^{2g} \alpha_j^n| \geq |\alpha_i|^n$

for infinitely many even ${n}$, which when combined with Theorem 5 implies that

$\displaystyle |\alpha_i|^n = O( p^{n/2} )$

for infinitely many even ${n}$. Taking ${n^{th}}$ roots and then sending ${n}$ to infinity (cf. the “tensor power trick“) we obtain (16) as required.