We present an algorithm which allows us to count solutions to a homogeneous equation of degree (for simplicity we assume , ) with running time which does not increase exponentially in number of variables. In other words, we are interested in computing the number of projective solutions
If we compute naively for then we can of course recover the polynomial ; the time required to do this, however, requires evaluations of . The input is given by terms of size , and the output size is approximately . We would like the running time to be polynomial in this quantity.
If , we are counting solutions of a univariate polynomial, and this can be done in time . For , we have an algorithm of Schoof-Pila for curves which has run time where depends on exponentially. In general, there is an algorithm (due to L. and Wan) which runs in time . Notice the in the exponent--we would like to lose this dependence.
The new result: If is `sufficiently generic' (we exclude a Zariski closed set which is efficiently computable), , and , then we can find using bit operations. As a corollary, we see that if is sufficiently generic, then there exists an algorithm which takes as input a prime , outputs the number of solutions , and has run time .
Recall that , where we write for the projective variety defined by the equation . The action of can be represented by a matrix with entries in a field of characteristic zero, and we find that
Instead, we work with the -adic theory, where is a -module for a ring . We compute instead , and compute the matrix of . (Specifically, where is the unramified extension of of degree and . Also our is actually the primitive part of the cohomology space.) Consider the family
We see that where , and is a matrix of power series around the origin satisfying the differential equation with initial condition , where is easily computed. This gives a way to compute in a radius around the origin, and we need to extend this to the closed disc of radius .
The entries of the matrices are -adic holomorphic functions, so to compute these modulo a power of we find rational functions with denominators corresponding to the values of where the variety becomes singular and then recover the numerator from the power series. Using overconvergence we get a bound on the degree of these rational functions. We evaluate the rational functions at . One gets nice complexity because we work with univariate power series, with decay in the coefficients on the order of , and one needs to take the power of approximately on the order of .
In the old algorithm, we would work in , the ring of power series in over an where is the unramified extension of of degree (if ) and modulo an infinite subspace; the power series we must work with have on the order of terms.
Problem. Find an algorithm which counts the number of points on a curve in time .
Back to the main index for Future directions in algorithmic number theory.