%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % Use latex to typeset this document. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % Documenta-LaTeX.sty (2e) % % Version 0.5 % % Copyright (C) 2000-2006 Ulf Rehmann % rehmann@mathematik.uni-bielefeld.de % % ------------------------------ PROLOGUE ----------------------------- % % This prologue is to be prepended to your LaTeX file in order to % give it the layout required by Documenta Mathematica. % Please edit the \documentclass line below, add \usepackage lines % according to your needs and % go to the line starting with \Title below, fill in title, % authors' names and so on and follow the further instructions there. % % Choose one of the commands \documentclass[]{} or \documentstyle[]{} % depending on the version of LaTeX you use: % % % If you use LaTeX 2e use the following line (or similar): \documentclass[10pt,twoside]{article} % delete if this gives you any problems. %\usepackage[active]{srcltx} %*************Declaration Section****************** \usepackage{float} %\usepackage[hypertex]{hyperref} %\usepackage[hyperindex,pdfmark]{hyperref} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amssymb} \hoffset=-0.05\textwidth \textwidth=1.10\textwidth \voffset=-0.05\textheight \textheight=1.10\textheight %\bibliographystyle{amsalpha} \newcommand{\edit}[1]{\footnote{[[#1]]}\marginpar{\hfill {\sf[[\thefootnote]]}}} \renewcommand{\edit}[1]{} \newcommand{\editwas}[1]{\footnote{[[#1]]}\marginpar{\hfill {\sf[[\thefootnote]]}}} \renewcommand{\editwas}[1]{} \newcommand{\an}{{\rm an}} \newcommand{\e}{\mathbf{e}} \DeclareFontEncoding{OT2}{}{} % to enable usage of cyrillic fonts \newcommand{\textcyr}[1]{% {\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}% \selectfont #1}} \newcommand{\Sha}{{\mbox{\textcyr{Sh}}}} \newcommand{\Gam}{\Gamma} \newcommand{\cO}{\mathcal{O}} \newcommand{\ds}{\displaystyle} \newcommand{\M}{\mathcal{M}} \newcommand{\E}{\mathbf{E}} \newcommand{\q}{\mathbf{q}} \newcommand{\ra}{\rightarrow} \newcommand{\la}{\leftarrow} \newcommand{\con}{\equiv} \newcommand{\set}[1]{\{#1\}} \newcommand{\alp}{\alpha} \newcommand{\vtwo}[2]{\left(\begin{matrix}#1\\#2\end{matrix}\right)} \newcommand{\eps}{\varepsilon} \newcommand{\A}{\mathbf A} \newcommand{\Q}{\mathbf{Q}} \newcommand{\C}{\mathbf{C}} \newcommand{\D}{{\mathbf D}} \newcommand{\Z}{\mathbf{Z}} \newcommand{\F}{\mathbf{F}} \newcommand{\cE}{\mathcal{E}} \newcommand{\et}{\text{\rm\'et}} \newcommand{\h}{\mathfrak{h}} \newcommand{\p}{\mathfrak{p}} \newcommand{\m}{\mathfrak{m}} \renewcommand{\l}{\ell} \renewcommand{\t}{\tau} \renewcommand{\a}{\mathfrak{a}} \renewcommand{\H}{\HH} \DeclareMathOperator{\new}{new} \DeclareMathOperator{\tor}{tor} \DeclareMathOperator{\Frob}{Frob} \DeclareMathOperator{\Gal}{Gal} \DeclareMathOperator{\ab}{ab} \DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\ord}{ord} \DeclareMathOperator{\SL}{SL} \renewcommand{\set}{=} \newcommand{\ggeq}{\,\,\,\underline{\gg}\,\,\,} \newcommand{\isom}{\cong} %%%% Theoremstyles \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{claim}[theorem]{Claim} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{hypothesis}[theorem]{Hypothesis} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{question}[theorem]{Question} \newtheorem{problem}[theorem]{Problem} \newtheorem{alg}[theorem]{Algorithm} \newtheorem{openproblem}[theorem]{Open Problem} %\theoremstyle{remark} \newtheorem{goal}[theorem]{Goal} \newtheorem{remark}[theorem]{Remark} \newtheorem{remarks}[theorem]{Remarks} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newenvironment{algorithm}[1]{% \begin{alg}[#1]\index{algorithm!#1}\sf }% {\end{alg}} \newenvironment{steps}% {\begin{enumerate}\setlength{\itemsep}{0.1ex}}{\end{enumerate}} \DeclareMathOperator{\HH}{H} \renewcommand{\H}{\HH} \numberwithin{equation}{section} \numberwithin{figure}{section} \numberwithin{table}{section} % If you use LaTeX 2.09 or earlier use the following line (or similar): %\documentstyle[10pt,twoside]{article} % % Please go to the line starting with \Title below, fill in title, % authors' names and so on and follow the further instructions there. % % The final values of the following 4 uncommented lines will be filled in % by Doc. Math. after the manuscript has been accepted for publication. % \def\YEAR{\year}\newcount\VOL\VOL=\YEAR\advance\VOL by-1995 \def\firstpage{585}\def\lastpage{622} \def\received{September 9, 2005}\def\revised{May 2, 2006} \def\communicated{} % \makeatletter \def\magnification{\afterassignment\m@g\count@} \def\m@g{\mag=\count@\hsize6.5truein\vsize8.9truein\dimen\footins8truein} \makeatother %%% Choose 10pt/12pt: %\oddsidemargin1.66cm\evensidemargin1.66cm\voffset1.2cm%10pt \oddsidemargin1.91cm\evensidemargin1.91cm\voffset1.4cm%10pt %\magnification1200\oddsidemargin.41cm\evensidemargin.41cm\voffset-.75cm%12pt %\textwidth12.5cm\textheight19.5cm \textwidth12.0cm\textheight19.0cm \font\eightrm=cmr8 \font\caps=cmcsc10 % Theorem, Lemma etc \font\ccaps=cmcsc10 % Sections \font\Caps=cmcsc10 scaled \magstep1 % Title \font\scaps=cmcsc8 % %-----------------headlines----------------------------------- %\input german.sty % uncomment if necessary %\usepackage{german} % uncomment if necessary \pagestyle{myheadings} \pagenumbering{arabic} \setcounter{page}{\firstpage} \def\bfseries{\normalsize\caps} \makeatletter \setlength\topmargin {14\p@} \setlength\headsep {15\p@} \setlength\footskip {25\p@} \setlength\parindent {20\p@} \@specialpagefalse\headheight=8.5pt \def\DocMath{} \def\DocMath{{\def\th{\thinspace}\scaps Documenta Math.}} \renewcommand{\@oddfoot}{\hfill\scaps Documenta Mathematica $\cdot$ Extra Volume Coates (\number\YEAR) \number\firstpage--\lastpage\hfill} \renewcommand{\@evenfoot}{\ifnum\thepage>\lastpage\hfill\scaps Documenta Mathematica $\cdot$ Extra Volume Coates (\number\YEAR) \hfill\else\@oddfoot\fi}% \renewcommand{\@evenhead}{% \ifnum\thepage>\lastpage\rlap{\thepage}\hfill% \else\rlap{\thepage}\slshape\leftmark\hfill{\caps\SAuthor}\hfill\fi}% \renewcommand{\@oddhead}{% \ifnum\thepage=\firstpage{\DocMath\hfill\llap{\thepage}}% \else{\slshape\rightmark}\hfill{\caps\STitle}\hfill\llap{\thepage}\fi}% \makeatother \def\TSkip{\bigskip} \newbox\TheTitle{\obeylines\gdef\GetTitle #1 \ShortTitle #2 \SubTitle #3 \Author #4 \ShortAuthor #5 \EndTitle {\setbox\TheTitle=\vbox{\baselineskip=20pt\let\par=\cr\obeylines% \halign{\centerline{\Caps##}\cr\noalign{\medskip}\cr#1\cr}}% \copy\TheTitle\TSkip\TSkip% \def\next{#2}\ifx\next\empty\gdef\STitle{#1}\else\gdef\STitle{#2}\fi% \def\next{#3}\ifx\next\empty% \else\setbox\TheTitle=\vbox{\baselineskip=20pt\let\par=\cr\obeylines% \halign{\centerline{\caps##} #3\cr}}\copy\TheTitle\TSkip\TSkip\fi% %\setbox\TheTitle=\vbox{\let\par=\cr\obeylines% %\halign{\centerline{\caps##} #4\cr}}\copy\TheTitle\TSkip\TSkip% \centerline{\caps #4}\TSkip\TSkip% \def\next{#5}\ifx\next\empty\gdef\SAuthor{#4}\else\gdef\SAuthor{#5}\fi% \ifx\received\empty\relax \else\centerline{\eightrm Received: \received}\fi% \ifx\revised\empty\TSkip% \else\centerline{\eightrm Revised: \revised}\TSkip\fi% \ifx\communicated\empty\relax \else\centerline{\eightrm Communicated by \communicated}\fi\TSkip\TSkip% \catcode'015=5}}\def\Title{\obeylines\GetTitle} \def\Abstract{\begingroup\narrower \parskip=\medskipamount\parindent=0pt{\caps Abstract. }} \def\EndAbstract{\par\endgroup\TSkip} \long\def\MSC#1\EndMSC{\def\arg{#1}\ifx\arg\empty\relax\else {\par\narrower\noindent% 2000 Mathematics Subject Classification: #1\par}\fi} \long\def\KEY#1\EndKEY{\def\arg{#1}\ifx\arg\empty\relax\else {\par\narrower\noindent Keywords and Phrases: #1\par}\fi\TSkip} \newbox\TheAdd\def\Addresses{\vfill\copy\TheAdd\vfill \ifodd\number\lastpage\vfill\eject\phantom{.}\vfill\eject\fi} {\obeylines\gdef\GetAddress #1 \Address #2 \Address #3 \Address #4 \EndAddress {\def\xs{6.0truecm}\parindent=0pt \setbox0=\vtop{{\obeylines\hsize=\xs#1\par}}\def\next{#2} \ifx\next\empty % 1 address \setbox\TheAdd=\hbox to\hsize{\hfill\copy0\hfill} \else\setbox1=\vtop{{\obeylines\hsize=\xs#2\par}}\def\next{#3} \ifx\next\empty % 2 addresses \setbox\TheAdd=\hbox to\hsize{\hfill\copy0\hfill\copy1\hfill} \else\setbox2=\vtop{{\obeylines\hsize=\xs#3\par}}\def\next{#4} \ifx\next\empty\ % 3 addresses \setbox\TheAdd=\vtop{\hbox to\hsize{\hfill\copy0\hfill\copy1\hfill} \vskip20pt\hbox to\hsize{\hfill\copy2\hfill}} \else\setbox3=\vtop{{\obeylines\hsize=\xs#4\par}} \setbox\TheAdd=\vtop{\hbox to\hsize{\hfill\copy0\hfill\copy1\hfill} \vskip20pt\hbox to\hsize{\hfill\copy2\hfill\copy3\hfill}} \fi\fi\fi\catcode'015=5}}\gdef\Address{\obeylines\GetAddress} \hfuzz=0.1pt\tolerance=2000\emergencystretch=20pt\overfullrule=5pt \begin{document} %%%%% ------------- fill in your data below this line ------------------- %%%%% The following lines \Title ... \EndAddress must ALL be present %%%%% and in the given order. \Title %%%%% Put here the title. Line breaks will be recognized. Computation of {\sl \large p}-Adic Heights and Log Convergence \ShortTitle $p$-Adic Heights and Log Convergence %%%%% Running title for odd numbered pages, ONE line, please. %%%%% If none is given, \Title will be used instead. \SubTitle %%%%% A possible subtitle goes here. {\small In celebration of John Coates' 60th birthday} \Author %%%%% Put here name(s) of authors. Line breaks will be recognized. Barry Mazur, William Stein\footnote{This material is based upon work % supported by the National Science Foundation under Grant % No. 0555776.}, John Tate \ShortAuthor Mazur, Stein, Tate %%%%%% Running title for even numbered pages, ONE line, please. %%%%%% If none is given, \Author will be used instead. \EndTitle \Abstract %%%%% Put here the abstract of your manuscript. %%%%% Avoid macros and complicated TeX expressions, as this is %%%%% automatically translated and posted as an html file. This paper is about computational and theoretical questions regarding $p$-adic height pairings on elliptic curves over a global field $K$. The main stumbling block to computing them efficiently is in calculating, for each of the completions $K_v$ at the places~$v$ of~$K$ dividing~$p$, a {\it single quantity}: the value of the $p$-adic modular form ${\bf E}_2$ associated to the elliptic curve. Thanks to the work of Dwork, Katz, Kedlaya, Lauder and Monsky-Washnitzer we offer an efficient algorithm for computing these quantities, i.e., for computing the value of ${\bf E}_2$ of an elliptic curve. We also discuss the $p$-adic convergence rate of canonical expansions of the $p$-adic modular form~${\bf E}_2$ on the Hasse domain. In particular, we introduce a new notion of log convergence and prove that $\E_2$ is log convergent. \EndAbstract \MSC %%%%% 2000 Mathematics Subject Classification: 11F33, 11Y40, 11G50 \EndMSC \KEY %%%%% Keywords and Phrases: $p$-adic heights, algorithms, $p$-adic modular forms, Eisenstein series, sigma-functions \EndKEY %%%%% All 4 \Address lines below must be present. To center the last %%%%% entry, no empty lines must be between the following \Address %%%%% and \EndAddress lines. %%%%% Address of first Author here \Address Barry Mazur Department of Mathematics Harvard University mazur@math.harvard.edu \Address John Tate Department of Mathematics University of Texas at Austin tate@math.utexas.edu \Address William A. Stein Department of Mathematics University of California at San Diego wstein@ucsd.edu \Address \EndAddress %% %% Make sure the last tex command in your manuscript %% before the first \end{document} is the command \Addresses %% %%---------------------Here the prologue ends--------------------------------- %%--------------------Here the manuscript starts------------------------------ \parindent15pt \section{Introduction}\label{sec:intro} Let $p$ be an odd prime number, and $E$ an elliptic curve over a global field $K$ that has good ordinary reduction at $p$. Let $L$ be any (infinite degree) Galois extension with a continuous injective homomorphism $\rho$ of its Galois group to $\Q_p$. To the data $(E,K,\rho)$, one associates\footnote{See \cite{mazur-tate:canonical}, \cite{schneider:height1} \cite{schneider:height2}, \cite{MR1042777}, \cite{MR1091621}, \cite {MR1263527}, \cite{MR1299736}, \cite{MR2021039}, and \cite{MR2076563}.} a canonical (bilinear, symmetric) ($p$-adic) height pairing $$ ( \ ,\ )_{\rho} : E(K)\times E(K) \longrightarrow \Q_p. $$ Such pairings are of great interest for the arithmetic of~$E$ over~$K$, and they arise specifically in $p$-adic analogues of the Birch and Swinnerton-Dyer conjecture.\footnote{See \cite{schneider:height1}, \cite{schneider:height2} \cite{mazur-tate:canonical}, \cite{mazur-tate:refined}, \cite{perrin-riou:expmath}. See also the important recent work of Jan Nekov{\'a}{\v{r}} \cite{nekovar:selmer}.} The goal of this paper is to discuss some computational questions regarding $p$-adic height pairings. The main stumbling block to computing them efficiently is in calculating, for each of the completions $K_v$ at the places~$v$ of~$K$ dividing~$p$, the value of the $p$-adic modular form ${\bf E}_2$ associated to the elliptic curve with a chosen Weierstrass form of good reduction over $K_v$. We shall offer an algorithm for computing these quantities, i.e., for computing the value of ${\bf E}_2$ of an elliptic curve (that builds on the works of Katz and Kedlaya listed in our bibliography) and we also discuss the $p$-adic convergence rate of canonical expansions of the $p$-adic modular form ${\bf E}_2$ on the Hasse domain, where for $p\ge 5$ we view ${\bf E}_2$ as an infinite sum of classical modular forms divided by powers of the (classical) modular form ${\bf E}_{p-1}$, while for $p\le 5$ we view it as a sum of classical modular forms divided by powers of~${\bf E}_4$. We were led to our fast method of computing $\E_2$ by our realization that the more naive methods, of computing it by integrality or by approximations to it as function on the Hasse domain, were not practical, because the convergence is ``logarithmic'' in the sense that the $n$th convergent gives only an accuracy of~$\log_p(n)$. We make this notion of log convergence precise in Part~\ref{part2}, where we also prove that ${\bf E}_2$ is log convergent. The reason why this constant ${\bf E}_2$ enters the calculation is because it is needed for the computation of the $p$-adic sigma function \cite{mazur-tate:sigma}, which in turn is the critical element in the formulas for height pairings. For example, let us consider the {\it cyclotomic} $p$-adic height pairing in the special case where $K=\Q$ and $p\geq 5$. If $G_{\Q}$ is the Galois group of an algebraic closure of $\Q$ over $\Q$, we have the natural surjective continuous homomorphism $\chi: G_{\Q} \to \Z_p^*$ pinned down by the standard formula $g(\zeta) = \zeta^{\chi(g)}$ where $g \in G_{\Q}$ and $\zeta$ is any $p$-power root of unity. The $p$-adic logarithm $\log_p:\Q_p^* \to (\Q_p,+)$ is the unique group homomorphism with $\log_p(p)=0$ that extends the homomorphism $\log_p:1+p\Z_p \to \Q_p$ defined by the usual power series of $\log(x)$ about $1$. Explicitly, if $x\in\Q_p^*$, then $$\log_p(x) = \frac{1}{p-1}\cdot \log_p(u^{p-1}),$$ where $u = p^{-\ord_p(x)} \cdot x$ is the unit part of~$x$, and the usual series for $\log$ converges at $u^{p-1}$. The composition $(\frac{1}{p}\cdot \log_p)\circ \chi$ is a cyclotomic linear functional $G_{\Q} \to \Q_p$ which, in the body of our text, will be dealt with (thanks to class field theory) as the idele class functional that we denote $\rho_{\Q}^{\rm cycl}$. Let $\cE$ denote the N\'eron model of~$E$ over~$\Z$. Let $P\in E(\Q)$ be a non-torsion point that reduces to $0\in E(\F_p)$ and to the connected component of $\cE_{\F_\ell}$ at all primes $\ell$ of bad reduction for~$E$. Because $\Z$ is a unique factorization domain, any nonzero point $P=(x(P),y(P)) \in E(\Q)$ can be written uniquely in the form $(a/d^2, b/d^3)$, where $a,b,d \in \Z$, $\gcd(a,d)=\gcd(b,d)=1$, and $d>0$. The function $d(P)$ assigns to $P$ this square root~$d$ of the denominator of $x(P)$. Here is the formula for the {\it cyclotomic} $p$-adic height of $P$, i.e., the value of $$h_p(P) := -{\frac{1}{2}}(P,P)_p \in \Q_p$$ where $(\ ,\ )_p$ is the height pairing attached to $G_{\Q} \to \Q_p$, the cyclotomic linear functional described above: \begin{equation}\label{eqn:heightdef} h_p(P) = \frac{1}{p}\cdot \log_p\left(\frac{\sigma(P)}{d(P)}\right) \in \Q_p. \end{equation} Here $\sigma = \sigma_p$ is the $p$-adic sigma function of \cite{mazur-tate:sigma} associated to the pair $(E,\omega)$. \edit{I added this entire paragraph.} The $\sigma$-function depends only on $(E,\omega)$ and not on a choice of Weierstrass equation, and behaves like a modular form of weight $-1$, that is $\sigma_{E,c\omega} =c\cdot \sigma_{E,\omega}$. It is ``quadratic'' the sense that for any $m\in\Z$ and point~$Q$ in the formal group $E^f(\overline{\Z}_p)$, we have \begin{equation}\label{eqn:quad} \sigma(mQ) = \sigma(Q)^{m^2} \cdot f_m(Q), \end{equation} where $f_m$ is the $m$th division polynomial of~$E$ relative to~$\omega$ (as in \cite[App.~1]{mazur-tate:sigma}). The $\sigma$-function is ``bilinear''\label{page:bil} in that for any $P,Q \in E^f(\Z_p)$, we have \begin{equation}\label{eqn:bil} \frac{\sigma(P-Q)\cdot \sigma(P+Q)}{\sigma^2(P)\cdot \sigma^2(Q)} = x(Q) - x(P). \end{equation} See \cite[Thm.~3.1]{mazur-tate:sigma} for proofs of the above properties of~$\sigma$. The height function~$h_p$ of (\ref{eqn:heightdef}) extends uniquely to a function on the full Mordell-Weil group $E(\Q)$ that satisfies $h_p(nQ) = n^2 h_p(Q)$ for all integers~$n$ and $Q \in E(\Q)$. For $P,Q \in E(\Q)$, setting %\edit{William: Barry, you had $-h_p(Q)$, %and I changed it to $h_p(Q)$. Yes, you re right (B.M.)} $$( P, Q )_p = h_p(P)+h_p(Q) -h_p(P+Q),$$ we obtain a pairing on $E(\Q)$. The {\em $p$-adic regulator} of $E$ is the discriminant of the induced pairing on $E(\Q)_{/\tor}$ (well defined up to sign), and we have the following standard conjecture about this height pairing. \begin{conjecture} The cyclotomic height pairing $(\ , \ )_p$ is nondegenerate; equivalently, the $p$-adic regulator is nonzero. \end{conjecture} \begin{remark} Height pairings attached to other $p$-adic linear functionals can be degenerate; in fact, given an elliptic curve defined over $\Q$ with good ordinary reduction at $p$, and $K$ a quadratic imaginary field over which the Mordell-Weil group $E(K)$ is of odd rank, the $p$-adic anticyclotomic height pairing for $E$ over $K$ is {\em always} degenerate. \end{remark} %We now give definitions of $\log_p$, $d$, and $\sigma$. The $p$-adic $\sigma$ function is the most mysterious quantity in (\ref{eqn:heightdef}). % and it turns out the mystery is closely related %to the difficulty of computing the $p$-adic number $\E_2(E,\omega)$, %where $\E_2$ is the $p$-adic weight $2$ Eisenstein series. There are many ways to define~$\sigma$, e.g., \cite{mazur-tate:sigma} contains $11$ different characterizations of~$\sigma$! We now describe a characterization that leads directly to an algorithm (see Algorithm~\ref{alg:int}) to compute~$\sigma(t)$. Let \begin{equation}\label{eqn:xt} x(t) = \frac{1}{t^2} + \cdots \in \Z_p((t)) \end{equation} be the formal power series that expresses $x$ in terms of the local parameter $t=-x/y$ at infinity. %\editwas{I'm worried about whether %this is in $\Z((t))$ if the Weierstrass equation is very strange.} The following theorem, which is proved in \cite{mazur-tate:sigma}, uniquely determines~$\sigma$ and $c$. \begin{theorem}\label{thm:uniqde} There is exactly one odd function $\sigma(t) = t + \cdots \in t\Z_p[[t]]$ and constant $c\in \Z_p$ that together satisfy the differential equation \begin{equation}\label{eqn:sigmadef} x(t) + c = -\frac{d}{\omega}\left( \frac{1}{\sigma} \frac{d\sigma}{\omega}\right), \end{equation} where $\omega$ is the invariant differential $dx/(2y+a_1x+a_3)$ associated with our chosen Weierstrass equation for $E$. \end{theorem} %\edit{William: I removed the $1+$ in this formula. It should % be $1\cdot$ but I don't think it is necessary to signal constant = $1$.} %\editwas{I'm worried: do we need ``odd''. Also is coeff %of $t=1$ required?} \begin{remark}The condition that $\sigma$ is odd and that the coefficient of $t$ is $1$ are essential. \end{remark} In (\ref{eqn:heightdef}), by $\sigma(P)$ we mean $\sigma(-x/y)$, where $P=(x,y)$. We have thus given a complete definition of $h_p(Q)$ for any point $Q \in E(\Q)$ and a prime $p\geq 5$ of good ordinary reduction for $E$. \subsection{The $p$-adic $\sigma$-function} The differential equation (\ref{eqn:sigmadef}) leads to a slow algorithm to compute $\sigma(t)$ to any desired precision. This is Algorithm~\ref{alg:int} below, which we now summarize. If we expand (\ref{eqn:sigmadef}), we can view $c$ as a formal variable and solve for $\sigma(t)$ as a power series with coefficients that are polynomials in~$c$. Each coefficient of $\sigma(t)$ must be in $\Z_p$, so we obtain conditions on~$c$ modulo powers of~$p$. Taking these together for many coefficients must eventually yield enough information to compute $c\pmod{p^n}$, for a given $n$, hence $\sigma(t) \pmod{p^n}$. This integrality algorithm is hopelessly slow in general. %inefficient if one wants $n$ or $p$ to %be at all large. Wuthrich remarks that in his experiments, %approximately $p^n$ coefficients of $\sigma$ have to be computed to %get $c$ up to precision $p^n$, so this method is Another approach to computing~$\sigma$ is to observe that, up to a constant,~$c$ is closely related to the value of a certain $p$-adic modular form. More precisely, suppose that $E$ is given by a (not necessarily minimal) Weierstrass equation \begin{equation}\label{eqn:weq} y^2 + a_1 xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6, \end{equation} and let $\omega = dx/(2y+a_1x + a_3)$. Let $x(t)$ be as in (\ref{eqn:xt}). Then the series \begin{equation}\label{eqn:wpx} \wp(t) = x(t) + \frac{a_1^2 + 4a_2}{12}\in\Q((t)) \end{equation} satisfies $(\wp')^2 = 4\wp^3 - g_2 \wp - g_3$. In \cite{mazur-tate:sigma} we find\footnote{There is a sign error in \cite{mazur-tate:sigma}.} that \begin{equation}\label{eqn:wpe2} x(t) + c = \wp(t) - \frac{1}{12}\cdot \E_2(E,\omega), \end{equation} where $\E_2(E,\omega)$ is the value of the Katz $p$-adic weight~$2$ Eisenstein series at $(E,\omega)$, and the equality is of elements of $\Q_p((t))$. Using the definition of $\wp(t)$ and solving for $c$, we find that \begin{equation}\label{eqn:ce2} c = \frac{a_1^2 + 4a_2}{12} - \frac{1}{12} \E_2(E,\omega). \end{equation} Thus computing $c$ is equivalent to computing the $p$-adic number $\E_2(E,\omega)$. Having computed~$c$ to some precision, we then solve for $\sigma$ in (\ref{eqn:sigmadef}) using Algorithm~\ref{alg:sigma} below. %It should now be crystal clear that the nub of the computation of %$h_p(P)$ is in computing the single number $\E_2(E,\omega)$. %There are two attitudes towards the computation of $\E_2$: %\begin{enumerate} %\item A surprisingly fast procedure for computing it ``one at a % time'', which will be explained in Part~\ref{part1} (in %particular, see Section~\ref{sec:e2cohom}). %\item Procedures that compute it ``all at once'' as a $p$-adic modular %form. In Part~\ref{part2}, we will provide evidence for thinking %that this is destined to be a rather slow undertaking. %\end{enumerate} \subsection{$p$-adic analogues of the Birch and Swinnerton-Dyer conjecture} One motivation for this paper is to provide tools for doing computations in support of $p$-adic analogues of the BSD conjectures (see \cite{mtt}), especially when $E/\Q$ has rank at least~$2$. %Substantial theoretical work has been done toward these conjectures, %which maybe be useful for getting information about Shafarevich-Tate %and Selmer groups of elliptic curves. For example, in \cite{pr:exp}, Perrin-Riou uses her results about the $p$-adic BSD conjecture in the supersingular case to prove that $\Sha(E/\Q)[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 \cite{mazur-rubin:large_selmer} have also obtained results %that could be viewed as fitting into this program. Another motivation for this work comes from the study of the fine structure of Selmer modules. Let $K$ be a number field and $\Lambda$ the $p$-adic integral group ring of the Galois group of the maximal ${\bf Z}_p$-power extension of $K$. Making use of fundamental results of Nekov{\'a}{\v{r}} \cite{nekovar:selmer} and of Greenberg \cite{MR1977007} one can construct (see \cite{mazur-rubin:large_selmer}) for certain elliptic curves defined over $K$, a skew-Hermitian matrix with coefficients in $\Lambda$ from which one can read off a free $\Lambda$-resolution of the canonical Selmer $\Lambda$-module of the elliptic curve in question over $K$. To compute the entries of this matrix modulo the square of the augmentation ideal in $\Lambda$ one must know {\it all} the $p$-adic height pairings of the elliptic curve over $K$. Fast algorithms for doing this provide us with an important first stage in the computation of free $\Lambda$-resolutions of Selmer $\Lambda$-modules. The paper \cite{bsdalg1} is about computational verification of the full Birch and Swinnerton-Dyer conjecture for specific elliptic curves~$E$. There are many cases in which the rank of~$E$ is~$1$ and the upper bound on $\#\Sha(E/\Q)$ coming from Kolyvagin's Euler system is divisible by a prime $p\geq 5$ that also divides a Tamagawa number. In such cases, theorems of Kolyvagin and Kato combined with explicit computation do not give a sufficiently sharp upper bound on $\#\Sha(E/\Q)$. However, it should be possible in these cases to compute $p$-adic heights and $p$-adic $L$-functions, and use results of Kato, Schneider, and others to obtain better bounds on $\#\Sha(E/\Q)$. Wuthrich and the second author (Stein) are writing a paper on this. \subsection{Sample computations} In Section~\ref{sec:sample} we illustrate our algorithms with curves of ranks $1, 2, 3, 4 \text{ and } 5$, and two twists of $X_0(11)$ of rank $2$. \vspace{2em} \noindent{\bf Acknowledgement:} It is a pleasure to thank Nick Katz for feedback that led to Section~\ref{sec:cohom}. We would also like to thank Mike Harrison for discussions about his implementation of Kedlaya's algorithm in Magma, Kiran Kedlaya for conversations about his algorithm, Christian Wuthrich for feedback about computing $p$-adic heights, Alan Lauder for discussions about computing $\E_2$ in families, and Fernando Gouvea for remarks about non-overconvergence of $\E_2$. We would also like to thank all of the above people for comments on early drafts of the paper. Finally, we thank Jean-Pierre Serre for the proof of Lemma~\ref{tate:lem6.6}. \part{Heights, $\sigma$-functions, and ${\bf E}_2$}\label{part1} \section{The Formulas } In this section we give formulas for the $p$-adic height pairing in terms of the $\sigma$ function. We have already done this over $\Q$ in Section~\ref{sec:intro}. Let $p$ be an (odd) prime number,~$K$ a number field, and~$E$ an elliptic curve over~$K$ with good ordinary reduction at all places of $K$ above $p$. For any non-archimedean place~$w$ of~$K$, let $k_w$ denote the residue class field at~$w$. \subsection{General global height pairings} By the {\it idele class ${\Q}_p$-vector space} of $K$ let us mean $$ I(K)={\Q}_p\otimes_{\Z}\left\{{\A}_K^*/\left(K^*\cdot \prod_{v \,\,\nmid\,\, p}{\cal O}_v^*\cdot {\rm C}\right)\right\}, $$ where ${\A}_K^*$ is the group of ideles of $K$, and $ {\rm C}$ denotes its connected component containing the identity. Class field theory gives us an identification $I(K) =\Gamma(K)\otimes_{{\Z}_p}{\Q}_p$, where $ \Gamma(K)$ is the Galois group of the maximal ${\Z}_p$-power extension of $K$. For every (nonarchimedean) place $v$ of $K$, there is a natural homomorphism $\iota_v: K_v^* \to I(K)$. %\edit{William: tthere are some bad breaks here, but I don't think it % is time to worry specifically about them, since there will surely be % further corrections and changings of the draft.} For $K$-rational points $\alpha, \beta \in E(K)$ we want to give explicit formulas for an element that we might call the ``universal" $p$-adic height pairing of~$\alpha$ and~$\beta$; denote it $(\alpha, \beta) \in I(K)$. If $\rho: I(K) \to {\Q}_p$ is any linear functional, then the {\em $\rho$-height pairing} is a symmetric bilinear pairing $$(\ ,\ )_{\rho}: E(K)\times E(K) \to {\Q}_p, $$ defined as the composition of the universal pairing with the linear functional~$\rho$: $$ (\alpha, \beta)_{\rho} =\rho(\alpha, \beta)\in {\Q}_p. $$ We define the {\em $\rho$-height} of a point $\alpha \in E(K)$ by: $$h_{\rho}(\alpha) = -{\frac{1}{2}} (\alpha, \alpha)_{\rho}\in {\Q}_p.$$ Of course, any such (nontrivial) linear functional $\rho$ uniquely determines a ${\Z}_p$-extension, and we sometimes refer to the $\rho$-height pairing in terms of this ${\Z}_p$-extension. E.g., if $\rho$ cuts out the cyclotomic ${\Z}_p$-extension, then the $\rho$-height pairing is a normalization of the {\it cyclotomic height pairing} that has, for the rational field, already been discussed in the introduction. If $K$ is quadratic imaginary, and $\rho$ is the anti-cyclotomic linear functional, meaning that it is the unique linear functional (up to normalization) that has the property that $\rho({\bar x}) = -\rho(x)$ where ${\bar x}$ is the complex conjugate of $x$, then we will be presently obtaining explicit formulas for this anti-cyclotomic height pairing. We will obtain a formula for $(\alpha, \beta) \in I(K)$ by defining, for every nonarchimedean place, $v$, of $K$ a ``local height pairing," $(\alpha, \beta)_v \in K_v^*$. These local pairings will be very sensitive to some auxiliary choices we make along the way, but for a fixed $\alpha$ and $\beta$ the local height pairings $(\alpha, \beta)_v$ will vanish for all but finitely many places~$v$; the global height is the sum of the local ones and will be independent of all the choices we have made. \subsection{Good representations} \label{sec:good_rep} Let $\alpha, \beta \in E(K)$. By a {\em good representation} of the pair $\alpha, \beta$ we mean that we are given a four-tuple of points $(P,Q,R,S)$ in $E(K)$ (or, perhaps, in $E(K')$ where $K'/K$ is a number field extension of $K$) such that \begin{itemize} \item $\alpha$ is the divisor class of the divisor $[P]-[Q]$ of $E$, and $\beta$ is the divisor class of the divisor $[R]-[S]$, \item $P,Q,R,S$ are four distinct points, \item for each $v \ | \ p$ all four points $P,Q,R,S$ specialize to the same point on the fiber at~$v$ of the N{\'e}ron model of $E$. \item at all places~$v$ of~$K$ the points $P,Q,R,S$ specialize to the same component of the fiber at~$v$ of the N{\'e}ron model of $E$. \end{itemize} We will show how to erase these special assumptions later, but for now, let us assume all this, fix a choice of a good representation, $P,Q,R,S$, of $(\alpha, \beta)$ as above, and give the formulas in this case. \subsection{Local height pairings when $v \mid p$} Let $\sigma_v$ be the canonical $p$-adic $\sigma$-function attached to the elliptic curve~$E$ over~$K_v$ given in Weierstrass form. We may view $\sigma_v$ as a mapping from $E_1(K_v)$ to $K_v^*$, where $E_1(K_v)$ is the kernel of the reduction map $E(K_v) \to E(k_v)$, and $E(k_v)$ denotes the group of points on the reduction of $E$ modulo $v$. Define $(\alpha, \beta)_v \in K_v^*$ by the formula, $$ (\alpha, \beta)_v= \frac{\sigma_v(P-R)\sigma_v(Q-S)}{\sigma_v(P-S) \sigma_v(Q-R)}\ \in\ K_v^*. $$ The dependence of $\sigma$ on the Weierstrass equation is through the differential $\omega = dx/(2y+a_1x+a_3)$, and $\sigma_{c\omega} =c\sigma_\omega$, so this depends upon the choice of $P, Q, R, S$, but does not depend on the choice of Weierstrass equation for~$E$. \subsection{ Local height pairings when $v \nmid p$} First let $x$ denote the ``$x$-coordinate" in some minimal Weierstrass model for~$A$ at~$v$. Define for a point $T$ in $E(K_v)$ the rational number $\lambda_v(T)$ to be {\it zero} if $x(T) \in {\cal O}_v$, and to be $-\frac{1}{2}v(x(T))$ if $x(T) \,\, {\not \in}\,\, {\cal O}_v$. Next, choose a uniformizer $\pi_v$ of $K_v$ and define: $$ {\tilde\sigma}_v(T) = \pi_v^{\lambda_v(T)}, $$ the square of which is in $K_v^*.$ We think of ${\tilde\sigma}_v$ as a rough replacement for $\sigma_v$ in the following sense. The $v$-adic valuation of ${\tilde\sigma}_v$ is the same as $v$-adic valuation of the $v$-adic sigma function (if such a function is definable at $v$) and therefore, even if $\sigma_v$ cannot be defined, ${\tilde\sigma}_v$ is a perfectly serviceable substitute at places~$v$ at which our $p$-adic idele class functionals $\rho$ are necessarily unramified, and therefore sensitive only to the $v$-adic valuation. For $v \nmid p$, put: $$ (\alpha, \beta)_v= \frac{{\tilde\sigma}_v(P-R){\tilde\sigma}_v(Q-S)}{{\tilde\sigma}_v(P-S) {\tilde\sigma}_v(Q-R)}. $$ The square of this is in $K_v^*$. However, note that $\pi_v^{\lambda_v(T)}$ really means $\sqrt{\pi_v}^{2\lambda_v(T)}$, for a fixed choice of $\sqrt{\pi_v}$ and that the definition of $(\alpha,\beta)_v$ is independent of the choice of square root and therefore that $(\alpha,\beta)_v$, not only its square, is in $K_v^*$. Our local height $(\alpha, \beta)_v$, depends upon the choice of $P,Q,R,S$ and of the uniformizer $\pi_v$. \subsection{How the local heights change, when we change our choice of divisors} Let $\beta \in E(K)$ be represented by both $[R]-[S]$ and $[R']-[S']$. Let $\alpha \in E(K)$ be represented by $[P]-[Q]$. Moreover let both four-tuples $P,Q,R,S$ and $P,Q,R',S'$ satisfy the {\it good representation} hypothesis described at the beginning of Section~\ref{sec:good_rep}. Since, by hypothesis, $[R]-[S]-[R']+[S']$ is linearly equivalent to zero, there is a rational function $f$ whose divisor of zeroes and poles is $$ (f) = [R]-[S]-[R']+[S']. $$ If~$v$ is a nonarchimedean place of $K$ define $(\alpha, \beta)_v$ to be as defined in the previous sections using the choice of four-tuple of points $P,Q,R,S$, (and of uniformizer $\pi_v$ when $v \nmid p$). Similarly, define $(\alpha, \beta)'_v$ to be as defined in the previous sections using the choice of four-tuple of points $P,Q,R',S'$, (and of uniformizer $\pi_v$ when $v \nmid p$). \begin{proposition} \begin{enumerate} \item If $v\ | \ p$ then $$ (\alpha, \beta)_v = \frac{f(P)}{f(Q)}\cdot (\alpha, \beta)'_v\ \in\ K_v^*. $$ \item If $v\ \nmid \ p$ then there is a unit $u$ in the ring of integers of $K_v$ such that $$ (\alpha, \beta)_v^2 = u\cdot \left(\frac{f(P)}{f(Q)}\cdot (\alpha, \beta)'_v\right)^2\ \in\ K_v^*. $$ \end{enumerate} \end{proposition} \subsection{ The global height pairing more generally} We can then form the sum of local terms to define the global height $$ (\alpha, \beta) =\ \ \ \frac{1}{2}\sum_v \iota_v((\alpha, \beta)_v^2)\ \in\ I(K). $$ This definition is independent of any of the (good representation) choices $P,Q,R,S$ and the $\pi_v$'s made. It is independent of the choice of $\pi_v$'s because the units in the ring of integers of $K_v$ is in the kernel of $\iota_v$ if $v\nmid p$. It is independent of the choice of $P,Q,R,S$ because by the previous proposition, a change (an allowable one, given our hypotheses) of $P,Q,R,S$ changes the value of $(\alpha, \beta)$ by a factor that is a principal idele, which is sent to zero in $I(K)$. What if, though, our choice of $P,Q,R,S$ does {\it not} have the property that~$\alpha$ and~$\beta$ reduce to the same point in the N{\'e}ron fiber at~$v$ for all $v \ | \ p$, or land in the same connected component on each fiber of the N{\'e}ron model? In this case the pair $\alpha, \beta$ do not have a {\it good representation}. But replacing $\alpha, \beta$ by $m\cdot \alpha,n\cdot \beta$ for sufficiently large positive integers $m,n$ we can guarantee that the pair $m\cdot \alpha, n\cdot \beta$ does possess a good representation, and obtain formulas for $(\alpha, \beta)$ by: $$ (\alpha, \beta)= \frac{1}{mn}(m\cdot \alpha, n\cdot \beta). $$ Note in passing that to compute the global height pairing $(\alpha,\alpha)$ for a nontorsion point $\alpha \in E(K)$ that specializes to $0$ in the N\'eron fiber at $v$ for all $v \ | \ p$, and that lives in the connected component containing the identity in all N\'eron fibers, we have quite a few natural choices of {\it good representations}. For example, for positive integers $m \ne n$, take $$P= (m+1)\cdot \alpha; \ Q = m\cdot \alpha;\ R= (n+1)\cdot \alpha; \ S = n\cdot \alpha.$$ Then for any $p$-adic idele class functional $\rho$ the global $\rho$-height pairing $(\alpha, \alpha)_{\rho}$ is given by \begin{align*} &\sum_{v\ | \ p} \rho_v\left\{\frac{ \sigma_v((m-n)\alpha)^2}{\sigma_v((m-n+1)\alpha)\cdot \sigma_v((m-n-1)\alpha)}\right\} \\ & \qquad\qquad\qquad + \sum_{v\ \nmid \ p} \rho_v \left\{\frac{{\tilde\sigma}_v((m-n)\alpha)^2}{{\tilde\sigma}_v((m-n+1)\alpha)\cdot {\tilde\sigma}_v((m-n-1)\alpha)}\right\}, \end{align*} which simplifies to $$ (2(m-n)^2- (m-n+1)^2 - (m-n-1)^2)\cdot \left\{ \sum_{v\ | \ p} \rho_v \sigma_v(\alpha) + \sum_{v\ \nmid \ p} \rho_v {\tilde\sigma_v}(\alpha)\right \}. $$ \edit{I added a subscript of $v$ to the right-most $\tilde{\sigma}$ in this formula.} Since $(2(m-n)^2- (m-n+1)^2 - (m-n-1)^2) = -2$ we have the formula $$h_{\rho}(\alpha) = -{\frac{1}{2}}(\alpha,\alpha)_{\rho}$$ quoted earlier. \subsection{ Formulas for the $\rho$-height}\label{sec:formulas_rhoheight} For each $v$, let $\sigma_v$ be the canonical $p$-adic $\sigma$-function of $E$ over $K_v$ given in Weierstrass form. Suppose $P\in E(K)$ is a (non-torsion) point that reduces to~$0$ in $E(k_v)$ for each $v\mid p$, and to the connected component of all special fibers of the N\'eron model of~$E$. Locally at each place~$w$ of~$K$, we have a denominator $d_w(P)$, well defined up to units. % \begin{remark} % The local denominator $d_w(P)$ is really nothing more than a % rough-and-ready substitute for an inverse of $\sigma_w(P)$ up to a % unit; it can be called upon to serve as such a thing even if we % cannot define $\sigma_w(P)$ precisely. This is what we use, then, % instead of the $\sigma$ function at places where we only are % interested in the $\sigma$ function up to a unit, i.e., where $\psi$ % is unramified. % \end{remark} % \edit{I'm worried about the $1/2$ in the definition of the % $\lambda$'s previously. We should make sure that the normalization % here is correct; and there as well (Barry); {\bf New note from % barry: } I'm no longer worried, and as it turned out---see % above-- there really should have been a $-{\frac{1}{2}}$ but % please check me; also, it is, pretty much, up to us to decide the % normalization of $h_{\rho}$ for this paper, since we are, I think, % defining everything precisely, and I suspect the literature has a % bunch of different normalizations, so of course we better have a % self-consistent normalization throughout, but also the ``best" % one. Is this a good one?} We have $$ h_{\rho}(P) = \sum_{v\ |\ p} \rho_v(\sigma_v(P)) - \sum_{w\,\,\nmid\,\, p}\rho_w(d_w(P)). $$ Note that $h_{\rho}$ is quadratic because of the quadratic property of $\sigma$ from (\ref{eqn:quad}), and the $h_{\rho}$-pairing is then visibly bilinear. See also property (\ref{eqn:bil}). %\edit{But maybe one should take a closer look and see %exactly where to insert the appropriate sentence so that it keeps %things clear. {\bf Barry:} this is as good a place as any for it.} \subsection{Cyclotomic $p$-adic heights} The idele class ${\Q}_p$-vector space $I({\Q})$ attached to ${\Q}$ is canonically isomorphic to ${\Q}_p\otimes {\Z}_p^*$. Composition of this canonical isomorphism with the mapping $1 \times{\frac{1}{p}}{\rm log}_p$ induces an isomorphism $$ \rho_{\text{cycl}}^{\Q}:I({\Q}) = {\Q}_p\otimes {\Z}_p^* \xrightarrow{\,\,\,\,\,\cong\,\,\,\,\,} {\Q}_p. $$ For $K$ any number field, consider the homomorphism on idele class ${\Q}_p$-vector spaces induced by the norm $N_{K/ {\Q}}:I(K) \to I({\Q})$, and define $$ \rho_{\text{cycl}}^K: I(K) \to {\Q}_p $$ as the composition $$ \rho_{\text{cycl}}^K = \rho_{\text{cycl}}^{\Q}\circ N_{K/ {\Q}}. $$ By the {\em cyclotomic height pairing} for an elliptic curve $E$ over $K$ (of good ordinary reduction at all places $v$ of $K$ above $p$) we mean the $\rho_\text{cycl}^K$-height pairing $E(K)\times E(K) \to {\Q}_p$. We put $$ h_p(P)= h_{\rho_{\text{cycl}}^K }(P) $$ for short. Here is an explicit formula for it. $$ h_p(P) = {\frac{1}{p}} \cdot \left(\sum_{v\mid p} \log_p(N_{K_v/\Q_p}(\sigma_v(P))) - \sum_{w\nmid p}\ord_w(d_w(P)) \cdot \log_p(\#k_w)\right). $$ %\edit{Over $\Q$ we normalized this by putting a factor of $1/p$ out % front. What do you want to put out front in the general case? %I'm guessing we want $1/p^{[K:\Q]}$, but could be wrong. Barry: I removed the $1/p^{\rm degree}$ factor here. It shouldn't be there.} If we assume that $P$ lies in a sufficiently small (finite index) subgroup of $E(K)$ (see \cite[Prop.~2]{wuthrich:heightfamily}), then there will be a global choice of denominator $d(P)$, and the formula simplifies to $$ h_p(P) = \frac{1}{p} \cdot \log_p\left( \prod_{v\mid p} N_{K_v/\Q_p}\left(\frac{\sigma_v(P)}{d(P)} \right) \right). $$ \subsection{Anti-cyclotomic $p$-adic heights} Let $K$ be a quadratic imaginary field in which $p$ splits as $(p) = \pi\cdot {\bar \pi}$. Suppose $\rho: \A_K^*/K^* \to \Z_p$ is a nontrivial {\em anti-cyclotomic} idele class character, meaning that if ${\bf c}: \A_K^*/K^* \to \A_K^*/K^*$ denotes the involution of the idele class group induced by complex conjugation $x\mapsto {\bar x}$ in $K$, then $\rho\cdot {\bf c} = -\rho$. Then the term $$ \sum_{v\ |\ p}\rho_v(\sigma_v(P))$$ in the formula for the $\rho$-height at the end of Section~\ref{sec:formulas_rhoheight} is just $$ \sum_{v\ |\ p} \rho_v(\sigma_v(P)) = \rho_{\pi}(\sigma_{\pi}(P)) - \rho_{\pi}(\sigma_{\pi}({\bar P})), $$ so we have the following formula for the $\rho$-height of $P$: $$ h_{\rho}(P)= \rho_{\pi}(\sigma_{\pi}(P)) - \rho_{\pi}(\sigma_{\pi}({\bar P})) - \sum_{w\,\,\nmid\,\, p}\rho_w(d_w(P)). $$ \begin{remark} The Galois equivariant property of the $p$-adic height pairing implies that if $P$ is a $\Q$-rational point, its anti-cyclotomic height is $0$. Specifically, let $K/k$ be any Galois extension of number fields, with Galois group $G = \Gal(K/k)$. Let $V=V(K)$ be the $\Q_p$-vector space (say) defined as $(G_K)^{\ab}\otimes {\Q}_p$, so that $V$ is naturally a $G$-representation space. Let~$E$ be an elliptic curve over $k$ and view the Mordell-Weil group $E(K)$ as equipped with its natural $G$-action. Then (if~$p$ is a good ordinary prime for $E$) we have the $p$-adic height pairing $$ \langle P, Q\rangle \in V, $$ for $P,Q \in E(K)$ and we have Galois equivariance, $$ \langle g\cdot P, g\cdot Q\rangle = g\cdot\langle P, Q\rangle, $$ for any $g$ in the Galois group. Put $k = {\bf Q}$, $K/k$ a quadratic imaginary field. Then $V$ is of dimension two, with $V = V^+ \oplus V^-$ each of the $V^\pm$ being of dimension one, with the action of complex conjugation, $g \in G$ on $V^\pm$ being given by the sign; so that $V^+$ corresponds to the cyclotomic ${\bf Z}_p$-extension and $V^-$ corresponds to the anticyclotomic ${\bf Z}_p$- extension. In the notation above, the anticyclotomic height of $P$ and $Q$ is just $\langle g\cdot P, g\cdot Q\rangle^-$ where the superscript $-$ means projection to $V^-$. Suppose that $P \in E({\bf Q})$, so that $g\cdot P = P$. Then we have by Galois equivariance $$\langle P, P\rangle^- = \langle g\cdot P, g\cdot P\rangle^-= - \langle P, P\rangle^-,$$ so $\langle P, P\rangle^- = 0$. More generally, the anticyclotomic height is zero as a pairing on either $E(K)^+\times E(K)^+$ or $E(K)^- \times E(K)^-$ and can only be nonzero on $E(K)^+\times E(K)^-$. If $E(K)$ is of odd rank, then the ranks of $E(K)^+$ and $E(K)^-$ must be different, which obliges the pairing on $E(K)^+\times E(K)^-$ to be either left-degenerate or right-degenerate (or, of course, degenerate on both sides). Rubin and the first author conjecture that it is nondegenerate on one side (the side, of course having smaller rank); for more details see, e.g., \cite[Conj.~11]{mazur-rubin:pairings_arith}. \end{remark} %\edit{Mazur: It is possible that in the quadratic imaginary situation the terms %(in the rho-height formula) involving the $d_w$'s can be more neatly % packaged? I haven't tried, but since it is SO neat in the cyclotomic % case, it may be worth a look here.} \section{The Algorithms}\label{sec:cohom} Fix an elliptic curve $E$ over $\Q$ and a good ordinary prime $p\geq 5$. In this section we discuss algorithms for computing the cyclotomic $p$-adic height of elements of $E(\Q)$. \subsection{Computing the $p$-adic $\sigma$-function} First we explicitly solve the differential equation (\ref{eqn:sigmadef}). Let $z(t)$ be the formal logarithm on $E$, which is given by $z(t) = \int \frac{\omega}{dt} = t + \cdots$ (here the symbol $\int$ means formal integration with $0$ constant term). There is a unique function $F(z)\in\Q((z))$ such that $t = F(z(t))$. Set $x(z) = x(F(z))$. Rewrite (\ref{eqn:sigmadef}) as \begin{equation}\label{eqn:sigmaz} x(z) + c = -\frac{d}{\omega}\left(\frac{d\log(\sigma)}{\omega}\right). \end{equation} A crucial observation is that $$ x(z)+c = \frac{1}{z^2} - \frac{a_1^2+4a_2}{12} + c + \cdots; $$ in particular, the coefficient of $1/z$ in the expansion of $g(z)=x(z)+c$ is~$0$. Since $z = \int (\omega/dt)$ we have $dz = (\omega/dt)dt = \omega$, hence $dz/\omega=1$, so \begin{equation}\label{eqn:inz} -\frac{d}{\omega}\left(\frac{d\log(\sigma)}{\omega}\right) = -\frac{dz}{\omega}\frac{d}{dz} \left( \frac{d \log(\sigma)}{\omega} \right) = -\frac{d}{dz} \left( \frac{d\log(\sigma)}{dz}\right). \end{equation} Write $\sigma(z) = z\sigma_0(z)$ where $\sigma_0(z)$ has nonzero constant term. Then \begin{equation}\label{eqn:inz2} -\frac{d}{dz} \left( \frac{d\log(\sigma)}{dz}\right) = \frac{1}{z^2} - \frac{d}{dz} \left( \frac{d\log(\sigma_0)}{dz}\right). \end{equation} Thus combining (\ref{eqn:sigmaz})--(\ref{eqn:inz2}) and changing sign gives $$ \frac{1}{z^2} - x(z) - c = \frac{d}{dz} \left( \frac{d\log(\sigma_0)}{dz}\right). $$ This is particularly nice, since $g(z) = \frac{1}{z^2} - x(z) - c \in \Q[[z]]$. We can thus solve for $\sigma_0(z)$ by formally integrating twice and exponentiating: $$ \sigma_0(z) = \exp\left(\int\int g(z) dz dz\right), $$ where we choose the constants in the double integral to be $0$, so $\int\int g = 0 + 0z + \cdots $. Using (\ref{eqn:wpe2}) we can rewrite $g(z)$ in terms of $e_2 = \E_2(E,\omega)$ and $\wp(z)$ as $$ g(z) = \frac{1}{z^2} -(x(z) + c) = \frac{1}{z^2} - \wp(z)+ \frac{e_2}{12}. $$ Combining everything and using that $\sigma(z) = z\sigma_0(z)$ yields $$ \sigma(z) = z \cdot \exp\left(\int\int \left(\frac{1}{z^2} - \wp(z) + \frac{e_2}{12} \right)dz dz\right), $$ Finally, to compute $\sigma(t)$ we compute $\sigma(z)$ and obtain $\sigma(t)$ as $\sigma(z(t))$. We formalize the resulting algorithm below. \begin{algorithm}{The Canonical $p$-adic Sigma Function}\label{alg:sigma} Given an elliptic curve~$E$ over~$\Q$, a good ordinary prime~$p$ for~$E$, and an approximation $e_2$ for $\E_2(E,\omega)$, this algorithm computes an approximation to $\sigma(t)\in\Z_p[[t]]$. \begin{steps} \item{}[Compute Formal Log]\label{alg:sigma1} Compute the formal logarithm $z(t)=t + \cdots \in \Q((t))$ using that \begin{equation}\label{eqn:formal_log} \ds z(t) = \int \frac{dx/dt}{2y(t)+a_1x(t) + a_3}, \qquad\text{(0 constant term)} \end{equation} where $x(t)=t/w(t)$ and $y(t)=-1/w(t)$ are the local expansions of~$x$ and~$y$ in terms of $t=-x/y$, and $w(t) = \sum_{n\geq 0} s_n t^n$ is given by the following explicit inductive formula (see, e.g., \cite[pg.~18]{bluher:formal}): $$ s_0 = s_1 = s_2 = 0, \qquad s_3 = 1, \qquad \text{and for $n\geq 4$,} $$ $$ s_n = a_1 s_{n-1} + a_2 s_{n-2} + a_3\sum_{i+j=n} s_i s_j + a_4 \sum_{i+j = n-1} s_i s_j + a_6 \sum_{i+j+k=n} s_i s_j s_k. $$ % in % \cite[Ch.~IV.1]{silverman:aec}.\footnote{Note that the formula for the % formal group addition on page 114 of \cite{silverman:aec} is % incorrect. In the numerator, the summand $-2a_4\lambda\nu - % 3a_6\lambda^2\nu$ should be replaced by $+2a_4\lambda\nu + % 3a_6\lambda^2\nu$.} \item{}[Reversion] Using a power series ``reversion'' (functional inverse) algorithm, find the unique power series $F(z)\in\Q[[z]]$ such that $t=F(z)$. Here $F$ is the reversion of $z$, which exists because $z(t) = t + \cdots$. \item{}[Compute $\wp$] Compute $\alpha(t) \set x(t) + (a_1^2 + 4a_2)/12 \in \Q[[t]]$, where the $a_i$ are as in (\ref{eqn:weq}). Then compute the series $\wp(z) = \alpha(F(z))\in \Q((z))$. \item{}[Compute $\sigma(z)$] Set $\ds g(z)\set \frac{1}{z^2} - \wp(z) + \frac{e_2}{12}\in\Q_p((z))$, % \edit{The theory suggests the last term should be $-e_2/12$ but the calculations do not % work unless I use $+e_2/12$. There are probably two % normalizations of $E_2$ in the references. GULP -- here we %need to be extra careful. William: I more convinced by Katz's %argument that his $\E_2$ is right than the one in Mazur-Tate.} and compute $$\ds \sigma(z) \set z\cdot \exp\left(\int \int g(z) dz dz\right) \in \Q_p[[z]].$$ \item{}[Compute $\sigma(t)$] Set $\sigma(t) \set \sigma(z(t))\in t\cdot \Z_p[[t]]$, where $z(t)$ is the formal logarithm computed in Step~\ref{alg:sigma1}. Output $\sigma(t)$ and terminate. \end{steps} \end{algorithm} %\begin{remark} % The trick of changing from $\wp(t)$ to $\wp(z)$ allows us to solve a % certain differential equation using just simple operations with % power series. %\end{remark} %\edit{Insert explanation of exactly how we used the formal %logarithm to transform a difficult differential equation %in terms of $t$ into an easy one. I learned this from %a paper or thesis of Wuthrich.} \subsection{Computing $\E_2(E,\omega)$ using cohomology} \label{sec:e2cohom} This section is about a fast method of computation of $\E_2(E,\omega)$ for individual ordinary elliptic curves, ``one at a time''. The key input is \cite[App.~2]{katz:padicprop} (see also \cite{katz:padic_interp}), which gives an interpretation of $\E_2(E,\omega)$ as the ``direction'' of the unit root eigenspace (cf. formula A.2.4.1 of \cite[App.~2]{katz:padicprop}) of Frobenius acting on the one-dimensional de Rham cohomology of $E$. Concretely, consider an elliptic curve~$E$ over $\Z_p$ with good ordinary reduction. Assume that $p\geq 5$. Fix a Weierstrass equation for~$E$ of the form $ y^2 = 4x^3 - g_2x - g_3, $ The differentials $\omega=dx/y$ and $\eta=xdx/y$ form a $\Z_p$-basis for the first $p$-adic de Rham cohomology group~$\H^1$ of~$E$, and we wish to compute the matrix~$F$ of absolute Frobenius with respect to this basis. Frobenius is $\Z_p$-linear, since we are working over $\Z_p$; if we were working over the Witt vectors of $\F_q$, then Frobenius would only be semi-linear. We explicitly calculate~$F$ (to a specified precision) using Kedlaya's algorithm, which makes use of Monsky-Washnitzer cohomology of the affine curve $E-\cO$. Kedlaya designed his algorithm for computation of zeta functions of hyperelliptic curves over finite fields. An intermediate step in Kedlaya's algorithm is computation of the matrix of absolute Frobenius on $p$-adic de Rham cohomology, via Monsky-Washnitzer cohomology. For more details see \cite{kedlaya:counting_mw} and \cite{kedlaya:counting-errata}. For recent formulations and applications of fast algorithms to compute Frobenius eigenvalues, see \cite{lauder-wan}. Now that we have computed $F$, we deduce $\E_2(E,\omega)$ as follows. The unit root subspace is a direct factor, call it~$U$, of $\H^1$, and we know that a complementary direct factor is the $\Z_p$ span of~$\omega$. We also know that $F(\omega)$ lies in $p\H^1$, and this tells us that, $\!\!\!\!\mod{p^n}$, the subspace~$U$ is the span of $F^n(\eta)$. Thus if for each~$n$, we write $ F^n(\eta) = a_n\omega + b_n\eta, $ then $b_n$ is a unit (congruent $\!\!\!\pmod{p}$ to the $n$th power of the Hasse invariant) and $\E_2(E,\omega) \con -12a_n/b_n \pmod{p^n}.$ Note that $a_n$ and $b_n$ are the entries of the second column of the matrix $F^n$. %In terms of speed of convergence, once we have $F$, we iterate %it~$n$ times to calculate $P \pmod{p^n}$. \begin{algorithm}{Evaluation of $\E_2(E,\omega)$}\label{alg:e2} Given an elliptic curve over~$\Q$ and a good ordinary prime~$p\geq 5$, this algorithm approximates $\E_2(E,\omega)\in \Z_p$ modulo $p^n$. \begin{steps} \item{}[Invariants] Let $c_4$ and $c_6$ be the $c$-invariants of a minimal model of~$E$. Set $$a_4\set -\frac{c_4}{2^4\cdot 3}\qquad\text{and}\qquad a_6 \set -\frac{c_6}{2^5\cdot 3^3}.$$ \item{}[Kedlaya] Apply Kedlaya's algorithm to the hyperelliptic curve $y^2=x^3 + a_4x + a_6$ (which is isomorphic to $E$) to obtain the matrix $F$ (modulo $p^n$) of the action of absolute Frobenius on the basis $$ \omega=\frac{dx}{y}, \qquad \eta=\frac{xdx}{y}. $$ We view $F$ as acting from the left. \item{}[Iterate Frobenius] Compute the second column $\vtwo{a}{b}$ of $F^n$, so $\Frob^n(\eta) = a\omega + b\eta$. \item{}[Finished] Output $-12a/b$ (which is a number modulo $p^n$, since~$b$ is a unit). \end{steps} \end{algorithm} \subsection{Computing $\E_2(E,\omega)$ using integrality} \label{sec:integrality} The algorithm in this section is more elementary than the one in Section~\ref{sec:e2cohom}, and is directly motivated by Theorem~\ref{thm:uniqde}. In practice it is very slow, except if~$p$ is small (e.g., $p=5$) and we only require $\E_2(E,\omega)$ to very low precision. Our guess is that it should be exponentially hard to compute a quantity using a log convergent series for it, and that this ``integrality'' method is essentially the same as using log convergent expansions. Let~$c$ be an indeterminate and in view of (\ref{eqn:ce2}), write $e_2 = -12c + a_1^2 + 4a_2 \in \Q[c]$. If we run Algorithm~\ref{alg:sigma} with this (formal) value of $e_2$, we obtain a series $\sigma(t,c) \in \Q[c][[t]]$. For each prime $p\geq 5$, Theorem~\ref{thm:uniqde} implies that there is a unique choice of $c_p\in \Z_p$ such that $\sigma(t,c_p) = t + \cdots \in t\Z_p[[t]]$ is odd. Upon fixing a prime~$p$, we compute the coefficients of $\sigma(t,c)$, which are polynomials in~$\Q[c]$; integrality of $\sigma(t,c_p)$ then imposes conditions that together must determine~$c_p$ up to some precision, which depends on the number of coefficients that we consider. Having computed~$c_p$ to some precision, we recover $\E_2(E,\omega)$ as $-12c_p + a_1^2 + 4a_2$. We formalize the above as an algorithm. \begin{algorithm}{Integrality}\label{alg:int} Given an elliptic curve over~$\Q$ and a good ordinary prime~$p\geq 5$, this algorithm approximates the associated $p$-adic $\sigma$-function. \begin{steps} \item{}[Formal Series] Use Algorithm~\ref{alg:sigma} with $e_2 = -12c + a_1^2 + 4a_2$ to compute $\sigma(t) \in \Q[c][[t]]$ to some precision. \item{}[Approximate $c_p$] Obtain constraints on $c$ using that the coefficients of $\sigma$ must be in $\Z_p$. These determine $c$ to some precision. (For more details see the example in Section~\ref{sec:ex-integrality}). \end{steps} \end{algorithm} \subsection{Computing cyclotomic $p$-adic heights} Finally we give an algorithm for computing the cyclotomic $p$-adic height $h_p(P)$ that combines Algorithm~\ref{alg:e2} with the discussion elsewhere in this paper. We have computed $\sigma$ and $h_p$ in numerous cases using the algorithm described below, and implementations of the ``integrality'' algorithm described above, and the results match. % We have also done %several computations of $h_p$ using other methods \edit{Tate's -- % explain}, and again the results match. \begin{algorithm}{The $p$-adic Height}\label{alg:padic_height} Given an elliptic curve~$E$ over $\Q$, a good ordinary prime~$p$, and a non-torsion element $P\in E(\Q)$, this algorithm approximates the $p$-adic height $h_p(P) \in \Q_p$. \begin{steps} \item{}[Prepare Point] Compute a positive integer~$m$ such that $mP$ reduces to $\cO\in E(\F_p)$ and to the connected component of $\mathcal{E}_{\F_\ell}$ at all bad primes $\ell$. For example,~$m$ could be the least common multiple of the Tamagawa numbers of $E$ and $\#E(\F_p)$. Set $Q\set mP$ and write $Q=(x,y)$. \item{}[Denominator] Let $d$ be the positive integer square root of the denominator of $x$. \item{}[Compute $\sigma$] Approximate $\sigma(t)$ using Algorithm~\ref{alg:sigma} together with either Algorithm~\ref{alg:e2} or Algorithm~\ref{alg:int}, and set $s \set \sigma(-x/y) \in \Q_p$. \item{}[Height] Compute $\ds h_p(Q) \set \frac{1}{p}\log_p\left(\frac{s}{d}\right)$, then $\ds h_p(P) \set \frac{1}{m^2} \cdot h_p(Q)$. Output $h_p(P)$ and terminate. \end{steps} \end{algorithm} \section{Sample Computations}\label{sec:sample} We did the calculations in this section using SAGE \cite{sage} and Magma \cite{magma}. In particular, SAGE includes an optimized implementation due to J. Balakrishnan, R. Bradshaw, D. Harvey, Y. Qiang, and W. Stein of our algorithm for computing $p$-adic heights for elliptic curves over $\Q$. This implementation includes further tricks, e.g., for series manipulation, which are not described in this paper. \subsection{The rank one curve of conductor $37$}\label{sec:ex-integrality} Let $E$ be the rank $1$ curve $y^2+y=x^3-x$ of conductor $37$. The point $P=(0,0)$ is a generator for $E(\Q)$. We illustrate the above algorithms in detail by computing the $p$-adic height of~$P$ for the good ordinary prime~$p=5$. The steps of Algorithm~\ref{alg:padic_height} are as follows: \begin{enumerate} \item{}[Prepare Point] The component group of $\cE_{\F_{37}}$ is trivial. The group $E(\F_{5})$ has order $8$ and the reduction of $P$ to $E(\F_{5})$ also has order~$8$, so let $$ Q=8P = \left(\frac{21}{25},\,\, -\frac{69}{125}\right). $$ \item{}[Denominator] We have $d=5$. \item{}[Compute $\sigma$] We illustrate computation of $\sigma(t)$ using both Algorithm~\ref{alg:e2} and Algorithm~\ref{alg:int}. \begin{enumerate} \item{}[Compute $\sigma(t,c)$] We use Algorithm~\ref{alg:sigma} with $e_2 = 12c - a_1^2 - 4a_2$ to compute~$\sigma$ as a series in~$t$ with coefficients polynomials in~$c$, as follows: \begin{enumerate} \item{}[Compute Formal Log] Using the recurrence, we find that \begin{align*} w(t) &=t^{3} + t^{6} - t^{7} + 2t^{9} - 4t^{10} + 2t^{11} + 5t^{12} - 5t^{13} + 5t^{14} + \cdots \end{align*} Thus \begin{align*} x(t) &= t^{-2} - t + t^{2} - t^{4} + 2t^{5} - t^{6} - 2t^{7} + 6t^{8} - 6t^{9} - 3t^{10} + \cdots \\ y(t) &= -t^{-3} + 1 - t + t^{3} - 2t^{4} + t^{5} + 2t^{6} - 6t^{7} + 6t^{8} + 3t^{9} + \cdots \end{align*} so integrating (\ref{eqn:formal_log}) we see that the formal logarithm is $$ z(t) = t + \frac{1}{2}t^{4} - \frac{2}{5}t^{5} + \frac{6}{7}t^{7} - \frac{3}{2}t^{8} + \frac{2}{3}t^{9} + 2t^{10} - \frac{60}{11}t^{11} + 5t^{12} + \cdots $$ \item{}[Reversion] Using reversion, we find $F$ with $F(z(t)) = t$: $$ F(z) = z - \frac{1}{2}z^{4} + \frac{2}{5}z^{5} + \frac{1}{7}z^{7} - \frac{3}{10}z^{8} + \frac{2}{15}z^{9} - \frac{1}{28}z^{10} + \frac{54}{385}z^{11} + \cdots $$ \item{}[Compute $\wp$] We have $a_1=a_2=0$, so $$ \alpha(t) = x(t) + (a_1^2 + 4a_2)/12 = x(t), $$ so $$ \wp(z) = x(F(z)) = z^{-2} + \frac{1}{5}z^{2} - \frac{1}{28}z^{4} + \frac{1}{75}z^{6} - \frac{3}{1540}z^{8} + \cdots %\frac{1943}{3822000}z^{10} + \cdots $$ Note that the coefficient of $z^{-1}$ is $0$ and all exponents are even. \item{}[Compute $\sigma(t,c)$] Noting again that $a_1=a_2 = 0$, we have \begin{align*} g(z,c) &= \frac{1}{z^2} - \wp(z) + \frac{12c-a_1^2 - 4a_2}{12}\\ &= c -\frac{1}{5}z^{2} + \frac{1}{28}z^{4} - \frac{1}{75}z^{6} + \frac{3}{1540}z^{8} - \frac{1943}{3822000}z^{10} + \cdots \end{align*} Formally integrating twice and exponentiating, we obtain \begin{align*} \sigma(z,c) &= z\cdot \exp\left(\int \int g(z,c) dz dz\right) \\ &= z\cdot \exp\Bigl( \frac{c}{2} \cdot z^2 -\frac{1}{60}z^{4} + \frac{1}{840}z^{6} - \frac{1}{4200}z^{8} + \frac{1}{46200}z^{10} \\ & \qquad - \frac{1943}{504504000}z^{12} + \cdots \Bigr)\\ &= z + \frac{1}{2}cz^{3} + \left(\frac{1}{8}c^2 - \frac{1}{60}\right)z^{5} + \left(\frac{1}{48}c^3 - \frac{1}{120}c + \frac{1}{840}\right)z^{7} +\\ & \qquad \left(\frac{1}{384}c^4 - \frac{1}{480}c^2 + \frac{1}{1680}c - \frac{1}{10080}\right)z^{9} + \cdots \end{align*} Finally, \begin{align*} \sigma(t) = \sigma(z(t)) &= t + \frac{1}{2}ct^{3} + \frac{1}{2}t^{4} + \left(\frac{1}{8}c^2 - \frac{5}{12}\right)t^{5} + \frac{3}{4}ct^{6} + \\ & \qquad \left(\frac{1}{48}c^3 - \frac{73}{120}c + \frac{103}{120}\right)t^{7} + \cdots \\ \end{align*} \end{enumerate} \item{}[Approximate] The first coefficient of $\sigma(t)$ that gives integrality information is the coefficient of $t^7$. Since $$ \frac{1}{48}c^3 - \frac{73}{120}c + \frac{103}{120} \in \Z_5, $$ multiplying by $5$ we see that $$ \frac{5}{48}c^3 - \frac{73}{24}c + \frac{103}{24} \con 0 \pmod{5}. $$ Thus $$ c \con \frac{103}{24} \cdot \frac{24}{73} \con 1 \pmod{5}. $$ The next useful coefficient is the coefficient of $t^{11}$, which is $$ \frac{1}{3840}c^5 - \frac{169}{2880}c^3 + \frac{5701}{6720}c^2 + \frac{127339}{100800}c - \frac{40111}{7200} $$ Multiplying by $25$, reducing coefficients, and using integrality yields the congruence $$ 10c^5 + 5c^3 + 20c^2 + 2c + 3\con 0 \pmod{25}. $$ Writing $c=1+5d$ and substituting gives the equation $10d+15 \con 0 \pmod{25}$, so $2d + 3 \con 0 \pmod{5}$. Thus $d \con 1 \pmod{5}$, hence $c = 1 + 5 + O(5^2)$. Repeating the procedure above with more terms, we next get new information from the coefficient of $t^{31}$, where we deduce that $c = 1 + 5 + 4\cdot 5^2 + O(5^3)$. \end{enumerate} \noindent{\bf Using Algorithm~\ref{alg:e2}:} Using Kedlaya's algorithm (as implemented in \cite{magma}) we find almost instantly that $$ \E_2(E,\omega) = 2 + 4\cdot5 + 2\cdot5^3 + 5^4 + 3\cdot5^5 + 2\cdot5^6 + 5^8 + 3\cdot5^9 + 4\cdot5^{10} + \cdots. $$ Thus $$ c = \frac{1}{12} \E_2(E,\omega) = 1 + 5 + 4\cdot5^2 + 5^3 + 5^4 + 5^6 + 4\cdot5^7 + 3\cdot5^8 + 2\cdot5^9 + 4\cdot 5^{10} + \cdots, $$ which is consistent with what we found above using integrality. \item{}[Height] For $Q=(x,y)=8(0,0)$ as above, we have $$ s = \sigma\left(-\frac{x}{y}\right) = \sigma\left(\frac{35}{23}\right) = 4\cdot 5 + 5^2 + 5^3 + 5^4 + \cdots, $$ so \begin{align*} h_5(Q) &= \frac{1}{5}\cdot \log_5\left(\frac{s}{5}\right) = \frac{1}{5}\cdot \log_5(4 + 5 + 5^2 + 5^3 + 2\cdot 5^5 + \cdots)\\ &= 3 + 5 + 2\cdot 5^3 + 3\cdot 5^4 + \cdots. \end{align*} Finally, $$ h_5(P) = \frac{1}{8^2} \cdot h_5(Q) = 2 + 4\cdot 5 + 5^2 + 2\cdot 5^3 + 2\cdot 5^4 + \cdots. $$ \end{enumerate} % Table~\ref{tab:37} lists the good ordinary primes with $5 < p<100$ % and the corresponding $p$-adic height (mod $p^3$) of $P$, where in each case % we used Algorithm~\ref{alg:e2} to compute~$\sigma$. % \begin{figure}[H] % \caption{The Rank $1$ Curve of Conductor $37$\label{tab:37}} % \begin{center} % \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline % $p$ & % 5& 7& 11& 13& 23& 29& 31& 41& 43& 47 & 53 \\\hline % $h_p(P)$ & 37 & 605& -218 & $-47\cdot 13^2$ & -3069& -9942&-333 & -12807 &-2982 &3684 & % $20869\cdot 53^{-2}$ \\\hline % \end{tabular} % \vspace{2ex} % \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}\hline % $p$ & % 59& 61& 67& 71& 73& 79& 83& 89& 97 \\\hline % $h_p(P)$ & -92910 & 27875 &$-1215\cdot 67$ &-30692 &-133761 & 42634 &2618 &-145804 % & -45277\\\hline % \end{tabular} % \end{center} % \end{figure} \begin{remark} A {\em very} good check to see whether or not any implementation of the algorithms in this paper is really correct, is just to make control experiments every once in a while, by computing $h(P)$ and then comparing it with $h(2P)/4$, $h(3P)/9$, etc. In particular, compute $h(P) - h(nP)/n^2 $ for several~$n$ and check that the result is $p$-adically small. We have done this in many cases for the implementation used to compute the tables in this section. \end{remark} \subsection{Curves of ranks $1$, $2$, $3$, $4$, and $5$} \subsubsection{Rank $1$} The first (ordered by conductor) curve of rank $1$ is the curve with Cremona label 37A, which we considered in Section~\ref{sec:ex-integrality} above. \begin{center} \begin{tabular}{|c|l|}\hline $p$ & $p$-adic regulator of {\bf 37A}\\ \hline 5 & $1 + 5 + 5^2 + 3\cdot5^5 + 4\cdot5^6 + O(5^7)$ \\\hline 7 & $1 + 7 + 3\cdot7^2 + 7^3 + 6\cdot7^4 + 2\cdot7^5 + 4\cdot7^6 + O(7^7)$ \\\hline 11 & $7 + 9\cdot11 + 7\cdot11^2 + 8\cdot11^3 + 9\cdot11^4 + 2\cdot11^5 + 7\cdot11^6 + O(11^7)$ \\\hline 13 & $12\cdot13 + 5\cdot13^2 + 9\cdot13^3 + 10\cdot13^4 + 4\cdot13^5 + 2\cdot13^6 + O(13^7)$ \\\hline 23 & $20 + 10\cdot23 + 18\cdot23^2 + 16\cdot23^3 + 13\cdot23^4 + 4\cdot23^5 + 15\cdot23^6 + O(23^7)$ \\\hline 29 & $19 + 4\cdot29 + 26\cdot29^2 + 2\cdot29^3 + 26\cdot29^4 + 26\cdot29^5 + 17\cdot29^6 + O(29^7)$ \\\hline 31 & $15 + 10\cdot31 + 13\cdot31^2 + 2\cdot31^3 + 24\cdot31^4 + 9\cdot31^5 + 8\cdot31^6 + O(31^7)$ \\\hline 41 & $30 + 2\cdot41 + 23\cdot41^2 + 15\cdot41^3 + 27\cdot41^4 + 8\cdot41^5 + 17\cdot41^6 + O(41^7)$ \\\hline 43 & $30 + 30\cdot43 + 22\cdot43^2 + 38\cdot43^3 + 11\cdot43^4 + 29\cdot43^5 + O(43^6)$ \\\hline 47 & $11 + 37\cdot47 + 27\cdot47^2 + 23\cdot47^3 + 22\cdot47^4 + 34\cdot47^5 + 3\cdot47^6 + O(47^7)$ \\\hline 53 & $26\cdot53^{-2} + 30\cdot53^{-1} + 20 + 47\cdot53 + 10\cdot53^2 + 32\cdot53^3 + O(53^4)$ \\\hline \end{tabular} \end{center} Note that when $p=53$ we have $\#E(\F_p)=p$, i.e., $p$ is anomalous. \subsection{Rank $2$} The first curve of rank $2$ is the curve 389A of conductor 389. The $p$-adic regulators of this curve are as follows: \begin{center} \begin{tabular}{|c|l|}\hline $p$ & $p$-adic regulator of {\bf 389A}\\ \hline 5 & $1 + 2\cdot5 + 2\cdot5^2 + 4\cdot5^3 + 3\cdot5^4 + 4\cdot5^5 + 3\cdot5^6 + O(5^7)$ \\\hline 7 & $6 + 3\cdot7^2 + 2\cdot7^3 + 6\cdot7^4 + 7^5 + 2\cdot7^6 + O(7^7)$ \\\hline 11 & $4 + 7\cdot11 + 6\cdot11^2 + 11^3 + 9\cdot11^4 + 10\cdot11^5 + 3\cdot11^6 + O(11^7)$ \\\hline 13 & $9 + 12\cdot13 + 10\cdot13^2 + 5\cdot13^3 + 5\cdot13^4 + 13^5 + 9\cdot13^6 + O(13^7)$ \\\hline 17 & $4 + 8\cdot17 + 15\cdot17^2 + 11\cdot17^3 + 13\cdot17^4 + 16\cdot17^5 + 6\cdot17^6 + O(17^7)$ \\\hline 19 & $3 + 5\cdot19 + 8\cdot19^2 + 16\cdot19^3 + 13\cdot19^4 + 14\cdot19^5 + 11\cdot19^6 + O(19^7)$ \\\hline 23 & $17 + 23 + 22\cdot23^2 + 16\cdot23^3 + 3\cdot23^4 + 15\cdot23^5 + O(23^7)$ \\\hline 29 & $9 + 14\cdot29 + 22\cdot29^2 + 29^3 + 22\cdot29^4 + 29^5 + 20\cdot29^6 + O(29^7)$ \\\hline 31 & $1 + 17\cdot31 + 4\cdot31^2 + 16\cdot31^3 + 18\cdot31^4 + 21\cdot31^5 + 8\cdot31^6 + O(31^7)$ \\\hline 37 & $28 + 37 + 11\cdot37^2 + 7\cdot37^3 + 3\cdot37^4 + 24\cdot37^5 + 17\cdot37^6 + O(37^7)$ \\\hline 41 & $20 + 26\cdot41 + 41^2 + 29\cdot41^3 + 38\cdot41^4 + 31\cdot41^5 + 23\cdot41^6 + O(41^7)$ \\\hline 43 & $40 + 25\cdot43 + 15\cdot43^2 + 18\cdot43^3 + 36\cdot43^4 + 35\cdot43^5 + O(43^6)$ \\\hline 47 & $25 + 24\cdot47 + 7\cdot47^2 + 11\cdot47^3 + 35\cdot47^4 + 3\cdot47^5 + 9\cdot47^6 + O(47^7)$ \\\hline \end{tabular} \end{center} \subsection{Rank $3$} The first curve of rank $3$ is the curve 5077A of conductor 5077. The $p$-adic regulators of this curve are as follows: \begin{center} \begin{tabular}{|c|l|}\hline $p$ & $p$-adic regulator of {\bf 5077A}\\ \hline 5 & $5^{-2} + 5^{-1} + 4 + 2\cdot5 + 2\cdot5^2 + 2\cdot5^3 + 4\cdot5^4 + 2\cdot5^5 + 5^6 + O(5^7)$ \\\hline 7 & $1 + 3\cdot7 + 3\cdot7^2 + 4\cdot7^3 + 4\cdot7^5 + O(7^7)$ \\\hline 11 & $6 + 11 + 5\cdot11^2 + 11^3 + 11^4 + 8\cdot11^5 + 3\cdot11^6 + O(11^7)$ \\\hline 13 & $2 + 6\cdot13 + 13^3 + 6\cdot13^4 + 13^5 + 4\cdot13^6 + O(13^7)$ \\\hline 17 & $11 + 15\cdot17 + 8\cdot17^2 + 16\cdot17^3 + 9\cdot17^4 + 5\cdot17^5 + 11\cdot17^6 + O(17^7)$ \\\hline 19 & $17 + 9\cdot19 + 10\cdot19^2 + 15\cdot19^3 + 6\cdot19^4 + 13\cdot19^5 + 17\cdot19^6 + O(19^7)$ \\\hline 23 & $7 + 17\cdot23 + 19\cdot23^3 + 21\cdot23^4 + 19\cdot23^5 + 22\cdot23^6 + O(23^7)$ \\\hline 29 & $8 + 16\cdot29 + 11\cdot29^2 + 20\cdot29^3 + 9\cdot29^4 + 8\cdot29^5 + 24\cdot29^6 + O(29^7)$ \\\hline 31 & $17 + 11\cdot31 + 28\cdot31^2 + 3\cdot31^3 + 17\cdot31^5 + 29\cdot31^6 + O(31^7)$ \\\hline 43 & $9 + 13\cdot43 + 15\cdot43^2 + 32\cdot43^3 + 28\cdot43^4 + 18\cdot43^5 + 3\cdot43^6 + O(43^7)$ \\\hline 47 & $29 + 3\cdot47 + 46\cdot47^2 + 4\cdot47^3 + 23\cdot47^4 + 25\cdot47^5 + 37\cdot47^6 + O(47^7)$ \\\hline \end{tabular} \end{center} For $p=5$ and $E$ the curve 5077A, we have $\#E(\F_5) = 10$, so $a_p\con 1\pmod{5}$, hence $p$ is anamolous. %\edit{William: Barry, is 5077A still considered anamolous at $5$ %even though we don't have $a_p=1$?} \subsection{Rank $4$} Next we consider the curve of rank $4$ with smallest known conductor ($234446 = 2\cdot 117223$): $$ y^2 + xy = x^3 - x^2 - 79x + 289. $$ Note that computation of the $p$-adic heights is just as fast for this curve as the above curves, i.e., our algorithm for computing heights is insensitive to the conductor, only the prime $p$ (of course, computing the Mordell-Weil group could take much longer if the conductor is large). \begin{center} \begin{tabular}{|c|l|}\hline $p$ & $p$-adic regulator of rank $4$ curve\\ \hline 5 & $2\cdot5^{-2} + 2\cdot5^{-1} + 3\cdot5 + 5^2 + 4\cdot5^3 + 4\cdot5^4 + 3\cdot5^5 + 3\cdot5^6 + O(5^7)$ \\\hline 7 & $6\cdot7 + 4\cdot7^2 + 5\cdot7^3 + 5\cdot7^5 + 3\cdot7^6 + O(7^7)$ \\\hline 11 & $5 + 10\cdot11 + 5\cdot11^2 + 11^3 + 3\cdot11^5 + 11^6 + O(11^7)$ \\\hline 13 & $12 + 2\cdot13 + 4\cdot13^2 + 10\cdot13^3 + 3\cdot13^4 + 5\cdot13^5 + 7\cdot13^6 + O(13^7)$ \\\hline 17 & $15 + 8\cdot17 + 13\cdot17^2 + 5\cdot17^3 + 13\cdot17^4 + 7\cdot17^5 + 14\cdot17^6 + O(17^7)$ \\\hline 19 & $14 + 16\cdot19 + 15\cdot19^2 + 6\cdot19^3 + 10\cdot19^4 + 7\cdot19^5 + 13\cdot19^6 + O(19^7)$ \\\hline 23 & $3 + 15\cdot23 + 15\cdot23^2 + 12\cdot23^4 + 20\cdot23^5 + 7\cdot23^6 + O(23^7)$ \\\hline 29 & $25 + 4\cdot29 + 18\cdot29^2 + 5\cdot29^3 + 27\cdot29^4 + 23\cdot29^5 + 27\cdot29^6 + O(29^7)$ \\\hline 31 & $21 + 26\cdot31 + 22\cdot31^2 + 25\cdot31^3 + 31^4 + 3\cdot31^5 + 14\cdot31^6 + O(31^7)$ \\\hline 37 & $34 + 14\cdot37 + 32\cdot37^2 + 25\cdot37^3 + 28\cdot37^4 + 36\cdot37^5 + O(37^6)$ \\\hline 41 & $33 + 38\cdot41 + 9\cdot41^2 + 35\cdot41^3 + 25\cdot41^4 + 15\cdot41^5 + 30\cdot41^6 + O(41^7)$ \\\hline 43 & $14 + 34\cdot43 + 12\cdot43^2 + 26\cdot43^3 + 32\cdot43^4 + 26\cdot43^5 + O(43^6)$ \\\hline 47 & $43 + 47 + 17\cdot47^2 + 28\cdot47^3 + 40\cdot47^4 + 6\cdot47^5 + 7\cdot47^6 + O(47^7)$ \\\hline \end{tabular} \end{center} \subsection{Rank $5$} Next we consider the curve of rank $5$ with smallest known conductor, which is the prime 19047851. The curve is $$ y^2 + y = x^3 - 79x + 342 $$ \begin{center} \begin{tabular}{|c|l|}\hline $p$ & $p$-adic regulator of rank $5$ curve\\ \hline 5 & $2\cdot5 + 5^2 + 5^3 + 2\cdot5^4 + 5^5 + 5^6 + O(5^7)$ \\\hline 7 & $2 + 6\cdot7 + 4\cdot7^2 + 3\cdot7^3 + 6\cdot7^4 + 2\cdot7^5 + 4\cdot7^6 + O(7^7)$ \\\hline 11 & $10 + 11 + 6\cdot11^2 + 2\cdot11^3 + 6\cdot11^4 + 7\cdot11^5 + 5\cdot11^6 + O(11^7)$ \\\hline 13 & $11 + 8\cdot13 + 3\cdot13^2 + 4\cdot13^3 + 10\cdot13^4 + 5\cdot13^5 + 6\cdot13^6 + O(13^7)$ \\\hline 17 & $4 + 11\cdot17 + 4\cdot17^2 + 5\cdot17^3 + 13\cdot17^4 + 5\cdot17^5 + 2\cdot17^6 + O(17^7)$ \\\hline 19 & $11 + 7\cdot19 + 11\cdot19^2 + 7\cdot19^3 + 9\cdot19^4 + 6\cdot19^5 + 10\cdot19^6 + O(19^7)$ \\\hline 23 & $14 + 14\cdot23 + 20\cdot23^2 + 6\cdot23^3 + 19\cdot23^4 + 9\cdot23^5 + 15\cdot23^6 + O(23^7)$ \\\hline 29 & $3 + 5\cdot29 + 20\cdot29^3 + 21\cdot29^4 + 18\cdot29^5 + 11\cdot29^6 + O(29^7)$ \\\hline 31 & $4 + 26\cdot31 + 11\cdot31^2 + 12\cdot31^3 + 3\cdot31^4 + 15\cdot31^5 + 22\cdot31^6 + O(31^7)$ \\\hline 37 & $3 + 20\cdot37 + 11\cdot37^2 + 17\cdot37^3 + 33\cdot37^4 + 5\cdot37^5 + O(37^7)$ \\\hline 41 & $3 + 41 + 35\cdot41^2 + 29\cdot41^3 + 22\cdot41^4 + 27\cdot41^5 + 25\cdot41^6 + O(41^7)$ \\\hline 43 & $35 + 41\cdot43 + 43^2 + 11\cdot43^3 + 32\cdot43^4 + 11\cdot43^5 + 18\cdot43^6 + O(43^7)$ \\\hline 47 & $25 + 39\cdot47 + 45\cdot47^2 + 25\cdot47^3 + 42\cdot47^4 + 13\cdot47^5 + O(47^6)$ \\\hline \end{tabular} \end{center} Note that the regulator for $p=5$ is not a unit, and $\#E(F_5)=9$. This is the only example of a regulator in our tables with positive valuation. %\begin{figure}[H]\caption{Twists of $X_0(11)$}\label{tbl:twists} %\begin{center} %\begin{tabular}{|c||c|c|c|c|c|c|} \hline % & 5 & 7 & 13 & 17 & 23 \\ \hline\hline %$-47$ & 241 & 48 & 8448 & 71282 & $23^{-2}\cdot 125405$ \\\hline %232 & 522 & 239 & 8966 & 57386 & 16874 \\ \hline %\end{tabular} %\end{center} %\end{figure} \part{Computing expansions for $\E_2$ in terms of classical modular forms}\label{part2} We next study convergence of $\E_2$ in the general context of $p$-adic and overconvergent modular forms. Coleman, Gouvea, and Jochnowitz prove in \cite{MR1317641} that $\E_2$ is {\em transcendental} over the ring of overconvergent modular forms, so $\E_2$ is certainly non-overconvergent. However, $\E_2$ is {\em log convergent} in a sense that we make precise in this part of the paper. %The questions of this section were %motivated by searching for a (slow) method of computation of $\E_2$, %which, however, works for every ordinary elliptic curve ``once and for %all.'' %More precisely, suppose $E_t$ is an elliptic curves over $\Q(t)$ with %invariant differential $\omega_t$. It would be interesting to obtain %a formula for $\E_2(E_t,\omega_t)$ as an element of $\Q_p((t))$. This %might shed light on the analytic behavior of the $p$-adic modular %form~$\E_2$. Note that Wuthrich \cite{wuthrich:heightfamily} has %studied the related problem of finding the height of a point $P_t$ on %$E_t$. \section{Questions about rates of convergence}\label{sec:logconvgen} Fix $p$ a prime number, which, in this section, we will assume is $\ge 5$. We only consider modular forms of positive even integral weight, on $\Gamma_0(M)$ for some~$M$, and with Fourier coefficients in $\C_p$. By a {\it classical modular form} we will mean one with these properties, and by a {\it Katz modular form} we mean a $p$-adic modular form in the sense of Katz (\cite{katz:padicprop}), again with these properties, i.e., of integral weight $k \ge 0$, of tame level~$N$ for a positive integer~$N$ prime to~$p$, and with Fourier coefficients in $\C_p$. A {\em $p$-integral modular form} is a modular form with Fourier coefficients in $\Z_p$. Note that throughout Sections~\ref{sec:logconvgen} and \ref{sec:preciselogconv}, all our modular forms can be taken to be with coefficients in~$\Q_p$. If~$f$ is a classical, or Katz, modular form, we will often simply identify the form~$f$ with its Fourier expansion, $f = \sum_{n \ge 0} c_f(n)q^n$. By $\ord_p(f)$ we mean the greatest lower bound of the non-negative integers $ {\rm ord}_p(c_f(n))$ for $n \ge 0$. The valuation $\ord_p$ on $\C_p$ here is given its natural normalization, i.e., $\ord_p(p) =1$. We say two $p$-integral modular forms are {\em congruent} modulo~$p^n$, denoted $$f \equiv g\ \pmod{p^n},$$ if their corresponding Fourier coefficients are congruent modulo $p^n$. Equivalently, $f \equiv g \pmod{p^n}$ if $\ord_p(f-g) \ge n$. Recall the traditional notation, $$ \sigma_{k-1}(n)=\sum_{0\,\, <\,\, d \ | \ n}d^{k-1}, $$ and put $\sigma(n)=\sigma_1(n)$. Let $E_k= -b_k/2k + \sum_{n=0}^{\infty}\sigma_{k-1}(n) q^n$ be the Eisenstein series of even weight $k \ge 2$, and denote by ${\cal E}_k$ the ``other natural normalization" of the Eisenstein series, $$ {\cal E}_k= 1 -\frac{2k}{b_k} \cdot \sum_{n=0}^{\infty}\sigma_{k-1}(n) q^n,$$ for $k \ge 2$. We have $${\cal E}_{p-1} \equiv 1 \pmod{p}. $$ (Note that ${\cal E}_k$ is the $q$-expansion of the Katz modular form that we denote by ${\bf E}_k$ elsewhere in this paper.) For $k > 2$ these are classical modular forms of level $1$, while the Fourier series $E_2= -1/24 + \sum_{n=0}^{\infty}\sigma(n) q^n$, and the corresponding ${\cal E}_2$, are not; nevertheless, they may all be viewed as Katz modular forms of tame level $1$. Put $$ \sigma^{(p)}(n)=\sum_{0 \,\,<\,\, d \ | \ n; \ (p,d)=1}d, $$ so that we have: \begin{equation}\label{eqn:logconv1} \sigma(n)= \sigma^{(p)}(n) + p\sigma^{(p)}(n/p) + p^2\sigma^{(p)}(n/p^2)+\cdots \end{equation} where the convention is that $\sigma^{(p)}(r)=0$ if $r$ is not an integer. Let $V = V_p$ be the operator on power series given by the rule: $$V\left(\sum _{n\ge 0}c_nq^n\right) = \ \sum _{n\ge 0}c_nq^{pn}.$$ If $F=\sum _{n\ge 0}c_nq^n$ is a classical modular form of weight $k$ on $\Gamma_0(M)$, then $V(F)$ is (the Fourier expansion of) a classical modular form of weight $k$ on $\Gamma_0(Mp)$ (cf. \cite[Ch. VIII]{lang:modular}). The Fourier series $$ E_2^{(p)}= (1-pV)E_2 = \frac{p-1}{24} + \sum \sigma_{1}^{(p)}(n)q^n $$ is, in contrast to $E_2$, a classical modular form (of weight~$2$ on $\Gamma_0(p)$) and we can invert the formula of its definition to give the following equality of Fourier series: \begin{equation}\label{eqn:logconv2} E_2 = \sum_{\nu \ge 0} p^{\nu}V^{\nu} E_2^{(p)}, \end{equation} this equality being, for the corresponding Fourier coefficients other than the constant terms, another way of phrasing (\ref{eqn:logconv1}). \begin{definition}[Convergence Rate]\label{defn:convrate} We call a function $\alpha(\nu)$ taking values that are either positive integers or $+\infty$ on integers $\nu = 0, \pm 1, \pm 2, \dots$ a {\em convergence rate} if $\alpha(\nu)$ is a non-decreasing function such that $\alpha(\nu) = 0$ for $ \nu \le 0$, $\alpha(\nu+\mu) \le \alpha(\nu) + \alpha(\mu)$, and $\alpha(\nu)$ tends to $+\infty$ as $\nu$ does. \end{definition} A simple nontrivial example of a convergence rate is $$ \alpha(\nu) = \begin{cases} 0 & \text{ for } \nu \leq 0,\\ \nu & \text{ for } \nu \geq 0. \end{cases} $$ If $\alpha(\nu)$ is a convergence rate, put $T\alpha(\nu) = \alpha(\nu-1)$; note that $T\alpha(\nu)$ is also a convergence rate ($T$ translates the graph of $\alpha$ one to the right). Given a collection $\{\alpha_j\}_{j \in J}$ of convergence rates, the ``max" function $\alpha(\nu)= {\rm max}_{j \in J}\ \alpha_j(\nu)$ is again a convergence rate. \begin{definition}[$\alpha$-Convergent] Let $\alpha$ be a convergence rate. A Katz modular form $f$ is $ \alpha$-{\em convergent} if there is a function $a:\Z_{\geq 0} \to \Z_{\geq 0}$ such that \begin{equation}\label{eqn:logconv3} f = \sum_{\nu=0}^{\infty} p^{a(\nu)}f_{\nu}{\cal E}_{p-1}^{-\nu} \end{equation} with $f_\nu$ a classical $p$-integral modular form (of weight $k+\nu(p-1)$ and level $N$) and $a(\nu) \ge \alpha(\nu)$ for all $\nu \ge 0$. \end{definition} If $ \alpha' \le \alpha$ are convergence rates and a modular form~$f$ is $\alpha$-{\em convergent} then it is also $\alpha'$-{\em convergent}. As formulated, an expansion of the shape of (\ref{eqn:logconv3}) for a given $f$ is not unique but \cite{katz:padicprop} and \cite{gouvea:slnm} make a certain sequence of choices that enable them to get canonical expansions of the type (\ref{eqn:logconv3}), dependent on those initial choices. Specifically, let $M_{\rm classical} (N, k, \Z_p)$ denote the $\Z_p$-module of classical modular forms on $\Gamma_0(N)$ of weight $k$ and with Fourier coefficients in $\Z_p$. Multiplication by ${\cal E}_{p-1}$ allows one to identify $M_{\rm classical} (N, k, \Z_p)$ with a saturated ${\Z}_p$-lattice in $M_{\rm classical} (N, k+p-1, \Z_p)$. (The lattice is saturated because multiplication by $E_{p-1} \!\!\!\pmod{p}$ is injective, since it is the identity map on $q$-expansions.) {\em Fix}, for each $k$, a $\Z_p$-module, $$ C(N, k+p-1, \Z_p)\subset M_{\rm classical} (N, k+p-1, \Z_p) $$ that is complementary to ${\cal E}_{p-1}\cdot M_{\rm classical} (N, k, \Z_p)\subset M_{\rm classical} (N, k+p-1, \Z_p)$. Requiring the classical modular forms $f_\nu$ of the expansion (\ref{eqn:logconv3}) to lie in these complementary submodules, i.e., $f_\nu \in C (N, k+\nu(p-1), \Z_p)$ for all~$\nu$, pins down the expansion uniquely. Let us call an expansion of the form $$f = \sum_{\nu=0}^{\infty} p^{a(\nu)}f_\nu{\cal E}_{p-1}^{-\nu}$$ pinned down by a choice of complementary submodules as described above a {\em Katz expansion} of $f$. A {\em classical} $p$-integral modular form is, of course, $ \alpha$-convergent for every $\alpha$. For any given convergence rate~$\alpha$, the $ \alpha$-convergent Katz modular forms of tame level $N$ are closed under multiplication, and the collection of them forms an algebra over the ring of classical modular forms of level $N$ (with Fourier coefficients in $\Z_p$). Any Katz $p$-integral modular form is $\alpha$-convergent, for some convergence rate~$\alpha$ (see~\cite{gouvea:slnm}). % .\edit{Why; I couldn't easily see this -- William. THis is given % very explicitly here, as I remember. But maybe we want a more % specific citation in this book?} \begin{proposition}\label{prop:convcong} A Katz $p$-integral modular form $f$ of weight $k$ and tame level $N$ as above is $\alpha$-convergent if and only if the Fourier series of $f{\cal E}_{p-1}^{\nu}$ is congruent to the Fourier series of a classical $p$-integral modular form (of weight $k + \nu(p-1)$ and level $N$) modulo $p^{\alpha(\nu+1)}$ for every integer $\nu \ge 0$. \end{proposition} \begin{proof} We use the $q$-expansion principle. Specifically, if $G_{\nu}$ is a classical modular form such that $f{\cal E}_{p-1}^{\nu}\equiv G_{\nu}\pmod{p^{\alpha(\nu+1)}}$ then $g_{\nu}= p^{-\alpha(\nu+1)}(f{\cal E}_{p-1}^{\nu}-G_{\nu})$ is again a Katz modular form, and we can produce the requisite $\alpha$-convergent Katz expansion by inductive consideration of these $g_{\nu}$'s. (Note that the other implication is trivial. Also note our running hypothesis that $p\geq 5$.) %\edit{*** We only proved <==. What about ==>. I think this other %direction is trivial by reducing both sides modulo $p^*$, {\em except} %possibly if $p=3$, since then we get $\cE_2$ appearing in first %of the sum. I guess we excluded $p\leq 3$ for our running hypothesis. %We might mention that this is a place where we use this exclusion. -- William} \end{proof} In view of this, we may define, for any $f$ as in Proposition~\ref{prop:convcong}, the function $a_f(\nu)$ (for $\nu \ge 0$) as follows: $a_f(0)=0$, and for $\nu \ge 1$, $a_f(\nu)$ is the largest integer $a$ such that $f{\cal E}_{p-1}^{\nu-1}$ is congruent to a classical $p$-integral modular form (of weight $k + (\nu-1)(p-1)$ and level $N$) modulo $p^a$. \begin{corollary} The Katz $p$-integral modular form $f$ is $\alpha$-convergent for any convergence rate~$\alpha$ that is majorized by the function $a_f$. (I.e., for which $\alpha(\nu) \leq a_f(\nu)$ for all $\nu\geq 0$.) \end{corollary} \begin{definition}[Overconvergent of Radius $r$] Let $r \in \Q$ be a positive rational number. A Katz $p$-integral modular form $f$ of tame level $N$ is {\em overconvergent of radius $r$} if and only if it is $\alpha$-convergent for some function $\alpha$ such that $\alpha(\nu) \ge r\cdot \nu $ for all $\nu$, and $\alpha(\nu)- r\cdot \nu$ tends to infinity with $\nu$. \end{definition} \begin{remarks} It is convenient to say, for two function $\alpha(\nu)$ and $\alpha'(\nu)$, that $$\alpha(\nu) \ggeq \alpha'(\nu)$$ if $\alpha(\nu) \ge \alpha'(\nu)$ and $\alpha(\nu) - \alpha'(\nu)$ tends to infinity with $\nu$. So, we may rephrase the above definition as saying that $f$ is overconvergent with radius $r$ if it is $\alpha$-convergent with $\alpha(\nu) \ggeq r\cdot \nu $. The above definition is equivalent to the definition of \cite{katz:padicprop, gouvea:slnm} except for the fact that the word {\em radius} in these references does not denote the rational number $r$ above, but rather a choice of $p$-adic number whose $\ord_p$ is $r$. We may think of our manner of phrasing the definition as being a {\em definition by Katz expansion convergence rate} as opposed to what one might call the {\em definition by rigid analytic geometric behavior}, meaning the equivalent, and standard, formulation (cf. \cite{katz:padicprop}) given by considering $f$ as a rigid analytic function on an appropriate extension of the Hasse domain in the (rigid analytic space associated to) $X_0(N)$. \end{remarks} \begin{definition}[(Precisely) Log Convergent]\label{defn:logconv} A Katz $p$-integral modular form $f$ is {\em log-convergent} if $c\cdot \log(\nu) \le a_f(\nu)$ for some positive constant $c$ and all but finitely many~$\nu$ (equivalently: if it is $\alpha$-convergent for $\alpha(\nu) = c\cdot \log(\nu)$ for some positive constant~$c$). We will say that $f$ is {\em precisely log-convergent} if there are positive constants $c, C$ such that $c\cdot \log(\nu) \le a_f(\nu) \le C\cdot \log(\nu)$ for all but finitely many~$\nu$. \end{definition} \begin{remark} As in Definition~\ref{defn:convrate} above, we may think of this manner of phrasing the definition as being a {\em definition by Katz expansion convergence rate}. This seems to us to be of some specific interest in connection with the algorithms that we present in this article for the computation of $\E_2$. For more theoretical concerns, however, we think it would be interesting to give, if possible, an equivalent {\em definition by rigid analytic geometric behavior}: is there some explicit behavior at the ``rim" of the Hasse domain that characterizes log-convergence? \end{remark} \begin{proposition}\label{prop:katzadmit} Let $p\geq 5$. Let~$f$ be a Katz $p$-integral modular form of weight~$k$ and tame level~$N$ that admits an expansion of the type $$f = \sum_{\nu=0}^{\infty} p^{\nu}{\cal F}_{\nu}{\cal E}_{p-1}^{-\nu}$$ where, for all $\nu \ge 0$, ${\cal F}_\nu$ is a classical $p$-integral modular form (of weight $k + \nu(p-1)$) on $\Gamma_0(p^{\nu+1})$. Then $f$ is log-convergent and $$\liminf_{n\to\infty} \frac{a_f(n)}{\log(n)} \geq \frac{1}{\log(p)}.$$ \end{proposition} \begin{proof} The classical modular form ${\cal F}_\nu$ on $\Gamma_0(p^{\nu+1})$ is an overconvergent Katz modular form of radius $r$ for any $r$ such that $r < {\frac{1}{p^{\nu-1}(p+1)}}$ (cf. \cite{katz:padicprop}, \cite[Cor.~II.2.8]{gouvea:slnm}). Let $${\cal F}_\nu = \sum_{\mu=0}^{\infty} f_{\mu}^{(\nu)}{\cal E}_{p-1}^{-\mu}$$ be its Katz expansion. So, $$\ord_p( f_{\mu}^{(\nu)}) \ggeq \left(\frac{1}{p^{\nu-1}(p+1)} -\epsilon_{\mu, \nu}\right)\cdot \mu$$ for any choice of positive $\epsilon_{\mu, \nu}$. We have $$f = \sum_{\nu=0}^{\infty} p^{\nu}\sum_{\mu=0}^{\infty} f_{\mu}^{(\nu)}{\cal E}_{p-1}^{-(\mu+\nu)},$$ or (substituting $\gamma = \mu + \nu$) $$ f = \sum_{\gamma =0}^{\infty} \left\{\sum_{\nu=0}^{\gamma} p^{\nu}\ f_{\gamma-\nu}^{(\nu)}\right\}{\cal E}_{p-1}^{-\gamma}. $$ Putting $G_{\gamma} = \sum_{\nu=0}^{\gamma} p^{\nu}\ f_{\gamma-\nu}^{(\nu)}$ we may write the above expansion as $$f = \sum_{\gamma =0}^{\infty} G_{\gamma}{\cal E}_{p-1}^{-\gamma},$$ and we must show that $$\ord_p (G_{\gamma}) \ge c\cdot {\rm log}(\gamma)$$ for some positive constant $c$. For any $\nu \le \gamma$ we have $$ \ord_p \left( p^{\nu}\ f_{\gamma-\nu}^{(\nu)}\right) \ggeq \nu + \left(\frac{1}{p^{\nu-1}(p+1)} -\epsilon_{\gamma-\nu, \nu}\right)(\gamma-\nu). $$ We need to find a lower bound for the minimum value achieved by the right-hand side of this equation. To prepare for this, first note that at the extreme value $\nu =0$ we compute $\ord_p (\ f_{\gamma}^{(0)}) \ge \left(\frac{p}{(p+1)} -\epsilon_{\gamma, 0}\right)\cdot \gamma$, and to study the remaining cases, $\nu =1,\dots, \gamma$, we look at the function $$R(t)= t + \left(\frac{1}{p^{t-1}(p+1)}\right)(\gamma-t)$$ in the range $1\le t \le \gamma$. This, by calculus, has a unique minimum at $t = t_\gamma \in (1, \gamma)$ given by the equation \begin{equation}\label{eqn:logconv4} \frac{p+1}{p}\cdot p^{t_\gamma} = \log(p)\cdot (\gamma - t_\gamma) +1. \end{equation} Define $e_{\gamma} = t_{\gamma}- \log_p (\gamma)$ and substituting, we get: \begin{equation} p^{e_\gamma} = \frac{p\log(p)}{p+1} - \frac{p\log(p)}{p+1} \frac{e_{\gamma}}{\gamma} +A_{\gamma} \end{equation} where $A_{\gamma}$ goes to zero, as $\gamma$ goes to $\infty$. If $e_\gamma$ is positive we get that $$ p^{e_\gamma} \le \frac{p\log(p)}{p+1} +A_{\gamma}$$ and so $e_\gamma$ is bounded from above, independent of $\gamma$, while if $e_{\gamma} = -d_{\gamma} $ with $d_\gamma$ positive, we have $$ \frac {1}{p^{d_\gamma}} = \frac{p\log(p)}{p+1} + \frac{p\log(p)}{p+1} \frac{d_{\gamma}}{\gamma} +A_{\gamma}.$$ Recall that since $t_\gamma > 0$ we also have $d_\gamma < \log_p(\gamma)$, so that the right hand side of the displayed equation tends to $\frac{p\log(p)}{p+1}$ as $\gamma$ goes to~$\infty$, so the equation forces~$d_\gamma$ to be bounded from above, as $\gamma$ tends to~$\infty$. This discussion gives: \begin{lemma} \label{tate:lem6.4} The quantity $|t_\gamma-\log_p(\gamma)|$ is bounded independent of $\gamma$. \end{lemma} Substituting $t_{\gamma} = \log_p(\gamma) + e_{\gamma}$ in the defining equation for $R(t)$ and noting the boundedness of $|e_{\gamma}|$, we get that $|R(t_{\gamma})-\log_p(\gamma)|$ is bounded as $\gamma$ goes to~$\infty$, thereby establishing our proposition. \end{proof} %\begin{remark} % The ``$c$" of Definition~\ref{defn:logconv} can be taken to be any % positive number $< {\rm log}(p)$. %\end{remark} \begin{corollary}\label{cor:katzlc} For all $p\geq 5$, the Katz modular form $f=E_2$ is log-convergent and $$ \liminf_{n\to\infty} \frac{a_f(n)}{\log(n)} \ge \frac{1}{\log(p)}. $$ \end{corollary} \begin{proof} The modular forms $V^{\nu}E_2^{(p)}$ are classical modular forms on $\Gamma_0(p^{\nu+1})$ and therefore formula (\ref{eqn:logconv1}) exhibits $E_2$ as having a Katz expansion of the shape of (\ref{eqn:logconv3}). Proposition~\ref{prop:katzadmit} then implies the corollary. \end{proof} \begin{remark}\label{rem:precise} Is $E_2$ {\em precisely} log-convergent? The minimal $c$ (cf. Definition~\ref{defn:logconv}) that can be taken in the $\log$-convergence rate for $f=E_2$ is $\limsup_{n\to \infty}(a_f(n)/\log(n))$. Is this minimal $c$ equal to $1/\log(p)$? It is for $p=5$, as we will show in Section~\ref{sec:preciselogconv}. The previous discussion tells us that, as a kind of generalization of the well-known congruence $$ E_2{\cal E}_{p-1} \equiv E_{p+1}\pmod{p}, $$ we have that for any $\epsilon > 0$, and all but finitely many $\nu$, there are classical modular forms ${\cal G}_{\nu}$ of level $1$ and weight $2+\nu(p-1)$ such that $$E_2{\cal E}_{p-1}^{\nu} \equiv {\cal G}_{\nu} \pmod{p^{\lfloor(1-\epsilon){\rm log}_p(\nu)\rfloor}} .$$ \end{remark} Let $\theta = qd/dq$ denote the standard shift operator; so that if $f = \sum_{n\ge 0}c_nq^n$, then $\theta(f )= \sum_{n\ge 0}nc_nq^n$. We have $\ord_p(\theta (f)) \ge \ord_p(f)$. The operator $\theta$ preserves Katz modular forms, and {\em almost} preserves classical modular forms in the sense that if $f$ is a classical modular form of weight $k \ge 2$ then so is $F=\theta(f) -kfE_2/12$ (cf.~\cite{katz:padicprop}). Note, also, that $\ord_p(F) \ge \ord_p(f)$. \begin{corollary} The operator $\theta$ preserves log-convergent Katz modular forms. \end{corollary} \begin{proof} Let $f$ be a log-convergent Katz $p$-integral modular form of weight $k$, of tame conductor~$N$ with a Katz expansion, \begin{equation}\label{eqn:logconv5} f = \sum_{\nu=0}^{\infty} p^{a(\nu)}f_{\nu}{\cal E}_{p-1}^{-\nu} \end{equation} where $a(\nu) \ge c\cdot {\rm log}(\nu)$ for some positive $c$, and the $f_{\nu}$'s are classical $p$-integral modular forms on $\Gamma_0(N)$. Let $F_{\nu}= \theta(f_{\nu}) -(k+ \nu(p-1))f_{\nu}E_2/12$ (which is a classical modular form of weight $k+2+ \nu(p-1)$ on $\Gamma_0(N)$). Put $$ G= \theta(E_{p-1}) - \frac{p-1}{12} {\cal E}_{p-1}E_2. $$ Apply the derivation $\theta$ to (\ref{eqn:logconv5}) to get \begin{align*} \theta(f) &= \sum_{\nu=0}^{\infty} p^{a(\nu)}\Bigl\{(F_{\nu}+(k+ \nu(p-1))f_{\nu}E_2/12) {\cal E}_{p-1}^{-\nu} - \\ & \qquad\qquad \qquad\qquad \qquad \nu f_{\nu}{\cal E}_{p-1}^{-\nu-1}\left(G+ \frac{p-1}{12} {\cal E}_{p-1}E_2\right) \Bigr\}. \end{align*} or: $$ \theta(f) = A + BE_2 - C - DE_2,$$ where \begin{align*} A&=\sum_{\nu=0}^{\infty} p^{a(\nu)}F_{\nu}{\cal E}_{p-1}^{-\nu},\\ B&= \sum_{\nu=0}^{\infty} p^{a(\nu)}(k+ \nu(p-1))f_{\nu}/12) {\cal E}_{p-1}^{-\nu},\\ C&= \sum_{\nu=0}^{\infty} p^{a(\nu)}\nu f_{\nu}G {\cal E}_{p-1}^{-\nu-1},\\ D&= \sum_{\nu=0}^{\infty} p^{a(\nu)}\frac{p-1}{12}\nu f_{\nu}{\cal E}_{p-1}. \end{align*} Now $A,B, C,D$ are all log-convergent, as is $E_2$ by Corollary~\ref{cor:katzlc}. Therefore so is $ \theta(f) $. \end{proof} \section{Precise log convergence of $E_2$ for $p=2,3,5$}\label{sec:preciselogconv} In this section we assume $p=2$, $3$ or $5$ and let $P, Q, R$ denote the Eisenstein series of level 1 of weights $2, 4, 6$, respectively, normalized so that the constant term in its Fourier expansion is 1. Let~$f$ be a Katz form of tame level~1 and weight~$k$. Write $k=4d+6e$, with~$d$ an integer $\ge -1$ and $e=0$ or~$1$. Then $fQ^{-d}R^{-e}$ is a Katz form of weight~$0$, that is, a Katz function. Since~$0$ is the only supersingular value of $j$ for $p=2,3,5$, a Katz function has an expansion in powers of $j^{-1}$ convergent everywhere on the disc $|j^{-1}| \le 1$. Hence, putting $z=j^{-1}$, we can write $$ f = Q^dR^e \sum_{n=0}^\infty c_f(n)z^n = \sum_{n=0}^\infty R^e\Delta^nQ^{-3n+d}. $$ with $c_f(n) \in \Q_p$ and $c_f(n) \to 0$ as $ n\to \infty$. Let $$C_{f,p}(N) = \min_{n>N}(\ord_p(c_f(n))).$$ \begin{theorem}\label{tate:thm6.1} For $p=5$, we have $C_{f,5}(N) = a_f(3N+1-d)$, for all large~$N$. \end{theorem} \begin{proof} Notice that for $p=5$, ${\cal E}_{p-1}=Q$. Let $\nu=3N+1-d$ for large $N$. Then $$ Q^{\nu-1} f = \sum_{n=0}^N c(n) R^e \Delta^n Q^{3(N-n)} + R^eQ^d\sum_{n>N}c(n)z^n =F+G, $$ say. We have $\ord_5(G)=\min_{n>N} (\ord_5(c(n))=C_{f,5}(N)$. \footnote{To justify this claim we extend our definition of $\ord_p$ from the ring of Katz forms with Fourier coefficients in~$\Z$ to the ring $\Z_p[[q]]$ of all formal power series with coefficients in~$\Z$. Moreover, since $z \in q+q^2\Z_p[[q]]$, we have $\Z_p[[q]]=\Z_p[[z]]$, and for a formal series $g=\sum a_nq^n = \sum b^nz^n$, we have $\ord_p(g) =\min(\ord_p(a_n))=\min(\ord_p(b_n))$. Also (Gauss Lemma) the rule $\ord(g_1g_2)=\ord(g_1)+\ord(g_2)$ holds. Since $\ord_5(R)=\ord_5(Q)=0$, it follows that $\ord_5(G)=C_{f,5}(N)$ as claimed.} Since $F$ is a classical modular form of weight $12N+6e$ it follows from the definition of $a_f$ that $a_f(\nu) \ge C_{f,5}(N)$. On the other hand, since $\{R^e\Delta^nQ^{3(N-n)} : 0\le n\le N\}$ is a basis for the space of classical modular forms of weight $12N+6e$, it is clear that for any such classical form $F'$, the difference $Q^{\nu-1}f-F'$ is a 5-adic Katz form which can be written as $R^eQ^{3N}g$ with $g$ a Katz function whose $z$-expansion coefficients are $c(n)$ for $n>N$. Thus $\ord_5(Q^{\nu-1}f-F')\le C_{f,5}(N)$. \end{proof} We have defined $f$ to be log convergent if $$ \liminf_{n\to\infty}\frac{a_f(n)}{\log(n)}>0, $$ and to be precisely log convergent if in addition $$ \limsup_{n\to\infty}\frac{a_f(n)}{\log(n)}< \infty. $$ \begin{lemma}\label{tate:lem6.2} Suppose $h(n)$ and $H(n)$ are nondecreasing funcions defined for all sufficiently large positive integers $n$. If for some integers $r>0$ and $s$ we have $H(N)=h(rN+s)$ for all sufficiently large integers N, then $$ \liminf_{n\to\infty}\frac{h(n)}{\log(n)} =\liminf_{N\to\infty}\frac{H(N)}{\log(N)}, $$ and $$ \limsup_{n\to\infty}\frac{h(n)}{\log(n)} =\limsup_{N\to\infty}\frac{H(N)}{\log(N)}. $$ \end{lemma} \begin{proof} We use the fact that $\frac{\log(rx+s)}{\log(x)} \to 1$ as $x\to \infty.$ For $n$ and $N$ related by $$ rN+s \le n \le r(N+1)+s $$ we have $$ \frac{h(n)}{\log(n)} \le \frac{h(r(N+1)+s}{\log(rN+s)} =\frac{H(N+1)}{\log(N+1)} \cdot \frac{\log(N+1)}{\log(rN+s)}. $$ Similarly, $$ \frac{h(n)}{\log(n)} \ge \frac{h(rN+s}{\log(r(N+1)+s)} =\frac{H(N)}{\log(N)} \cdot \frac{\log(N)}{\log(r(N+1)+s)}. $$ This proves the lemma, because the second factor of the right hand term in each line approaches 1 as $N$ goes to infinity. \end{proof} Theorem~\ref{tate:thm6.1} and Lemma~\ref{tate:lem6.2} show that for $p=5$ we can replace $a_f$ by $C_f$ in the definition of log convergent and precisely log convergent. Therefore we define log convergent and precisely log convergent for $p=2$ and $p=3$ by using $C_{f,p}$ as a replacement for $a_f$. \begin{theorem}\label{tate:thm6.3} For $p=2, 3\text{ or }5$, the weight 2 Eisenstein series $P=\E_2$ is precisely log convergent. In fact, $$ \lim_{n\to\infty} \frac{C_{P,p}(n)}{\log(n)} = \frac{1}{\log(p)}.$$ %\edit{BARRY (asked by John): % Does Remark~\ref{rem:precise} imply % that for $f=P$ that $\limsup$ is $\ge 1/\log(p)$, so that this % theorem can be improved and simplified to % simply: $\lim_{n \to \infty} (C_{P,p}(n)/log(n) = 1/log(p)$ for % $p= 2,3$, AND 5? In particular, can we replace the %$\le$ by an $=$ in the final limit of the theorem?} \end{theorem} During the proof of this theorem we write $c(n)=c_P(n)$ and $C_p(n)=C_{P,p}$. The cases $p=2, 3$ follow immediately from results of Koblitz (cf. \cite{koblitz}). Koblitz writes $ P=\sum a_nj^{-n}\frac{qdj}{jdq}$. Since $dj/j=-dz/z$, and as we will see later in this proof, $qdz/zdq=R/Q$, Koblitz's $a_n$ is the negative of our $c(n)$, hence $\ord_p(c(n))=\ord_p(a_n)$. Koblitz shows that if we let $l_p(n) = 1 + \lfloor \log(n)/\log(p) \rfloor$, the number of digits in the expression of $n$ in base $p$, and let $s_p(n)$ denote the sum of those digits, then $\ord_2(c(n))=l_2(n)+3s_2(n)$ and $\ord_3(c(n))=l_3(n)+s_3(n)$. From this it is an easy exercise to show $$ C_2(n)=\lfloor \log(n+1)/\log(2)\rfloor +4 \quad\text{ and }\quad C_3(n)=\lfloor(\log(n+1)/\log(3)\rfloor + 2, $$ formulas from which cases $p=2$ and $p=3$ of the theorem are evident. Investigating the case $p=5$ we found experimentally with a PARI program that the following conjecture holds for $n<1029$. \begin{conjecture}\label{tate:conj6.4} We have $\ord_5(c(n))\ge l_5(2n)$, with equality if $n$ written in base 5 contains only the digits 0,1 or 2, but no 3 or 4. \end{conjecture} It is easy to see that Conjecture~\ref{tate:conj6.4} implies that $$ \limsup_{n\to\infty} \frac{C_5(n)}{\log(n)} = \frac{1}{\log(5)}. $$ We already know from Corollary~\ref{cor:katzlc} that $$ \liminf_{n\to\infty} \frac{a_P(n)}{\log(n)} \ge \frac{1}{\log(5)}. $$ By Lemma~\ref{tate:lem6.2}, this is equivalent to $$ \liminf_{n\to\infty} \frac{C_{P,5}(n)}{\log(n)} \ge \frac{1}{\log(5)}. $$ Hence to finish the proof of Theorem~\ref{tate:thm6.3}, we need only prove \begin{equation}\label{eqn:thm6.3eq} \limsup_{n\to\infty} \frac{C_{P,5}(n)}{\log(n)} \le \frac{1}{\log(5)}. \end{equation} To prove (\ref{eqn:thm6.3eq}) it is enough to prove that Conjecture~\ref{tate:conj6.4} holds for $n=5^m$, that is, $\ord_5(c(n))=m+1$. Indeed that equality implies that $C_5(n)\le m+1$ for $n<5^m$ and, choosing $m$ such that $5^{m-1}\le n < 5^m$, shows that for every $n$ we have $C_5(n) \le m+1 \le \log(n)/\log(5) +2$. To prove $\ord_5(c(n))=m+1$ we use two lemmas. \begin{lemma}\label{tate:lem6.5} We have $\frac{PQ}{R}-1=3\frac{zdQ}{Qdz}.$ \end{lemma} \begin{proof} Let $\theta$ denote the classical operator $qd/dq$. From the formula $\Delta = q\prod_{n\geq 1}(1-q^n)^{24}$ we get by logarithmic differentiation the classical formula $$\frac{\theta\Delta}{\Delta} = P.$$ From $z = 1/j = \Delta/Q^3$ we get by logarithmic differentiation that $$\frac{\theta z}{z} = \frac{\theta\Delta}{\Delta} - 3\frac{\theta Q}{Q} = P - 3\frac{\theta Q}{Q}.$$ By a formula of Ramanujan (cf. \cite[Thm.~4]{jps}) we have $$ 3\frac{\theta Q}{Q} = P - \frac{R}{Q}. $$ Substituting gives $$ \frac{\theta z}{z} = \frac{R}{Q}, $$ and dividing the next to last equation by the last proves the lemma. \end{proof} \begin{lemma}\label{tate:lem6.6} Let $F=\sum_{n\ge 1} \sigma_3(n)q^n$, so that $Q=1+240F$. Then $F\equiv \sum_{m\ge 0} (z^{5^m}+ z^{2\cdot 5^m}) \pmod 5$. \end{lemma} \begin{proof} Guessing this result by computer experiment, we asked Serre for a proof. He immediately supplied two, one of which is the following. During the rest of this proof all congruences are understood to be modulo 5. Since $F=z+3z^2+\cdots$, the statement to be proved is equivalent to $F-F^5 \equiv z+3z^2$. Using the trivial congruence $Q\equiv 1$ and the congruence $P\equiv R$ (the case $p=5$ of a congruence of Swinnerton-Dyer, (cf. \cite[Thm.~5]{jps}), we note that $$z=\Delta/Q^3\equiv \Delta = (Q^3-R^2)/1728 \equiv 2-2R^2.$$ The case $p=5, k=4$ of formula (**) in section 2.2 of \cite{jps} reads $F-F^5 \equiv \theta^3R$. By Ramanujan's formula $$ \theta R=(PR-Q^2)/2\equiv 3R^2-3, $$ one finds that indeed $$ \theta^3R \equiv 2R^4-R^2-1 \equiv z+3z^2, $$ which proves Lemma~\ref{tate:lem6.6}. \end{proof} Let $F=\sum_{n\ge 1}b(n)z^n$. By Lemma~\ref{tate:lem6.6}, $b(5^m)$ and $b(2\cdot 5^m)$ are not divisible by 5. Therefore the $5^m$th and $2\cdot 5^m$th coefficients of $zdF/dz=\sum_{n\ge 1}nb(n)z^n$ are divisible exactly by $5^m$. By Lemma~\ref{tate:lem6.5} we have $$ \sum_{n\ge 1}c(n)z^n = \frac{PQ}{R}-1=3\frac{zdQ}{Qdz}=3\frac{240zdF}{(1+240F)dz}. $$ This shows that $\ord_5(c(5^m))=\ord_5(c(2\cdot 5^m))=m+1$ thereby completing the proof of Theorem~\ref{tate:thm6.3}. \begin{remark} For $p=2$ or 3 a simple analogue of Lemma~\ref{tate:lem6.6} holds, namely $F\equiv \sum_{m\ge 0} z^{p^m} \pmod p$. This can be used to obtain Koblitz's result for the very special case $n=p^m$. \end{remark} \section{Discussion} \subsection{Log convergence} The running hypothesis in Section~\ref{sec:logconvgen} is that $p \ge 5$, but in Section~\ref{sec:preciselogconv} we considered only $p=2,3,5$. In dealing with the different primes, our discussion changes strikingly, depending on the three slightly different cases: \begin{enumerate} \item[(1)] \label{case1} $p = 2,3$ \item[(2)] \label{case2} $p = 5$ \item[(3)] \label{case3} $p \ge 5$ \end{enumerate} For (\ref{case1}), in Section~\ref{sec:preciselogconv} we used expansions in powers of $z=1/j$ to give a careful analysis of convergence rates, and in contrast, the general discussion of Section~\ref{sec:logconvgen} {\em must} keep away from those cases $p=2,3$, in order to maintain the formulation that it currently has. The prime $p=5$ is in a very fortunate position because it can be covered by the general discussion a la (\ref{case3}); but we have also given a precise ``power series in $1/j$'' treatment of $p=5$. These issues suggest four questions: \begin{enumerate} \item Is there any relationship between the convergence rate analysis we give, and computation-time estimates for the actual algorithms? \item We have produced an algebra of log-convergent modular forms, and it has at least one new element that the overconvergent forms do not have, namely~$\E_2$. Moreover, it is closed under the action of $\theta$, i.e., ``Tate twist''. Are there other interesting Hecke eigenforms in this algebra that we should know about? Going the other way, are there any Hecke eigenforms that are {\em not} log-convergent? Is there something corresponding to the ``eigencurve'' (it would have to be, at the very least, a surface) that $p$-adically interpolates log-convergent eigenforms? Is a limit (in the sense of $\ord_p$'s of Fourier coefficients) of log-convergent eigenforms again log-convergent? For this last question to make sense, we probably need to know the following: \item Is there a rigid-analytic growth type of definition (growth at the rim of the Hasse domain) that characterizes log-convergence, just as there is such a definition characterizing overconvergence? \item Almost certainly one could treat the case $p=7$ by expansions in powers of $1/(j-1728) = \Delta/R^2$ in the same way that we did $p=5$ with powers of $1/j = \Delta/Q^3$. The case $p=13$ might be more interesting. \end{enumerate} %\edit{Items 2,3 in section 7 are still too "chatty" for an actual paper. %So we should remember to "rework" this a bit.} \subsection{Uniformity in the algorithms} We are most thankful to Kiran Kedlaya and Alan Lauder for some e-mail communications regarding an early draft of our article. The topic they address is the extent to which the algorithms for the computation of ${\bf E}_2$ of an elliptic curve are ``uniform'' in the elliptic curve, and, in particular, whether one can get fast algorithms for computing ${\bf E}_2$ of specific families of elliptic curves. In this section we give a brief synopsis of their comments. A ``reason'' why ${\bf E}_2$ should turn out not to be overconvergent is that Katz's formula relates it to the direction of the unit-root subspace in one-dimensional de Rham cohomology, and that seems only to make (at least naive) sense in the ordinary case (and not for points in a supersingular disc, not even ones close to the boundary). Nevertheless, part of the algorithm has good uniformity properties. \begin{enumerate} \item {\em Calculating the matrix of Frobenius:} One can calculate the matrix of Frobenius for, say, all elliptic curves in the Legendre family (or any one-parameter family) and the result is overconvergent everywhere, so this should be relatively efficient. This can be done either by the algorithm developed by Kedlaya, or also using the Gauss-Manin connection, as in Lauder's work, which is probably faster. An approach to computing the ``full'' Frobenius matrix ``all at once'' for elliptic curves in the Legendre family has been written up and implemented in Magma by Ralf Gerkmann: See \cite{gerkmann} for the paper and program. Lauder's paper \cite{lauder} also discusses Kedlaya's algorithm ``all at once'' for a one-parameter family of hyperelliptic curves using the Gauss-Manin connection. \item {\em Extracting the unit root subspace in de Rham cohomology:} To compute ${\bf E}_2$ for an individual elliptic curve, one can specialize the Frobenius matrix and extract the unit root. But extracting only the unit root part over the entire family at once would involve non-overconvergent series, and consequently might be slow. The {\it unit root zeta function}, which encodes the unit root of Frobenius over a family of ordinary elliptic curves, has been very well studied by Dwork and Wan (cf. \cite{MR1740990}). \end{enumerate} \subsection{Other future projects} \begin{enumerate} %\item the question about the value of E_2 on the canonical lifting \item Explicitly compute anticyclotomic $p$-adic heights, and apply this to the study of universal norm questions that arise in \cite{mazur-rubin:large_selmer}. \item Further investigate Kedlaya's algorithm with a parameter in connection with log convergence and computation of heights. \item Determine if the equality $\lim_{n \to \infty} a_{P}(n)/\log(n) = 1/\log(p)$ holds for all primes~$p$, as it does for $p=5$ by Theorem \ref{tate:thm6.3}. \end{enumerate} \newcommand{\etalchar}[1]{$^{#1}$} \providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace} \providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR } % \MRhref is called by the amsart/book/proc definition of \MR. \providecommand{\MRhref}[2]{% \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2} } \providecommand{\href}[2]{#2} \begin{thebibliography}{GJP{\etalchar{+}}05} \bibitem[Bes04]{MR2076563} Amnon Besser, \emph{The {$p$}-adic height pairings of {C}oleman-{G}ross and of {N}ekov\'a\v r}, Number theory, CRM Proc. Lecture Notes, vol.~36, Amer. Math. Soc., Providence, RI, 2004, pp.~13--25. \MR{2076563 (2005f:11130)} \bibitem[Blu]{bluher:formal} Antonia~W. Bluher, \emph{A {L}eisurely {I}ntroduction to {F}ormal {G}roups and {E}lliptic {C}urves,\\ {\tt http://www.math.uiuc.edu/algebraic-number-theory/0076/}}. \bibitem[BCP97]{magma} W.~Bosma, J.~Cannon, and C.~Playoust, \emph{The {M}agma algebra system. {I}. {T}he user language}, J. Symbolic Comput. \textbf{24} (1997), no.~3--4, 235--265, Computational algebra and number theory (London, 1993). \MR{1 484 478} \bibitem[Col91]{MR1091621} Robert~F. Coleman, \emph{The universal vectorial bi-extension and {$p$}-adic heights}, Invent. Math. \textbf{103} (1991), no.~3, 631--650. \MR{1091621 (92k:14021)} \bibitem[CGJ95]{MR1317641} Robert~F. Coleman, Fernando~Q. Gouv{\^e}a, and Naomi Jochnowitz, \emph{{$E\sb 2$}, {$\Theta$}, and overconvergence}, Internat. Math. Res. Notices (1995), no.~1, 23--41 (electronic). \MR{1317641 (96d:11047)} \bibitem[Ger05]{gerkmann} Ralf Gerkmann, {\tt http://www.mathematik.uni-mainz.de/\\ \~{ }gerkmann/ellcurves.html}, (2005). \bibitem[Gre03]{MR1977007} Ralph Greenberg, \emph{Galois theory for the {S}elmer group of an abelian variety}, Compositio Math. \textbf{136} (2003), no.~3, 255--297. \MR{1977007 (2004c:11097)} \bibitem[GJP{\etalchar{+}}05]{bsdalg1} G.~Grigorov, A.~Jorza, S.~Patrikis, C.~Patrascu, and W.~Stein, \emph{Verification of the {B}irch and {S}winnerton-{D}yer {C}onjecture for {S}pecific {E}lliptic {C}urves}, (Submitted)\\{\tt http://modular.fas.harvard.edu/papers/bsdalg/} (2005). \bibitem[Gou88]{gouvea:slnm} F.\thinspace{}Q. Gouv\^{e}a, \emph{Arithmetic of $p$-adic modular forms}, Springer-Verlag, Berlin, 1988. \MR{91e:11056} \bibitem[IW03]{MR2021039} Adrian Iovita and Annette Werner, \emph{{$p$}-adic height pairings on abelian varieties with semistable ordinary reduction}, J. Reine Angew. Math. \textbf{564} (2003), 181--203. \MR{2021039 (2004j:11066)} \bibitem[SJ05]{sage} William Stein and David Joyner, \emph{Sage: System for algebra and geometry experimentation}, Communications in Computer Algebra (SIGSAM Bulletin) (July 2005), {\tt http://sage.sourceforge.net/}. \bibitem[Kat73]{katz:padicprop} Nicholas~M. Katz, \emph{{$p$}-adic properties of modular schemes and modular forms}, Modular functions of one variable, III (Proc. Internat. Summer School, Univ. Antwerp, Antwerp, 1972), Springer, Berlin, 1973, pp.~69--190. Lecture Notes in Mathematics, Vol. 350. \MR{0447119 (56 \#5434)} \bibitem[Kat76]{katz:padic_interp} \bysame, \emph{{$p$}-adic interpolation of real analytic {E}isenstein series}, Ann. of Math. (2) \textbf{104} (1976), no.~3, 459--571. \MR{0506271 (58 \#22071)} \bibitem[Ked01]{kedlaya:counting_mw} Kiran~S. Kedlaya, \emph{Counting points on hyperelliptic curves using {M}onsky-{W}ashnitzer cohomology}, J. Ramanujan Math. Soc. \textbf{16} (2001), no.~4, 323--338. \MR{1877805 (2002m:14019)} \bibitem[Ked03]{kedlaya:counting-errata} K.\thinspace{}S. Kedlaya, \emph{Errata for: ``{C}ounting points on hyperelliptic curves using {M}onsky-{W}ashnitzer cohomology'' [{J}. {R}amanujan {M}ath.\ {S}oc.\ {\bf 16} (2001), no. 4, 323--338}, J. Ramanujan Math. Soc. \textbf{18} (2003), no.~4, 417--418, Dedicated to Professor K. S. Padmanabhan. \MR{2 043 934} \bibitem[Kob77]{koblitz} Neil Koblitz, {\em $2$-adic and $3$-adic ordinals of the (1/$j$)-expansion coefficients for the weight 2 Eisenstein series, Bull. L.M.S. 9 (1977), 188-192.} \bibitem[Lan95]{lang:modular} S.~Lang, \emph{Introduction to modular forms}, Springer-Verlag, Berlin, 1995, With appendixes by D. Zagier and W. Feit, Corrected reprint of the 1976 original. \bibitem[Lau03]{lauder} A.\thinspace{}G.\thinspace{}B. Lauder, \emph{Rigid cohomology and $p$-adic point counting}, to appear in a special issue of J. de Théorie des Nombres de Bordeaux,\\ {\tt http://www.maths.ox.ac.uk/\~{ }lauder/}. \bibitem[LW02]{lauder-wan} A.\thinspace{}G.\thinspace{}B. Lauder and D. Wan, \emph{Counting rational points on varieties over finite fields of small characteristic}, to appear in an MSRI Computational Number Theory Proceedings (October, 2002). \bibitem[MR04]{mazur-rubin:pairings_arith} Barry Mazur and Karl Rubin, \emph{Pairings in the arithmetic of elliptic curves}, Modular curves and abelian varieties, Progr. Math., vol. 224, Birkh\"auser, Basel, 2004, pp.~151--163. \MR{MR2058649 (2005g:11095)} \bibitem[MT83]{mazur-tate:canonical} B.~Mazur and J.~Tate, \emph{Canonical height pairings via biextensions}, Arithmetic and geometry, Vol. I, Progr. Math., vol.~35, Birkh\"auser Boston, Boston, MA, 1983, pp.~195--237. \MR{717595 (85j:14081)} \bibitem[MT87]{mazur-tate:refined} \bysame, \emph{Refined conjectures of the ``{B}irch and {S}winnerton-{D}yer type''}, Duke Math. J. \textbf{54} (1987), no.~2, 711--750. \MR{899413 (88k:11039)} \bibitem[MT91]{mazur-tate:sigma} \bysame, \emph{The {$p$}-adic sigma function}, Duke Math. J. \textbf{62} (1991), no.~3, 663--688. \MR{93d:11059} \bibitem[MTT86]{mtt} B.~Mazur, J.~Tate, and J.~Teitelbaum, \emph{On {$p$}-adic analogues of the conjectures of {B}irch and {S}winnerton-{D}yer}, Invent. Math. \textbf{84} (1986), no.~1, 1--48. \MR{830037 (87e:11076)} \bibitem[Nek93]{MR1263527} Jan Nekov{\'a}{\v{r}}, \emph{On {$p$}-adic height pairings}, S\'eminaire de Th\'eorie des Nombres, Paris, 1990--91, Progr. Math., vol. 108, Birkh\"auser Boston, Boston, MA, 1993, pp.~127--202. \MR{1263527 (95j:11050)} \bibitem[Nek03]{nekovar:selmer} \bysame, \emph{Selmer Complexes}, 2003, see\\ {\tt http://www.math.jussieu.fr/\~{ }nekovar/pu/}. \bibitem[Pla94]{MR1299736} Andrew Plater, \emph{Supersingular {$p$}-adic height pairings on elliptic curves}, Arithmetic geometry (Tempe, AZ, 1993), Contemp. Math., vol. 174, Amer. Math. Soc., Providence, RI, 1994, pp.~95--105. \MR{1299736 (95h:11056)} \bibitem[PR03a]{perrin-riou:expmath} Bernadette Perrin-Riou, \emph{Arithm\'etique des courbes elliptiques \`a r\'eduction supersinguli\`ere en {$p$}}, Experiment. Math. \textbf{12} (2003), no.~2, 155--186. \MR{2016704 (2005h:11138)} \bibitem[PR03b]{pr:exp} \bysame, \emph{Arithm\'etique des courbes elliptiques \`a r\'eduction supersinguli\`ere en {$p$}}, Experiment. Math. \textbf{12} (2003), no.~2, 155--186. \MR{2016704} \bibitem[RM05]{mazur-rubin:large_selmer} K.~Rubin and B.~Mazur, \emph{Organizing the arithmetic of elliptic curves}, in preparation. \bibitem[Sch82]{schneider:height1} Peter Schneider, \emph{{$p$}-adic height pairings. {I}}, Invent. Math. \textbf{69} (1982), no.~3, 401--409. \MR{679765 (84e:14034)} \bibitem[Sch85]{schneider:height2} \bysame, \emph{{$p$}-adic height pairings. {II}}, Invent. Math. \textbf{79} (1985), no.~2, 329--374. \MR{778132 (86j:11063)} \bibitem[Ser73]{jps} J-P. Serre, \emph{Congruences et formes modulaires [d'apr\`es {H}.\thinspace{}{P}.\thinspace{}{F}.\ {S}winnerton-{D}yer]}, S\'eminaire Bourbaki, 24e ann\'ee (1971/1972), Exp. No. 416 (Berlin), Springer, 1973, pp.~319--338. Lecture Notes in Math., Vol. 317. \bibitem[Sil92]{silverman:aec} J.\thinspace{}H. Silverman, \emph{The arithmetic of elliptic curves}, Springer-Verlag, New York, 1992, Corrected reprint of the 1986 original. \bibitem[Wan99]{MR1740990} Daqing Wan, \emph{Dwork's conjecture on unit root zeta functions}, Ann. of Math. (2) \textbf{150} (1999), no.~3, 867--927. \MR{MR1740990 (2001a:11108)} \bibitem[Wut04]{wuthrich:heightfamily} Christian Wuthrich, \emph{On {$p$}-adic heights in families of elliptic curves}, J. London Math. Soc. (2) \textbf{70} (2004), no.~1, 23--40. \MR{2064750} \bibitem[Zar90]{MR1042777} Yuri~G. Zarhin, \emph{{$p$}-adic heights on abelian varieties}, S\'eminaire de Th\'eorie des Nombres, Paris 1987--88, Progr. Math., vol.~81, Birkh\"auser Boston, Boston, MA, 1990, pp.~317--341. \MR{1042777 (91f:11043)} \end{thebibliography} \Addresses \end{document}