Algorithmic Theory of Zeta Functions over Finite Fields

Daqing Wan^{∗}

March 30, 2003

Department of Mathematics University of California Irvine, CA 92697-3875 Email: dwan@math.uci.edu

Abstract

This is an expanded version of my lecture given at the 2000 MSRI introductory workshop on computational number theory. It gives a brief introductory account of the general algorithmic theory of the zeta function of an algebraic set defined over a finite field.

1 Introduction

Let F_{q} be a finite field of q elements and p its characteristic. Let X be an algebraic set defined over F_{q}. For each positive integer k, let N_{k} denote the number of F_{q^{k}}-rational points on X. The zeta function Z(X) of X is the generating function

Z(X) = Z(X, T) = exp(∑_{k=1}^{∞} \frac{N_{k}}{k} T^{k}).

The zeta function contains important arithmetic and geometric information about X. It has been studied extensively in connection with the celebrated Weil conjectures [37].

Both practical applications and theoretical investigations make a good understanding of the zeta function from an algorithmic point of view increasingly important. The aim of this paper is to present a brief introductory account of the various fundamental problems and results in the emerging algorithmic theory of zeta functions. We shall focus on general properties rather than on results that are restricted to special cases. In particular, in most of this paper we do not assume X to be smooth and projective, although in that case one can often say more.

∗Partially supported by the NSF and the NSFC

The contents are organized as follows. In Section 2 we review general properties of zeta functions from an algorithmic point of view. A naive effective algorithm for computing the zeta function is given. If the characteristic p is small, one can use Dwork’s p-adic method to obtain a polynomial time algorithm for computing the zeta function in the case that the numbers of variables and defining equations for X are fixed.

In Section 3, we show that the general case of algebraic sets can be reduced in various ways to the case that X is a hypersurface. A more detailed discussion of that crucial case is given in Section 4, with emphasis on the smooth projective case. In Section 5 we consider the complex pure weight decomposition. Using the LLL factorization algorithm and Deligne’s main theorem, we show that, when the zeta function is given, one can compute in polynomial time how many zeros and poles with a given complex absolute value it has. In Section 6, which is devoted to the p-adic pure slope decomposition, we use the theory of Newton polygons to obtain a similar result for the number of zeros and poles with a given p-adic absolute value.

We conclude the paper by giving, in Section 7, an algorithm for the simpler problem of computing the zeta function modulo p. This algorithm shares several characteristic features with the general p-adic method for computing the full zeta function that is presented in [22]. Section 7 may thus serve as an introduction to [22].

All algorithms in this paper are deterministic. Probabilistic algorithms will not be discussed. Time is measured in bit operations.

Acknowledgment. It is a pleasure to thank S. Gao, H.W. Lenstra, Jr., and A.M. Odlyzko for several interesting discussions. Special thanks are due to the referee for many helpful suggestions.

2 Generalities on computing zeta functions

Let X be an algebraic set defined over a finite field F_{q} of q elements of characteristic p. For computational purposes, we may assume that X is affine, i.e., that it is the subset of affine n-space A^{n} defined by a system of polynomial equations:

