Edixhoven: About Point Counting over Arbitrary Finite Fields

Consider a system of equations $f_1(x_1,\dots,x_n)=0$, $\dots$, $f_m(x_1,\dots,x_n)=0$ given by polynomials $f_i \in \mathbb{F}_q[x_1,\dots,x_n]$. 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 $q=p^r$.

Question. For fixed $n$, is there an algorithm that computes the number of solutions in $\mathbb{F}_q$ in time polynomial in the quantities: $\log q$ (or $r$ and $\log p$), $d=\max_i \deg f_i$, and $m$?

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

Conceptually, all methods use Lefschetz fixed points formula:

$$\char93 X(\mathbb{F}_q)= \textstyle{\sum_{i=0}^{2\dim X}} (-1)^i {\mathrm{Tr}}({\mathrm{Frob}}_q\vert H^i_c(X))$$

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

$$E(\overline{\mathbb{F}_q})[\ell]\spcheck=H^1(E_{\overline{\mathbb{F}_q},et},\mathbb{F}_\ell).$$

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

We consider as an example the modular form $\Delta=q \prod_{n \geq 1} (1-q^n)^{24}=\sum_{n \geq 1} \tau(n) q^n$ is an eigenform of weight $12$, viewed as a function on the upper half-plane. Then $\Delta(dq/q)^{\otimes 6}$ is an $SL_2(\mathbb{Z})$-invariant on $\mathfrak{H}$, so it descends to $\mathfrak{H}/SL_2(\mathbb{Z})$. The variety we work with is the ten-fold product of the universal elliptic curve $E$; we find that $H^{11}(E^{10})$ has dimension $2$. For all $p$, and $\ell \neq p$, $\tau(p) \bmod \ell$ is the trace of ${\mathrm{Frob}}_p$ on $H^{11}(E^{10}_{\overline{\mathbb{F}_p},et},\mathbb{F}_\ell)$, which is also the trace of ${\mathrm{Frob}}_p$ on $H^{11}(E^{10}_{\overline{\mathbb{Q}},et},\mathbb{F}_\ell)$ with ${\mathrm{Gal}}(\overline{\mathbb{Q}}/\mathbb{Q})$ acting on it: it is the two-dimensional Galois representation (modulo $\ell$) associated to $\Delta$. The action factors through ${\mathrm{Gal}}(K_{\Delta,\ell}/\mathbb{Q})$ acting faithfully where $K_{\Delta,\ell}/\mathbb{Q}$ is a finite extension.

Compute explicitly the extension $K_{\Delta,\ell}$. One gets as a byproduct a computation of the actual representation, which we cannot easily compute now. A bit of work yields that $K_{\Delta,\ell}$ is the Galois closure of the field definition of a suitable element $x \in J_1(\ell)(\overline{\mathbb{Q}})[\ell]$, where $J_1(\ell)$ is the jacobian of $X_1(\ell)$, if $X_1(\ell)(C)=\mathfrak{H}/\Gamma_1(\ell)$ together with te cusps, and $\Gamma_1(\ell)$ is the set of matrices $\begin{pmatrix}a & b c & d \end{pmatrix}$ with $a \equiv 1 \pmod{\ell}$, $c \equiv 0 \pmod{\ell}$. Still: need to compute this efficiently. This is not so easy because the genus $g$ of $X_1(\ell)$ is quadratic in $\ell$.

We have the following strategy for finding $\mathbb{Q}(x)$ (based a suggestion of Jean-Marc Couveignes). We have a surjection

$$X_1(\ell)(\mathbb{C})^g \to J_1(\ell)(\mathbb{C})=\mathbb{C}^g/\Lambda$$

where $\Lambda=H_1(X_1(\ell)(\mathbb{C}),\mathbb{Z})$. We have $\mathbb{C}^g/\Lambda \supset (1/\ell)\Lambda/\Lambda \ni x$. (For $r$ prime, $T_r \cdot x = \tau(r) \cdot x$.) This map on complex points is given by $(Q_1,\dots,Q_g) \in X_1(\ell)(\mathbb{C})$ maps to the point $[Q_1+\dots+Q_g-gP_0]=\sum_{i=1}^{g} \int_{P_0}^{Q_i} (\omega_1,\dots,\omega_g) \in \mathbb{C}^g/\Lambda$. Here, for $P_0$ one can choose a $\mathbb{Q}$-rational cusp.

Generically, there is a unique point $(Q_1,\dots,Q_g)$ up to permutation which gives the point $x$, namely, $\alpha=\sum_i j(Q_i) \in \mathbb{Q}(x)$. Now one estimates the height of $\alpha$, approximates $\alpha$ in $\mathbb{C}$ by lifting (numerically) the straight line path from 0 to $x$ (possible because the map $X_1(\ell)^g \to J_1(\ell)$ is generically unramified). It will probably be a good idea to replace the divisor $gP_0$ by a sum of $g$ distinct points $P_1,\ldots,P_g$, with small height, defined over a small and solvable extension of  $\mathbb{Q}$. As $x$ and the $P_i$ determine the $Q_i$ (up to permutation), and as $x$ is a torsion point (Néron-Tate height zero) one expects that the height of $\alpha$ is not much bigger than that of the $P_i$. So one hopes that the required number of correct digits of the approximation of $\alpha$ grows polynomially in $\ell$. The tool to be used for estimating the height of $\alpha$ 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.