Kedlaya: Counting Points using p-adic Cohomology

We introduce a different $ p$-adic setup for counting points (or equivalently computing zeta functions). If $ X$ is a variety over $ \mathbb{F}_q$, we want to count points using `de Rham' cohomology. We will demonstrate Monsky-Washnitzer cohomology (a kind of rigid cohomology for smooth affine varieties). We restrict to the case where $ X$ is an affine curve, since in higher dimensions other methods will be faster. Then $ X={\mathrm{Spec}}\mathbb{F}_q[t_1,\dots,t_n]/(f_1,\dots,f_m)$.

Let $ W=W(\mathbb{F}_q)$ be the Witt vectors, and let $ K=W[1/p]$ be the fraction field of $ W$. Define

$\displaystyle W\langle t_1,\dots, t_n \rangle ^{\dagger}$ $\displaystyle =\left\{\textstyle{\sum}_I c_I t^I:I=(i_1,\dots,i_n) \in \mathbb{Z}_{\geq 0}^n, c_I \in W, \right.$    
  $\displaystyle \qquad \left.\text{convergent for $t_i \in \overline{K}$}, \vert t_i\vert \leq 1+\epsilon\text{ for some $\epsilon>0$}\right\}.$    

In other words, $ v_p(c_I) \geq r\epsilon_I-c$ for some $ r,c$ with $ r>0$. Modulo $ p$, $ W\langle t_1,\dots,t_n \rangle ^{\dagger}$ reduces to the polynomial ring $ \mathbb{F}_q[t_1,\dots,t_n]$, since all but finitely many coefficients are divisible by $ p$. We define $ K\langle t_1,\dots,t_n \rangle ^{\dagger}=W\langle t_1,\dots,t_n\rangle ^{\dagger}[1/p]$. Let

$\displaystyle A^{\text{int}}=W\langle \widetilde{t_1},\dots,\widetilde{t_n} \rangle ^{\dagger}/(\widetilde{f_1},\dots,\widetilde{f_n}) $

where $ \widetilde{f_i}$ is a lift of $ f_i$. Then

$\displaystyle A^{\text{int}}[1/p]=K\langle \widetilde{t_1},\dots,\widetilde{t_n}\rangle ^{\dagger}/(\widetilde{f_1},\dots,\widetilde{f_n}). $

There exists a lift so that $ A^{\text{int}}$ is flat over $ W$.

Let $ \Omega_A^1$ be the $ A$-module generated by symbols $ dt_1,\dots,dt_n$ modulo the submodule generated by $ d\widetilde{f_1},\dots,d\widetilde{f_m}$. Then there is a $ K$-linear derivation $ d:A \to \Omega_A^1$. Letting $ \Omega_A^i=\bigwedge_A^i \Omega_A^i$; you get the de Rham complex

$\displaystyle A=\Omega_A^0 \xrightarrow{d} \Omega_A^1 \xrightarrow{d} \dots $

and you `define'

$\displaystyle H_{MW}^i(X)=\frac{\ker(\Omega_A^i \to \Omega_A^{i+1})}{{\mathrm{img}}(\Omega_A^{i-1} \to \Omega_A^i)}. $

It turns out that $ H_{MW}^q(X)$ is independent of choices ($ A$ is unique up to noncanonical isomorphism, funny automorphisms are homotopic to the identity) and given $ X \to Y$, there is a map $ A_Y \to A_X$ and the induced maps $ H_{MW}^i(Y) \to H_{MW}^i(X)$ also do not depend on choices.

The spaces $ H^i(X)$ are finite-dimensional, but it is not obvious; it relies upon relating this cohomology to rigid cohomology for proper varieties, namely, crystalline cohomology which we know is finite-dimensional for other reasons. Moreover, they satisfy the Lefschetz trace formula: if $ F:X \to X$ is the $ q$-power Frobenius, then (Monsky)

$\displaystyle \char93  X(\mathbb{F}_{q^i})=\textstyle{\sum}_j (-1)^j {\mathrm{Tr}}((qF^{-1})^i\vert H^j(X)). $

The idea: try to compute $ H^i(X)$ and the map induced by $ F$ (find $ A^{\text{int}} \to A^{\text{int}}$ lifting $ q$-power Frobenius).

Example. Look at $ X={\mathrm{Spec}}\mathbb{F}_q[x,y,z]/(y^2-f(x),yz-1)$ with $ {\mathrm{char}}\mathbb{F}_q=p$ odd. Let $ \deg f=2g+1$, $ f$ monic. Lift it to $ A=K\langle x,y,z\rangle ^{\dagger}/(y^2-P(x),yz-1)$, where $ P(x)$ is monic, degree $ 2g+1$ over $ W$. It is easy to compute that $ H^0(X)$ is one-dimensional. Now $ H^1(X)$ is generated by $ x^i dx/y$ for $ i=0,\dots,2g-1$, and $ x^i dx/y^2$, $ i=0,\dots,2g$. Note $ H^1(X)$ splits under $ y \mapsto -y$ into plus and minus eigenspaces.

You need to find relations in $ H^1(X)$ that $ d(x^i/y^j)=0$. (This is a special situation: all relations are `algebraic'.) Lift the $ p$-power Frobenius by $ W \to W$ by the Witt vector Frobenius, $ x \mapsto x^p$, and $ y \mapsto y^p\sqrt{F(P(x))/P(X)^p}$. Compose this map with itself $ n$ times to get a $ q$-power Frobenius lift, and this allows us to compute the zeta function of a genus $ g$ hyperelliptic curve over $ \mathbb{F}_{p^n}$ in time $ \widetilde{O}(g^4 n^3 p)$.




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