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:

$\displaystyle \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

$\displaystyle 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

$\displaystyle 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.