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

$$W\langle t_1,\dots, t_n \rangle ^{\dagger} =\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.$$

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

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

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

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

and you `define'

$$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)

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