Programming Research Group Research Report RR-02-15

Alan G.B. Lauder

December 2002, 36pp.

Abstract

We introduce a systematic new approach to the computation of zeta functions of varieties over finite fields. The method is based upon the following idea. To compute the zeta function of a smooth hypersurface, one embeds it in a one-parameter family of hypersurfaces, such that the fibre at the origin is smooth and has an easily computed zeta function, e.g., is a diagonal hypersurface. Associated to this family is a differential equation, the Picard-Fuchs equation. By solving this equation numerically around the origin, one is then able to recover the zeta function of any smooth fibre in the family, and in particular, the original hypersurface. The great merit of this approach is that the complexity is largely independent of the dimension of the variety, since one essentially always studies a one-dimensional deformation problem. This is not the case with all previous methods. The method is developed in full detail for a particular type of affine hypersurface, namely, Artin-Schreier covers defined by polynomials whose leading forms are diagonal. In this case, the algorithm has a cubic time dependence on the field size, and quartic time dependence on the field charactertistic, in all dimensions. Our main theorem also has an application to counting modular solutions to integer polynomial equations.