\documentclass[11pt]{article}1\hoffset=-0.06\textwidth2\textwidth=1.12\textwidth3\voffset=-0.06\textheight4\textheight=1.12\textheight5\bibliographystyle{amsalpha}6\include{macros}7\renewcommand{\set}{\leftarrow}8\title{An Algorithm for Computing $p$-Adic Heights Using Monsky-Washnitzer Cohomology}9\date{Notes for a Talk at MIT on 2004-10-15}10\author{William Stein}11\renewcommand{\E}{\mathbb{E}}12\begin{document}13\maketitle14%\tableofcontents1516Let $E$ be an elliptic curve over~$\Q$ and suppose17$$P=(x,y)=\left(\frac{a}{d^2},\frac{b}{d^3}\right)\in E(\Q),$$ with $a,b,d\in\Z$ and18$\gcd(a,d)=\gcd(b,d)=1$. The19\defn{naive height} of $P$ is20$$\tilde{h}(P) = \log\max\{|a|,d^2\},$$21and the \defn{canonical height} of $P$ is22$$23h(P) = \lim_{n\to\infty} \frac{h(2^n P)}{4^n}.24$$25This definition is not good for computation, because26$2^n P$ gets huge very quickly, and computing27$2^n P$ exactly, for~$n$ large, is not reasonable.28%The canonical height is quadratic, in the sense that29%$h(mP) = m^2 h(P)$ for all integer $m$.3031In \cite[\S3.4]{cremona:algs}, Cremona describes an efficient method32(due mostly to Silverman) for computing $h(P)$. One defines33\defn{local heights} $\hat{h}_p:E(\Q)\to\R$, for all primes $p$, and34$\hat{h}_\infty:E(\Q)\to\R$ such that $$h(P) = \hat{h}_\infty(P) +35\sum \hat{h}_p(P).$$36The local heights $\hat{h}_p(P)$ are easy to37compute explicitly. For example, when $p$ is a prime of good38reduction, $\hat{h}_p(P) = \max\{0,-\ord_p(x)\}\cdot \log(p)$.3940{\em This paper is {\bf NOT} about local heights $\hat{h}_p$, and we will41not mention them any further.} Instead, this paper is about a canonical global42$p$-adic height function43$$h_p : E(\Q)\to\Q_p.$$44These height functions are genuine height functions; e.g., $h_p$45is a quadratic function, i.e, $h_p(mP) = m^2 h(P)$ for all~$m$.46They appear when defining the $p$-adic regulators that appear in the47Mazur-Tate $p$-adic analogues of the Birch and Swinnerton-Dyer48conjecture.4950\vspace{3ex}51\noindent{\bf Acknowledgement:} Barry Mazur, John Tate, Mike Harrison,52Christian Wuthrich, Nick Katz.5354\section{The $p$-Adic Height Pairing}55Let $E$ be an elliptic curve over~$\Q$ and suppose $p\geq 5$ is a prime56such that $E$ has good ordinary reduction at $p$. Suppose $P\in E(\Q)$57is a point that reduces to $0\in E(\F_p)$ and to the connected58component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.59We will define functions $\log_p$, $\sigma$, and $d$ below.60In terms of these functions, the $p$-adic height of $P$ is61\begin{equation}\label{eqn:heightdef}62h_p(P) = \frac{1}{p}\cdot \log_p\left(\frac{\sigma(P)}{d(P)}\right) \in \Q_p.63\end{equation}64The function $h_p$ satisfies $h_p(nP) = n^2 h_p(P)$ for all integers~$n$,65so it naturally extends to a function on the full Mordell-Weil group $E(\Q)$.66Setting $$\langle P, Q\rangle = \frac{1}{2}\cdot (h_p(P+Q)-h_p(P)-h_p(Q)),$$67we obtain a {\em nondegenerate} pairing on68$E(\Q)_{/\tor}$, and the $p$-adic regulator is the discriminant69of this pairing (which is well defined up to sign).7071Investigations into $p$-adic Birch and Swinnerton-Dyer conjectures for72curves of positive rank inevitably lead to questions about such height73pairings, which motivate our interest in computing it to74high precision.7576We now define each of the undefined quantities in77(\ref{eqn:heightdef}). The function $\log_p:\Q_p^* \to \Q_p$ is the78unique homomorphism with $\log_p(p)=1$ that extends the homomorphism79$\log_p:1+p\Z_p \to \Q_p$ defined by the usual power series of $\log(x)$ about $1$. Thus80if $x\in\Q_p^*$, we can compute $\log_p(x)$ using the formula81$$\log_p(x) = \frac{1}{p-1}\cdot \log_p(u^{p-1}),$$82where $u =83p^{-\ord_p(x)} \cdot x$.8485The denominator $d(P)$ is the square root of the denominator of the86$x$-coordinate of $P$.8788The $\sigma$ function is the most mysterious quantity in89(\ref{eqn:heightdef}), and it turns out the mystery is closely related90to the difficulty of computing the $p$-adic number $\E_2(E,\omega)$,91where $\E_2$ is the $p$-adic weight $2$ Eisenstein series. There are92{\em many} ways to define or characterize $\sigma$, e.g.,93\cite{mazur-tate:sigma} contains $11$ different characterizations!94Let $$x(t) = \frac{1}{t^2} + \cdots \in \Z((t))$$95be the formal power96series that expresses $x$ in terms of $t=-x/y$ locally near $0\in E$.97Then Mazur and Tate prove there is exactly one function $\sigma(t)\in98t\Z_p[[t]]$ and constant $c\in \Q_p$ that satisfy the equation99\begin{equation}\label{eqn:sigmadef}100x(t)101+ c = -\frac{d}{\omega}\left( \frac{1}{\sigma}102\frac{d\sigma}{\omega}\right).103\end{equation}104This defines $\sigma$, and,105unwinding the meaning of the expression on the right, it leads to an106algorithm to compute $\sigma(t)$ to any desired precision,107which we now sketch.108109If we expand (\ref{eqn:sigmadef}), we can view $c$ as a formal110variable and solve for $\sigma(t)$ as a power series with coefficients111that are polynomials in $c$. Each coefficient of $\sigma(t)$ must be112in $\Z_p$, so when there are denominators in the polynomials in $c$,113we obtain conditions on $c$ modulo powers of $p$. Taking these114together for many coefficients yields enough scraps of information to115get $c\pmod{p^n}$, for some small $n$, hence $\sigma(t) \pmod{p^n}$.116However, this algorithm is {\em extremely inefficient} and its117complexity is unclear (how many coefficients are needed to compute $c$118to precision $p^n$?).119120For the last 15 or 20 years, the above unsatisifactory algorithm has121been the standard one for computing $p$-adic heights, e.g., when122investigating $p$-adic analogues of the BSD conjecture.123\begin{center}124{\em The situation125changed a few weeks ago...}126\end{center}127\section{Using Cohomology to Compute $\sigma$}128Suppose that $E$ is an elliptic curve over $\Q$ given by a Weierstrass equation129$$130y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6.131$$132Let $x(t)$ be the formal series as before, and set133$$\wp(t) = x(t) + (a_1^2 + 4a_2)/12\in\Q((t)).$$134(The function $\wp$ satisfies $(\wp')^2 = 4\wp^3 - g_2 \wp - g_3$, etc.; it's135the formal analogue of the usual complex $\wp$-function.)136In \cite{mazur-tate:sigma}, Mazur and Tate prove that137$$138x(t) + c = \wp(t) + \frac{1}{12}\cdot \E_2(E,\omega),139$$140where $\E_2(E,\omega)$ is the value of the Katz $p$-adic141weight~$2$ Eisenstein series at $(E,\omega)$, and the equality is of142elements of $\Q_p((t))$. Thus computing $c$ is equivalent143to computing $\E_2(E,\omega)$.144145This summer, Mazur, Tate, and I explored many ideas for computing146$\E_2(E,\omega)$. Though each was interesting and promising, nothing147led to a better algorithm that just computing $c$ as sketched above.148Perhaps the difficult of computing $\E_2(E,\omega)$ is somehow at the149heart of the theory?150151Barry wrote to Nick Katz, who fired off the following email:152153\subsection{Katz's Email}154\begin{verbatim}155Date: Thu, 8 Jul 2004 13:53:13 -0400156From: Nick Katz <nmk@Math.Princeton.EDU>157Subject: Re: convergence of the Eisenstein series of weight two158To: mazur@math.harvard.edu, nmkatz@Math.Princeton.EDU159Cc: tate@math.utexas.edu, was@math.harvard.edu160161It seems to me you want to use the interpretation of P as the162"direction of the unit root subspace", that should make it fast to163compute. Concretely, suppose we have a pair (E, \omega) over Z_p, and164to fix ideas p is not 2 or 3. Then we write a Weierstrass eqn for E,165y^2 = 4x^3 - g_2x - g_3, so that \omega is dx/y, and we denote by \eta166the differential xdx/y. Then \omega and \eta form a Z_p basis of167H^1_DR = H^1_cris, and the key step is to compute the matrix of168absolute Frobenius (here Z_p linear, the advantage of working over169Z_p: otherwise if over Witt vectors of an F_q, only \sigma-linear).170[This calculation goes fast, because the matrix of Frobenius lives171over the entire p-adic moduli space, and we are back in the glory days172of Washnitzer-Monsky cohomology (of the open curve E - {origin}).]173174Okay, now suppose we have computed the matrix of Frob in the175basis \omega, \eta. The unit root subspace is a direct factor, call176it U, of the H^1, and we know that a complimentary direct factor is177Fil^1 := the Z_p span of \omega. We also know that Frob(\omega) lies178in pH^1, and this tells us that, mod p^n, U is the span of179Frob^n(\eta). What this means concretely is that if we write,180for each n,181182Frob^n(\eta) = a_n\omega + b_n\eta,183184then b_n is a unit (cong mod p to the n'th power of the Hasse185invariant) and that P is something like the ratio a_n/b_n (up to a186sign and a factor 12 which i don't recall offhand but which is in my187Antwerp appendix and also in my "p-adic interp. of real188anal. Eis. series" paper).189190So in terms of speed of convergence, ONCE you have Frob, you191have to iterate it n times to calculate P mod p^n. Best, Nick192\end{verbatim}193194\subsection{The Algorithms}195The following algorithms culminate in an algorithm for computing196$h_p(P)$ that incorporates Katz's ideas with the discussion elsewhere197in this paper. I have computed $\sigma$ and $h_p$ in numerous198cases using the algorithm described below, and using my199implementations of the ``integrality'' algorithm described above200and also Wuthrich's algorithm, and the results match. The analysis201of some of the necessary precision is not complete. I also have202not analyzed the complexity.203204The first algorithm computes $\E_2(E,\omega)$.205\begin{algorithm}{Evaluation of $\E_2(E,\omega)$}\label{alg:e2}206Given an elliptic curve over~$\Q$ and prime~$p$, this algorithm207computes $\E_2(E,\omega)\in \Q_p$ (to precision $O(p^n)$ say) . We208assume that Kedlaya's algorithm is available for computing a209presentation of the $p$-adic Monsky-Washnitzer cohomology of210$E-\{(0,0)\}$ with Frobenius action.211\begin{steps}212\item Let $c_4$ and $c_6$ be the $c$-invariants of a minimal model213of~$E$. Set214$$a_4\set -\frac{c_4}{2^4\cdot 3}\qquad\text{and}\qquad215a_6 \set -\frac{c_6}{2^5\cdot 3^3}.$$216\item Apply Kedlaya's algorithm to the hyperelliptic curve217$y^2=x^3 + a_4x + a_6$ (which is isomorphic to $E$) to obtain the matrix218$M$ of the action of absolute Frobenius219on the basis220$$\omega=\frac{dx}{y}, \qquad \eta=\frac{xdx}{y}$$221to precision $O(p^n)$. (We view $M$ as acting222from the left.)223\item224We know $M$ to precision $O(p^n)$.225Compute the $n$th power of $M$ and let226$\vtwo{a}{b}$ be the second column of $M^n$.227Then $\Frob^n(\eta) = a\omega + b\eta$228229\item Output $M$ and $-12a/b$ (which is $\E_2(E,\omega)$), then terminate.230\end{steps}231\end{algorithm}232233The next algorithm uses the above algorithm to compute $\sigma(t)$.234\begin{algorithm}{The Canonical $p$-adic Sigma Function}\label{alg:sigma}235Given an elliptic curve~$E$ and a good ordinary prime~$p$, this236algorithm computes $\sigma(t)\in\Z_p[[t]]$ modulo $(p^n, t^m)$ for237any given positive integers $n,m$. (I have {\em not} figured out238exactly what precision each object below must be computed to.)239\begin{steps}240\item Using Algorithm~\ref{alg:e2}, compute $e_2 = \E_2(E,\omega)\in241\Z_p$ to precision $O(p^n)$.242\item Compute the formal power series $x = x(t) \in \Q[[t]]$243associated to the formal group of $E$ to precision $O(t^m)$.244\item Compute the formal logarithm $z(t) \in \Q((t))$ to precision245$O(t^m)$ using that $\ds z(t) = \int \frac{dx/dt}{(2y(t)+a_1x(t) + a_3)},$246where $x(t)=t/w(t)$ and $y(t)=-1/w(t)$ are the formal $x$247and $y$ functions, and $w(t)$ is given by the explicit inductive248formula in \cite[Ch.~7]{silverman:aec}. (Here $t=-x/y$ and $w=-1/y$ and249we can write $w$ as a series in $t$.)250\item Using a power series ``reversion'' (functional inverse)251algorithm (see e.g., Mathworld), find the power series $F(z)\in\Q[[z]]$ such that252$t=F(z)$. Here $F$ is the reversion of $z$, which exists because253$z(t) = t + \cdots$.254\item Set $\wp(t) \set x(t) + (a_1^2 + 4a_2)/12 \in \Q[[t]]$ (to precision255$O(t^m)$), where the256$a_i$ are the coefficients of the Weierstrass equation of $E$.257Then compute the series $\wp(z) = \wp(F(z))\in \Q((z))$.258\item Set $\ds g(z)\set \frac{1}{z^2} - \wp(z) + \frac{e_2}{12}\in\Q_p((z))$.259(Note:260The theory suggests the last term should be $-e_2/12$ but the calculations do not261work unless I use the above formula. Maybe there are two262normalizations of $E_2$ in the literature?)263\item Set264$\ds \sigma(z) \set z\cdot \exp\left(\int \int g(z) \dz \dz\right)265\in \Q_p[[z]]$.266\item Set $\sigma(t) \set \sigma(z(t))\in t\cdot \Z_p[[t]]$, where $z(t)$267is the formal logarithm computed above. Output $\sigma(t)$268and terminate.269\end{steps}270\end{algorithm}271272\begin{remark}273The trick of changing from $\wp(t)$ to $\wp(z)$ is essential so that274we can solve a certain differential equation using just operations275with power series.276\end{remark}277278The final algorithm uses $\sigma(t)$ to compute the $p$-adic height.279\begin{algorithm}{$p$-adic Height}280Given an elliptic curve~$E$ over $\Q$, a good ordinary prime~$p$,281and an element $P\in E(\Q)$, this algorithm computes the282$p$-adic height $h_p(P) \in \Q_p$ to precision $O(p^n)$.283(I will ignore the precision below, though this must be not284be ignored for the final version of this paper.)285\begin{steps}286\item{}[Prepare Point] Compute an integer $m$ such that287$mP$ reduces to $0\in E(\F_p)$ and to the connected288component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.289For example,~$m$ could be the least common multiple of the Tamagawa numbers290of $E$ and $\#E(\F_p)$. Set $Q\set mP$ and write $Q=(x,y)$.291\item{}[Denominator] Let $d$ be the positive integer square root of the292denominator of $x$.293\item{}[Compute $\sigma$] Compute $\sigma(t)$ using294Algorithm~\ref{alg:sigma}, and set $s \set \sigma(-x/y) \in \Q_p$.295\item{}[Logs] Compute296$\ds h_p(Q) \set \frac{1}{p}\log_p\left(\frac{s}{d}\right)$, and297$\ds h_p(P) \set \frac{1}{m^2} \cdot h_p(Q)$. Output $h_p(P)$ and terminate.298\end{steps}299\end{algorithm}300301\section{Future Directions}302303Suppose $E_t$ is an elliptic curves over $\Q(t)$. It might be304extremely interesting to obtain formula for $\E_2(E_t)$ as something305like (?) a power series in $\Q_p[[t]]$. This might shed light on the306analytic behavior of the $p$-adic modular form $\E_2$, and on Tate's307recent surprising experimental observations about the behavior of the308$(1/j)$-expansion of~$\E_2 E_4/E_6$.309310It would also be interesting to do yet more computations in support of311$p$-adic analogues of the BSD conjectures of \cite{mtt}, especially312when $E/\Q$ has large rank. Substantial theoretical work has been313done toward these $p$-adic conjectures, and this work may be useful to314algorithms for computing information about Shafarevich-Tate and Selmer315groups of elliptic curves. For example, in \cite{pr:exp}, Perrin-Riou316uses her results about the $p$-adic BSD conjecture in the317supersingular case to prove that $\Sha(E/\Q)[p]=0$ for certain~$p$ and318elliptic curves~$E$ of rank $>1$, for which the work of Kolyvagin and319Kato does not apply. Mazur and Rubin (with my computational input)320are also obtaining results that could be viewed as fitting into this321program.322323I would like to optimize the implementation of the algorithm.324Probably the most time-consuming step is computation of325$\E_2(E,\omega)$ using Kedlaya's algorithm. My current implementation326uses Michael Harrison's implementation of Kedlaya's algorithm for327$y^2=f(x)$, with $f(x)$ of arbitrary degree. Perhaps implementing328just what is needed for $y^2=x^3+ax+b$ might be more efficient. Also,329Harrison tells me his implementation isn't nearly as optimized as it330might be.331332It might be possible to compute $p$-adic heights on Jacobians of333hyperelliptic curves.334335Formulate everything above over number fields, and extend to the case336of additive reduction.337338Supersingular reduction?339340\section{Examples}341The purpose of this section is to show you how to use the MAGMA package342I wrote for computing with $p$-adic heights, and give you a sense343for how fast it is.344345\begin{verbatim}346> function EC(s) return EllipticCurve(CremonaDatabase(),s); end function;347> E := EC("37A");348> Attach("padic_height.m");349> P := good_ordinary_primes(E,100); P;350[ 5, 7, 11, 13, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73,35179, 83, 89, 97 ]352> for p in P do time print p, regulator(E,p,10); end for;3535 22229672 + O(5^11)354Time: 0.0403557 317628041 + O(7^11)356...35789 15480467821870438719 + O(89^10)358Time: 1.19035997 -11195795337175141289 + O(97^10)360Time: 1.490361362> E := EC("389A");363> P := good_ordinary_primes(E,100); P;364[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,36567, 71, 73, 79, 83, 89, 97 ]366> for p in P do time print p, regulator(E,p,10); end for;3675 -3871266 + O(5^11)368Time: 0.2603697 483898350 + O(7^11)370...37189 9775723521676164462 + O(89^10)372Time: 1.33037397 -13688331881071698338 + O(97^10)374Time: 1.820375376> E := EC("5077A");377> P := good_ordinary_primes(E,100); P;378[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 43, 47, 53, 59, 61, 67, 71,37973, 79, 83, 89, 97 ]380> for p in P do time print p, regulator(E,p,10); end for;3815 655268*5^-2 + O(5^7)382Time: 0.8003837 -933185758 + O(7^11)384...38589 -3325438607428779200 + O(89^10)386Time: 1.91038797 -5353586908063282167 + O(97^10)388Time: 2.010389390--------391392> E := EC("37A");393> time regulator(E,5,50);394115299522541340178416234094637464047 + O(5^51)395Time: 1.860396> Valuation(115299522541340178416234094637464047 - 22229672,5);3979398399> time regulator(E,97,50);400-5019271523950156862996295340254565181870308222348277984940964806\40197957622583267105973403430183075091 + O(97^50)402Time: 31.7403\end{verbatim}404405406\bibliography{biblio}407\end{document}408409410411412413414