Sharedwww / talks / padic_heights / pheight.texOpen in CoCalc
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
17
Let $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\},$$
22
and the \defn{canonical height} of $P$ is
23
$$
24
h(P) = \lim_{n\to\infty} \frac{h(2^n P)}{4^n}.
25
$$
26
This 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
32
In \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).$$
37
The local heights $\hat{h}_p(P)$ are easy to
38
compute explicitly. For example, when $p$ is a prime of good
39
reduction, $\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
42
not 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.$$
45
These height functions are genuine height functions; e.g., $h_p$
46
is a quadratic function, i.e, $h_p(mP) = m^2 h(P)$ for all~$m$.
47
They appear when defining the $p$-adic regulators that appear in the
48
Mazur-Tate $p$-adic analogues of the Birch and Swinnerton-Dyer
49
conjecture.
50
51
\vspace{3ex}
52
\noindent{\bf Acknowledgement:} Barry Mazur, John Tate, Mike Harrison,
53
Christian Wuthrich, Nick Katz.
54
55
\section{The $p$-Adic Height Pairing}
56
Let $E$ be an elliptic curve over~$\Q$ and suppose $p\geq 5$ is a prime
57
such that $E$ has good ordinary reduction at $p$. Suppose $P\in E(\Q)$
58
is a point that reduces to $0\in E(\F_p)$ and to the connected
59
component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.
60
We will define functions $\log_p$, $\sigma$, and $d$ below.
61
In 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}
65
The function $h_p$ satisfies $h_p(nP) = n^2 h_p(P)$ for all integers~$n$,
66
so it naturally extends to a function on the full Mordell-Weil group $E(\Q)$.
67
Setting $$\langle P, Q\rangle = \frac{1}{2}\cdot (h_p(P+Q)-h_p(P)-h_p(Q)),$$
68
we obtain a {\em nondegenerate} pairing on
69
$E(\Q)_{/\tor}$, and the $p$-adic regulator is the discriminant
70
of this pairing (which is well defined up to sign).
71
72
Investigations into $p$-adic Birch and Swinnerton-Dyer conjectures for
73
curves of positive rank inevitably lead to questions about such height
74
pairings, which motivate our interest in computing it to
75
high precision.
76
77
We now define each of the undefined quantities in
78
(\ref{eqn:heightdef}). The function $\log_p:\Q_p^* \to \Q_p$ is the
79
unique 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
81
if $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}),$$
83
where $u =
84
p^{-\ord_p(x)} \cdot x$.
85
86
The denominator $d(P)$ is the square root of the denominator of the
87
$x$-coordinate of $P$.
88
89
The $\sigma$ function is the most mysterious quantity in
90
(\ref{eqn:heightdef}), and it turns out the mystery is closely related
91
to the difficulty of computing the $p$-adic number $\E_2(E,\omega)$,
92
where $\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!
95
Let $$x(t) = \frac{1}{t^2} + \cdots \in \Z((t))$$
96
be the formal power
97
series that expresses $x$ in terms of $t=-x/y$ locally near $0\in E$.
98
Then Mazur and Tate prove there is exactly one function $\sigma(t)\in
99
t\Z_p[[t]]$ and constant $c\in \Q_p$ that satisfy the equation
100
\begin{equation}\label{eqn:sigmadef}
101
x(t)
102
+ c = -\frac{d}{\omega}\left( \frac{1}{\sigma}
103
\frac{d\sigma}{\omega}\right).
104
\end{equation}
105
This defines $\sigma$, and,
106
unwinding the meaning of the expression on the right, it leads to an
107
algorithm to compute $\sigma(t)$ to any desired precision,
108
which we now sketch.
109
110
If we expand (\ref{eqn:sigmadef}), we can view $c$ as a formal
111
variable and solve for $\sigma(t)$ as a power series with coefficients
112
that are polynomials in $c$. Each coefficient of $\sigma(t)$ must be
113
in $\Z_p$, so when there are denominators in the polynomials in $c$,
114
we obtain conditions on $c$ modulo powers of $p$. Taking these
115
together for many coefficients yields enough scraps of information to
116
get $c\pmod{p^n}$, for some small $n$, hence $\sigma(t) \pmod{p^n}$.
117
However, this algorithm is {\em extremely inefficient} and its
118
complexity is unclear (how many coefficients are needed to compute $c$
119
to precision $p^n$?).
120
121
For the last 15 or 20 years, the above unsatisifactory algorithm has
122
been the standard one for computing $p$-adic heights, e.g., when
123
investigating $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$}
129
Suppose that $E$ is an elliptic curve over $\Q$ given by a Weierstrass equation
130
$$
131
y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6.
132
$$
133
Let $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
136
the formal analogue of the usual complex $\wp$-function.)
137
In \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
$$
141
where $\E_2(E,\omega)$ is the value of the Katz $p$-adic
142
weight~$2$ Eisenstein series at $(E,\omega)$, and the equality is of
143
elements of $\Q_p((t))$. Thus computing $c$ is equivalent
144
to computing $\E_2(E,\omega)$.
145
146
This summer, Mazur, Tate, and I explored many ideas for computing
147
$\E_2(E,\omega)$. Though each was interesting and promising, nothing
148
led to a better algorithm that just computing $c$ as sketched above.
149
Perhaps the difficult of computing $\E_2(E,\omega)$ is somehow at the
150
heart of the theory?
151
152
Barry wrote to Nick Katz, who fired off the following email:
153
154
\subsection{Katz's Email}
155
\begin{verbatim}
156
Date: Thu, 8 Jul 2004 13:53:13 -0400
157
From: Nick Katz <nmk@Math.Princeton.EDU>
158
Subject: Re: convergence of the Eisenstein series of weight two
159
To: mazur@math.harvard.edu, nmkatz@Math.Princeton.EDU
160
Cc: tate@math.utexas.edu, was@math.harvard.edu
161
162
It 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
164
compute. Concretely, suppose we have a pair (E, \omega) over Z_p, and
165
to fix ideas p is not 2 or 3. Then we write a Weierstrass eqn for E,
166
y^2 = 4x^3 - g_2x - g_3, so that \omega is dx/y, and we denote by \eta
167
the differential xdx/y. Then \omega and \eta form a Z_p basis of
168
H^1_DR = H^1_cris, and the key step is to compute the matrix of
169
absolute Frobenius (here Z_p linear, the advantage of working over
170
Z_p: otherwise if over Witt vectors of an F_q, only \sigma-linear).
171
[This calculation goes fast, because the matrix of Frobenius lives
172
over the entire p-adic moduli space, and we are back in the glory days
173
of Washnitzer-Monsky cohomology (of the open curve E - {origin}).]
174
175
Okay, now suppose we have computed the matrix of Frob in the
176
basis \omega, \eta. The unit root subspace is a direct factor, call
177
it U, of the H^1, and we know that a complimentary direct factor is
178
Fil^1 := the Z_p span of \omega. We also know that Frob(\omega) lies
179
in pH^1, and this tells us that, mod p^n, U is the span of
180
Frob^n(\eta). What this means concretely is that if we write,
181
for each n,
182
183
Frob^n(\eta) = a_n\omega + b_n\eta,
184
185
then b_n is a unit (cong mod p to the n'th power of the Hasse
186
invariant) and that P is something like the ratio a_n/b_n (up to a
187
sign and a factor 12 which i don't recall offhand but which is in my
188
Antwerp appendix and also in my "p-adic interp. of real
189
anal. Eis. series" paper).
190
191
So in terms of speed of convergence, ONCE you have Frob, you
192
have to iterate it n times to calculate P mod p^n. Best, Nick
193
\end{verbatim}
194
195
\subsection{The Algorithms}
196
The following algorithms culminate in an algorithm for computing
197
$h_p(P)$ that incorporates Katz's ideas with the discussion elsewhere
198
in this paper. I have computed $\sigma$ and $h_p$ in numerous
199
cases using the algorithm described below, and using my
200
implementations of the ``integrality'' algorithm described above
201
and also Wuthrich's algorithm, and the results match. The analysis
202
of some of the necessary precision is not complete. I also have
203
not analyzed the complexity.
204
205
The 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
214
of~$E$. Set
215
$$a_4\set -\frac{c_4}{2^4\cdot 3}\qquad\text{and}\qquad
216
a_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
220
on the basis
221
$$\omega=\frac{dx}{y}, \qquad \eta=\frac{xdx}{y}$$
222
to precision $O(p^n)$. (We view $M$ as acting
223
from the left.)
224
\item
225
We know $M$ to precision $O(p^n)$.
226
Compute the $n$th power of $M$ and let
227
$\vtwo{a}{b}$ be the second column of $M^n$.
228
Then $\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
234
The 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)},$
247
where $x(t)=t/w(t)$ and $y(t)=-1/w(t)$ are the formal $x$
248
and $y$ functions, and $w(t)$ is given by the explicit inductive
249
formula in \cite[Ch.~7]{silverman:aec}. (Here $t=-x/y$ and $w=-1/y$ and
250
we 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$.
258
Then 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)$
268
is the formal logarithm computed above. Output $\sigma(t)$
269
and 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
279
The final algorithm uses $\sigma(t)$ to compute the $p$-adic height.
280
\begin{algorithm}{$p$-adic Height}
281
Given an elliptic curve~$E$ over $\Q$, a good ordinary prime~$p$,
282
and 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
285
be 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
289
component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$.
290
For example,~$m$ could be the least common multiple of the Tamagawa numbers
291
of $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
293
denominator 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
304
Suppose $E_t$ is an elliptic curves over $\Q(t)$. It might be
305
extremely interesting to obtain formula for $\E_2(E_t)$ as something
306
like (?) a power series in $\Q_p[[t]]$. This might shed light on the
307
analytic behavior of the $p$-adic modular form $\E_2$, and on Tate's
308
recent surprising experimental observations about the behavior of the
309
$(1/j)$-expansion of~$\E_2 E_4/E_6$.
310
311
It would also be interesting to do yet more computations in support of
312
$p$-adic analogues of the BSD conjectures of \cite{mtt}, especially
313
when $E/\Q$ has large rank. Substantial theoretical work has been
314
done toward these $p$-adic conjectures, and this work may be useful to
315
algorithms for computing information about Shafarevich-Tate and Selmer
316
groups of elliptic curves. For example, in \cite{pr:exp}, Perrin-Riou
317
uses her results about the $p$-adic BSD conjecture in the
318
supersingular case to prove that $\Sha(E/\Q)[p]=0$ for certain~$p$ and
319
elliptic curves~$E$ of rank $>1$, for which the work of Kolyvagin and
320
Kato does not apply. Mazur and Rubin (with my computational input)
321
are also obtaining results that could be viewed as fitting into this
322
program.
323
324
I would like to optimize the implementation of the algorithm.
325
Probably the most time-consuming step is computation of
326
$\E_2(E,\omega)$ using Kedlaya's algorithm. My current implementation
327
uses Michael Harrison's implementation of Kedlaya's algorithm for
328
$y^2=f(x)$, with $f(x)$ of arbitrary degree. Perhaps implementing
329
just what is needed for $y^2=x^3+ax+b$ might be more efficient. Also,
330
Harrison tells me his implementation isn't nearly as optimized as it
331
might be.
332
333
It might be possible to compute $p$-adic heights on Jacobians of
334
hyperelliptic curves.
335
336
Formulate everything above over number fields, and extend to the case
337
of additive reduction.
338
339
Supersingular reduction?
340
341
\section{Examples}
342
The purpose of this section is to show you how to use the MAGMA package
343
I wrote for computing with $p$-adic heights, and give you a sense
344
for how fast it is.
345
346
\begin{verbatim}
347
> function EC(s) return EllipticCurve(CremonaDatabase(),s); end function;
348
> E := EC("37A");
349
> Attach("padic_height.m");
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,
352
79, 83, 89, 97 ]
353
> for p in P do time print p, regulator(E,p,10); end for;
354
5 22229672 + O(5^11)
355
Time: 0.040
356
7 317628041 + O(7^11)
357
...
358
89 15480467821870438719 + O(89^10)
359
Time: 1.190
360
97 -11195795337175141289 + O(97^10)
361
Time: 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,
366
67, 71, 73, 79, 83, 89, 97 ]
367
> for p in P do time print p, regulator(E,p,10); end for;
368
5 -3871266 + O(5^11)
369
Time: 0.260
370
7 483898350 + O(7^11)
371
...
372
89 9775723521676164462 + O(89^10)
373
Time: 1.330
374
97 -13688331881071698338 + O(97^10)
375
Time: 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,
380
73, 79, 83, 89, 97 ]
381
> for p in P do time print p, regulator(E,p,10); end for;
382
5 655268*5^-2 + O(5^7)
383
Time: 0.800
384
7 -933185758 + O(7^11)
385
...
386
89 -3325438607428779200 + O(89^10)
387
Time: 1.910
388
97 -5353586908063282167 + O(97^10)
389
Time: 2.010
390
391
--------
392
393
> E := EC("37A");
394
> time regulator(E,5,50);
395
115299522541340178416234094637464047 + O(5^51)
396
Time: 1.860
397
> Valuation(115299522541340178416234094637464047 - 22229672,5);
398
9
399
400
> time regulator(E,97,50);
401
-5019271523950156862996295340254565181870308222348277984940964806\
402
97957622583267105973403430183075091 + O(97^50)
403
Time: 31.7
404
\end{verbatim}
405
406
407
\bibliography{biblio}
408
\end{document}
409
410
411
412
413
414