Deformation Theory and The Computation of Zeta Functions

We present a new approach to the problem of computing the zetafunction of a hypersurface over a finite field. For a hypersurfacedefined by a polynomial of degree d in n variables over thefield of q elements, one desires an algorithm whose runningtime is a polynomial function of dⁿ log(q). (Here we assumed 2, for otherwise the problem is easy.) The case n = 1 isrelated to univariate polynomial factorisation and is comparativelystraightforward. When n = 2 one is counting points on curves,and the method of Schoof and Pila yields a complexity of , where the function C_d depends exponentiallyon d. For arbitrary n, the theorem of the author and Wan givesa complexity which is a polynomial function of (pdⁿ log(q))ⁿ,where p is the characteristic of the field. A complexity estimateof this form can also be achieved for smooth hypersurfaces usingthe method of Kedlaya, although this has only been worked outin full for curves. The new approach we present should yielda complexity which is a small polynomial function of pdⁿ log(q).In this paper, we work this out in full for Artin–Schreierhypersurfaces defined by equations of the form Z^p – Z= f, where the polynomial f has a diagonal leading form. Themethod utilises a relative p-adic cohomology theory for familiesof hypersurfaces, due in essence to Dwork. As a corollary ofour main theorem, we obtain the following curious result. Letf be a multivariate polynomial with integer coefficients whoseleading form is diagonal. There exists an explicit deterministicalgorithm which takes as input a prime p, outputs the numberof solutions to the congruence equation f = 0 op, and runs in bit operations, for any >0. This improves upon the elementary estimate of bit operations, where n is the number of variables,which can be achieved using Berlekamp's root counting algorithm.2000 Mathematics Subject Classification 11Y99, 11M38, 11T99.