Effective computation of zeta-functions

The Weil conjectures (proved by Dwork, Grothendieck, Deligne et al.) assert that for any algebraic variety $X$ over a finite field ${F}_q$, the power series

$$\zeta_X(T) = \exp \left( \sum_{i=1}^\infty \frac{\char93 X({F}_{q^i})}{i} T^i \right)$$

is a rational function of $T$; giving explicit methods for computing $\zeta_X(T)$ is a fundamental problem in computational number theory. In principle, one can do this by simply giving bounds on the degrees of the numerator and denominator, then explicitly computing $\char93 X({F}_{q^i})$ for enough values of $i$. (E.g., if $X$ is projective, one can choose a projective embedding of $X$, defined by certain equations, then count the number of points in projective space satisfying those equations.) In practice, this enumeration gives an algorithm which requires time exponential in the ``complexity'' of $X$ (e.g., the logarithm of the base field size $q$, and the degrees of the equations defining $X$) and thus can only be completed for relatively small examples.

Below we describe the current state of knowledge regarding subexponential methods for computing zeta functions. We omit mention of methods which improve on pure exhaustion but are still exponential, such as Mestre's ``baby step-giant step'' method for computing the zeta function of an elliptic curve.

Back to the main index for L-functions and Random Matrix Theory.