Computing Zeta Functions via p-adic Cohomology

Kiran S. Kedlaya^{⋆}

Department of Mathematics Massachusetts Institute of Technology 77 Massachusetts Avenue Cambridge, MA 02139

                           kedlaya@math.mit.edu
                      http://math.mit.edu/~kedlaya/

Abstract. We survey some recent applications of p-adic cohomology to machine computation of zeta functions of algebraic varieties over finite fields of small characteristic, and suggest some new avenues for further exploration.

1 Introduction

1.1 The zeta function problem

For X an algebraic variety over 𝔽_{q} (where we write q = p^{n} for p prime), the zeta function

Z(X, t) = exp (∑_{i=1}^{∞} \frac{t^{i}}{i} #X(𝔽_{q^{i}}))

is a rational function of t. This fact, the first of the celebrated Weil Conjectures, follows from Dwork’s proof using p-adic analysis [12], or from the properties of étale (ℓ-adic) cohomology (see [14] for an introduction).

In recent years, the algorithmic problem of determining Z(X, t) from defining equations of X has come into prominence, primarily due to its relevance in cryptography. Namely, to perform cryptographic functions using the Jacobian group of a curve over 𝔽_{q}, one must first compute the order of said group, and this is easily retrieved from the zeta function of the curve (as Q(1), where Q(t) is as defined below). However, the problem is also connected with other applications of algebraic curves (e.g., coding theory) and with other computational problems in number theory (e.g., determining Fourier coefficients of modular forms).

Even if one restricts X to being a curve of genus g, in which case

Z(X, t) = \frac{Q(t)}{(1 − t)(1 − qt)}

⋆ Thanks to Michael Harrison, Joe Suzuki, and Fré Vercauteren for helpful comments,

and to David Savitt for carefully reading an early version of this paper.

with Q(t) a polynomial over ℤ of degree 2g, there is no algorithm known^{1} for computing Z(X, t) which is polynomial in the full input size, i.e., in g, n, and log(p). However, if one allows polynomial dependence in p rather than its logarithm, then one can obtain a polynomial time algorithm using Dwork’s techniques, as shown by Lauder and Wan [30]. The purpose of this paper is to illustrate how these ideas can be converted into more practical algorithms in many cases.

This paper has a different purpose in mind than most prior and current work on computing zeta functions, which has been oriented towards low-genus curves over large fields (e.g., elliptic curves of “cryptographic size”). This problem is well under control now; however, we are much less adept at handling curves of high genus or higher dimensional varieties over small fields. It is in this arena that p-adic methods shoud prove especially valuable; our hope is for this paper, which mostly surves known algorithmic results on curves, to serve as a springboard for higher-genus and higher-dimensional investigations.

1.2 The approach via p-adic cohomology

Historically, although Dwork’s proof predated the advent of ℓ-adic cohomology, it was soon overtaken as a theoretical tool^{2} by the approach favored by the Grothendieck school, in which context the Weil conjectures were ultimately resolved by Deligne [8]. The purpose of this paper is to show that by contrast, from an algorithmic point of view, “Dworkian” p-adic methods prove to be much more useful.

A useful analogy is the relationship between topological and algebraic de Rham cohomology of varieties over ℂ. While the topological cohomology is more convenient for proving basic structural results, computations are often more convenient in the de Rham setting, since it is so closely linked to defining equations. The analogy is more than just suggestive: the p-adic constructions we have in mind are variants of and closely related to algebraic de Rham cohomology, from which they inherit some computability.

1.3 Other computational approaches

There are several other widely used approaches for computing zeta functions; for completeness, we briefly review these and compare them with the cohomological point of view.

The method of Schoof [45] (studied later by Pila [40] and Adleman-Huang [1]) is to compute the zeta function modulo ℓ for various small primes ℓ, then apply bounds on the coefficients of the zeta function plus the Chinese remainder theorem. This loosely corresponds to computing in ℓ-adic and not p-adic cohomology.

1 That is, unless one resorts to quantum computation: one can imitate Shor’s quantum factoring algorithm to compute the order of the Jacobian over 𝔽_{q^{n}} for n up to about 2g, and then recover Z(X, t). See [26].

2 The gap has been narrowed recently by the work of Berthelot and others; for instance, in [25], one recovers the Weil conjectures by imitating Deligne’s work using p-adic tools.

This has the benefit of working well even in large characteristic; on the downside, one can only treat curves, where ℓ-adic cohomology can be reinterpreted in terms of Jacobian varieties, and moreover, one must work with the Jacobians rather concretely (to extract division polynomials), which is algorithmically unwieldy. In practice, Schoof’s method has only been deployed in genus 1 (by Schoof’s original work, using improvements by Atkin, Elkies, Couveignes-Morain, etc.) and genus 2 (by work of Gaudry and Harley [17], with improvements by Gaudry and Schost [18]).

A more p-adic approach was given by Satoh [43], based on iteratively computing the Serre-Tate canonical lift [46] of an ordinary abelian variety, where one can read off the zeta function from the action of Frobenius on the tangent space at the origin. A related idea, due to Mestre, is to compute “p-adic periods” using a variant of the classical AGM iteration for computing elliptic integrals. This method has been used to set records for zeta function computations in characteristic 2 (e.g., [33]). The method extends in principle to higher characteristic [27] and genus (see [41], [42] for the genus 3 nonhyperelliptic case), but it seems difficult to avoid exponential dependence on genus and practical hangups in handling not-so-small characteristics.

We summarize the comparison between these approaches in the following table. (The informal comparison in the n column is based on the case of elliptic curves of a fixed small characteristic.)

Dependence on:

Algorithm class Applicability  p  n  g
Schoof  curves  polylog  big polynomial at least exponential
Canonical lift/AGM curves  polynomial small polynomial at least exponential
p-adic cohomology general nearly linear medium polynomial  polynomial

Table 1. Comparison of strategies for computing zeta functions

2 Some p-adic cohomology

In this section, we briefly describe some constructions of p-adic cohomology, amplifying the earlier remark that it strongly resembles algebraic de Rham cohomology.

2.1 Algebraic de Rham cohomology

We start by recalling how algebraic de Rham cohomology is constructed. First suppose X = Spec A is a smooth affine variety^{3} over a field K of characteristic

3 By “variety over K” we always mean a separated, finite type K-scheme.

zero. Let Ω_{A/K}^{1} be the module of Kähler differentials, and put Ω_{A/K}^{i} = ∧^{i}Ω_{A/K}^{1}; these are finitely generated locally free A-modules since X is smooth. By a theorem of Grothendieck [21], the cohomology of the complex Ω_{A/K}^{i} is finite dimensional.

If X is smooth but not necessarily affine, one has similar results on the sheaf level. That is, the hypercohomology of the complex formed by the sheaves of differentials is finite dimensional. In fact, Grothendieck proves his theorem first when X is smooth and proper, where the result follows by a comparison theorem to topological cohomology (via Serre’s GAGA theorem), then uses resolution of singularities to deduce the general case.

For general X, one can no longer use the modules of differentials, as they fail to be coherent. Instead, following Hartshorne [22], one (locally) embeds X into a smooth scheme Y, and computes de Rham cohomology on the formal completion of Y along X.

As one might expect from the above discussion, it is easiest to compute algebraic de Rham cohomology on a variety X if one is given a good compactification \overline{X}, i.e., a smooth proper variety such that \overline{X} \ X is a normal crossings divisor. Even absent that, one can still make some headway by computing with D-modules (where D is a suitable ring of differential operators), as shown by Oaku, Takayama, Walther, et al. (see for instance [52]).

2.2 Monsky-Washnitzer cohomology

We cannot sensibly work with de Rham cohomology directly in characteristic p, because any derivation will kill p-th powers and so the cohomology will not typically be finite dimensional. Monsky and Washnitzer [38], [36], [37] (see also [49]) introduced a p-adic cohomology which imitates algebraic de Rham cohomology by lifting the varieties in question to characteristic zero in a careful way.

Let X = Spec A be a smooth affine variety over a finite field 𝔽_{q} with q = p^{n}, and let W be the ring of Witt vectors over 𝔽_{q}, i.e., the unramified extension of ℤ_{p} with residue field 𝔽_{q}. By a theorem of Elkik [13], we can find a smooth affine scheme X̃ over W such that X̃ ×_{W} 𝔽_{q} ≅ X. While X̃ is not determined by X, we can “complete along the special fibre” to get something more closely bound to X.

Write X̃ = Spec Ã and let A^{†} be the weak completion of Ã, which is the smallest subring containing Ã of the p-adic completion of Ã which is p-adically saturated (i.e., if px ∈ A^{†}, then x ∈ A^{†}) and closed under the formation of series of the form

∑_{i_{1},...,i_{m}≥0} c_{i_{1},...,i_{m}}x_{1}^{i_{1}} ⋯ x_{m}^{i_{m}}

with c_{i_{1},...,i_{m}} ∈ W and x_{1}, …, x_{m} ∈ pA^{†}. We call A^{†} the (integral) dagger algebra associated to X; it is determined by X, but only up to noncanonical isomorphism.

In practice, one can describe the weak completion a bit more concretely, as in the following example.

Lemma 1. The weak completion of W [t_{1}, …, t_{n}] is the ring W ⟨t_{1}, …, t_{n}⟩^{†} of power series over W which converge for t_{1}, …, t_{n} within the disc (in the integral closure of W) around 0 of some radius greater than 1.

In general, A^{†} is always a quotient of W ⟨t_{1}, …, t_{n}⟩^{†} for some n.

We quickly sketch a proof of this lemma. On one hand, W ⟨t_{1}, …, t_{n}⟩^{†} (which is clearly p-adically saturated) is weakly complete: if x_{1}, …, x_{m} ∈ pW ⟨t_{1}, …, t_{n}⟩^{†}, then for t_{1}, …, t_{n} in some disc of radius strictly greater than 1, the series defining x_{1}, …, x_{m} converge to limits of norm less than 1, and so ∑ c_{i_{1},...,i_{m}}x_{1}^{i_{1}} ⋯ x_{m}^{i_{m}} converges on the same disc. On the other hand, any element of W ⟨t_{1}, …, t_{n}⟩^{†} has the form

∑_{j_{1},...,j_{n}≥0} e_{j_{1},...,j_{n}}t_{1}^{j_{1}} ⋯ t_{n}^{j_{n}}

where v_{p}(e_{j_{1},...,j_{n}}) + a(j_{1} + ⋯ + j_{n}) > −b for some a, b with a > 0 (but no uniform choice of a, b is possible). We may as well assume that 1/a is an integer, and that b > 0 (since the weak completion is saturated). Then it is possible to write this series as

∑_{i_{1},...,i_{m}≥0} c_{i_{1},...,i_{m}}x_{1}^{i_{1}} ⋯ x_{m}^{i_{m}}

where the x’s run over p^{j}t_{k} for j = 1, …, 1/a and k = 1, …, n; hence it lies in the weak completion.

The module of continuous differentials over A^{†} can be constructed as follows: given a surjection W ⟨t_{1}, …, t_{n}⟩^{†} → A^{†}, Ω_{A^{†}}^{1} is the A^{†}-module generated by dt_{1}, …, dt_{n} modulo enough relations to obtain a well-defined derivation d : A^{†} → Ω_{A^{†}}^{1} satisfying the rule

d ( ∑_{j_{1},...,j_{n}≥0} e_{j_{1},...,j_{n}}t_{1}^{j_{1}} ⋯ t_{n}^{j_{n}} ) = ∑_{i=1}^{n} ∑_{j_{1},...,j_{n}≥0} j_{i}e_{j_{1},...,j_{n}}(t_{1}^{j_{1}} ⋯ t_{i}^{j_{i}−1} ⋯ t_{n}^{j_{n}})dt_{i}.

Then the Monsky-Washnitzer cohomology (or MW-cohomology) H_{MW}^{i}(X) of X is the cohomology of the “de Rham complex”

⋯ →^{d} Ω_{A^{†}}^{i} ⊗_{W} W [\frac{1}{p}] →^{d} ⋯,

where Ω_{A^{†}}^{i} = ∧_{A^{†}}^{i}Ω_{A^{†}}^{i}. Implicit in this definition is the highly nontrivial fact that this cohomology is independent of all of the choices made. Moreover, if X → Y is a morphism of 𝔽_{q}-varieties, and A^{†} and B^{†} are corresponding dagger algebras, then the morphism lifts to a ring map B^{†} → A^{†}, and the induced maps H_{MW}^{i}(Y) → H_{MW}^{i}(X) do not depend on the choice of the ring map. The way this works (see [38] for the calculation) is that there are canonical homotopies (in the homological algebra sense) between any two such maps, on the level of the de Rham complexes.

MW-cohomology is always finite dimensional over W [\frac{1}{p}]; this follows from the analogous statement in rigid cohomology (see [5]). Moreover, it admits an analogue of the Lefschetz trace formula for Frobenius: if X is purely of dimension d, and F : A^{†} → A^{†} is a ring map lifting the q-power Frobenius map, then for all m > 0,

#X(𝔽_{q^{m}}) = ∑_{i=0}^{d}(−1)^{i} Trace(q^{dm}F^{−m}, H_{MW}^{i}(X)).

This makes it possible in principle, and ultimately in practice, to compute zeta functions by computing the action of Frobenius on MW-cohomology.

2.3 Rigid cohomology

As in the algebraic de Rham setting, it is best to view Monsky-Washnitzer cohomology in the context of a theory not limited to affine varieties. This context is provided by Berthelot’s rigid cohomology; since we won’t compute directly on this theory, we only describe it briefly. See [4] or [19, Chapter 4] for a somewhat more detailed introduction.^{4}

Suppose X is an 𝔽_{q}-variety which is the complement of a divisor in a smooth proper Y which lifts to a smooth proper formal W -scheme. Then this lift gives rise to a rigid analytic space Y^{an} via Raynaud’s “generic fibre” construction (its points are the subschemes of the lift which are integral and finite flat over W). This space comes with a specialization map to Y, and the inverse image of X is denoted ]X[ and called the tube of X. The rigid cohomology of X is the (coherent) cohomology of the direct limit of the de Rham complexes over all “strict neighborhoods” of ]X[ in Y^{an}. (Within Y^{an}, ]X[ is the locus where certain functions take p-adic absolute values less than or equal to 1; to get a strict neighborhood, allow their absolute values to be less than or equal to 1 + ϵ for some ϵ > 0.)

For general X, we can do the above locally (e.g., on affines) and compute hypercohomology via the usual spectral sequence; while the construction above does not sheafify, the complexes involves can be glued “up to homotopy”, which is enough to assemble the hypercohomology spectral sequence.

For our purposes, the relevance of rigid cohomology is twofold. On one hand, it coincides with Monsky-Washnitzer cohomology for X affine. On the other hand, it is related to algebraic de Rham cohomology via the following theorem. (This follows, for instance, from the comparison theorems of [5] plus the comparison theorem between crystalline and de Rham cohomology from [3].)

Theorem 1. Let Ỹ be a smooth proper W -scheme, let Z̃ ⊂ Ỹ be a relative normal crossings divisor, and set X̃ = Ỹ \Z̃. Then there is a canonical isomorphism

H_{dR}^{i}(X̃ ×_{W} (Frac W)) → H_{rig}^{i}(X̃ ×_{W} 𝔽_{q}).

4 We confess that a presentation at the level of detail we would like does not appear in print anywhere. Alas, these proceedings are not the appropriate venue to correct this!

In particular, if X is affine in this situation, its Monsky-Washnitzer cohomology is finite dimensional and all of the relations are explained by relations among algebraic forms, i.e., relations of finite length. This makes it much easier to construct “reduction algorithms”, such as those described in the next section.

One also has a comparison theorem between rigid cohomology and crystalline cohomology, a p-adic cohomology built in a more “Grothendieckian” manner. While crystalline cohomology only behaves well for smooth proper varieties, it has the virtue of being an integral theory. Thus the comparison to rigid cohomology equips the latter with a canonical integral structure. By repeating this argument in the context of log-geometry, one also obtains a canonical integral structure in the setting of Theorem 1; this is sometimes useful in computations.

3 Hyperelliptic curves in odd characteristic

The first^{5} class of varieties where p-adic cohomology was demonstrated to be useful for numerical computations is the class of hyperelliptic curves in odd characteristic, which we considered in [24]. In this section, we summarize the key features of the computation, which should serve as a prototype for more general considerations.

3.1 Overview

An overview of the computation may prove helpful to start with. The idea is to compute the action of Frobenius on the MW-cohomology of an affine hyperelliptic curve, and use the Lefschetz trace formula to recover the zeta function. Of course we cannot compute exactly with infinite series of p-adic numbers, so the computation will be truncated in both the series and p-adic directions, but we arrange to keep enough precision at the end to uniquely determine the zeta function.

Besides worrying about precision, carrying out this program requires making algorithmic two features of the Monsky-Washnitzer construction.

– We must be able to compute a Frobenius lift on a dagger algebra.

– We must be able to identify differentials forming a basis of the relevant cohomology space, and to “reduce” an arbitrary differential to a linear combination of the basis differentials plus an exact differential.

3.2 The dagger algebra and the Frobenius lift

Suppose that p ≠ 2, and let \overline{X} be the hyperelliptic curve of genus g given by the affine equation

y^{2} = P (x)

5 Although this seems to be the first overt use of MW-cohomology for numerically computing zeta functions in the literature, it is prefigured by work of Kato and Lubkin [23]. Also, similar computations appear in more theoretical settings, such as Gross’s work on companion forms [20].

with P (x) monic of degree 2g+1 over 𝔽_{q} with no repeated roots; in particular, \overline{X} has a rational Weierstrass point^{6} at infinity. Let X be the affine curve obtained from \overline{X} by removing all of the Weierstrass points, i.e., the point at infinity and the zeroes of y.

Choose a lift P̃(x) of P (x) to a monic polynomial of degree 2g + 1 over W. Then the dagger algebra corresponding to X is given by

W ⟨x, y, z⟩^{†}/(y^{2} − P̃(x), yz − 1),

whose elements can be expressed as ∑_{i∈ℤ} A_{i}(x)y^{i} with A_{i}(x) ∈ W [x], deg(A_{i}) ≤ 2g, and v_{p}(A_{i}) + c|i| > d for some constants c, d with c > 0.

The dagger algebra admits a p-power Frobenius lift σ given by

x ↦ x^{p}
y ↦ y^{p} (1 + \frac{P̃(x)^{σ} − P̃(x)^{p}}{P̃(x)^{p}} )^{1/2} ,

which can be computed by a Newton iteration. Here is where the removal of the Weierstrass points come in handy; the simple definition of σ above clearly requires inverting P̃(x), or equivalently y. It is possible to compute a Frobenius lift on the dagger algebra of the full affine curve (namely W ⟨x, y⟩^{†}/(y^{2} − P̃(x))), but this requires solving for the images of both x and y, using a cumbersome two-variable Newton iteration.

3.3 Reduction in cohomology

The hyperelliptic curve defined by y^{2} = P̃(x), minus its Weierstrass points, forms a lift X̃ of X of the type described in Theorem 1, so its algebraic de Rham cohomology coincides with the MW-cohomology H_{MW}^{1}(X). That is, the latter is generated by

\frac{x^{i}dx}{y} (i = 0, …, 2g − 1), \frac{x^{i}dx}{y^{2}} (i = 0, …, 2g)

and it is enough to consider “algebraic” relations. Moreover, the cohomology splits into plus and minus eigenspaces for the hyperelliptic involution y ↦ −y; the former is essentially the cohomology of ℙ^{1} minus the images of the Weierstrass points (since one can eliminate y entirely), so to compute the zeta function of \overline{X} we need only worry about the latter. In other words, we need only consider forms f(x)dx/y^{s} with s odd.

The key reduction formula is the following: if A(x) = P̃(x)B(x)+P̃′(x)C(x), then

\frac{A(x) dx}{y^{s}} ≡ (B(x) + \frac{2C′(x)}{s − 2}) \frac{dx}{y^{s−2}}

6 The case of no rational Weierstrass point is not considered in [24]; it has been worked out by Michael Harrison, and has the same asymptotics.

as elements of H_{MW}^{1}(X). This is an easy consequence of the evident relation

d (\frac{C(x)}{y^{s−2}}) ≡ 0

in cohomology.

We use this reduction formula as follows. Compute the image under Frobenius of \frac{x^{i}dx}{y} (truncating large powers of y or y^{−1}, and p-adically approximating coefficients). If the result is

∑_{j=−M}^{N} \frac{A_{j}(x) dx}{y^{2j+1}},

use the reduction formula to eliminate the j = N term in cohomology, then the j = N − 1 term, and so on, until no terms with j > 0 remain. Do likewise with the j = −M term, the j = −M + 1 term, and so on (using a similar reduction formula, which we omit; note that there are relatively few terms on that side anyway). Repeat for i = 0, …, 2g − 1, and construct the “matrix of the p-power Frobenius” Φ. Of course the p-power Frobenius is not linear, but the matrix of the q-power Frobenius is easily obtained as Φ^{σ^{n−1}} ⋯ Φ^{σ}Φ, where σ here is the Witt vector Frobenius and q = p^{n}.

3.4 Precision

We complete the calculation described above with a p-adic approximation of a matrix whose characteristic polynomial would exactly compute the numerator Q(t) of the zeta function. However, we can bound the coefficients of that numerator using the Weil conjectures: if Q(t) = 1 + a_{1}t + ⋯ + a_{2g}t^{2g}, then for 1 ≤ i ≤ g, a_{g+i} = q^{i}a_{g−i} and

|a_{i}| ≤ \binom{2g}{i}q^{i/2}.

In particular, computing a_{i} modulo a power of p greater than twice the right side determines it uniquely.

As noted at the end of the previous section, it is critical to know how much p-adic precision is lost in various steps of the calculation, in order to know how much initial precision is needed for the final calculation to uniquely determine the zeta function. Rather than repeat the whole analysis here, we simply point out the key estimate [24, Lemmas 2 and 3] and indicate where it comes from.

Lemma 2. For A_{k}(x) a polynomial over W of degree at most 2g and k ≥ 0 (resp. k < 0), the reduction of A_{k}(x)y^{2k+1} dx (i.e., the linear combination of x^{i} dx/y over i = 0, …, 2g − 1 cohomologous to it) becomes integral upon multiplication by p^{d} for d ≥ log_{p}((2g + 1)(k + 1) − 2) (resp. d ≥ log_{p}(−2k − 1)).

This is seen by considering the polar part of A_{k}(x)y^{2k+1} dx around the point at infinity if k < 0, or the other Weierstrass points if k > 0. Multiplying by p^{d} ensures that the antiderivatives of the polar parts have integral coefficients, which forces the reductions to do likewise.

It is also worth pointing out that one can manage precision rather simply by working in p-adic fixed point arithmetic. That is, approximate all numbers modulo some fixed power of p, regardless of their valuation (in contrast to padic floating point, where each number is approximated by a power of p times a mantissa of fixed precision). When a calculation produces undetermined highorder digits, fill them in arbitrarily once, but do not change them later. (That is, if x is computed with some invented high-order digits, each invocation of x later must use the same invented digits.) The analysis in [24], using the above lemma, shows that most of these invented digits cancel themselves out later in the calculation, and the precision loss in the reduction process ends up being negligible compared to the number of digits being retained.

3.5 Integrality

In practice, it makes life slightly^{7} easier if one uses a basis in which the matrix of Frobenius is guaranteed to have p-adically integral coefficients. The existence of such a basis is predicted by the comparison with crystalline cohomology, but an explicit good basis can be constructed “by hand” by careful use of Lemma 2. For instance, the given basis x^{i}dx/y (i = 0, …, 2g −1) is only good when p > 2g +1; on the other hand, the basis x^{i}dx/y^{3} (i = 0, …, 2g − 1) is good for all p and g.

3.6 Asymptotics

As for time and memory requirements, the runtime analysis in [24] together with [15] show that the algorithm requires time Õ(pn^{3}g^{4}) and space Õ(pn^{3}g^{3}), where again g is the genus of the curve and n = log_{p} q. (Here the “soft O” notation ignores logarithmic factors, arising in part from asymptotically fast integer arithmetic.)

4 Variations

In this section, we summarize some of the work on computing MW-cohomology for other classes of curves. We also mention some experimental results obtained from implementations of these algorithms.

7 But only slightly: the fact that there is some basis on which Frobenius acts by an integer matrix means that the denominators in the product Φ^{σ^{n−1}} ⋯ Φ^{σ}Φ can be bounded independently of n.

4.1 Hyperelliptic curves in characteristic 2

The method described in the previous section does not apply in characteristic 2, because the equation y^{2} = P (x) is nonreduced and does not give rise to hyperelliptic curves. Instead, one must view the hyperelliptic curve as an Artin-Schreier cover of ℙ^{1} and handle it accordingly; in particular, we must lift somewhat carefully. We outline how to do this following Denef and Vercauteren [9], [10]. (Analogous computations based more on Dwork’s work have been described by Lauder and Wan [31], [32], but they seem less usable in practice.)

Let \overline{X} be a hyperelliptic curve of degree g over 𝔽_{q}, with q = 2^{n}; it is defined by some plane equation of the form

y^{2} + h(x)y = f(x),

where f is monic of degree 2g +1 and deg(h) ≤ g. Let H be the monic squarefree polynomial over 𝔽_{q} with the same roots as h. By an appropriate substitution of the form y ↦ y + a(x), we can ensure that f vanishes at each root of H.

Let X be the affine curve obtained from \overline{X} by removing the point at infinity and the zero locus of H. Choose lifts H̃, h̃, f̃ of H, h, f to polynomials over W of the same degree, such that each root of h̃ is also a root of H̃, and each root of f̃ whose reduction mod p is a root of H is also a root of H̃. The dagger algebra corresponding to X is now given by

W ⟨x, y, z⟩^{†}/(y^{2} + h̃(x)y − f̃(x), H̃(x)z − 1),

and each element can be written uniquely as

∑_{i∈ℤ} A_{i}(x)H̃_{1}(x)^{i} + ∑_{i∈ℤ} B_{i}(x)yH̃_{1}(x)^{i}

with H̃_{1}(x) = x if H̃ is constant and H̃_{1}(x) = h̃(x) otherwise, deg(A_{i}) < deg(H̃_{1}) and deg(B_{i}) < deg(H̃_{1}) for all i, and v_{p}(A_{i}) + c|i| > d and v_{p}(B_{i}) + c|i| > d for some c, d with c > 0. The dagger algebra admits a Frobenius lift sending x to x^{2}, but this requires some checking, especially to get an explicit convergence bound; see [51, Lemma 4.4.1] for the analysis.

By Theorem 1, the MW-cohomology of X coincides with the cohomology of the hyperelliptic curve y^{2} + h̃(x)y − f̃(x) minus the point at infinity and the zero locus of H̃. Again, it decomposes into plus and minus eigenspaces for the hyperelliptic involution y ↦ −y − h̃(x), and only the minus eigenspace contributes to the zeta function of \overline{X}. The minus eigenspace is spanned by x^{i}y dx for i = 0, …, 2g − 1, there are again simple reduction formulae for expressing elements of cohomology in terms of this basis, and one can again bound the precision loss in the reduction; we omit details.

In this case, the time complexity of the algorithm is Õ(n^{3}g^{5}) and the space complexity is Õ(n^{3}g^{4}). If one restricts to ordinary hyperelliptic curves (i.e., those where H has degree g), the time and space complexities drop to Õ(n^{3}g^{4}) and Õ(n^{3}g^{3}), respectively, as in the odd characteristic case. It may be possible to optimize better for the opposite extreme case, where the curve has p-rank close to zero, but we have not tried to do this.

4.2 Other curves

Several variations on the theme developed above have been pursued. For instance, Gaudry and Gürel [15] have considered superelliptic curves, i.e., those of the form

y^{m} = P (x)

where m is not divisible by p. More generally still, Denef and Vercauteren consider the class of C_{a,b}-curves, as defined by Miura [35]. For a, b coprime integers, a C_{a,b}-curve is one of the form

y^{a} + ∑_{i=1}^{a−1} f_{i}(x)y^{i} + f_{0}(x) = 0,

where deg f_{0} = b and a deg f_{i} + bi < ab for i = 1, …, a − 1, and the above equation has no singularities in the affine plane.

These examples fit into an even broader class of potentially tractable curves, which we describe following Miura [35]. Recall that for a curve C and a point P, the Weierstrass monoid is defined to be the set of nonnegative integers which occur as the pole order at P of some meromorphic function with no poles away from P. Let a_{1} < ⋯ < a_{n} be a minimal set of generators of the Weierstrass monoid, and put d_{i} = gcd(a_{1}, …, a_{i}). Then the monoid is said to be Gorenstein (in the terminology of [39]) if for i = 2, …, n,

\frac{a_{i}}{d_{i}} ∈ \frac{a_{1}}{d_{i−1}} ℤ_{≥0} + ⋯ + \frac{a_{i−1}}{d_{i−1}} ℤ_{≥0}.

If the Weierstrass monoid of C is Gorenstein for some P, the curve C is said to be telescopic; its genus is then equal to

\frac{1}{2} (1 + ∑_{i=1}^{n} (\frac{d_{i−1}}{d_{i}} − 1) a_{i}) .

The cohomology of telescopic curves is easy to describe, so it seems likely that one can compute Monsky-Washnitzer cohomology on them. The case n = 2 is the C_{a,b} case; for larger n, this has been worked out by Suzuki [47] in what he calls the “strongly telescopic” case. This case is where for each i, the map from C to its image under the projective embedding defined by O(a_{i}P) is a cyclic cover (e.g., if C is superelliptic).

We expect that these can be merged to give an algorithm treating the general case of telescopic curves. One practical complication (already appearing in the C_{a,b} case) is that using a Frobenius lift of the form x ↦ x^{p} necessitates inverting an unpleasantly large polynomial in y; it seems better instead to iteratively compute the action on both x and y of a Frobenius lift without inverting anything.

4.3 Implementation

The algorithms described above have proved quite practicable; here we mention some implementations and report on their performance. Note that time and space usage figures are only meant to illustrate feasibility; they are in no way standardized with respect to processor speed, platform, etc. Also, we believe all curves and fields described below are “random”, without special properties that make them easier to handle.

The first practical test of the original algorithm from [24] seems to have been that of Gaudry and Gürel [15], who computed the zeta function of a genus 3 hyperelliptic curve over 𝔽_{3^{37}} in 30 hours (apparently not optimized). They also tested their superelliptic variant, treating a genus 3 curve over 𝔽_{2^{53}} in 22 hours.

Gaudry and Gürel [16] have also tested the dependence on p in the hyperelliptic case. They computed the zeta function of a genus 3 hyperelliptic curve over 𝔽_{251} in 42 seconds using 25 MB of memory, and over 𝔽_{10007} in 1.61 hours using 1.4 GB.

In the genus direction, Vercauteren [51, Sections 4.4–4.5] computed the zeta function of a genus 60 hyperelliptic curve over 𝔽_{2} in 7.64 minutes, and of a genus 350 curve over 𝔽_{2} in 3.5 days. We are not aware of any high-genus tests in odd characteristic; in particular, we do not know whether the lower exponent in the time complexity will really be reflected in practice.

Vercauteren [51, Section 5.5] has also implemented the C_{a,b}-algorithm in characteristic 2. He has computed the zeta function of a C_{3,4} curve over 𝔽_{2^{288}} in 8.4 hours and of a C_{3,5} curve over 𝔽_{2^{288}} in 12.45 hours.

Finally, we mention an implementation “coming to a computer near you”: Michael Harrison has implemented the computation of zeta functions of hyperelliptic curves in odd characteristic (with or without a rational Weierstrass point) in a new release of Magma. At the time of this writing, we have not seen any performance results.

5 Beyond hyperelliptic curves

We conclude by describing some of the rich possibilities for further productive computations of p-adic cohomology, especially in higher dimensions. A more detailed assessment, plus some explicit formulae that may prove helpful, appear in the thesis of Gerkmann [19] (recently completed under G. Frey).

5.1 Simple covers

The main reason the cohomology of hyperelliptic curves in odd characteristic is easily computable is that they are “simple” (Galois, cyclic, tamely ramified) covers of a “simple” variety (which admits a simple Frobenius lift). As a first step into higher dimensions, one can consider similar examples; for instance, a setting we are currently considering with de Jong (with an eye toward gathering data on the Tate conjecture on algebraic cycles) is the class of double covers of ℙ^{2} of fixed small degree.

One might also consider some simple wildly ramified covers, like Artin-Schreier covers, which can be treated following Denef-Vercauteren. (These are also good candidates for Lauder’s deformation method; see below.)

5.2 Toric complete intersections

Another promising class of varieties to study are smooth complete intersections in projective space or other toric varieties. These are promising because their algebraic de Rham cohomology can be computed by a simple recipe; see [19, Chapter 5].

Moreover, some of these varieties are of current interest thanks to connections to physics. For instance, Candelas et al. [6] have studied the zeta functions of some Calabi-Yau threefolds occurring as toric complete intersections, motivated by considerations of mirror symmetry.

5.3 Deformation

We mention also a promising new technique proposed by Lauder. (A related strategy has been proposed by Nobuo Tsuzuki [48] for computing Kloosterman sums.) Lauder’s strategy is to compute the zeta function of a single variety not in isolation, but by placing it into a family and studying, after Dwork, the variation in Frobenius along the family as the solution of a certain differential equation.^{8}

A very loose description of the method is as follows. Given an initial X, say smooth and proper, find a family f : Y → B over a simple one-dimensional base (like projective space) which is smooth away from finitely many points, includes X as one fibre, and has another fibre which is “simple”. We also ask for simplicity that the whole situation lifts to characteristic zero. For instance, if X is a smooth hypersurface, Y might be a family which linearly interpolates between the defining equation of X and that of a diagonal hypersurface.

One can now compute (on the algebraic lift to characteristic zero) the Gauss-Manin connection of the family; this will give in particular a module with connection over a dagger algebra corresponding to the part of B where f is smooth. One then shows that there is a Frobenius structure on this differential equation that computes the characteristic polynomial of Frobenius on each smooth fibre. That means the Frobenius structure itself satisfies a differential equation, which one solves iteratively using an initial condition provided by the simple fibre. (In the hypersurface example, one can write down by hand the Frobenius action on the cohomology of a diagonal hypersurface.)

Lauder describes explicitly how to carry out the above recipe for Artin-Schreier covers of projective space [28] and smooth projective hypersurfaces [29]. The technique has not yet been implemented on a computer, so it remains to be seen how it performs in practice. It is expected to prove most advantageous

8 Lest this strategy seem strangely indirect, note the resemblance to Deligne’s strategy [8] for proving the Riemann hypothesis component of the Weil conjectures!

for higher dimensional varieties, as one avoids the need to compute in multidimensional polynomial rings. In particular, Lauder shows that in his examples, the dependence of this technique on d = dim X is exponential in d, and not d^{2}. (This is essentially best possible, as the dimensions of the cohomology spaces in question typically grow exponentially in d.)

5.4 Additional questions

We conclude by throwing out some not very well-posed further questions and suggestions,.

– Can one can collect data about a class of “large” curves (e.g., hyperelliptic curves of high genus) over a fixed field, and predict (or even prove) some behavioral properties of the Frobenius eigenvalues of a typical such curve, in the spirit of Katz-Sarnak?

– With the help of cohomology computations, can one find nontrivial instances of cycles on varieties whose existence is predicted by the Tate conjecture? As noted above, we are looking into this with Johan de Jong.

– The cohomology of Deligne-Lusztig varieties furnish representations of finite groups of Lie type. Does the p-adic cohomology in particular shed any light on the modular representation theory of these varieties (i.e., in characteristic equal to that of the underlying field)?

– There is a close link between p-adic Galois representations and the p-adic differential equations arising here; this is most explicit in the work of Berger [2]. Can one extend this analogy to make explicit computations on p-adic Galois representations, e.g., associated to varieties over ℚ_{p}, or modular forms? The work of Coleman and Iovita [7] may provide a basis for this.

References

1. L.M. Adleman and M.-D. Huang, Counting rational points on curves and abelian varieties over finite fields, in H. Cohen (ed.), ANTS-II, Lecture Notes in Comp. Sci. 1122, Springer-Verlag, 1996, 1–16.

2. L. Berger, Représentations p-adiques et équations différentielles, Invent. Math. 148 (2002), 219–284.

3. P. Berthelot, Cohomologie cristalline des schémas de caractéristique p > 0, Lecture Notes in Math. 407, Springer-Verlag, 1974.

4. P. Berthelot, Géométrie rigide et cohomologie des variétés algébriques de caractéristique p, in Introductions aux cohomologies p-adiques (Luminy, 1984), Mém. Soc. Math. France 23 (1986), 7–32.

5. P. Berthelot, Finitude et pureté cohomologique en cohomologie rigide (with an appendix in English by A.J. de Jong), Invent. Math. 128 (1997), 329–377.

6. P. Candelas, X. de la Ossa and F. Rodriguez-Villegas, Calabi-Yau manifolds over finite fields, I, preprint (arXiv: hep-th/0012233).

7. R. Coleman and A. Iovita, Revealing hidden structures, preprint (URL

http://math.berkeley.edu/~coleman/).

8. P. Deligne, La conjecture de Weil. I, Publ. Math. IHES 43 (1974), 273–307.

9. J. Denef and F. Vercauteren, An extension of Kedlaya’s algorithm to Artin-Schreier curves in characteristic 2, in C. Fieker and D.R. Kohel (eds.), ANTS-V, Lecture Notes in Comp. Sci. 2369, Springer-Verlag, 2002, 308–323.

10. J. Denef and F. Vercauteren, An extension of Kedlaya’s algorithm to hyperelliptic curves in characteristic 2, to appear in J. Crypt.

11. J. Denef and F. Vercauteren, Computing zeta functions of C_{ab} curves using Monsky-Washnitzer cohomology, preprint (2003).

12. B. Dwork, On the rationality of the zeta function of an algebraic variety, Amer. J. Math. 82 (1960), 631–648.

13. R. Elkik, Solutions d’équations à coefficients dans un anneau hensélien, Ann. Sci. Éc. Norm. Sup. 6 (1973), 553–603.

14. E. Freitag and R. Kiehl, Étale cohomology and the Weil conjectures (translated by B.S. Waterhouse and W.C. Waterhouse), Ergebnisse der Math. 13, Springer-Verlag, 1998.

15. P. Gaudry and N. Gürel, An extension of Kedlaya’s point-counting algorithm to superelliptic curves, in Advances in Cryptology – ASIACRYPT 2001 (Gold Coast), Lecture Notes in Comp. Sci. 2248, Springer-Verlag, 2001, 480–494.

16. P. Gaudry and N. Gürel, Counting points in medium characteristic using Kedlaya’s

algorithm, preprint (URL http://www.inria.fr/rrrt/rr-4838.html).

17. P. Gaudry and R. Harley, Counting points on hyperelliptic curves over finite fields, in W. Bosma (ed.), ANTS-IV, Lecture Notes in Comp. Sci. 1838, Springer-Verlag, 2000, 313–332.

18. P. Gaudry and É. Schost, Construction of secure random curves of genus 2 over prime fields, to appear in Eurocrypt 2004.

19. R. Gerkmann, The p-adic cohomology of varieties over finite fields and applications to the computation of zeta functions, thesis, Universität Duisberg-Essen, 2003.

20. B.H. Gross, A tameness criterion for Galois representations associated to modular forms (mod p), Duke Math. J. 61 (1990), 445–517.

21. A. Grothendieck On the de Rham cohomology of algebraic varieties, Publ. Math. IHES 29 (1966), 95–103.

22. R. Hartshorne, On the De Rham cohomology of algebraic varieties, Publ. Math. IHES 45 (1975), 5–99.

23. G.C. Kato and S. Lubkin, Zeta matrices of elliptic curves, J. Number Theory 15 (1982), 318–330.

24. K.S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc. 16 (2001), 323–338; errata, ibid. 18 (2003), 417–418.

25. K.S. Kedlaya, Fourier transforms and p-adic “Weil II”, preprint (URL

http://math.mit.edu/~kedlaya/papers/).

26. K.S. Kedlaya, Quantum computation of zeta functions of curves, preprint (URL

http://math.mit.edu/~kedlaya/papers/).

27. D. Kohel, The AGM-X_{0}(N) Heegner point lifting algorithm and elliptic curve point counting, in Asiacrypt ’03, Lecture Notes in Comp. Sci. 2894, Springer-Verlag, 2003, 124–136.

28. A.G.B. Lauder, Deformation theory and the computation of zeta functions, to appear in Proc. London Math. Soc.

29. A.G.B. Lauder, Counting solutions to equations in many variables over finite fields, to appear in Foundations of Comp. Math.

30. A.G.B. Lauder and D. Wan, Counting points on varieties over finite fields of small characteristic, to appear in J.P. Buhler and P. Stevenhagen (eds.), Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography, MSRI Publications, Cambridge Univ. Press.

31. A.G.B. Lauder and D. Wan, Computing zeta functions of Artin-Schreier curves over finite fields, London Math. Soc. J. Comp. Math. 5 (2002), 34–55.

32. A.G.B. Lauder and D. Wan, Computing zeta functions of Artin-Schreier curves over finite fields II, J. Complexity, to appear.

33. R. Lercier and D. Lubicz, email to the NMBRTHRY mailing list, 5 December 2002

(URL http://listserv.nodak.edu/archives/nmbrthry.html).

34. J.-F.  Mestre,  Algorithmes  pour  compter  des  points  en
petite  caractéristique  en  genre  1  et  2,  preprint  (URL

http://www.math.univ-rennes1.fr/crypto/2001-02/mestre.ps).

35. S. Miura, Error correcting codes based on algebraic curves (in Japanese), thesis, University of Tokyo, 1997.

36. P. Monsky, Formal cohomology. II. The cohomology sequence of a pair, Ann. of Math. (2) 88 (1968), 218–238.

37. P. Monsky, Formal cohomology. III. Fixed point theorems, Ann. of Math. (2) 93 (1971), 315–343.

38. P. Monsky and G. Washnitzer, Formal cohomology. I, Ann. of Math. (2) 88 (1968), 181–217.

39. A. Nijenhuis and H.S. Wilf, Representations of integers by linear forms in nonnegative integers, J. Number Th. 4 (1972), 98–106.

40. J. Pila, Frobenius maps of abelian varieties and finding roots of unity in finite fields, Math. Comp. 55 (1990), 745–763.

41. C. Ritzenthaler, Problèmes arithmétiques relatifs à certaines familles de courbes sur les corps finis, thesis, Université Paris 7, 2003 (URL

http://www.math.jussieu.fr/~ritzenth/).

42. C. Ritzenthaler, Point counting on genus 3 non hyperelliptic curves, preprint (URL

http://www.math.jussieu.fr/~ritzenth/).

43. T. Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), 247–270.

44. T. Satoh, On p-adic point counting algorithms for elliptic curves over finite fields, ANTS-V, Lecture Notes in Comp. Sci. 2369, Springer-Verlag, 2002, 43–66.

45. R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Comp. 44 (1985), 483–494.

46. J.-P. Serre and J. Tate, Good reduction of abelian varieties, Ann. Math. (2) 88 (1968), 492–517.

47. J. Suzuki, An extension of Kedlaya’s order counting based on Miura theory, preprint.

48. N. Tsuzuki, Bessel F -isocrystals and an algorithm of computing Kloosterman sums, preprint.

49. M. van der Put, The cohomology of Monsky and Washnitzer, in Introductions aux cohomologies p-adiques (Luminy, 1984), Mém. Soc. Math. France 23 (1986), 33–59.

50. F. Vercauteren, Extensions of Kedlaya’s algorithm, notes from ECC 2002 talk

(URL http://www.cs.bris.ac.uk/~frederik/).

51. F. Vercauteren, Computing zeta functions of curves over finite fields, thesis, Katholieke Universiteit Leuven, 2003 (URL

http://www.cs.bris.ac.uk/~frederik/).

52. U. Walther, Algorithmic determination of the rational cohomology of complex varieties via differential forms, in Symbolic computation: solving equations in algebra, geometry, and engineering (South Hadley, MA, 2000), Contemp. Math. 286, Amer. Math. Soc. (Providence), 2001, 185–206.