Consider a system of equations , , given by polynomials . This is not essentially different than the case of a single hypersurface (every variety is birational to a hypersurface, or, also, one can use the inclusion-exclusion principle). We let .

**Question. **
For fixed , is there an algorithm that computes the number of
solutions in
in time polynomial in the quantities:
(or and ),
, and ?

If you fix , and , then the answer is yes (Lauder-Wan) using -adic methods. We discuss the case where is not fixed. If is not fixed, then one knows that the answer is yes for elliptic curves (Schoof) using -torsion points and curves of a given genus via the -torsion of their jacobian (Pila).

Conceptually, all methods use Lefschetz fixed points formula:

We consider as an example the modular form is an eigenform of weight , viewed as a function on the upper half-plane. Then is an -invariant on , so it descends to . The variety we work with is the ten-fold product of the universal elliptic curve ; we find that has dimension . For all , and , is the trace of on , which is also the trace of on with acting on it: it is the two-dimensional Galois representation (modulo ) associated to . The action factors through acting faithfully where is a finite extension.

Compute explicitly the extension . One gets as a byproduct a computation of the actual representation, which we cannot easily compute now. A bit of work yields that is the Galois closure of the field definition of a suitable element , where is the jacobian of , if together with te cusps, and is the set of matrices with , . Still: need to compute this efficiently. This is not so easy because the genus of is quadratic in .

We have the following strategy for finding (based a suggestion of Jean-Marc Couveignes). We have a surjection

Generically, there is a unique point up to permutation which gives the point , namely, . Now one estimates the height of , approximates in by lifting (numerically) the straight line path from 0 to (possible because the map is generically unramified). It will probably be a good idea to replace the divisor by a sum of distinct points , with small height, defined over a small and solvable extension of . As and the determine the (up to permutation), and as is a torsion point (Néron-Tate height zero) one expects that the height of is not much bigger than that of the . So one hopes that the required number of correct digits of the approximation of grows polynomially in . The tool to be used for estimating the height of is Arakelov geometry. A good indication that this proposed strategy works is that the height estimate works well in the function field case (a nice application of the Grothendieck-Riemann-Roch theorem).

Back to the
main index
for Future directions in algorithmic number theory.