An Algorithm for Computing p-Adic Heights Using Monsky-Washnitzer Cohomology

William Stein

Notes for a Talk at MIT on 2004-10-15

Let E be an elliptic curve over ℚ and suppose

P = (x, y) = (\frac{a}{d^{2}} , \frac{b}{d^{3}} ) ∈ E(ℚ),

with a, b, d ∈ ℤ and gcd(a, d) = gcd(b, d) = 1. The naive height of P is

h̃(P) = log max{|a|, d^{2}},

and the canonical height of P is

h(P) = lim_{n→∞} \frac{h(2^{n}P)}{4^{n}}.

This definition is not good for computation, because 2^{n}P gets huge very quickly, and computing 2^{n}P exactly, for n large, is not reasonable.

In [Cre97, §3.4], Cremona describes an efficient method (due mostly to Silverman) for computing h(P). One defines local heights ĥ_{p} : E(ℚ) → ℝ, for all primes p, and ĥ_{∞} : E(ℚ) → ℝ such that

h(P) = ĥ_{∞}(P) + ∑ ĥ_{p}(P).

The local heights ĥ_{p}(P) are easy to compute explicitly. For example, when p is a prime of good reduction, ĥ_{p}(P) = max{0, − ord_{p}(x)} · log(p).

This paper is NOT about local heights ĥ_{p}, and we will not mention them any further. Instead, this paper is about a canonical global p-adic height function

h_{p} : E(ℚ) → ℚ_{p}.

These height functions are genuine height functions; e.g., h_{p} is a quadratic function, i.e, h_{p}(mP) = m^{2}h(P) for all m. They appear when defining the p-adic regulators that appear in the Mazur-Tate p-adic analogues of the Birch and Swinnerton-Dyer conjecture.

Acknowledgement: Barry Mazur, John Tate, Mike Harrison, Christian Wuthrich, Nick Katz.

1 The p-Adic Height Pairing

Let E be an elliptic curve over ℚ and suppose p ≥ 5 is a prime such that E has good ordinary reduction at p. Suppose P ∈ E(ℚ) is a point that reduces to 0 ∈ E(𝔽_{p}) and to the connected component of E_{𝔽_{ℓ}} at all bad primes ℓ. We will define functions log_{p}, σ, and d below. In terms of these functions, the p-adic height of P is

h_{p}(P) = \frac{1}{p} · log_{p} (\frac{σ(P)}{d(P)}) ∈ ℚ_{p}.  (1.1)

The function h_{p} satisfies h_{p}(nP) = n^{2}h_{p}(P) for all integers n, so it naturally extends to a function on the full Mordell-Weil group E(ℚ). Setting

⟨P, Q⟩ = \frac{1}{2} · (h_{p}(P + Q) − h_{p}(P) − h_{p}(Q)),

we obtain a nondegenerate pairing on E(ℚ)_{/ tor}, and the p-adic regulator is the discriminant of this pairing (which is well defined up to sign).

Investigations into p-adic Birch and Swinnerton-Dyer conjectures for curves of positive rank inevitably lead to questions about such height pairings, which motivate our interest in computing it to high precision.

We now define each of the undefined quantities in (1.1). The function log_{p} : ℚ_{p}^{∗} → ℚ_{p} is the unique homomorphism with log_{p}(p) = 1 that extends the homomorphism log_{p} : 1 + pℤ_{p} → ℚ_{p} defined by the usual power series of log(x) about 1. Thus if x ∈ ℚ_{p}^{∗}, we can compute log_{p}(x) using the formula

log_{p}(x) = \frac{1}{p − 1} · log_{p}(u^{p−1}),

where u = p^{− ord_{p}(x)} · x.

The denominator d(P) is the square root of the denominator of the x-coordinate of P.

The σ function is the most mysterious quantity in (1.1), and it turns out the mystery is closely related to the difficulty of computing the p-adic number 𝔼_{2}(E, ω), where 𝔼_{2} is the p-adic weight 2 Eisenstein series. There are many ways to define or characterize σ, e.g., [MT91] contains 11 different characterizations! Let

x(t) = \frac{1}{t^{2}} + ⋯ ∈ ℤ((t))

be the formal power series that expresses x in terms of t = −x/y locally near 0 ∈ E. Then Mazur and Tate prove there is exactly one function σ(t) ∈ tℤ_{p}[[t]] and constant c ∈ ℚ_{p} that satisfy the equation

x(t) + c = −\frac{d}{ω} (\frac{1}{σ} \frac{dσ}{ω} ) .  (1.2)

This defines σ, and, unwinding the meaning of the expression on the right, it leads to an algorithm to compute σ(t) to any desired precision, which we now sketch.

