# Edixhoven: About Point Counting over Arbitrary Finite Fields

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:

where we denote cohomology with compact support. This is true for a scheme of finite type which is separated over . For these cohomology groups, one can take a -adic approach using a de Rham-type cohomology, lifting to a -adic ring and take the hypercohomology of the de Rham sequence, quite explicit and computable but the complexity is worse than linear in . Instead, one can also use mod methods ( ); here one takes the groups which is a lot less explicit. The derive from injective resolutions on the etale topology. In this setup, there is the advantage that you can choose . For an elliptic curve, one has

What is the simplest interesting case where we want to but cannot yet compute an with ? We think of surfaces, or modular forms of weight (to generalize the case of elliptic curves, which correspond to eigenforms of weight 2). We assume that there is a cohomology group of dimension (if it is of dimension , Frobenius acts as a power of the cyclotomic character).

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

where . We have . (For prime, .) This map on complex points is given by maps to the point . Here, for one can choose a -rational cusp.

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.