Skip to main content

Deformation theory and the computation of zeta functions II

Alan G.B. Lauder

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 (pdnlog(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 (pdnlog(q))O(n) bit operations, but falls short of the conjectured optimal complexity of (dnlog(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 ofn.

Institution
Oxford University Computing Laboratory
Month
April
Number
RR−03−10
Year
2003