If we expand (1.2), we can view c as a formal variable and solve for σ(t) as a power series with coefficients that are polynomials in c. Each coefficient of σ(t) must be in ℤ_{p}, so when there are denominators in the polynomials in c, we obtain conditions on c modulo powers of p. Taking these together for many coefficients yields enough scraps of information to get c (mod p^{n}), for some small n, hence σ(t) (mod p^{n}). However, this algorithm is extremely inefficient and its complexity is unclear (how many coefficients are needed to compute c to precision p^{n}?).

For the last 15 or 20 years, the above unsatisifactory algorithm has been the standard one for computing p-adic heights, e.g., when investigating p-adic analogues of the BSD conjecture.

The situation changed a few weeks ago...

2 Using Cohomology to Compute σ

Suppose that E is an elliptic curve over ℚ given by a Weierstrass equation

y^{2} + a_{1}xy + a_{3}y = x^{3} + a_{2}x^{2} + a_{4}x + a_{6}.

Let x(t) be the formal series as before, and set

℘(t) = x(t) + (a_{1}^{2} + 4a_{2})/12 ∈ ℚ((t)).

(The function ℘ satisfies (℘′)^{2} = 4℘^{3} − g_{2}℘ − g_{3}, etc.; it’s the formal analogue of the usual complex ℘-function.) In [MT91], Mazur and Tate prove that

x(t) + c = ℘(t) + \frac{1}{12} · 𝔼_{2}(E, ω),

where 𝔼_{2}(E, ω) is the value of the Katz p-adic weight 2 Eisenstein series at (E, ω), and the equality is of elements of ℚ_{p}((t)). Thus computing c is equivalent to computing 𝔼_{2}(E, ω).

This summer, Mazur, Tate, and I explored many ideas for computing 𝔼_{2}(E, ω). Though each was interesting and promising, nothing led to a better algorithm that just computing c as sketched above. Perhaps the difficult of computing 𝔼_{2}(E, ω) is somehow at the heart of the theory?

Barry wrote to Nick Katz, who fired off the following email:

2.1 Katz’s Email

Date: Thu, 8 Jul 2004 13:53:13 -0400
From: Nick Katz <nmk@Math.Princeton.EDU>
Subject: Re: convergence of the Eisenstein series of weight two
To: mazur@math.harvard.edu, nmkatz@Math.Princeton.EDU
Cc: tate@math.utexas.edu, was@math.harvard.edu
It seems to me you want to use the interpretation of P as the

"direction of the unit root subspace", that should make it fast to
compute. Concretely, suppose we have a pair (E, \omega) over Z_p, and
to fix ideas p is not 2 or 3.  Then we write a Weierstrass eqn for E,
y^2 = 4x^3 - g_2x - g_3, so that \omega is dx/y, and we denote by \eta
the differential xdx/y. Then \omega and \eta form a Z_p basis of
H^1_DR = H^1_cris, and the key step is to compute the matrix of
absolute Frobenius (here Z_p linear, the advantage of working over
Z_p: otherwise if over Witt vectors of an F_q, only \sigma-linear).
[This calculation goes fast, because the matrix of Frobenius lives
over the entire p-adic moduli space, and we are back in the glory days
of Washnitzer-Monsky cohomology (of the open curve E - {origin}).]
        Okay, now suppose we have computed the matrix of Frob in the
basis \omega, \eta. The unit root subspace is a direct factor, call
it U, of the H^1, and we know that a complimentary direct factor is
Fil^1 := the Z_p span of \omega. We also know that Frob(\omega) lies
in pH^1, and this tells us that, mod p^n, U is the span of
Frob^n(\eta). What this means concretely is that if we write,
for each n,
   Frob^n(\eta) = a_n\omega + b_n\eta,
