CoCalc Public Fileswww / talks / padic_heights / pheight.tex
Author: William A. Stein
1\documentclass[11pt]{article}
2\hoffset=-0.06\textwidth
3\textwidth=1.12\textwidth
4\voffset=-0.06\textheight
5\textheight=1.12\textheight
6\bibliographystyle{amsalpha}
7\include{macros}
8\renewcommand{\set}{\leftarrow}
9\title{An Algorithm for Computing $p$-Adic Heights Using Monsky-Washnitzer Cohomology}
10\date{Notes for a Talk at MIT on 2004-10-15}
11\author{William Stein}
12\renewcommand{\E}{\mathbb{E}}
13\begin{document}
14\maketitle
15%\tableofcontents
16
17Let $E$ be an elliptic curve over~$\Q$ and suppose
18$$P=(x,y)=\left(\frac{a}{d^2},\frac{b}{d^3}\right)\in E(\Q),$$ with $a,b,d\in\Z$ and
19$\gcd(a,d)=\gcd(b,d)=1$.  The
20\defn{naive height} of $P$ is
21$$\tilde{h}(P) = \log\max\{|a|,d^2\},$$
22and the \defn{canonical height} of $P$ is
23$$24 h(P) = \lim_{n\to\infty} \frac{h(2^n P)}{4^n}. 25$$
26This definition is not good for computation, because
27$2^n P$ gets huge very quickly, and computing
28$2^n P$ exactly, for~$n$ large, is not reasonable.
29%The canonical height is quadratic, in the sense that
30%$h(mP) = m^2 h(P)$ for all integer $m$.
31
32In \cite[\S3.4]{cremona:algs}, Cremona describes an efficient method
33(due mostly to Silverman) for computing $h(P)$.  One defines
34\defn{local heights} $\hat{h}_p:E(\Q)\to\R$, for all primes $p$, and
35$\hat{h}_\infty:E(\Q)\to\R$ such that $$h(P) = \hat{h}_\infty(P) + 36\sum \hat{h}_p(P).$$
37The local heights $\hat{h}_p(P)$ are easy to
38compute explicitly.  For example, when $p$ is a prime of good
39reduction, $\hat{h}_p(P) = \max\{0,-\ord_p(x)\}\cdot \log(p)$.
40
41{\em This paper is {\bf NOT} about local heights $\hat{h}_p$, and we will
42not mention them any further.}  Instead, this paper is about a canonical global
43$p$-adic height function
44$$h_p : E(\Q)\to\Q_p.$$
45These height functions are genuine height functions; e.g., $h_p$
46is a quadratic function, i.e, $h_p(mP) = m^2 h(P)$ for all~$m$.
47They appear when defining the $p$-adic regulators that appear in the
48Mazur-Tate $p$-adic analogues of the Birch and Swinnerton-Dyer
49conjecture.
50
51\vspace{3ex}
52\noindent{\bf Acknowledgement:} Barry Mazur, John Tate, Mike Harrison,
53Christian Wuthrich, Nick Katz.
54
55\section{The $p$-Adic Height Pairing}
56Let $E$ be an elliptic curve over~$\Q$ and suppose $p\geq 5$ is a prime
57such that $E$ has good ordinary reduction at $p$.  Suppose $P\in E(\Q)$
58is a point that reduces to $0\in E(\F_p)$ and to the connected
59component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.
60We will define functions $\log_p$, $\sigma$, and $d$ below.
61In terms of these functions, the $p$-adic height of $P$ is
62\begin{equation}\label{eqn:heightdef}
63  h_p(P) = \frac{1}{p}\cdot \log_p\left(\frac{\sigma(P)}{d(P)}\right) \in \Q_p.
64\end{equation}
65The function $h_p$ satisfies $h_p(nP) = n^2 h_p(P)$ for all integers~$n$,
66so it naturally extends to a function on the full Mordell-Weil group $E(\Q)$.
67Setting $$\langle P, Q\rangle = \frac{1}{2}\cdot (h_p(P+Q)-h_p(P)-h_p(Q)),$$
68we obtain a {\em nondegenerate} pairing on
69$E(\Q)_{/\tor}$, and the $p$-adic regulator is the discriminant
70of this pairing (which is well defined up to sign).
71
72Investigations into $p$-adic Birch and Swinnerton-Dyer conjectures for
74pairings, which motivate our interest in computing it to
75high precision.
76
77We now define each of the undefined quantities in
78(\ref{eqn:heightdef}).  The function $\log_p:\Q_p^* \to \Q_p$ is the
79unique homomorphism with $\log_p(p)=1$ that extends the homomorphism
80$\log_p:1+p\Z_p \to \Q_p$ defined by the usual power series of $\log(x)$ about $1$.  Thus
81if $x\in\Q_p^*$, we can compute $\log_p(x)$ using the formula
82$$\log_p(x) = \frac{1}{p-1}\cdot \log_p(u^{p-1}),$$
83where $u = 84p^{-\ord_p(x)} \cdot x$.
85
86The denominator $d(P)$ is the square root of the denominator of the
87$x$-coordinate of $P$.
88
89The $\sigma$ function is the most mysterious quantity in
90(\ref{eqn:heightdef}), and it turns out the mystery is closely related
91to the difficulty of computing the $p$-adic number $\E_2(E,\omega)$,
92where $\E_2$ is the $p$-adic weight $2$ Eisenstein series.  There are
93{\em many} ways to define or characterize $\sigma$, e.g.,
94\cite{mazur-tate:sigma} contains $11$ different characterizations!
95Let $$x(t) = \frac{1}{t^2} + \cdots \in \Z((t))$$
96be the formal power
97series that expresses $x$ in terms of $t=-x/y$ locally near $0\in E$.
98Then Mazur and Tate prove there is exactly one function $\sigma(t)\in 99t\Z_p[[t]]$ and constant $c\in \Q_p$ that satisfy the equation
101x(t)
102+ c = -\frac{d}{\omega}\left( \frac{1}{\sigma}
103  \frac{d\sigma}{\omega}\right).
104\end{equation}
105This defines $\sigma$, and,
106unwinding the meaning of the expression on the right, it leads to an
107algorithm to compute $\sigma(t)$ to any desired precision,
108which we now sketch.
109
110If we expand (\ref{eqn:sigmadef}), we can view $c$ as a formal
111variable and solve for $\sigma(t)$ as a power series with coefficients
112that are polynomials in $c$.  Each coefficient of $\sigma(t)$ must be
113in $\Z_p$, so when there are denominators in the polynomials in $c$,
114we obtain conditions on $c$ modulo powers of $p$.  Taking these
115together for many coefficients yields enough scraps of information to
116get $c\pmod{p^n}$, for some small $n$, hence $\sigma(t) \pmod{p^n}$.
117However, this algorithm is {\em extremely inefficient} and its
118complexity is unclear (how many coefficients are needed to compute $c$
119to precision $p^n$?).
120
121For the last 15 or 20 years, the above unsatisifactory algorithm has
122been the standard one for computing $p$-adic heights, e.g., when
123investigating $p$-adic analogues of the BSD conjecture.
124\begin{center}
125{\em The situation
126  changed  a few weeks ago...}
127\end{center}
128\section{Using Cohomology to Compute $\sigma$}
129Suppose that $E$ is an elliptic curve over $\Q$ given by a Weierstrass equation
130$$131y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6. 132$$
133Let $x(t)$ be the formal series as before, and set
134$$\wp(t) = x(t) + (a_1^2 + 4a_2)/12\in\Q((t)).$$
135(The function $\wp$ satisfies $(\wp')^2 = 4\wp^3 - g_2 \wp - g_3$, etc.; it's
136the formal analogue of the usual complex $\wp$-function.)
137In \cite{mazur-tate:sigma}, Mazur and Tate prove that
138$$139 x(t) + c = \wp(t) + \frac{1}{12}\cdot \E_2(E,\omega), 140$$
141where $\E_2(E,\omega)$ is the value of the Katz $p$-adic
142weight~$2$ Eisenstein series at $(E,\omega)$, and the equality is of
143elements of $\Q_p((t))$.  Thus computing $c$ is equivalent
144to computing $\E_2(E,\omega)$.
145
146This summer, Mazur, Tate, and I explored many ideas for computing
147$\E_2(E,\omega)$.  Though each was interesting and promising, nothing
148led to a better algorithm that just computing $c$ as sketched above.
149Perhaps the difficult of computing $\E_2(E,\omega)$ is somehow at the
150heart of the theory?
151
152Barry wrote to Nick Katz, who fired off the following email:
153
154\subsection{Katz's Email}
155\begin{verbatim}
156Date: Thu, 8 Jul 2004 13:53:13 -0400
157From: Nick Katz <nmk@Math.Princeton.EDU>
158Subject: Re: convergence of the Eisenstein series of weight two
159To: mazur@math.harvard.edu, nmkatz@Math.Princeton.EDU
160Cc: tate@math.utexas.edu, was@math.harvard.edu
161
162It seems to me you want to use the interpretation of P as the
163"direction of the unit root subspace", that should make it fast to
164compute. Concretely, suppose we have a pair (E, \omega) over Z_p, and
165to fix ideas p is not 2 or 3.  Then we write a Weierstrass eqn for E,
166y^2 = 4x^3 - g_2x - g_3, so that \omega is dx/y, and we denote by \eta
167the differential xdx/y. Then \omega and \eta form a Z_p basis of
168H^1_DR = H^1_cris, and the key step is to compute the matrix of
169absolute Frobenius (here Z_p linear, the advantage of working over
170Z_p: otherwise if over Witt vectors of an F_q, only \sigma-linear).
171[This calculation goes fast, because the matrix of Frobenius lives
172over the entire p-adic moduli space, and we are back in the glory days
173of Washnitzer-Monsky cohomology (of the open curve E - {origin}).]
174
175        Okay, now suppose we have computed the matrix of Frob in the
176basis \omega, \eta. The unit root subspace is a direct factor, call
177it U, of the H^1, and we know that a complimentary direct factor is
178Fil^1 := the Z_p span of \omega. We also know that Frob(\omega) lies
179in pH^1, and this tells us that, mod p^n, U is the span of
180Frob^n(\eta). What this means concretely is that if we write,
181for each n,
182
183   Frob^n(\eta) = a_n\omega + b_n\eta,
184
185then b_n is a unit (cong mod p to the n'th power of the Hasse
186invariant) and that P is something like the ratio a_n/b_n (up to a
187sign and a factor 12 which i don't recall offhand but which is in my
188Antwerp appendix and also in my "p-adic interp. of real
189anal. Eis. series" paper).
190
191        So in terms of speed of convergence, ONCE you have Frob, you
192have to iterate it n times to calculate P mod p^n. Best, Nick
193\end{verbatim}
194
195\subsection{The Algorithms}
196The following algorithms culminate in an algorithm for computing
197$h_p(P)$ that incorporates Katz's ideas with the discussion elsewhere
198in this paper.  I have computed $\sigma$ and $h_p$ in numerous
199cases using the algorithm described below, and using my
200implementations of the integrality'' algorithm described above
201and also Wuthrich's algorithm, and the results match.  The analysis
202of some of the necessary precision is not complete.  I also have
203not analyzed the complexity.
204
205The first algorithm computes $\E_2(E,\omega)$.
206\begin{algorithm}{Evaluation of $\E_2(E,\omega)$}\label{alg:e2}
207  Given an elliptic curve over~$\Q$ and prime~$p$, this algorithm
208  computes $\E_2(E,\omega)\in \Q_p$ (to precision $O(p^n)$ say) .  We
209  assume that Kedlaya's algorithm is available for computing a
210  presentation of the $p$-adic Monsky-Washnitzer cohomology of
211  $E-\{(0,0)\}$ with Frobenius action.
212\begin{steps}
213\item  Let $c_4$ and $c_6$ be the $c$-invariants of a minimal model
214of~$E$.  Set
215$$a_4\set -\frac{c_4}{2^4\cdot 3}\qquad\text{and}\qquad 216a_6 \set -\frac{c_6}{2^5\cdot 3^3}.$$
217\item Apply Kedlaya's algorithm to the hyperelliptic curve
218$y^2=x^3 + a_4x + a_6$ (which is isomorphic to $E$) to obtain the matrix
219$M$ of the action of absolute Frobenius
220on the basis
221$$\omega=\frac{dx}{y}, \qquad \eta=\frac{xdx}{y}$$
222to precision $O(p^n)$.   (We view $M$ as acting
223from the left.)
224\item
225We know $M$ to precision $O(p^n)$.
226Compute the $n$th power of $M$ and let
227$\vtwo{a}{b}$ be the second column of $M^n$.
228Then $\Frob^n(\eta) = a\omega + b\eta$
229
230\item Output $M$ and $-12a/b$ (which is $\E_2(E,\omega)$), then terminate.
231\end{steps}
232\end{algorithm}
233
234The next algorithm uses the above algorithm to compute $\sigma(t)$.
235\begin{algorithm}{The Canonical $p$-adic Sigma Function}\label{alg:sigma}
236  Given an elliptic curve~$E$ and a good ordinary prime~$p$, this
237  algorithm computes $\sigma(t)\in\Z_p[[t]]$ modulo $(p^n, t^m)$ for
238  any given positive integers $n,m$. (I have {\em not} figured out
239  exactly what precision each object below must be computed to.)
240\begin{steps}
241\item Using Algorithm~\ref{alg:e2}, compute $e_2 = \E_2(E,\omega)\in 242 \Z_p$ to precision $O(p^n)$.
243\item Compute the formal power series $x = x(t) \in \Q[[t]]$
244  associated to the formal group of $E$ to precision $O(t^m)$.
245\item Compute the formal logarithm $z(t) \in \Q((t))$ to precision
246$O(t^m)$ using that $\ds z(t) = \int \frac{dx/dt}{(2y(t)+a_1x(t) + a_3)},$
247where $x(t)=t/w(t)$ and $y(t)=-1/w(t)$ are the formal $x$
248and $y$ functions, and $w(t)$ is given by the explicit inductive
249formula in \cite[Ch.~7]{silverman:aec}. (Here $t=-x/y$ and $w=-1/y$ and
250we can write $w$ as a series in $t$.)
251\item Using a power series reversion'' (functional inverse)
252  algorithm (see e.g., Mathworld), find the power series $F(z)\in\Q[[z]]$ such that
253  $t=F(z)$.  Here $F$ is the reversion of $z$, which exists because
254  $z(t) = t + \cdots$.
255\item Set $\wp(t) \set x(t) + (a_1^2 + 4a_2)/12 \in \Q[[t]]$ (to precision
256$O(t^m)$), where the
257  $a_i$ are the coefficients of the Weierstrass equation of $E$.
258Then compute the series $\wp(z) = \wp(F(z))\in \Q((z))$.
259\item Set $\ds g(z)\set \frac{1}{z^2} - \wp(z) + \frac{e_2}{12}\in\Q_p((z))$.
260(Note:
261  The theory suggests the last term should be $-e_2/12$ but the calculations do not
262  work unless I use the above formula.  Maybe there are two
263  normalizations of $E_2$ in the literature?)
264\item Set
265$\ds \sigma(z) \set z\cdot \exp\left(\int \int g(z) \dz \dz\right) 266\in \Q_p[[z]]$.
267\item Set $\sigma(t) \set \sigma(z(t))\in t\cdot \Z_p[[t]]$, where $z(t)$
268is the formal logarithm computed above.  Output $\sigma(t)$
269and terminate.
270\end{steps}
271\end{algorithm}
272
273\begin{remark}
274  The trick of changing from $\wp(t)$ to $\wp(z)$ is essential so that
275  we can solve a certain differential equation using just operations
276  with power series.
277\end{remark}
278
279The final algorithm uses $\sigma(t)$ to compute the $p$-adic height.
280\begin{algorithm}{$p$-adic Height}
281Given an elliptic curve~$E$ over $\Q$, a good ordinary prime~$p$,
282and an element $P\in E(\Q)$, this algorithm computes the
283$p$-adic height $h_p(P) \in \Q_p$ to precision $O(p^n)$.
284(I will ignore the precision below, though this must be not
285be ignored for the final version of this paper.)
286\begin{steps}
287\item{}[Prepare Point] Compute an integer $m$ such that
288$mP$ reduces to $0\in E(\F_p)$ and to the connected
289component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.
290For example,~$m$ could be the least common multiple of the Tamagawa numbers
291of $E$ and $\#E(\F_p)$.  Set $Q\set mP$ and write $Q=(x,y)$.
292\item{}[Denominator] Let $d$ be the positive integer square root of the
293denominator of $x$.
294\item{}[Compute $\sigma$] Compute $\sigma(t)$ using
295  Algorithm~\ref{alg:sigma}, and set $s \set \sigma(-x/y) \in \Q_p$.
296\item{}[Logs] Compute
297$\ds h_p(Q) \set \frac{1}{p}\log_p\left(\frac{s}{d}\right)$, and
298$\ds h_p(P) \set \frac{1}{m^2} \cdot h_p(Q)$.  Output $h_p(P)$ and terminate.
299\end{steps}
300\end{algorithm}
301
302\section{Future Directions}
303
304Suppose $E_t$ is an elliptic curves over $\Q(t)$.  It might be
305extremely interesting to obtain formula for $\E_2(E_t)$ as something
306like (?) a power series in $\Q_p[[t]]$.  This might shed light on the
307analytic behavior of the $p$-adic modular form $\E_2$, and on Tate's
308recent surprising experimental observations about the behavior of the
309$(1/j)$-expansion of~$\E_2 E_4/E_6$.
310
311It would also be interesting to do yet more computations in support of
312$p$-adic analogues of the BSD conjectures of \cite{mtt}, especially
313when $E/\Q$ has large rank.  Substantial theoretical work has been
314done toward these $p$-adic conjectures, and this work may be useful to
315algorithms for computing information about Shafarevich-Tate and Selmer
316groups of elliptic curves.  For example, in \cite{pr:exp}, Perrin-Riou
317uses her results about the $p$-adic BSD conjecture in the
318supersingular case to prove that $\Sha(E/\Q)[p]=0$ for certain~$p$ and
319elliptic curves~$E$ of rank $>1$, for which the work of Kolyvagin and
320Kato does not apply.  Mazur and Rubin (with my computational input)
321are also obtaining results that could be viewed as fitting into this
322program.
323
324I would like to optimize the implementation of the algorithm.
325Probably the most time-consuming step is computation of
326$\E_2(E,\omega)$ using Kedlaya's algorithm.  My current implementation
327uses Michael Harrison's implementation of Kedlaya's algorithm for
328$y^2=f(x)$, with $f(x)$ of arbitrary degree.  Perhaps implementing
329just what is needed for $y^2=x^3+ax+b$ might be more efficient.  Also,
330Harrison tells me his implementation isn't nearly as optimized as it
331might be.
332
333It might be possible to compute $p$-adic heights on Jacobians of
334hyperelliptic curves.
335
336Formulate everything above over number fields, and extend to the case
338
339Supersingular reduction?
340
341\section{Examples}
342The purpose of this section is to show you how to use the MAGMA package
343I wrote for computing with $p$-adic heights, and give you a sense
344for how fast it is.
345
346\begin{verbatim}
347> function EC(s) return EllipticCurve(CremonaDatabase(),s); end function;
348> E := EC("37A");
350> P := good_ordinary_primes(E,100); P;
351[ 5, 7, 11, 13, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73,
35279, 83, 89, 97 ]
353> for p in P do time print p, regulator(E,p,10); end for;
3545 22229672 + O(5^11)
355Time: 0.040
3567 317628041 + O(7^11)
357...
35889 15480467821870438719 + O(89^10)
359Time: 1.190
36097 -11195795337175141289 + O(97^10)
361Time: 1.490
362
363> E := EC("389A");
364> P := good_ordinary_primes(E,100); P;
365[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
36667, 71, 73, 79, 83, 89, 97 ]
367> for p in P do time print p, regulator(E,p,10); end for;
3685 -3871266 + O(5^11)
369Time: 0.260
3707 483898350 + O(7^11)
371...
37289 9775723521676164462 + O(89^10)
373Time: 1.330
37497 -13688331881071698338 + O(97^10)
375Time: 1.820
376
377> E := EC("5077A");
378> P := good_ordinary_primes(E,100); P;
379[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 43, 47, 53, 59, 61, 67, 71,
38073, 79, 83, 89, 97 ]
381> for p in P do time print p, regulator(E,p,10); end for;
3825 655268*5^-2 + O(5^7)
383Time: 0.800
3847 -933185758 + O(7^11)
385...
38689 -3325438607428779200 + O(89^10)
387Time: 1.910
38897 -5353586908063282167 + O(97^10)
389Time: 2.010
390
391--------
392
393> E := EC("37A");
394> time regulator(E,5,50);
395115299522541340178416234094637464047 + O(5^51)
396Time: 1.860
397> Valuation(115299522541340178416234094637464047 - 22229672,5);
3989
399
400> time regulator(E,97,50);
401-5019271523950156862996295340254565181870308222348277984940964806\
402     97957622583267105973403430183075091 + O(97^50)
403Time: 31.7
404\end{verbatim}
405
406
407\bibliography{biblio}
408\end{document}
409
410
411
412
413
414