{ f_{1}(x_{1}, …, x_{n}) = 0, ; ⋮ ; f_{m}(x_{1}, …, x_{n}) = 0,

where f_{i} ∈ F_{q}[x_{1}, …, x_{n}]. Let

X(F_{q}) = {x = (x_{1}, …, x_{n}) ∈ F_{q}^{n} | f_{1}(x) = … = f_{m}(x) = 0}

be the finite set of F_{q}-rational points on X. It is clear that the cardinality #X(F_{q}) is effectively computable.

For algorithmic purposes, ‘giving’ F_{q} means specifying p as well as an irreducible polynomial h in one variable over F_{p} that defines F_{q}, so that q equals p^{deg h} (see [30] for a method to find such a polynomial h when q is given); elements of F_{q} are then represented as polynomials of degree less than deg h in a formal zero of h, with coefficients from F_{p}. ‘Giving’ X means specifying a system of m defining polynomials f_{i} in n variables with coefficients in F_{q}. Let d be the maximum of the total degrees of the polynomials f_{i}. Then the dense input size for X is O(m\binom{d+n}{n} log q), which is O(m(d + 1)^{n} log q). Our first fundamental problem is the following.

Problem 2.1 Given F_{q} and X, compute the number #X(F_{q}) in time polynomial in the dense input size O(m(d + 1)^{n} log q).

This problem is trivial if q is fixed, so we may assume that q is large. In theory, the problem of counting X(F_{q}) can be reduced to the zerodimensional case. Namely, let Y be the zero-dimensional algebraic set defined by

{f_{1} = … = f_{m} = 0, x_{1}^{q} − x_{1} = … = x_{n}^{q} − x_{n} = 0}.

Then it is clear that

#X(F_{q}) = #Y (F_{q}).

Following a suggestion of Eisenbud and Sturmfels, one may now compute a Gröbner basis for Y, and its cardinality equals #Y (F_{q}). However, as q gets large, the cases where the Gröbner basis computation can be done efficiently are likely to become increasingly exceptional. (See [12] for Gröbner bases.)

Let F̄_{q} denote a fixed algebraic closure of F_{q}. For each positive integer k, let F_{q^{k}} denote the unique subfield of F̄_{q} with q^{k} elements. Let #X(F_{q^{k}}) denote the number of F_{q^{k}}-rational points on X. The following problem is harder but more interesting than Problem 2.1.

Problem 2.2 Given F_{q} and X, compute the sequence of numbers #X(F_{q^{k}}) (k = 1, 2, …).

It may not be clear how a finite algorithm can compute an infinite sequence of numbers, but this will be clarified below. As we shall see, one can encode the entire sequence in a suitably defined generating function, which turns out to be a rational function. This so-called zeta function of X is finite in nature and can thus be written down in a finite amount of time. Actually doing this for given X is the content of Problem 2.2.

A geometric point of X is an F̄_{q}-rational point of X. From the equality

⋃_{k=1}^{∞} X(F_{q^{k}}) = X(F̄_{q})

we see that each geometric point of X will be counted somewhere in the sequence of numbers #X(F_{q^{k}}). This may explain why many of the subtle geometric invariants associated with an algebraic variety X can be read off from its zeta function, in addition to a wealth of arithmetic information.

Definition 2.3 The zeta function of X is the generating function

Z(X) = Z(X, T) = exp(∑_{k=1}^{∞} \frac{T^{k}}{k} #X(F_{q^{k}})).

The qth power Frobenius map Frob_{q} is the permutation of the set X(F̄_{q}) of geometric points of X defined by:

Frob_{q}: x = (x_{1}, …, x_{n}) ↦ x^{q} = (x_{1}^{q}, …, x_{n}^{q}).

The degree of a geometric point x is defined to be the smallest positive integer d such that

Frob_{q}^{d}(x) = x

or, equivalently, such that x ∈ X(F_{q^{d}}). A closed point over F_{q} is the orbit of a geometric point under Frob_{q}. All geometric points belonging to a given closed point have the same degree, and this common degree is called the degree of the closed point. We denote by |X| the set of closed points of X over F_{q}, and, for each positive integer k, by M_{k}(X) the number of closed points of X of degree k. Since each closed point of degree k consists of exactly k points in X(F_{q^{k}}), one deduces

#X(F_{q^{k}}) = ∑_{d|k} dM_{d}(X).

Considering the logarithmic derivative of the zeta function, one finds the Euler product expansion

Z(X) = ∏_{k=1}^{∞} \frac{1}{(1 − T^{k})^{M_{k}(X)}} = ∏_{x∈|X|} \frac{1}{1 − T^{deg(x)}} ∈ 1 + T Z[[T]].

As the Weil conjectures [37] predict, the zeta function is a rational function. The first proof, given by Dwork [11], used p-adic analysis. The second proof, given by Grothendieck, used the theory of ℓ-adic cohomology, where ℓ is a prime number different from p. These two proofs pioneered the general p-adic and ℓ-adic study of zeta functions over finite fields.

Theorem 2.4 The zeta function Z(X) is a rational function, i.e., it belongs to Q(T). If we write

Z(X, T) = \frac{R_{1}(X, T)}{R_{2}(X, T)}, (R_{1}, R_{2}) = 1, R_{i} ∈ 1 + T Q[T],

then we have R_{i} ∈ 1 + T Z[T].

The rationality of Z(X) has an interesting consequence for the numbers #X(F_{q^{k}}), as follows. Let β_{i} and γ_{j} denote the reciprocal zeros of R_{1}(X) and R_{2}(X), respectively, so that one has R_{1}(X) = ∏_{i}(1−β_{i}T) and R_{2}(X) = ∏_{j}(1 − γ_{j}T). Then one finds

∑_{k=1}^{∞} #X(F_{q^{k}})T^{k} = T \frac{d log Z(X, T)}{dT} = ∑_{j} \frac{γ_{j}T}{1 − γ_{j}T} − ∑_{i} \frac{β_{i}T}{1 − β_{i}T} .

This implies

#X(F_{q^{k}}) = ∑_{j} γ_{j}^{k} − ∑_{i} β_{i}^{k} for all k ≥ 1.

As a corollary, one deduces that for each positive integer k one has

Z(X ⊗ F_{q^{k}}) = \frac{∏_{i}(1 − β_{i}^{k}T)}{∏_{j}(1 − γ_{j}^{k}T)}.

The integrality of the coefficients of R_{i} can be deduced from the rationality of Z(X) and the following elementary result.

Lemma 2.5 Let f ∈ 1 + T Z[[T]] be a rational function. Write

f = \frac{f_{1}}{f_{2}} , (f_{1}, f_{2}) = 1 f_{i} ∈ 1 + T Q[T].

Then one has f_{i} ∈ 1 + T Z[T].

Proof. This is usually derived from the so-called lemma of Fatou, see Katz [15]. Here we include two additional proofs.

One proof uses the Newton polygon or the Weierstrass factorization theorem. Suppose some prime number ℓ occurs in the common denominator of the coefficients of f_{1}. Then the theory of Newton polygons shows that f_{1} has an ℓ-adic zero in the open unit disk |T |_{ℓ} < 1. But the power series f ∈ 1 + T Z[[T]] is clearly analytic and non-zero in the open unit disk |T |_{ℓ} < 1. This gives the desired contradiction.

A second proof, suggested by Hendrik Lenstra, uses Gauss’s lemma for power series. The content cont(g) of a non-zero power series g = ∑_{i} a_{i}T^{i} ∈ Z[[T]] is defined to be the greatest common divisor of its coefficients a_{i}. Call g primitive if cont(g) = 1 or, equivalently, if g is not in the kernel of the natural map Z[[T]] → F_{ℓ}[[T]] for any prime number ℓ. Since the rings F_{ℓ}[[T]] are domains, the product of any two primitive power series is primitive. One deduces

cont(g_{1}g_{2}) = cont(g_{1})cont(g_{2}),

which is Gauss’s lemma for power series.

Lenstra’s proof of Lemma 2.5 then proceeds as follow. Write f = g_{1}/g_{2}, where g_{i} ∈ Z[T] and (g_{1}, g_{2}) = 1 in Q[T]. It is clear that cont(f) = 1. The relation g_{1} = g_{2}f implies that cont(g_{1}) = cont(g_{2}). Cancelling this common factor, we may assume cont(g_{1}) = cont(g_{2}) = 1. Since g_{1} and g_{2} are relatively prime over Q, there is a positive integer n such that

n ∈ g_{1}Z[T] + g_{2}Z[T] ⊂ g_{2}Z[[T]],

the last inclusion because g_{1} = g_{2}f. Write n = hg_{2} with h ∈ Z[[T]]. Then one has

n = cont(n) = cont(h)cont(g_{2}) = cont(h).

Hence h is divisible by n. We conclude that g_{2}(0) = ±1. This implies 2.5.

In order to actually compute the zeta function, it is useful to know an upper bound for the total degree deg R_{1} + deg R_{2} of the zeta function. The following explicit bound was proved by Bombieri [5].

Theorem 2.6 The total degree of Z(X) satisfies

deg R_{1} + deg R_{2} < (4d + 9)^{n+m},

where

d = max_{1≤j≤m} deg(f_{j}).

Bombieri’s bound is a general purpose bound. Its proof depends on Dwork’s p-adic method. It can be improved in various ways, especially when one takes the Newton polytope of the defining polynomials f_{i} into account, as was done by Adolphson and Sperber [2]. The bound is reasonably good as a function of d, but the dependence on m can probably be significantly improved.

An easy consequence is the following result.

Corollary 2.7 The zeta function Z(X) is effectively computable.

This corollary is obvious in the special case that the zeta function Z(X) is known to be a polynomial, or known to be the reciprocal of a polynomial, up to some trivial known factors. In the general case, one can deduce Corollary 2.7 from Theorem 2.4 and Theorem 2.6 in several ways, for instance by using the results of Berlekamp-Massey on linear recurring sequences (see [3] for more detail). Here we use a simple linear algebra argument explained to me by Hendrik Lenstra.

Let D_{1} and D_{2} be upper bounds for the degree of the numerator and the denominator of Z(X), respectively. For instance, we can take D_{i} = D = (4d + 9)^{n+m}, by Theorem 2.6. Compute the first D_{1} + D_{2} + 1 terms of the power series

Z(X) = 1 + z_{1}T + z_{2}T^{2} + … + z_{D_{1}+D_{2}}T^{D_{1}+D_{2}} + …

by explicitly counting X(F_{q^{k}}) for k ≤ D_{1} + D_{2}. Write a_{i}, b_{i} for the coefficients of R_{1} and R_{2} to be determined:

R_{1}(X) = 1 + a_{1}T + … + a_{D_{1}}T^{D_{1}},
R_{2}(X) = 1 + b_{1}T + … + b_{D_{2}}T^{D_{2}}.

The congruence

R_{2}(X)Z(X) ≡ R_{1}(X) (mod T^{D_{1}+D_{2}+1})

gives a system of linear equations in the a_{i}’s and the b_{i}’s. This system has at least one rational solution, and using linear algebra we can find one. Denote it by

(a′_{1}, …, a′_{D_{1}}; b′_{1}, …, b′_{D_{2}}).

Let

R′_{1}(X) = 1 + a′_{1}T + … + a′_{D_{1}}T^{D_{1}},
R′_{2}(X) = 1 + b′_{1}T + … + b′_{D_{2}}T^{D_{2}}.

Then, the congruence

R′_{2}(X)Z(X) ≡ R′_{1}(X) (mod T^{D_{1}+D_{2}+1})

holds as well, and therefore

R_{2}(X)R′_{1}(X) ≡ R_{2}(X)R′_{2}(X)Z(X) ≡ R′_{2}(X)R_{1}(X) (mod T^{D_{1}+D_{2}+1}).

Since each of R_{2}R′_{1} and R′_{2}R_{1} has degree at most D_{1} + D_{2}, we deduce R_{2}R′_{1} = R′_{2}R_{1}, so

\frac{R′_{1}(X)}{R′_{2}(X)} = \frac{R_{1}(X)}{R_{2}(X)} = Z(X).

Removing the greatest common factor of R′_{1}(X) and R′_{2}(X), one obtains the reduced form of Z(X). The proof is complete.

The above effective algorithm immediately implies the following.

Corollary 2.8 For fixed n, m, d, q, the number #X(F_{q^{k}}) can be computed in time bounded by a polynomial in k.

We now estimate the output size of any algorithm computing Z(X). Trivially, one has #X(F_{q^{k}}) ≤ #A^{n}(F_{q^{k}}) = q^{nk}. Hence T · d log Z(X, T)/dT converges as a complex power series for |T | < q^{−n}, so its reciprocal poles β_{i} and γ_{j} are bounded by q^{n} in absolute value. Let D denote the total degree of Z(X). Then R_{1}(X) = ∏_{i}(1−β_{i}T) and R_{2}(X) = ∏_{j}(1−γ_{j}T) have altogether O(D) coefficients, each of which is O(2^{D}q^{nD}). Then, regardless of the input size for X, the output size of the algorithm is O(nD^{2} log q). There is no general formula for the total degree D. However, for fixed m, Bombieri’s degree bound (4d + 9)^{n+m} is reasonably good, and it is comparable to the dense input size O(m(d + 1)^{n} log q).

We shall be concerned with the case that m is fixed (or small). If m is large, then the problem of computing #X(F_{q}) is of a totally different, more combinatorial nature. The fundamental question that we consider is the following.

Problem 2.9 Given X with fixed m, compute the zeta function Z(X) in time bounded by a polynomial in (d + 1)^{n} log q.

Remarks. If X has a sizable automorphism group, then one can often speed up the computation of Z(X) by using a suitable equivariant theory. Examples include diagonal hypersurfaces, certain modular varieties, and certain Calabi-Yau hypersurfaces. In this paper, we do not assume that X is given with any additional structure of this sort.

Currently, the theory of zeta functions over finite fields comprises only two types of methods that are powerful enough to prove the rationality of the zeta function in the general case. These are the ℓ-adic method and the p-adic method, where ℓ denotes a prime number different from the characteristic p of the finite field F_{q}. It is thus natural to try and exploit these general methods for algorithmic purposes.

In the ℓ-adic method one attempts to compute Z(X) mod ℓ^{k} using a suitable ℓ-adic trace formula. The zeta function Z(X) can be recovered from its reduction modulo a single large prime power ℓ^{k}, or from its reductions modulo many small primes ℓ via the Chinese remainder theorem. Unfortunately, the available ℓ-adic trace formula is in the general case not yet effective. Thus the use of the ℓ-adic method is currently restricted to special varieties, such as curves and abelian varieties. In the cases in which it can be used, the ℓ-adic method usually results in a polynomial time algorithm if d, m, and n are fixed, see Schoof [33], Elkies [13], and Poonen [31] for the first examples. It is an important open problem to make the ℓ-adic method effective in the general case.

In the p-adic method one attempts to compute Z(X) mod p^{k} using a p-adic trace formula, where p^{k} is chosen so large that one can recover the zeta function Z(X) from its reduction modulo p^{k}. There are many p-adic trace formulas. All of them can be made effective, although not all of them result in efficient algorithms. The general feeling is that the p-adic method is quite efficient if the characteristic p is suitably small, regardless of the size of the field F_{q} of definition and regardless of the degree of X. In the companion paper [22] jointly written with Alan Lauder, we present a p-adic algorithm that proves the following theorem.

Theorem 2.10 There is an algorithm that, given X, computes the zeta function Z(X) in time bounded by a polynomial in 2^{m}d^{n^{2}}p^{n}(log q)^{n}.

For fixed m and n, and small p—say, p = O((d log q)^{c}) for some positive constant c—the algorithm of Theorem 2.10 runs in polynomial time, and it thus provides a partial solution to Problem 2.9. In Section 7 below, we illustrate some of the basic ideas of the p-adic method by treating an algorithm for the easier problem of computing Z(X) mod p. For more details the reader is referred to [22].

3 Reduction to hypersurfaces

For the computation of the zeta function, the general case of an affine algebraic set X defined by a system

f_{1}(x) = … = f_{m}(x) = 0

of m polynomial equations in n variables can be reduced to the case of an affine hypersurface defined by one single equation. In the present section we discuss various ways in which this reduction can be accomplished; not all of them are very efficient.

The quickest theoretical reduction depends on the observation that any algebraic set is birational to an affine hypersurface. One then continues by induction on the dimension. As it stands, this method is not very explicit. It may be of interest to make it both explicit and efficient.

A second method, which is explicit, exploits the inclusion-exclusion principle, as follows. For a subset I ⊂ {1, 2, …, m}, let H(I) be the affine hypersurface defined by

∏_{i∈I} f_{i} = 0,

and let H(I)^{c} be the complement of H(I) in A^{n}. Thus,

H(I) = ⋃_{i∈I}{f_{i} = 0},

H(I)^{c} = ⋂_{i∈I}{f_{i} ≠ 0}.

In particular, we have H(∅) = ∅ and H(∅)^{c} = A^{n}. The inclusion-exclusion principle implies that

Z(X) = ∏_{I⊂{1,2,...,m}} Z(H(I)^{c}, T)^{(−1)^{#I}} .

Since

Z(H(I)^{c}, T) = \frac{1}{(1 − q^{n}T)Z(H(I), T)},

we conclude that for m > 0 we have

Z(X) = ∏_{{I⊂\{1,2,...,m\} \atop I≠∅}} Z(H(I), T)^{(−1)^{#I−1}},

where the factor 1 corresponding to I = ∅ has been dropped. Each factor of the above product is now the zeta function of an affine hypersurface. Note that this reduction uses 2^{m} −1 hypersurfaces, but they are all in the original affine space A^{n}.

If we apply Theorem 2.6 to each factor in the above identity, then we find that the total degree of Z(X) is bounded by

∑_{k=1}^{m} \binom{m}{k}(4kd + 9)^{n+1} < 2^{m}(4md + 9)^{n+1}.

In some cases where m is large this is better than what one obtains by applying Theorem 2.6 directly.

If one is willing to work with the slightly more general situation of Lfunctions of exponential sums, then one can use the single polynomial

g(x, y) = y_{1}f_{1}(x) + … + y_{m}f_{m}(x)

in n + m variables. Let ζ_{p} denote a fixed primitive pth root of unity in an extension field of Q. For each positive integer k, define the exponential sum

S_{k}(g) = ∑_{x_{i},y_{j}∈F_{q^{k}}} ζ_{p}^{Tr_{k}(g(x,y))},

where Tr_{k} denotes the absolute trace from F_{q^{k}} to the prime field F_{p}. The L-function associated to g is defined to be

L(g, T) = exp(∑_{k=1}^{∞} \frac{S_{k}(g)}{k}T^{k}).

It is straightforward to check that

#X(F_{q^{k}}) = \frac{1}{q^{mk}} S_{k}(g).

This gives the desired reduction

Z(X) = L(g, \frac{1}{q^{m}} T).

Replacing f_{i} by af_{i}, one also deduces that

Z(X) = L(ag, \frac{1}{q^{m}} T)

for each non-zero a ∈ F_{q}.

One can avoid the L-function in the above reduction by using the zeta function of the following Artin-Schreier hypersurface in A^{m+n+1}:

Y: z^{p} − z = y_{1}f_{1}(x) + … + y_{m}f_{m}(x).

In fact, a direct calculation gives that

#Y (F_{q^{k}}) = ∑_{a∈F_{p}} S_{k}(ag) = q^{(m+n)k} + ∑_{a∈F_{p}^{∗}} S_{k}(ag).

It follows that

Z(Y, q^{−m}T) = \frac{1}{1 − q^{n}T} · ∏_{a∈F_{p}^{∗}} L(ag, q^{−m}T) = \frac{1}{1 − q^{n}T} Z(X)^{p−1}.

We obtain the formula

Z(X) = ((1 − q^{n}T) · Z(Y, q^{−m}T))^{1/(p−1)}.

For large p this reduction is not likely to be very efficient.

One can also use the affine hypersurface H ⊂ A^{m+n} defined by

H: g(x, y) = y_{1}f_{1}(x) + … + y_{m}f_{m}(x) = 0.

As S. Gao observed, one has

#H(F_{q}) = q^{m+n−1} + #X(F_{q})(q^{m} − q^{m−1}).

This shows that for the purpose of counting rational points, we can work with a single hypersurface in the affine space A^{m+n}. In terms of zeta functions, Gao’s formula says that

Z(H, T) = \frac{Z(X, q^{m}T)}{(1 − q^{m+n−1}T)Z(X, q^{m−1}T)}.

One can inductively solve for Z(X) in terms of Z(H, T). Doing this from the complex point of view, one gets the infinite complex product

Z(X) = ∏_{k=0}^{∞}(1 − q^{n−1−k}T) · ∏_{k=0}^{∞} Z(H, q^{−m−k}T).

Doing it from the p-adic point of view, one gets the infinite p-adic product

\frac{1}{Z(X)} = ∏_{k=0}^{∞}(1 − q^{n+k}T) · ∏_{k=0}^{∞} Z(H, q^{1−m+k}T).

There is a standard manner, as in Hilbert’s tenth problem [25], to define X by means of a system of equations of degree two. For example, if one of the equations defining X has a term ax_{1}x_{3}^{3}x_{4}^{2}, with a ∈ F_{q}, then one can introduce new variables x_{1,3}, x_{3,3}, x_{4,4}, x_{1,3,3,3}, as well as new equations

x_{1,3} = x_{1}x_{3},  x_{3,3} = x_{3}^{2},  x_{4,4} = x_{4}^{2},  x_{1,3,3,3} = x_{1,3}x_{3,3},

and replace the term ax_{1}x_{3}^{3}x_{4}^{2} by ax_{1,3,3,3}x_{4,4}; and one can proceed similarly with other terms. If one next applies Gao’s reduction, then one obtains a hypersurface H that is defined by a cubic polynomial.

An amusing application of Gao’s formula is the reduction of the Hasse-Weil meromorphy conjecture to the case of a cubic hypersurface. Let the polynomials f_{i} have integer coefficients, and let the affine algebraic sets X and H be defined as above, but now over Z. Let

ζ(X, z) = ∏_{p prime} Z(X ⊗ F_{p}, p^{−z})

be the global complex Hasse-Weil zeta function of X; it is defined for complex numbers z whose real part is sufficiently large. The Hasse-Weil conjecture asserts that ζ(X) can be extended to a meromorphic function on all of C. Gao’s formula implies that

ζ(H, z) = \frac{ζ(X, z − m)ζ(z + 1 − m − n)}{ζ(X, z − m + 1)},

where ζ(z) is the Riemann zeta function. From this relation, one deduces by induction or iteration that if the Hasse-Weil conjecture is valid for all cubic hypersurfaces H, then it is valid for all algebraic sets X. (By contrast, for Hilbert’s tenth problem on diophantine equations over the integers, one only obtains a reduction to quartic hypersurfaces.) If we write

ζ(X, z) = ∑_{k=1}^{∞} \frac{a_{k}(X)}{k^{z}}

as a Dirichlet series, then Corollary 2.7 shows that each coefficient a_{k}(X) is effectively computable.

4 Hypersurface examples

In this section, we focus on the crucial case of hypersurfaces. We discuss them by increasing dimension.

Example 1. Let X be the zero-dimensional hypersurface defined by f(x) = 0, where f(x) is a non-constant monic polynomial over F_{q} in one variable. Write

f(x) = P_{1}(x)^{k_{1}} ⋯ P_{e}(x)^{k_{e}},

where the P_{i}(x) are pairwise distinct monic irreducible polynomials in F_{q}[x] and the k_{i} are positive integers. Then the Euler product reads

Z(X) = ∏_{j=1}^{e} \frac{1}{1 − T^{deg P_{j}(x)}} .

It is not hard to show that one can compute Z(X) in polynomial time using the Frobenius map. Note that if one factors the polynomial f(x) first, one does not get a polynomial time algorithm for computing Z(X). This is because there is currently no known (deterministic) polynomial time algorithm for factoring univariate polynomials over F_{q} if p is large, see Wan [35] for a further discussion and for the close relation of Z(X) to various algorithms for factoring univariate polynomials over finite fields. This example also occurred as an exercise ascribed to Lenstra in Cohen’s book ([6], Chap. 6, Exerc. 8).

Example 2. Let f(x_{1}, x_{2}) ∈ F_{q}[x_{1}, x_{2}] be of degree d, and suppose that the homogenization of f(x_{1}, x_{2}) defines a smooth projective plane curve C_{d} over F_{q}. The genus g of the curve C_{d} is well known to be

g = \frac{(d − 1)(d − 2)}{2}.

From the Riemann-Roch theorem one can deduce (see Monsky [27])

Z(C_{d}, T) = \frac{P (C_{d}, T)}{(1 − T)(1 − qT)},

where P (C_{d}, T) is a polynomial of degree 2g. Weil proved that we further have

P (C_{d}, T) = ∏_{j=1}^{2g}(1 − α_{j}T), |α_{j}| = \sqrt{q}, α_{j}α_{2g+1−j} = q.

The Riemann-Roch theorem also shows that the special value P (C_{d}, 1) has the following arithmetic meaning:

P (C_{d}, 1) = #J(C_{d})(F_{q}) ∈ Z_{>0},

where J(C_{d}) is the Jacobian variety of C_{d}, which is a g-dimensional abelian variety over F_{q}. All these results hold for any smooth projective geometrically irreducible curve over F_{q}, not just for plane curves.

The ℓ-adic method can be made effective in the case of curves and abelian varieties. One can then use the Chinese remainder theorem as mentioned before. In this way, one obtains an algorithm for computing Z(C_{d}, T) with running time O((log q)^{Δ_{d}}), where Δ_{d} is in general an exponential function of d, see Schoof [33] and Pila [29]. Thus, for fixed d, the ℓ-adic method computes the zeta function Z(C_{d}, T) in polynomial time, although the algorithm is still doubly exponential in d. For hyperelliptic curves, the exponent Δ_{d} has been improved to a polynomial in d, see Adleman-Huang [1]. On the other hand, using the p-adic algorithm in [22], one can compute the zeta function Z(C_{d}, T) in time (dp log q)^{O(1)}, which is polynomial in d but exponential in log p. In particular, the zeta function Z(C_{d}, T) can be computed in polynomial time if p = O((d log q)^{O(1)}). This example is important because of its many applications in number theory and cryptography, see Koblitz [19] and Blake et al. [4]. For special types of curves in small characteristic, more practical versions of various p-adic algorithms have been designed by a number of authors, see Satoh [32], Kedlaya [17], Lauder-Wan [23], Denef-Vercauteren [10], and the references listed in those papers. Restricting Problem 2.9 to plane curves, we obtain the following.

Problem 4.1 Given a smooth projective plane curve C_{d} over F_{q}, compute Z(C_{d}, T) in time O((d log q)^{c}), where c is an explicit absolute positive constant.

Example 3. Let f(x_{1}, …, x_{n}) ∈ F_{q}[x_{1}, …, x_{n}] be of degree d, and suppose that the homogenization of f defines a smooth projective hypersurface H_{d} of dimension n − 1 over F_{q}. Then by the Weil conjectures [7] we can write

Z(H_{d}, T) = \frac{P (H_{d}, T)^{(−1)^{n}}}{∏_{j=0}^{n−1}(1 − q^{j}T)},

where P (H_{d}, T) ∈ 1 + T Z[T] is a polynomial of degree (see Monsky [27])

D = \frac{1}{d}\{(d − 1)^{n+1} + (−1)^{n+1}(d − 1)\},

and

P (H_{d}, T) = ∏_{j=1}^{D}(1 − α_{j}T), |α_{j}| = \sqrt{q}^{n−1}, α_{j}α_{D+1−j} = q^{n−1}.

This higher dimensional example is undoubtedly more difficult than the previous example of curves, and it has attracted a smaller amount of attention. Both theoretically and computationally, and from an applied point of view, our understanding of this case leaves a great deal to be desired. In particular, the ℓ-adic method has not been made effective for higher dimensional smooth projective hypersurfaces. We do know that by the p-adic algorithm in [22], the zeta function Z(H_{d}, T) can be computed in time (d^{n}p log q)^{O(n)} for any (n − 1)-dimensional hypersurface H_{d}, not necessarily smooth or projective. This gives a polynomial time algorithm for small p and fixed n. In the smooth projective case, it should be possible to improve the exponent O(n) by finer p-adic cohomological methods. In fact, Lauder [20][21] has gone further and used the deformation method on the cohomology space to show that the zeta function can be computed in time (d^{n}p log q)^{O(1)} for suitable smooth projective (n − 1)-dimensional hypersurface H_{d}. It would be interesting to explore possible applications of higher dimensional hypersurfaces. As a special case of Problem 2.9, we have the following.

Problem 4.2 Given a smooth projective (n − 1)-dimensional hypersurface H_{d} defined over F_{q}, compute Z(H_{d}, T) in time bounded by a polynomial in (d + 1)^{n} log q.

Lauder’s recent results solve this problem if p is small.

5 Pure weight decomposition

In this section, we consider the problem of computing the numbers of zeros and poles of Z(X) with a given complex absolute value, for any algebraic set X defined over F_{q}. Let R(X, T) be the numerator or the denominator of the zeta function Z(X).

Over the complex numbers C, we can write

R(X, T) = ∏_{i}(1 − α_{i}T),

where each α_{i} is a non-zero algebraic integer. Define the weight of a non-zero complex number α by

w(α) = log_{q}(αᾱ),

where ᾱ denotes the complex conjugate of α. An elementary archimedean estimate shows that

#X(F_{q^{k}}) = O(q^{k dim(X)}),

where the implied constant depends on the degree of X. As in Section 2, one deduces the elementary estimate

|α_{i}| ≤ q^{dim(X)}, w(α_{i}) ≤ 2 dim(X).

The following much deeper result is a consequence of Deligne’s main theorem on the Weil conjectures [8].

Theorem 5.1 The weights of the reciprocal roots α_{i} of R(X, T) are integers in the interval [0, 2 dim(X)]. That is, for each α_{i}, there is an integer w_{i} with 0 ≤ w_{i} ≤ 2 dim(X) such that

α_{i}ᾱ_{i} = q^{w_{i}}.

In particular, each α_{i} is an ℓ-adic unit for all prime numbers ℓ ≠ p. Furthermore, each α_{i} and its Galois conjugates have the same weight.

The last part of the theorem can be deduced from the first part in an elementary manner, as shown in the following result of Lenstra.

Lemma 5.2 Let f ∈ Q[T] be an irreducible polynomial. Suppose α and β are two complex roots of f with αᾱ ∈ Q and ββ̄ ∈ Q. Then one has αᾱ = ββ̄.

Proof. Let αᾱ = a, ββ̄ = b, and deg(f) = n > 0. We need to show that a = b. Since there is a field isomorphism Q(α) ≅ Q(β) that sends α to β, we have

N_{Q(α)/Q}(α) = N_{Q(β)/Q}(β),

where N denotes the norm map. From a ∈ Q and Q(α) = Q(ᾱ) one deduces

a^{n} = N_{Q(α)/Q}(a) = N_{Q(α)/Q}(α)N_{Q(ᾱ)/Q}(ᾱ) = N_{Q(α)/Q}(α)^{2}.

Similarly,

b^{n} = N_{Q(β)/Q}(β)^{2}.

Putting the above together, one deduces that a^{n} = b^{n}. Since a ≥ 0 and b ≥ 0, we conclude that a = b. The proof is complete.

For an integer w with 0 ≤ w ≤ 2 dim(X), let

R(w, X, T) = ∏_{w(α_{i})=w}(1 − α_{i}T).

This is called the pure weight w part of R(X, T). By the above theorem of Deligne, each R(w, X, T) is a polynomial in 1 + T Z[T]. The pure weight decomposition is

R(X, T) = ∏_{w=0}^{2 dim(X)} R(w, X, T), R(w, X, T) ∈ 1 + T Z[T].

Theorem 5.3 Given the zeta function Z(X), one can compute all pure parts R(w, X, T) in polynomial time.

Proof. By the LLL (Lenstra-Lenstra-Lovász [24]) factorization algorithm, the polynomial R(X, T) can be factored as a product of irreducible polynomials in polynomial time:

R(X, T) = ∏_{i} g_{i}(T),

where each factor

g_{i} ∈ 1 + T Z[T]

is irreducible over Q. Write

g_{i}(T) = 1 + a_{i1}T + … + a_{ie_{i}}T^{e_{i}} = ∏_{j=1}^{e_{i}}(1 − β_{ij}T), a_{ie_{i}} ≠ 0.

By Deligne’s theorem 5.1, each β_{ij} is pure of some integer weight w_{i}. Hence a_{ie_{i}}^{2} = ∏_{j} β_{ij}β̄_{ij} = q^{e_{i}w_{i}}, and therefore

a_{ie_{i}} = ±\sqrt{q}^{w_{i}e_{i}} ∈ Z.

One can recover the integer weight w_{i} from

w_{i} = 2\frac{log_{q} |a_{ie_{i}}|}{e_{i}}.

The pure weight w part of Z(X) is then

R(w, X, T) = ∏_{w_{i}=w} g_{i}(T).

The theorem is proved.

Clearly, for each irreducible factor g_{i}(T) of R(X, T), the map β_{ij} ↦ β̄_{ij} = q^{w_{i}}/β_{ij} permutes the reciprocal roots of g_{i}(T). This gives the following functional equation.

Corollary 5.4 For each w, the pure weight part R(w, X, T) satisfies

R(w, X, 1/(q^{w}T)) = ±q^{−wd(w,R)/2}T^{−d(w,R)}R(w, X, T),

where d(w, R) denotes the degree of R(w, X, T).

The following is also immediate from Theorem 5.3.

Corollary 5.5 Given the zeta function, the degrees d(w, R) of all pure weight parts R(w, X, T) can be computed in polynomial time.

The pure degrees d(w, R) contain important geometric information about the variety X. For instance, if R_{2} denotes the denominator of Z(X), then d(2 dim(X), R_{2}) is the number of top-dimensional components of X ⊗ F̄_{q}. If X is a geometrically irreducible curve and R_{1} denotes the numerator of Z(X), then d(1, R_{1}) is twice the genus of the non-singular model of X. If X is smooth and projective, the pure degrees d(w, R) are geometric invariants, that is, they depend only on X ⊗ F̄_{q}. In fact, in this smooth projective case, they are given by the ℓ-adic Betti numbers, as shown in the proof of the following result.

Corollary 5.6 For any smooth projective variety X defined over F_{q}, the ℓ-adic Betti numbers of X can be effectively computed, where ℓ ≠ p.

Proof. For a smooth projective variety X over F_{q}, the ℓ-adic trace formula states

Z(X) = ∏_{i=0}^{2 dim(X)} det(I − (Frob|H^{i}(X ⊗ F̄_{q}, Q_{ℓ}))T)^{(−1)^{i−1}},

where Frob denotes the geometric Frobenius map. By the Weil conjectures as proved in [7], each (complex) eigenvalue of Frob acting on H^{i} has weight equal to i. Thus, the ith Betti number

B_{i}(X, ℓ) = dim_{Q_{ℓ}} H^{i}(X ⊗ F̄_{q}, Q_{ℓ})

is given by the formula

B_{i}(X, ℓ) = \{ \begin{matrix}d(i/2, R_{1}), & if i is odd, \\ d(i/2, R_{2}), & if i is even, \end{matrix}

where R_{1} and R_{2} are the numerator and denominator of Z(X), respectively. The corollary follows.

Let Y be a smooth projective scheme over Z and let X = Y ⊗ F_{p} be the reduction modulo p of Y. The cohomological comparison theorem shows that for all large primes p, the pure degrees d(w, R(X, T)) depend only on the geometry of Y ⊗ Q̄, not on the chosen large prime p.

If X is singular or open, the pure degrees d(w, R) may not be geometric invariants, as it may happen that a root and a pole of Z(X) have a quotient that is a root of unity. On the other hand, it is clear that the pure difference degrees d(w, R_{1})−d(w, R_{2}) are geometric invariants, where we recall that R_{1} and R_{2} denote the numerator and the denominator of Z(X), respectively.

It would be interesting to know if the pure degrees d(w, R) can be computed in polynomial time without the zeta function being given. Even for a singular plane curve this seems to be unknown. In the case of a smooth projective complete intersection there is a well-known formula showing that the pure degrees can be computed from the total degree of Z(X) and the dimension of X; see Example 3 of Section 4 for the case of a smooth projective hypersurface and [9] (page 39–61) for the general smooth projective complete intersection case.

For arbitrary X over F_{q}, not necessarily smooth or projective, Grothendieck [14] has shown that for ℓ ≠ p there is a similar ℓ-adic formula in terms of ℓ-adic cohomology with compact support:

Z(X) = ∏_{i=0}^{2 dim(X)} det(I − (Frob|H_{c}^{i}(X ⊗ F̄_{q}, Q_{ℓ}))T)^{(−1)^{i−1}}.

But in this generality, even the conjectured independence of the ℓ-adic Betti numbers on ℓ is unknown. The following result of Katz [16] provides weak evidence in this direction. It gives an explicit upper bound for the ℓ-adic Betti numbers with compact support that is independent of ℓ. It is obtained by means of an inductive reduction to the Bombieri-Adolphson-Sperber degree bound for Z(X), which in turn is p-adic in nature.

Theorem 5.7 Let the polynomials f_{1}, …, f_{m} form a system of defining equations for the affine algebraic set X, and put d = max_{i} deg(f_{i}). Then, for every prime number ℓ ≠ p, we have

∑_{i≥0} dim_{Q_{ℓ}} H_{c}^{i}(X ⊗ F̄_{q}, Q_{ℓ}) ≤ 2^{m+2}(md + 3)^{n+1}.

Turning to global zeta functions, it may be of interest to point out that the real parts of the zeros of the classical Riemann zeta function ζ(z) are not known to be effectively computable in a finite region. To make this precise, denote, for real numbers w ∈ (0, 1) and t > 0, by d(w, ζ; t) the number of zeros of ζ(z) that lie on the line segment

Re(z) = w, 0 ≤ Im(z) ≤ t.

For any given t, there are only finitely many w for which d(w, ζ; t) > 0. The following computational problem is now analogous to finding the pure weight decomposition: given t, determine the finitely many positive integers among the numbers d(w, ζ; t), for 0 ≤ w ≤ 1, as well as approximations to the corresponding numbers w. No effective algorithm for doing this is currently available. The main difficulty is caused by the possibility of a multiple zero or zeros that are very close to each other, see Odlyzko [28]. Of course, the Riemann hypothesis says that d(w, ζ; t) = 0 for all t and all w ≠ 1/2.

6 Pure slope decomposition

In the previous section, we considered the problem of purity decomposition of Z(X) from the complex point of view. One can also consider the purity decomposition from a non-archimedean point of view. If ℓ is a prime number different from p, then Deligne’s Theorem 5.1 shows that Z(X) is already pure from an ℓ-adic point of view. Thus, we will consider the remaining p-adic case in this section. Let R(X, T) again denote either the numerator or the denominator of Z(X).

Let C_{p} be the completion of a fixed algebraic closure of Q_{p}. Over C_{p}, we can write

R(X, T) = ∏_{i}(1 − α_{i}T),

where each α_{i} is a non-zero algebraic integer in C_{p}. Define the slope of a non-zero element α ∈ C_{p} by

s(α) = ord_{q}(α) = − log_{q} |α|_{p},

where |·|_{p} denotes the p-adic absolute value, normalized such that |p| = 1/p. The slopes s(α_{i}) are non-negative rational numbers since the α_{i} are algebraic integers. One immediately derives the bound

0 ≤ s(α_{i}) ≤ s(α_{i}ᾱ_{i}) = w(α_{i}) ≤ 2 dim(X).

This bound can be improved somewhat. Deligne’s integrality theorem [9] (page 384–400) states that q^{dim(X)}/α_{i} is an algebraic integer. We deduce the following result.

Theorem 6.1 The slopes s(α_{i}) are rational numbers in [0, dim(X)].

Other than in the complex absolute value case, α_{i} and its Galois conjugates over Q may have different slopes. Of course, each α_{i} and its Galois conjugates over Q_{p} do have the same slope. The slopes s(α_{i}) are not integers (or half integers) in general. They are merely rational numbers. It would be interesting to get good bounds for the denominators of the slopes s(α_{i}).

For a rational number s with 0 ≤ s ≤ dim(X), let

R(s, X, T) = ∏_{s(α_{i})=s}(1 − α_{i}T).

This is called the pure slope s part of R(X, T). We have the p-adic purity decomposition

R(X, T) = ∏_{s∈Q} R(s, X, T).

The question is then to understand each pure slope part R(s, X, T).

Note that in general, the pure slope parts R(s, X, T) do not have coefficients in Z any more. The theory of Newton polygons implies that R(s, X, T) is a polynomial in 1 + T (Q̄ ∩ Z_{p})[T], as we shall see now.

Write

R(X, T) = 1 + a_{1}T + … + a_{e}T^{e} = ∏_{i=1}^{e}(1 − α_{i}T), a_{e} ≠ 0.

Definition 6.2 The Newton polygon NP(R) of R(X, T) is the lower convex hull in the plane R^{2} of the points

(k, ord_{q}(a_{k})), k = 0, 1, …, e.

A basic property of the Newton polygon is the following result, see Koblitz [18].

Theorem 6.3 The polynomial R(X, T) ∈ 1 + T Z[T] has exactly h reciprocal zeros α_{i} with slope ord_{q}(α_{i}) = s (counting multiplicities) if and only if NP(R) has a side of slope s and horizontal length h. Furthermore, the coefficients of R(s, X, T) are in Z_{p} for each s.

The following is an immediate consequence.

Corollary 6.4 Let d(s, R) denote the degree of R(s, X, T). Then, d(s, R) is the horizontal length of the slope s side of NP(R). In particular, when Z(X) is given, the p-adic pure degrees d(s, R) can be computed in polynomial time.

Figure 1: Newton polygon

It would be interesting to know if the p-adic pure degrees d(s, R) can be computed in polynomial time without the zeta function being given. This amounts to computing the Newton polygons of the numerator and the denominator of the zeta function. Even in a very well-behaved situation such as the smooth projective hypersurface case, we do not have a complete answer in general; see Wan [36] for a theoretical introduction to Newton polygons for zeta functions and L-functions. In the smooth projective case, the p-adic pure degrees d(s, R) are geometric invariants.

If X is the good reduction modulo p of some smooth projective scheme over Z, the p-adic pure degrees d(s, R) depend not just on the geometry of the generic fibre Y ⊗ Q̄, but also on the chosen prime p. Thus, the padic pure degrees d(s, R) contain arithmetic information on Y. They are related to but much deeper than the topological Hodge numbers of Y ⊗ Q defined in terms of the De Rham cohomology of Y ⊗ Q, see Mazur [26] for an introductory account. Describing the variation of d(s, R) as p varies is a very subtle arithmetic problem, already in the special case that Y ⊗ Q is an elliptic curve.

As a polynomial with coefficients in Z_{p}, the pure slope part R(s, X, T) cannot be written down in a finite amount of time. However, given R(X, T), one can compute the pure slope parts R(s, X, T) modulo any given power of p in polynomial time using the Newton polygon and Hensel lifting. Note that here we do not factor R(X, T) into a product of irreducible factors over Q_{p}, which is a harder problem.

7 Zeta functions modulo p

In [22] a p-adic algorithm for computing the zeta function Z(X) is given, where p is the characteristic of F_{q}. In this final section, we describe some of the basic ideas behind that algorithm by showing how Z(X) may be computed modulo p. The method expands the outline given in Wan [35].

Without loss of generality we may restrict to hypersurfaces. Thus, let X be the affine hypersurface defined by a polynomial f(x_{1}, …, x_{n}) over F_{q} of total degree d in n variables. Let A_{d} be the F_{q}-vector space of polynomials in x_{1}, …, x_{n} of total degree at most d that are divisible by the product x_{1} ⋯ x_{n}:

A_{d} = (x_{1} ⋯ x_{n}F_{q}[x_{1}, …, x_{n}])_{≤d}.

It has a row basis e⃗ consisting of monomials

e⃗ = {x^{u}|u = (u_{1}, …, u_{n}), u_{i} ≥ 1, |u| ≤ d},

where

x^{u} = x_{1}^{u_{1}} ⋯ x_{n}^{u_{n}}, |u| = u_{1} + … + u_{n}.

One computes that

dim_{F_{q}} A_{d} = \binom{d}{n}.

Definition 7.1 Let σ be the pth power Frobenius map acting on F_{q}:

σ(a) = a^{p}, a ∈ F_{q}.

Let ψ_{p} be the σ^{−1}-linear operator on the F_{q}-vector space F_{q}[x_{1}, …, x_{n}] defined by

ψ_{p}(∑_{u} a_{u}x^{u}) = ∑_{u} σ^{−1}(a_{u})ψ_{p}(x^{u}),

where

ψ_{p}(x^{u}) = \{ \begin{matrix}x^{u/p}, & if p|u, \\ 0, & otherwise. \end{matrix}

Define

ψ_{q} = ψ_{p}^{r} = ψ_{p} ∘ ⋯ ∘ ψ_{p}

to be the rth iterate of ψ_{p}, where q = p^{r}.

Since σ^{r} is the identity on F_{q}, the operator ψ_{q} is actually F_{q}-linear, although ψ_{p} is only σ^{−1}-linear. The operator ψ_{q} is a left inverse of the qth power Frobenius map on F_{q}[x] = F_{q}[x_{1}, …, x_{n}]. For any polynomial g ∈ F_{q}[x], multiplication by g is also an F_{q}-linear map from F_{q}[x] to itself.

Lemma 7.2 The F_{q}-linear composed operator ψ_{q} ∘ f^{q−1} maps the finite dimensional F_{q}-subspace A_{d} of F_{q}[x] to itself; here f^{q−1} denotes multiplication by f^{q−1}. Similarly, the σ^{−1}-linear composed operator ψ_{p} ∘ f^{p−1} maps A_{d} to itself, and we have the relation

ψ_{q} ∘ f^{q−1} = (ψ_{p} ∘ f^{p−1})^{r}.

Proof. Let h ∈ A_{d}. Then h has degree at most d, so f^{q−1}h has degree at most d(q − 1) + d = dq. Thus, the degree of ψ_{q}(f^{q−1}h) is at most d. Furthermore, if h is divisible by x_{1} ⋯ x_{n}, then ψ_{q}(f^{q−1}h) is also divisible by x_{1} ⋯ x_{n}. This proves that ψ_{q}(f^{q−1}h) ∈ A_{d}. The proof of the second part of the lemma is the same. To prove the last part, we write

q − 1 = (p − 1) + p(p − 1) + … + p^{r−1}(p − 1).

This gives

f(x)^{q−1} = ∏_{i=0}^{r−1} f^{σ^{i}}(x^{p^{i}})^{p−1},

where f^{σ^{i}}(x) denotes the polynomial obtained by applying σ^{i} to the coefficients of f. Using the easily checked relation

ψ_{p} ∘ g^{σ}(x^{p}) = g(x) ∘ ψ_{p},

one deduces

ψ_{q} ∘ f^{q−1} = ψ_{p}^{r} ∘ ∏_{i=0}^{r−1} f^{σ^{i}}(x^{p^{i}})^{p−1} = (ψ_{p} ∘ f^{p−1})^{r}.

The lemma is proved.

Theorem 7.3 Let X be the affine hypersurface defined by a polynomial f(x_{1}, …, x_{n}) over F_{q} of total degree d in n variables. Then we have the congruence formula

(Z(X)^{(−1)^{n}} mod p) = det(I − (ψ_{q} ∘ f^{q−1}|A_{d})T).

Before we prove this result, we first recall some facts on L-functions in characteristic p. Let g ∈ F_{q}[x] = F_{q}[x_{1}, …, x_{n}]. For a geometric point x ∈ A^{n}(F̄_{q}), the product g(x)g(x^{q}) ⋯ g(x^{q^{deg(x)−1}}) is an element of F_{q} that clearly depends only on the orbit (the closed point) of x under the qth power Frobenius map. We define the L-function of g by

L(g, T) = ∏_{x} \frac{1}{1 − g(x)g(x^{q}) ⋯ g(x^{q^{deg(x)−1}})T^{deg(x)}} ∈ 1 + T F_{q}[[T]],

where x runs over the set of closed points of the affine space A^{n} over F_{q}.

For a real number c, write A_{c} for the finite dimensional F_{q}-subspace of F_{q}[x] generated by the monomials of total degree at most c that are divisible by the product x_{1} ⋯ x_{n}. If the total degree of g is at most e, one checks as in the above lemma that the operator ψ_{q} ∘ g maps the subspace A_{e/(q−1)} to itself. Furthermore, the (matrix of the) induced map ψ_{q} ∘ g on the quotient vector space x_{1} ⋯ x_{n}F_{q}[x]/A_{e/(q−1)} is strictly triangular with respect to the monomial basis {x^{u}|u_{i} ≥ 1, |u| > e/(q − 1)}. Thus, the composed operator ψ_{q} ∘ g acting on the infinite dimensional F_{q}-vector space x_{1} ⋯ x_{n}F_{q}[x] has a well defined characteristic power series det(I − (ψ_{q} ∘ g|x_{1} ⋯ x_{n}F_{q}[x])T), which is given by the polynomial

det(I − (ψ_{q} ∘ g|x_{1} ⋯ x_{n}F_{q}[x])T) = det(I − (ψ_{q} ∘ g|A_{e/(q−1)})T).

The characteristic p version of Dwork’s trace formula for the affine space A^{n}, as given in [34], implies that

L(g, T)^{(−1)^{n−1}} = det(I − (ψ_{q} ∘ g|x_{1} ⋯ x_{n}F_{q}[x])T)

and thus

L(g, T)^{(−1)^{n−1}} = det(I − (ψ_{q} ∘ g|A_{e/(q−1)})T).

The reader is referred to [22] to see the Dwork trace formula over the ntorus, which is cleaner than the Dwork trace formula over the affine n-space A^{n}.

We now return to the proof of the theorem. Taking g = f^{q−1} and e = d(q − 1), we deduce that e/(q − 1) = d and

L(f^{q−1}, T)^{(−1)^{n−1}} = det(I − (ψ_{q} ∘ f^{q−1}|A_{d})T).

For a geometric point x ∈ A^{n}(F̄_{q}), one has

g(x)g(x^{q}) ⋯ g(x^{q^{deg(x)−1}}) = f(x)^{q^{deg(x)}−1},

which is 0 or 1 according as x ∈ X(F̄_{q}) or not. It follows that L(f^{q−1}, T) is the reduction modulo p of the zeta function of the complement of X in A^{n}. Hence for n > 0 we obtain

L(f^{q−1}, T) = (1/Z(X) mod p).

Substituting this into the above formula for L(f^{q−1}, T)^{(−1)^{n−1}}, we obtain the theorem.

Corollary 7.4 The zeta function Z(X) modulo p can be computed in time bounded by a polynomial in p\binom{d}{n} log q.

Proof. Recall that q = p^{r}. Let M_{1} be the matrix of the σ^{−1}-linear map ψ_{p} ∘ f^{p−1} with respect to the row monomial basis e⃗ of A_{d}. That is,

(ψ_{p} ∘ f^{p−1})(e⃗) = e⃗M_{1}.

Then, by the σ^{−1}-linearity of ψ_{p} ∘ f^{p−1}, we deduce

(ψ_{p} ∘ f^{p−1})^{2}(e⃗) = (ψ_{p} ∘ f^{p−1})(e⃗M_{1}) = e⃗M_{1}M_{1}^{σ^{−1}},

where M_{1}^{σ^{−1}} is obtained from M_{1} by applying σ^{−1} to each entry (and similarly with M_{1}^{σ^{−i}} below). By iteration, one finds that the matrix of the F_{q}-linear map

ψ_{q} ∘ f^{q−1} = (ψ_{p} ∘ f^{p−1})^{r}

with respect to the row basis e⃗ is given by

M_{r} = M_{1}M_{1}^{σ^{−1}} ⋯ M_{1}^{σ^{−(r−1)}}.

The matrix M_{1} can be written down in time (p\binom{d}{n} log q)^{O(1)}. It follows that the matrix M_{r} can also be computed in time (p\binom{d}{n} log q)^{O(1)}. The zeta function modulo p is essentially just the characteristic polynomial of the matrix M_{r}:

(Z(X)^{(−1)^{n}} mod p) = det(I − M_{r}T).

The corollary is proved. Alternatively, applying σ^{r−1} to the above congruence formula, we have

(Z(X)^{(−1)^{n}} mod p) = det(I − M_{1}^{σ^{r−1}} ⋯ M_{1}^{σ}M_{1}T).

This formula may be slightly more efficient from a computational point of view.

If p is small, that is, p = (\binom{d}{n} log q)^{O(1)}, the above corollary gives a polynomial time algorithm for computing Z(X) modulo p. If p is large, we do not get a polynomial time algorithm.

References

[1] L.M. Adleman and M.D. Huang, Counting rational points on curves and abelian varieties over finite fields, Lecture Notes in Computer Science, 1122 (1996), 1–16.

[2] A. Adolphson and S. Sperber, On the degree of the L-function associated with an exponential sum, Compositio Math., 68 (1988), no. 2, 125–159.

[3] R.E. Blahut, Decoding of cyclic codes and codes on curves, in Handbook of Coding Theory, edited by V.S. Pless and W.C. Huffman, 1998, 1569–1633.

[4] I.F. Blake, G. Seroussi, N.P. Smart, Elliptic Curves in Cryptography, London Mathematical Society Lecture Note Series, 265, Cambridge University Press, Cambridge, 2000.

[5] E. Bombieri, On exponential sums in finite fields, II, Invent. Math., 47 (1978), 29–39.

[6] H. Cohen, A Course in Computational Number Theory, Springer-Verlag, Berlin, 1993.

[7] P. Deligne, La Conjecture de Weil, I, Publ. Math., IHES, 43 (1974), 273–307.

[8] P. Deligne, La Conjecture de Weil, II, Publ. Math., IHES, 52 (1980), 137–252.

[9] P. Deligne and N. Katz, Groupes de Monodromie en Géométrie Algébrique, SGA 7 II, Lecture Notes in Math., 340 (1973).

[10] J. Denef and F. Vercauteren, An extension of Kedlaya’s algorithm to Artin-Schreier curves in characteristic 2, preprint, 2002.

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

[12] D. Eisenbud, Commutative Algebra, GTM, Springer-Verlag, New York, 1995.

[13] N.D. Elkies, Elliptic and modular curves over finite fields and related computational issues, in Computational perspectives on number theory (Chicago, IL, 1995), 21–76, AMS/IP Stud. Adv. Math., 7, Amer. Math. Soc., Providence, RI, 1998.

[14] A. Grothendieck, Formule de Lefschetz et rationalité des fonctions L, Séminaire Bourbaki, exposé 279, 1964/65.

[15] N. Katz, On a theorem of Ax, Amer. J. Math., 93 (1971), 485–499.

[16] N. Katz, Sums of Betti numbers in arbitrary characteristic, Finite Fields Appl., 7 (2001), 29–44.

[17] K.S. Kedlaya, Counting points on hyperelliptic curves using Monsky-Washnitzer cohomology, J. Ramanujan Math. Soc., 16 (2001), 323–338.

[18] N. Koblitz, p-adic Numbers, p-adic Analysis, and Zeta Functions, GTM, Springer, 1996.

[19] N. Koblitz, Hyperelliptic cryptosystems, J. Cryptology, 1 (1989), 139–150.

[20] A. Lauder, Deformation theory and the computation of zeta functions, Proc. London Math. Soc., to appear.

[21] A. Lauder, Counting solutions to equations in many variables over fintie fields, prperpint.

[22] A. Lauder and D. Wan, Counting points on varieties over finite fields of small characteristic, these proceedings.

[23] A. Lauder and D. Wan, Computing zeta functions of Artin-Schreier curves over finite fields, LMS J. Comput. Math., 5 (2002), 34–55.

[24] A.K. Lenstra, H.W. Lenstra, Jr., L. Lovász, Factoring polynomials with rational coefficients. Math. Ann., 261 (1982), no. 4, 515–534.

[25] Y.V. Matiyasevich, Hilbert’s Tenth Problem, The MIT Press, 1996.

[26] B. Mazur, Frobenius and the Hodge filtration, Bull. Amer. Math. Soc., 78 (1972), 653–667.

[27] P. Monsky, p-adic Analysis and Zeta Functions, Lectures in Mathematics, Kyoto University, Tokyo, 1970.

[28] A.M. Odlyzko, Analytic computations in number theory, Mathematics of Computation 1943–1993: a half-century of computational mathematics (Vancouver, BC, 1993), 451–463, Proc. Sympos. Appl. Math., 48, Amer. Math. Soc., Providence, RI, 1994.

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

[30] C. Pomerance, Primality testing: variations on a theme of Lucas, these proceedings.

[31] B. Poonen, Computational aspects of curves of genus at least 2, Lecture Notes in Computer Science, 1122 (1996), 283–306.

[32] 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.

[33] R. Schoof, Elliptic curves over finite fields and the computation of square root modulo p, Math. Comp., 44 (1985), 483–494.

[34] D. Wan, Meromorphic continuation of L-functions of p-adic representations, Ann. Math., 143 (1996), 469–498.

[35] D. Wan, Computing zeta functions over finite fields, Contemporary Mathematics, 225 (1999), 131–141.

[36] D. Wan, Variation of p-adic Newton polygons for L-functions of exponential sums, preprint.

[37] A. Weil, Numbers of solutions of equations in finite fields, Bull. Amer. Math. Soc., 55 (1949), 497–508.