then b_n is a unit (cong mod p to the n'th power of the Hasse
invariant) and that P is something like the ratio a_n/b_n (up to a
sign and a factor 12 which i don't recall offhand but which is in my
Antwerp appendix and also in my "p-adic interp. of real
anal. Eis. series" paper).
        So in terms of speed of convergence, ONCE you have Frob, you
have to iterate it n times to calculate P mod p^n. Best, Nick

2.2 The Algorithms

The following algorithms culminate in an algorithm for computing h_{p}(P) that incorporates Katz’s ideas with the discussion elsewhere in this paper. I have computed σ and h_{p} in numerous cases using the algorithm described below, and using my implementations of the “integrality” algorithm described above and also Wuthrich’s algorithm, and the results match. The analysis of some of the necessary precision is not complete. I also have not analyzed the complexity.

The first algorithm computes 𝔼_{2}(E, ω).

Algorithm 2.1 (Evaluation of 𝔼_{2}(E, ω)). Given an elliptic curve over ℚ and prime p, this algorithm computes 𝔼_{2}(E, ω) ∈ ℚ_{p} (to precision O(p^{n}) say) . We assume that Kedlaya’s algorithm is available for computing a presentation of the p-adic Monsky-Washnitzer cohomology of E − {(0, 0)} with Frobenius action.

1. Let c_{4} and c_{6} be the c-invariants of a minimal model of E. Set

a_{4} ← −\frac{c_{4}}{2^{4} · 3}  and  a_{6} ← −\frac{c_{6}}{2^{5} · 3^{3}} .

2. Apply Kedlaya’s algorithm to the hyperelliptic curve y^{2} = x^{3} + a_{4}x + a_{6} (which is isomorphic to E) to obtain the matrix M of the action of absolute Frobenius on the basis

ω = \frac{dx}{y}, η = \frac{xdx}{y}

to precision O(p^{n}). (We view M as acting from the left.)

3. We know M to precision O(p^{n}). Compute the nth power of M and let (\begin{matrix}a \\ b \end{matrix}) be

the second column of M^{n}. Then Frob^{n}(η) = aω + bη

4. Output M and −12a/b (which is 𝔼_{2}(E, ω)), then terminate.

The next algorithm uses the above algorithm to compute σ(t).

Algorithm 2.2 (The Canonical p-adic Sigma Function). Given an elliptic curve E and a good ordinary prime p, this algorithm computes σ(t) ∈ ℤ_{p}[[t]] modulo (p^{n}, t^{m}) for any given positive integers n, m. (I have not figured out exactly what precision each object below must be computed to.)

1. Using Algorithm 2.1, compute e_{2} = 𝔼_{2}(E, ω) ∈ ℤ_{p} to precision O(p^{n}).

2. Compute the formal power series x = x(t) ∈ ℚ[[t]] associated to the formal group of E to precision O(t^{m}).

3. Compute the formal logarithm z(t) ∈ ℚ((t)) to precision O(t^{m}) using that z(t) =

∫ \frac{dx/dt}{(2y(t) + a_{1}x(t) + a_{3})}, where x(t) = t/w(t) and y(t) = −1/w(t) are the formal

x and y functions, and w(t) is given by the explicit inductive formula in [Sil92, Ch. 7]. (Here t = −x/y and w = −1/y and we can write w as a series in t.)

4. Using a power series “reversion” (functional inverse) algorithm (see e.g., Mathworld), find the power series F (z) ∈ ℚ[[z]] such that t = F (z). Here F is the reversion of z, which exists because z(t) = t + · · ·.

5. Set ℘(t) ← x(t) + (a_{1}^{2} + 4a_{2})/12 ∈ ℚ[[t]] (to precision O(t^{m})), where the a_{i} are the coefficients of the Weierstrass equation of E. Then compute the series ℘(z) = ℘(F (z)) ∈ ℚ((z)).

6. Set g(z) ← \frac{1}{z^{2}} − ℘(z) + \frac{e_{2}}{12} ∈ ℚ_{p}((z)). (Note: The theory suggests the last term should be −e_{2}/12 but the calculations do not work unless I use the above formula. Maybe there are two normalizations of E_{2} in the literature?)

7. Set σ(z) ← z · exp (∫ ∫ g(z) dz dz) ∈ ℚ_{p}[[z]].

8. Set σ(t) ← σ(z(t)) ∈ t·ℤ_{p}[[t]], where z(t) is the formal logarithm computed above. Output σ(t) and terminate.

Remark 2.3. The trick of changing from ℘(t) to ℘(z) is essential so that we can solve a certain differential equation using just operations with power series.

The final algorithm uses σ(t) to compute the p-adic height.

Algorithm 2.4 (p-adic Height). Given an elliptic curve E over ℚ, a good ordinary prime p, and an element P ∈ E(ℚ), this algorithm computes the p-adic height h_{p}(P) ∈ ℚ_{p} to precision O(p^{n}). (I will ignore the precision below, though this must be not be ignored for the final version of this paper.)

1. [Prepare Point] Compute an integer m such that mP reduces to 0 ∈ E(𝔽_{p}) and to the connected component of E_{𝔽_{ℓ}} at all bad primes ℓ. For example, m could be the least common multiple of the Tamagawa numbers of E and #E(𝔽_{p}). Set Q ← mP and write Q = (x, y).

2. [Denominator] Let d be the positive integer square root of the denominator of x.

3. [Compute σ] Compute σ(t) using Algorithm 2.2, and set s ← σ(−x/y) ∈ ℚ_{p}.

4. [Logs] Compute h_{p}(Q) ← \frac{1}{p} log_{p} (\frac{s}{d}), and h_{p}(P) ← \frac{1}{m^{2}} · h_{p}(Q). Output h_{p}(P)

and terminate.

3 Future Directions

Suppose E_{t} is an elliptic curves over ℚ(t). It might be extremely interesting to obtain formula for 𝔼_{2}(E_{t}) as something like (?) a power series in ℚ_{p}[[t]]. This might shed light on the analytic behavior of the p-adic modular form 𝔼_{2}, and on Tate’s recent surprising experimental observations about the behavior of the (1/j)-expansion of 𝔼_{2}E_{4}/E_{6}.

It would also be interesting to do yet more computations in support of p-adic analogues of the BSD conjectures of [MTT86], especially when E/ℚ has large rank. Substantial theoretical work has been done toward these p-adic conjectures, and this work may be useful to algorithms for computing information about Shafarevich-Tate and Selmer groups of elliptic curves. For example, in [PR03], Perrin-Riou uses her results about the p-adic BSD conjecture in the supersingular case to prove that � (E/ℚ)[p] = 0 for certain p and elliptic curves E of rank > 1, for which the work of Kolyvagin and Kato does not apply. Mazur and Rubin (with my computational input) are also obtaining results that could be viewed as fitting into this program.

I would like to optimize the implementation of the algorithm. Probably the most time-consuming step is computation of 𝔼_{2}(E, ω) using Kedlaya’s algorithm. My current implementation uses Michael Harrison’s implementation of Kedlaya’s algorithm for y^{2} = f(x), with f(x) of arbitrary degree. Perhaps implementing just what is needed for y^{2} = x^{3} + ax + b might be more efficient. Also, Harrison tells me his implementation isn’t nearly as optimized as it might be.

It might be possible to compute p-adic heights on Jacobians of hyperelliptic curves. Formulate everything above over number fields, and extend to the case of additive

reduction.

Supersingular reduction?

4 Examples

The purpose of this section is to show you how to use the MAGMA package I wrote for computing with p-adic heights, and give you a sense for how fast it is.

> function EC(s) return EllipticCurve(CremonaDatabase(),s); end function;
> E := EC("37A");
> Attach("padic_height.m");
> P := good_ordinary_primes(E,100); P;
[ 5, 7, 11, 13, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97 ]
> for p in P do time print p, regulator(E,p,10); end for;
5 22229672 + O(5^11)
Time: 0.040
7 317628041 + O(7^11)
...
89 15480467821870438719 + O(89^10)
Time: 1.190
97 -11195795337175141289 + O(97^10)
Time: 1.490
> E := EC("389A");
> P := good_ordinary_primes(E,100); P;
[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61,
67, 71, 73, 79, 83, 89, 97 ]
> for p in P do time print p, regulator(E,p,10); end for;
5 -3871266 + O(5^11)
Time: 0.260
7 483898350 + O(7^11)
...
89 9775723521676164462 + O(89^10)
Time: 1.330
97 -13688331881071698338 + O(97^10)
Time: 1.820
> E := EC("5077A");
> P := good_ordinary_primes(E,100); P;
[ 5, 7, 11, 13, 17, 19, 23, 29, 31, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97 ]
> for p in P do time print p, regulator(E,p,10); end for;
5 655268*5^-2 + O(5^7)
Time: 0.800
7 -933185758 + O(7^11)
...
89 -3325438607428779200 + O(89^10)

Time: 1.910
97 -5353586908063282167 + O(97^10)
Time: 2.010
--------
> E := EC("37A");
> time regulator(E,5,50);
115299522541340178416234094637464047 + O(5^51)
Time: 1.860
> Valuation(115299522541340178416234094637464047 - 22229672,5);
9
> time regulator(E,97,50);
-5019271523950156862996295340254565181870308222348277984940964806\
     97957622583267105973403430183075091 + O(97^50)
Time: 31.7

References

[Cre97] J. E. Cremona, Algorithms for modular elliptic curves, second ed., Cambridge University Press, Cambridge, 1997, Complete text available at

        http://www.maths.nott.ac.uk/personal/jec/book/.

[MT91] B. Mazur and J. Tate, The p-adic sigma function, Duke Math. J. 62 (1991), no. 3, 663–688. MR 93d:11059

[MTT86] B. Mazur, J. Tate, and J. Teitelbaum, On p-adic analogues of the conjectures of Birch and Swinnerton-Dyer, Invent. Math. 84 (1986), no. 1, 1–48. MR MR830037 (87e:11076)

[PR03] Bernadette Perrin-Riou, Arithmétique des courbes elliptiques à réduction supersingulière en p, Experiment. Math. 12 (2003), no. 2, 155–186. MR MR2016704

[Sil92] J. H. Silverman, The arithmetic of elliptic curves, Springer-Verlag, New York, 1992, Corrected reprint of the 1986 original.