Programming Research Group Research ReportRR-03-10

Alan G.B. Lauder

April 2003, 39pp.

Abstract

Let f be a homogeneous polynomial of degree d in n variables over the finite field with q elements of characteristic p. Assume that the projective hypersurface defined by f is smooth, and that p ≠ 2 with d not divisible by p. We show that one may compute the zeta function of this hypersurface in (pdⁿlog(q))^O(1) bit operations, where ^O(1) denotes an absolute constant. This improves upon an earlier algorithm of the author and Wan which requires (pdⁿlog(q))^O(n) bit operations, but falls short of the conjectured optimal complexity of (dⁿlog(q))^O(1) bit operations. In the algorithm, one deforms the polynomial f through a one-dimensional family to obtain a non-singular diagonal form. The p-adic variation of the zeta functions of fibres in this family is controlled by a differential equation. Taking the zeta function of the diagonal hypersurface as a starting point, solving locally the differential equation, and using a p-adic analytic continuation algorithm, one can compute the zeta function of the hypersurface defined by f. The key point is that because the deformation is one-dimensional, the complexity of the algorithm is largely independent of n.