\documentclass[11pt]{article}
\usepackage[active]{srcltx}
\usepackage[british]{babel}
\usepackage{amsmath,amssymb,amsthm,mathrsfs, url}
\usepackage[mathcal]{euscript}
\hoffset=-0.05\textwidth
\textwidth=1.1\textwidth
%\usepackage[a4paper,body={14cm,23cm}, includefoot]{geometry}
\usepackage[dvips]{color}

\newcommand{\william}[1]{\footnote{[[William: #1]]}\marginpar{\hfill {\sf[[\thefootnote]]}}}

\newcommand{\christian}[1]{\footnote{[[Christian: #1]]}\marginpar{\hfill {\sf[[\thefootnote]]}}}


%--   Cyrillic 
\input cyracc.def \font\tencyr=wncyr10 \def\russe{\tencyr\cyracc} 
\def\Sha{\text{\russe{Sh}}}

%--   nicer <=
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}

%--   Colours   
\definecolor{dgreen}{rgb}{0,0.4,0.4}
\definecolor{dblue}{rgb}{0,0,0.7}
\definecolor{red}{rgb}{1,0,0}

%--   Theorems  
\newtheoremstyle{mythm}{11pt}{11pt}{\it\color{dblue}}{}{\bf\color{dblue}}{.}{\newline}{}
\theoremstyle{mythm}
\newtheorem{thm}{Theorem}
\newtheorem{thmkato}[thm]{Kato's Theorem}

\newtheoremstyle{mypl}{11pt}{11pt}{\it\color{dblue}}{}{\bf\color{dblue}}{.}{ }{}
\theoremstyle{mypl}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}{Corollary}
\newtheorem{alg}[thm]{Algorithm}

\newtheoremstyle{mycon}{11pt}{11pt}{\it\color{dgreen}}{}{\bf\color{dgreen}}{.}{ }{}
\theoremstyle{mycon}
\newtheorem{con}{Conjecture}

\newenvironment{algorithm}[1]{%
\begin{alg}[#1]%\index{algorithm!#1}
\sf}{\end{alg}}

\newenvironment{steps}%
{\begin{enumerate}\setlength{\itemsep}{0.1ex}}{\end{enumerate}}

%named versions
\newenvironment{theorem}[1]{\begin{thm} {\bf (#1)}}{\end{thm}}

\newenvironment{conjecture}[1]{\begin{con} {\bf (#1)}}{\end{con}}



%-- Operators  
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\HH}{H}
\DeclareMathOperator{\Gl}{GL}
\DeclareMathOperator{\Gal}{Gal}
\DeclareMathOperator{\rk}{rank}
\DeclareMathOperator{\Reg}{Reg}

\DeclareMathOperator{\an}{an}

\DeclareMathOperator{\tor}{tor}
\DeclareMathOperator{\ord}{ord} 
\DeclareMathOperator{\Col}{Col} 

%-- Abbrevations   
\newcommand{\sss}{\scriptscriptstyle}
\newcommand{\liminj}{\varinjlim}
\newcommand{\limproj}{\varprojlim}
\newcommand{\vu}{\upsilon}
\newcommand{\mf}{\mathfrak}


\newcommand{\cross}{\times}
\newcommand{\isom}{\cong}

\renewcommand{\O}{\mathcal{O}}

%-- Fields
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\Qp}{\QQ_p}
\newcommand{\FF}{\mathbb{F}}
%\newcommand{\QZ}{{{}^{\QQ_p}\!/\!{}_{\ZZ_p}}}
\newcommand{\QZ}{{\QQ_p/\ZZ_p}}


%-- Iwasawa theory  
\newcommand{\QQinf}{{}_\infty\QQ}
\newcommand{\Kinf}{{}_\infty K}
\newcommand{\QQn}{{}_n\QQ}
\newcommand{\QQnplusone}{{}_{n+1}\QQ}
%\newcommand{\Hinf}{\mathbb{H}}
\newcommand{\Hinfloc}{\mathbb{H}_{\text{loc}}^1}
\newcommand{\Hinfglob}{\mathbb{H}_{\text{glob}}^1}
\newcommand{\Ginf}{{}_{\infty\!} G}
\newcommand{\cinf}{{}_{\infty} c}


%-- Elliptic Curves   
\newcommand{\Lstar}{L^{\ast}(E,1)}
\newcommand{\Sel}{\mathcal{Sel}}
\newcommand{\Rel}{\mathcal{R}}
\newcommand{\Tp}{T_{\! p}}
\newcommand{\Xinf}{X(E/\QQinf)}

\newcommand{\LL}{\mathcal{L}}
\newcommand{\Linv}{\mathscr{L}}

%-- Arrows   

\newcommand{\IncTo}{\hookrightarrow}
\newcommand{\rTo}{\longrightarrow}

%-- small-er indices

\newcommand{\OmegaE}{\Omega_{\sss E}}
\newcommand{\qE}{q_{\sss E}}
\newcommand{\ZeroE}{O_{\sss E}}
\newcommand{\logE}{\log_{\sss E}}
\newcommand{\gE}{g_{\sss E}}
\newcommand{\fE}{f_{\sss E}}
\newcommand{\etaE}{\eta_{\sss E}}
\newcommand{\omegaE}{\omega_{\sss E}}
   
%-- series
\newcommand{\bigO}{\mathbf{O}}   
   
   
%-- 
\newcommand{\note}[1]{{\sf\small[[#1]]}}
\newcommand{\old}[1]{} 

%-- Title.

\begin{document}

\author{William Stein and Christian Wuthrich}
\title{Computations About Tate-Shafarevich Groups Using Iwasawa Theory}

\maketitle

\abstract{We explain how to combine deep results from Iwasawa theory
  with explicit computation to obtain information about $p$-parts of
  Tate-Shafarevich groups of elliptic curves over $\QQ$.  This method
  provides a practical way to compute $\#\Sha(E/\QQ)(p)$ in many cases
  when traditional $p$-descent methods are completely impractical and
  also in situations where results of Kolyvagin and Kato do not
  apply.}


\section{Introduction}\label{ranksha_sec}

%\william{Be sure to cite \cite{colmez}, perrin-riou, etc.}

%\william{In sections 3--5, it would be good to have an actual
%short (!) illustrative example in each section.}

Let $E$ be an elliptic curve defined over $\QQ$ and let
\begin{equation}\label{w_eq}
   y^2 \, + \, a_1\, x\,y\, + \,a_3\,y \,=\, x^3 \, + \, a_2\, x^2\, + \,a_4\,x\, + \,a_6
\end{equation}
be a choice of global minimal Weierstrass equation for $E$.  Then
Mordell proved  that
the set of rational points $E(\QQ)$ is an abelian group of finite rank
$r=\rk(E(\QQ))$.  Birch and Swinnerton-Dyer then conjectured that $ r
= \ord_{s=1} L(E,s), $ where $L(E,s)$ is the Hasse-Weil $L$-function
of $E$ (see Conjecture~\ref{bsd_con} below).  We call $r_{\an} =
\ord_{s=1} L(E,s)$ the analytic rank of $E$.

By an {\em algorithm} we mean a finite sequence of steps that, given
any valid input, will terminate in a finite amount of time.  There is
no known algorithm that {\em has been proved to be correct} that
computes $r$ in all cases.  One can computationally obtain upper and
lower bounds in any particular case.  One way to give a lower bound on
$r$ is to search for linearly independent points of small height via
the method of descent, which involves searching for points of even
smaller height on a collection of auxiliary curves.  Constructions of
complex and $p$-adic Heegner points can also be used in some cases to
bound the rank from below.  To compute an upper bound on the rank $r$,
in the case of analytic ranks $0$ and $1$ one can use Kolyvagin's work
on the Euler systems of Heegner points; in general, the only known
method is to do an $n$-descent for some integer $n>1$. The 2-descents
implemented by John Cremona~\cite{cremona}, by Denis
Simon~\cite{simon} in Pari~\cite{pari} (and SAGE~\cite{sage}) and by
Geoffe Bailey in Magma, and the $3$ and $4$ descents in
Magma and described in~\cite{cremonaetal}, are particularly
powerful. But they may fail in practice to compute the exact rank due
to the presence of $2$ or $3$-torsion elements in the Tate-Shafarevich
group.
 
The Tate-Shafarevich group, denoted by $\Sha(E/\QQ)$, is a torsion
abelian group associated to $E/\QQ$. It is the kernel of the
localization map
 \begin{equation*}
  0\rTo \Sha(E/\QQ) \rTo \HH^1(\QQ,E)\rTo \bigoplus_\vu\HH^1(\QQ_\vu,E),
 \end{equation*}
where the product runs over all places $\vu$ in $\QQ$. The arithmetic
importance of this group lies in its geometric interpretation. There
is a bijection from $\Sha(E/\QQ)$ to the $\QQ$-isomorphism classes of
principal homogeneous spaces $C/\QQ$ of $E$ which have points
everywhere locally. In particular, such a $C$ is a curve of genus 1
defined over $\QQ$ whose Jacobian is isomorphic to $E$.  Nontrivial
elements in $\Sha(E/\QQ)$ correspond to curves $C$ which defy the
Hasse principle, i.e., have a point over every completion of $\QQ$,
but have no points over $\QQ$.

\begin{conjecture}{Shafarevich and Tate}\label{consha_con}
	The group $\Sha(E/\QQ)$ is finite.
\end{conjecture}


These two invariants, the rank $r$ and the Tate-Shafarevich group
$\Sha(E/\QQ)$, are encoded in the Selmer groups of $E$.  Fix a prime
$p$, and let $E(p)$ denote the $\Gal(\bar\QQ/\QQ)$-module of all
torsion points of $E$ whose orders are powers of $p$. The Selmer group
$ \Sel_p(E/\QQ)$ is defined by the following exact sequence:
 \begin{equation*}
  0\rTo \Sel_p(E/\QQ)\rTo \HH^1(\QQ,E(p))\rTo \bigoplus_\vu \HH^1(\QQ_\vu,E)\, .
 \end{equation*}
Likewise, for any positive integer $m$,
the $m$-Selmer group is defined by
the exact sequence
$$0 \to \Sel^{(m)}(E/\QQ) \to \HH^1(\QQ,E[m])\rTo \bigoplus_\vu \HH^1(\QQ_\vu,E)$$
where $E[m]$ is the subgroup of elements of order dividing $m$ in $E$.

It follows from the Kummer sequence that
there are short exact sequences
 \begin{equation*}
  0\rTo E(\QQ)/m E(\QQ) \rTo \Sel^{(m)}(E/\QQ)\rTo \Sha(E/\QQ)[m]\rTo 0
 \end{equation*}
and
 \begin{equation*}
  0\rTo E(\QQ)\otimes \QZ \rTo \Sel_p(E/\QQ)\rTo \Sha(E/\QQ)(p)\rTo 0\,.
 \end{equation*}
If the Tate-Shafarevich group is finite, then the $\ZZ_p$-corank of
$\Sel_p(E/\QQ)$ is equal to the rank $r$ of $E(\QQ)$.
 
The finiteness of $\Sha(E/\QQ)$ is only known for curves of analytic
rank $0$ and $1$ in which case computation of Heegner points and
Kolyvagin's work on Euler systems gives an explicit computable
multiple of its order.  The group $\Sha(E/\QQ)$ is not known to be
finite for even a single elliptic curve with $r_{\an}\geq 2$.  In such
cases, the best one can do using current techniques is hope to bound
the $p$-part $\Sha(E/\QQ)(p)$ of $\Sha(E/\QQ)$, for specific primes
$p$.  Even this might not a priori be possible, since it is not known
that $\Sha(E/\QQ)(p)$ is finite.  However, if it were the case that
$\Sha(E/\QQ)(p)$ is finite (as Conjecture~\ref{consha_con} asserts),
then this could be verified by computing Selmer groups
$\Sel^{(p^n)}(E/\QQ)$ for sufficiently many $n$ (see, e.g.,
\cite{stoll}).  Note that practical unconditional computation of
$\Sel^{(p^n)}(E/\QQ)$ is prohibitively difficult for all but a few
very small $p^n$.

%\subsection{Something} ?

We present in this paper two algorithms using $p$-adic $L$-functions
$\LL_p(E,T)$. They are $p$-adic analogs of the complex function
$L(E,s)$ (see Section~\ref{lp_sec} for the definition). Both
algorithms rely heavily on the work of Kato~\cite{kato}, which is
considered to be a major breakthrough in the direction of a proof of
the $p$-adic version of the Birch and Swinnerton-Dyer conjecture (see
Section~\ref{pbsd_sec}). The possibility of using these results to
compute information about the Tate-Shafarevich group is well known to
specialists and was for instance mentioned in~\cite{colmez} which
gives also a nice overview over the $p$-adic Birch and Swinnerton-Dyer
conjecture. For supersingular primes these methods have been used by
Perrin-Riou in~\cite{pr00}.

The first algorithm, which we describe
Section~\ref{rankalgorithm_sec}, finds a provable upper bound for the
rank~$r$ of $E(\QQ)$ by simply computing approximations to the
$p$-adic $L$-series for various small primes $p$. Any upper bound on
the vanishing of $\LL_p(E,T)$ at $T=0$ is known to be an upper bound
on the rank~$r$.


The second algorithm, which we discuss in
Section~\ref{shaalgorithm_sec}, gives a new method for computing
bounds on the order of $\Sha(E/\QQ)(p)$, for specific primes $p$.  We
will exclude $p=2$, since traditional descent methods work well at
$p=2$, and Iwasawa theory is not as well developed for $p=2$.  We also
exclude some primes~$p$, e.g., those for which~$E$ has additive
reduction, since much of the theory we rely on has not yet been developed
in this case yet (see Section~\ref{additive_sec}
and~\ref{shaalgorithm_sec}).

Our second algorithm uses again the $p$-adic $L$-functions
$\LL_p(E,T)$, but also requires that the full Mordell-Weil group
$E(\QQ)$ is known. Its output, if it yields any output, is a proven
upper bound on the order of $\Sha(E/\QQ)(p)$; in particular, it will
often prove the finiteness of the $p$-primary part of the
Tate-Shafarevich group.  But it will not be able to give any
information about the structure of $\Sha(E/\QQ)(p)$ as an abelian
group or any information on its elements. For such finer results on
the Tate-Shafarevich group, there is currently no other general method
than to use $p^n$-descents as described above, or use visibility
\cite{vis} to relate $\Sha(E/\QQ)(p)$ to Mordell-Weil groups of other
elliptic curves or abelian varieties.  The computability of the upper
bound on $\#\Sha(E/\QQ)(p)$ relies on several conjectures, such as the
finiteness of $\Sha(E/\QQ)(p)$ and Conjectures~\ref{conreg_con}
and~\ref{conreg_ss_con} on the non-degeneracy of the $p$-adic height
on $E$.  Under the assumption of the so-called main conjecture of
Iwasawa theory (see Section~\ref{mainconjecture_sec}), the result of
the algorithm is known to be equal to the order of $\Sha(E/\QQ)(p)$.
There are several cases when this conjecture is known to hold by
Greenberg and Vatsal in~\cite{grvat}, by Grigorov in~\cite{grigorov},
and in a forthcoming paper by Skinner and Urban.

Note that both algorithms can possibly be implemented also to give
bounds on the rank $E(K)$ and bounds on $\#\Sha(E/K)(p)$ for number
fields $K$ which are abelian extensions of $\QQ$.
 
\subsection{Overview}
The article is structured as follows. We start by recalling the Birch
and Swinnerton-Dyer conjecture and its algorithmic consequences. In
Section~\ref{lp_sec}, we define $p$-adic $L$-functions and explain
how to compute them. Next we define the $p$-adic regulator,
treating separately the cases of split multiplicative and
supersingular reduction. This leads to the formulation of the
$p$-adic Birch and Swinnerton-Dyer conjectures. In
Section~\ref{iwasawa_sec}, we recall the basic definitions and results
for the algebraic $p$-adic $L$-functions defined using Iwasawa
theory. This leads us naturally to the statement of the main
conjecture and the theorem of Kato. Concrete examples illustrate
the theory throughout these sections.
 
We then explain first the implication of these results in the case the
curve has analytic rank $0$, followed by the case of analytic rank
$1$. Finally we present in Section~\ref{rankalgorithm_sec}
and~\ref{shaalgorithm_sec} the algorithms for bounding the rank and
the order of the $p$-primary part of $\Sha(E/\QQ)$. We conclude the
article with a section of further explicit examples produced by the
algorithms.  A forthcoming sequence to this paper will apply the
theory in this paper to produce numerous tables and analyses of the
resulting data.
 
\subsection*{Acknowledgments} 
The authors would like to thank Henri Darmon, Jer\^ome Grand'maison,
Ralph Greenberg and Dimitar Jetchev for helpful discussions and
comments. We are also greatly indebted to Robert Pollack whose code
for computing $p$-adic $L$-functions was the starting basis of this
article. He also greatly helped us with the error estimates in
Section~\ref{lp_sec}.

%% -------------------------------------------------------------------------
\section{The Birch and Swinnerton-Dyer conjecture}\label{bsd_sec}

Let $E$ be an elliptic curve defined over $\QQ$.
If the Birch and Swinnerton-Dyer conjecture (Conjecture~\ref{bsd_con}
below) were true, it would yield an algorithm to compute both the rank
$r$ and the order of $\Sha(E/\QQ)$.

Let $E$ be an elliptic curve over $\QQ$, and let $L(E,s)$ be the
Hasse-Weil $L$-function associated to the $\QQ$-isogeny class of $E$.
According to \cite{bcdt} (which completes work initiated
in~\cite{wiles}), the function $L(E,s)$ is holomorphic on the whole
complex plane.  Let $\omegaE$ be the invariant differential
$dx/(2y+a_1 x+a_3)$ of a minimal Weierstrass equation~\eqref{w_eq} of
$E$. We write $\OmegaE=\int_{E(\RR)} \omegaE \in \RR_{>0}$ for the
N\'eron period of $E$.

\begin{conjecture}{Birch and Swinnerton-Dyer}\label{bsd_con}
  \begin{enumerate}
  \item The order of vanishing of the Hasse-Weil function $L(E,s)$ at $s=1$ is equal to the rank $r=\rk(E(\QQ))$.
  \item The leading term $\Lstar$ of the Taylor expansion of $L(E,s)$ at $s=1$ satisfies
  \begin{equation}\label{bsd_eq}
   \frac{\Lstar}{\OmegaE} = \frac{\prod_\vu c_\vu\cdot \#\Sha(E/\QQ)}{(\#E(\QQ)_{\tor})^2}\cdot\Reg(E/\QQ)
  \end{equation}
   where the Tamagawa numbers are denoted by $c_\vu$ and $\Reg(E/\QQ)$
   is the regulator of $E$, i.e., the discriminant of the  N\'eron-Tate canonical
   height pairing on $E(\QQ)$. 
  \end{enumerate}
\end{conjecture}

Below we write $\#\Sha(E/\QQ)_{\an}$ for the order of $\Sha(E/\QQ)$
that is predicted by Conjecture~\ref{bsd_con}.
 
Cassels proved in \cite{cassels} that if Conjecture~\ref{bsd_eq} is
true for an elliptic curve $E$ over $\QQ$, then it is true for all
curves that are $\QQ$-isogenous to $E$.

\begin{prop}\label{bsdalgorithm_prop}
 If Conjecture~\ref{bsd_con} is true, then there is an algorithm to compute~$r$
 and $\#\Sha(E/\QQ)$.
\end{prop}
\begin{proof}  

  The proof is well known, but we repeat it here since it illustrates
  several key ideas.  By naively searching for points in $E(\QQ)$ we
  obtain a lower bound on $r$, which is closer and closer to the true
  rank $r$, the longer we run the search.  At some point this lower
  bound will equal $r$, but without using further information we have
  no way to know if that has occured.  As explained, e.g.,
  in~\cite{cremona, cohen:nt2, dokchitser:lfun}, we can for any $k$ compute
  $L^{(k)}(E,1)$ to any desired precision.  Such computations yield
  upper bounds on $r_{\an}$.  In particular, if we compute
  $L^{(k)}(E,1)$ and it is nonzero (to the precision of our
  computation), then $r_{\an} < k$.  Eventually this method will also
  converge to give the correct value of $r_{\an}$, though again without
  further information we do not know when this will occur.  However, if we
  know Conjecture~\ref{bsd_con}, we know that $r = r_{\an}$, hence at
  some point the lower bound on $r$ computed using point searches will
  equal the upper bound on $r_{\an}$ computed using the $L$-series.
  At this point, by Conjecture~\ref{bsd_con} we know the true value of both
  $r$ and $r_{\an}$. 
 
Once $r$ is known, one can compute $E(\QQ)$ via a point search (as
explained in \cite[\S3.5]{cremona} or \cite[\S1.2]{stein:bsd}),
hence we can approximate $\Reg(E/\QQ)$ to any desired precision.  All
other quantities in~\eqref{bsd_eq} can also be approximated to any
desired precision.  Solving for $\#\Sha(E/\QQ)$ in~\eqref{bsd_eq} and
computing all other quantities to large enough precision to determine
the integer $\#\Sha(E/\QQ)_{\an}$ then determines $\#\Sha(E/\QQ)$, as claimed.
\end{proof}
 
We wish to emphasize that this algorithm would only produce the order
of $\Sha(E/\QQ)$ but no information about its structure as an abelian
group.  One could in theory compute the structure of $\Sha(E/\QQ)$ by
doing an explicit $n$-descent where $n^2=\#\Sha(E/\QQ)$.  The two
algorithms presented at the end of this article will mimic the ideas
of the proof of this proposition, but instead of working with the
complex $L$-function it will be in a $p$-adic setting.
 
   
%% -------------------------------------------------------------------------
\section{The $p$-adic $L$-function}\label{lp_sec}

We will assume for the rest of this article that $E$ does not admit
complex multiplication, though curves with complex multiplication are
an area of active research for these methods (see e.g., \cite{rubincetraro,
  pollackrubin}).

In order to formulate a $p$-adic analogue of the conjecture of Birch
and Swinnerton-Dyer, one needs first a $p$-adic version of the
analytic function $L(E,s)$. Mazur and Swinnerton-Dyer~\cite{mazurswd}
have found such a function. We refer to~\cite{mtt} for details on the
construction and the historic references.

Let $\pi\colon X_0(N)\rTo E$ be the modular parametrization of $E$ and
let $c_{\pi}$ be the Manin constant, i.e., the positive integer
satisfying $c_\pi\cdot\pi^{*}\omegaE = 2\pi i f(\tau) d\tau$ with $f$
the newform associated to $E$. Manin conjectured that $c_{\pi}=1$, and
much work has been done toward this conjecture (see \cite{edixhoven,
  maninconstant}).
 
Given a rational number $r$, consider the image $\pi_{*}(\{r\})$ in
$H_1(E,\RR)$ of the path joining $r$ to $i\,\infty$ in the upper half
plane.  Define
\begin{equation*}
  \lambda^{+}(r) =\frac{c_{\pi}}{2}\cdot \left( \int_{\pi_{*}(\{r\})} \omegaE + \int_{\pi_{*}(\{-r\})} \omegaE \right) = \pi i \cdot \left ( \int_r^{i\infty} f(\tau)\, d\tau + \int_{-r}^{i\infty} f(\tau)\, d\tau \right ) 
 \end{equation*} 
There is a basis $\{\gamma_{+},\gamma_{-}\}$ of $H_1(E,\ZZ)$ such that $\int_{\gamma_{+}} \omegaE$ is equal to $\OmegaE$ if $E(\RR)$ is connected and to $\tfrac{1}{2}\,\OmegaE$ otherwise.
By a theorem of Manin~\cite{manin}, we know that $\lambda^{+}(r)$ belongs to 
$\QQ\cdot \OmegaE$. We define the modular symbol $[r]^{+}\in\QQ$ to be
\begin{equation*}
    [r]^{+} \cdot \OmegaE  = \lambda^{+}(r)
\end{equation*}
for all $r\in\QQ$.  In particular we have $[0]^{+}=L(E,1)\cdot
\OmegaE^{-1}$.  The quantity $[r]^{+}$ can be computed
algebraically using modular symbols and linear algebra
(see \cite{cremona}). 

% or in some cases (e.g., when $N$ is square free)
%numerically, by approximating both $\OmegaE$ using the Gauss
%arithmetic-geometric mean and $\lambda^{+}(r)$ by summing a rapidly
%convergent series, and bounding the denominator of
%$\lambda^{+}(r)/\OmegaE$ using results about modular
%symbols.\william{way more details go here.}
   
Let $p$ be a prime of semi-stable reduction. We write\footnote{%
The context should make it clear if we speak about $a_p$ or $a_2$ and $a_3$ as in~\eqref{w_eq}.} 
$a_p$ for the trace of Frobenius.  Suppose first that $E$ has good
reduction at $p$. Then $N_p=p+1-a_p$ is the number of points on
$\tilde{E}(\FF_p)$. Let $X^2 -a_p\cdot X +p$ be the characteristic
polynomial of Frobenius and let $\alpha\in\bar\QQ_p$ be a root of this
polynomial such that $\ord_p(\alpha) <1 $. There are two different
possible choices if $E$ has supersingular reduction and there is a
single possibility for primes where $E$ has good ordinary reduction.
Now if $E$ has multiplicative reduction at $p$, then $a_p$ is $1$ if
it is split multiplicative and $a_p$ is $-1$ if it is non-split
multiplicative reduction.  In either multiplicative case, we have to
take $\alpha=a_p$.
 
Define a measure on $\ZZ_p^\times$ with values in $\QQ(\alpha)$ by
\begin{equation*}
  \mu_{\alpha} ( a + p^k \ZZ_p ) = \frac{1}{\alpha^k}\cdot \left[\frac{a}{p^k}\right]^{+} -\frac{1}{\alpha^{k+1}}\cdot \left[\frac{a}{p^{k-1}}\right]^{+}
 \end{equation*}
for any $k\geq 1$ and $a\in\ZZ_p^\times$. Given a continuous character
$\chi$ on $\ZZ_p^\times$ with values in the completion $\CC_p$ of the
algebraic closure of $\QQ_p$, we may integrate $\chi$ against
$\mu_{\alpha}$.  Any invertible element $x$ of $\ZZ_p^{\times}$ can be
written as $\omega(x)\cdot \langle x\rangle$ where $\omega(x)$ is a
$(p-1)$st root of unity and $\langle x\rangle$ belongs to
$1+2p\ZZ_p$. We define the analytic $p$-adic $L$-function by
 \begin{equation*}
   L_\alpha (E,s) = \int_{\ZZ_p^\times} \langle x\rangle^{s-1} \, d\mu_{\alpha}(x)
   \quad\text{ for all $s\in\ZZ_p$.}
 \end{equation*}
where by $\langle x\rangle^{s-1}$ we mean $\exp_p((s-1)\cdot
\log_p(\langle x\rangle ))$. The function $L_\alpha(E,s)$ extends to a
locally analytic function in $s$ on the disc defined by $\vert s-
1\vert < 1$ (see \S13 in~\cite{mtt}).
 
Let $\Ginf$ be the Galois group of the cyclotomic extension
$\QQ(\mu_{p^\infty})$ obtained by adjoining to $\QQ$ all $p$-power
roots of unity. By $\kappa$ we denote the cyclotomic character
$\Ginf\rTo \ZZ_p^\times$.  Because the cyclotomic character is an
isomorphism, choosing a topological generator $\gamma$ in $\Gamma =
\Ginf^{4(p-1)}$ amounts to picking an element $\kappa(\gamma)$ in
$1+2p\ZZ_p^\times$.  With this choice, we may convert the function
$L_{\alpha}(E,s)$ into a $p$-adic power series in $T =
\kappa(\gamma)^{s-1}-1$. We write $\LL_{\alpha}(E,T)$ for this series
in $\QQ_p(\alpha)[\![T]\!]$. We have

\begin{equation}\label{Lpser_eq}
  \LL_{\alpha}(E,T) = \int_{\ZZ_p^\times} (1+T)^{\frac{\log(x)}{\log(\kappa(\gamma))}} d\mu_\alpha(x)\,.
 \end{equation}

% % Christian : I agree. I should have set $a$ before writing the sum. Of course any choice of $a$'s will make the polynomials expression for $\LL$ converge. As to the remark on modular symbols see footnote~\ref{modsymb_footnote}.}
% For each $a\in (\ZZ/p^k\ZZ)^\times$, fix the choice of lift $\omega(b)\cdot
% \kappa(\gamma)^j$ with $1 \leq b \leq p-1$ and $0\leq j \leq
% p^{k-1} - 1$.  Using the above lifts, as in~\cite{pollack}, we define
% the following polynomial:
%  \begin{align*}
%   P_n &= \sum_{a\in(\ZZ/p^k\ZZ)^{\times}} 
%   \left[\frac{a}{p^k}\right]^{+} \cdot (1+T)^{ \frac{\log(a)}{\log(\kappa(\gamma))}} \\
%    & = \sum_{j=0}^{p^{k-1}-1}\, \sum_{b=1}^{p-1}\, \left[\frac{\omega(b)\cdot \kappa(\gamma)^j}{p^k}\right]^{+} \cdot (1+T)^j,
%  \end{align*}
% where we changed the summation by putting $ a = \omega(b) \cdot
% \kappa(\gamma)^j$.  Then the approximation as a Riemann
% sum of the above integral for $\LL_{\alpha}(E,T)$ can be
% written as
%  \begin{equation*}
%   \LL_{\alpha}(E,T)  = \lim_{k\to\infty} \left( \frac{1}{\alpha^k} \cdot P_{k} - \frac{1}{\alpha^{k+1}}\cdot P_{k-1} \right)\,.
%  \end{equation*}

Let $\tau(a)\in\ZZ_p^*$ be the Teichmuller lift of $a$.
For each integer $n\geq 1$, define a polynomial
$$
P_{n}(T) = 
   \sum_{a=1}^{p-1} \left( \sum_{j=0}^{p^{n-1}-1} \mu_{E}
      \left(\tau(a)(1+p)^j + p^n\ZZ_p\right) \cdot (1+T)^j \right).
$$
\begin{prop}
We have that the $p$-adic limit of these polynomials is the $p$-adic
$L$-series:
$$
   \lim_{n\to\infty} P_n(T) = \LL_{\alpha}(E, T).
$$
\end{prop}


This convergence is coefficient-by-coefficient, in the sense that
if
$P_{n}(T) = \sum_j a_{n,j} T^j$ and 
$\LL_{\alpha}(E,T) = \sum_j a_j T^j$, then
$$
\lim_{n \to \infty} a_{n,j} = a_j.
$$ 
We now give a proof of this convergence and in doing so obtain an
upper bound for $|a_j - a_{n,j}|$.



For any choice $\zeta_r$ of $p^r$-th root  
of unity in $\CC_p$, 
let $\chi_r$ be the $\CC_p$-valued 
character of $\ZZ_p^\times$ of order $p^r$ which
factors through $1+p\ZZ_p$ and sends $1+p$ to $\zeta_r$.
%$g(\chi_r)$ is the Gauss sum.  
Note that the conductor of $\chi_r$ is $p^{r+1}$.

\begin{lem}\label{lem:rval}
Let $\zeta_r$ be a $p^r$-th root of unity with
$1 \leq r \leq n-1$, and let $\chi_r$ be
the corresponding character of order $p^{r+1}$,
as above.  Then
$$
  P_{n}(\zeta_r-1) = \int_{\ZZ_p^\times} \chi_r ~d\mu_{E}
$$
In particular, note that the right hand side does not depend on $n$.
\end{lem}
\begin{proof}
Writing $\chi=\chi_r$, we have
\begin{align*}
P_{n}(\zeta_r-1) 
&= \sum_{a=1}^{p-1} \sum_{j=0}^{p^{n-1}-1} \mu_{E}\left(\tau(a)(1+p)^j + p^n\ZZ_p\right) \cdot \zeta_r^j \\
&= \sum_{a=1}^{p-1} \sum_{j=0}^{p^{n-1}-1} \mu_{E}\left(\tau(a)(1+p)^j + p^n\ZZ_p\right) \cdot \chi\left((1+p)^j\right) \\
&= \sum_{ b \in (\ZZ/p^n\ZZ)^*} \mu_{E}\left(b + p^n\ZZ_p\right) \cdot \chi(b) \\
&= \int_{\ZZ_p^\times} \chi ~d\mu_{E}.
\end{align*}
In the second to the last equality, we use that
$$(\ZZ/p^n\ZZ)^* \isom (\ZZ/p\ZZ)^* \cross (1+p (\ZZ/p^n\ZZ))^*$$
to sum over lifts
of $b\in (\ZZ/p^n\ZZ)^*$ of the form $\tau(a)(1+p)^j$, i.e., a Teichmuller lift times
a power of $(1+p)^j$.
In the last equality, we use that $\chi$ has conductor $p^n$,
so is constant on the residue classes modulo $p^n$, i.e.,
the last equality is just the Riemann sums definition of the 
given integral.

%and thus the claim follows from the standard
%interpolation property \eqref{eq:interp} of the $p$-adic $L$-function.  
\end{proof}

%(Note that the conductor of the character $\chi_r$ is $p^{r+1}$.  This
%is part of the indexing problem and is the reason this claim is only
%true under the {\it strict} inequality $r<n$.)

For each positive integer $n$, let $w_n(T) = (1+T)^{p^n}-1$.
\begin{cor}\label{cor:div}
We have that
$$
w_{n-1}(T) \text{~divides~} P_{n+1}(T) - P_{n}(T).
$$
\end{cor}
\begin{proof} 
By Lemma~\ref{lem:rval},
$P_{n+1}(T)$ and $P_{n}(T)$ agree on 
$\zeta_j-1$ for $0 \leq j \leq n-1$
and any choice $\zeta_j$ of $p^j$-th root of unity,
so their difference vanishes on every
root of the polynomial
$w_{n-1}(T) = (1+T)^{p^{n-1}} - 1$.
The claimed divisibility follows, since
$w_{n-1}(T)$ has distinct roots. 
\end{proof}

\begin{lem}\label{lem:minval}
Let 
$f(T) = \sum_j b_j T^j$ and $g(T)=\sum_j c_j T^j$ 
be in $\O[T]$ with $\O$ a finite extension of $\ZZ_p$.  
If $f(T)$ divides $g(T)$, then 
$$
  \ord_p(c_j) \geq \min_{0 \leq i \leq j} \ord_p(b_i).
$$
\end{lem}
\begin{proof}
We have $f(T)k(T) = g(T)$.
The lemma follows
by using the definition of polynomial
multiplication and the non-archimedean property of $\ord_p$
on each coefficient of $g(T)$.
\end{proof}

As above, let $a_{n,j}$ be the $j$th coefficient of 
the polynomial $P_n(T)$.
Let
$$
   c_n = \max(0, - \min_j \ord_p(a_{n,j}))
$$ 
so that $p^{c_n} P_{n}(T) \in \ZZ_p[T]$, i.e., $c_n$
is the smallest power of $p$ that clears the denominator.
For any $j>0$,
let
$$
  e_{n,j} = \min_{1 \leq i \leq j} \ord_p \binom{p^n}{i}.
$$
be the min of the valuations of the coefficients of $w_{n}(T)$,
as in Lemma~\ref{lem:minval}.

\begin{prop}\label{prop:padicerr}
For all $n\geq 0$, we have
$
  a_{n+1,0} = a_{n,0},
$
and for $j>0$,
$$
\ord_p(a_{n+1,j} - a_{n,j}) \geq  e_{n-1,j} - \max(c_{n}, c_{n+1}).
$$
\end{prop}
\begin{proof}
Let $c = \max(c_{n},c_{n+1})$.
The divisibility of Corollary~\ref{cor:div} implies that there
is a polynomial $h(T)\in \Qp[T]$ with 
$$
w_{n-1}(T) \cdot p^{c} h(T) = p^{c} P_{n+1}(T) - p^{c}P_{n}(T)
$$
and thus (by Gauss' lemma) $p^{c} h(T) \in \ZZ_p[T]$ 
since the right hand side of the equation is integral and $w_{n-1}(T)$ 
is a primitive polynomial.
Applying Lemma~\ref{lem:minval} and renormalizing by $p^{c}$
gives the result.
\end{proof}

%If $p$ is an ordinary prime, then I guess $c_n = 0$ for all $n$
%(Christian should know this better than me -- maybe there is a problem
%with a denominator bounded independent of $n$ when the Galois
%representation isn't surjective.) For $p$ supersingular, $c_n =
%\frac{n+1}{2}$.

For $j$ fixed, $e_{n-1,j} - \max(c_{n+1}, c_n)$
goes to infinity as $n$ grows since the $c_k$ are uniformly
bounded (they are bounded by the power of $p$ that
divides the order of the cuspidal subgroup of $E$).
Thus, $\{ a_{n,j} \}$ is a 
Cauchy sequence and Proposition~\ref{prop:padicerr} implies that that
$$
  \ord_p(a_j - a_{n,j}) \geq  e_{n-1,j} - \max(c_{n+1},c_n).
$$

 
 \subsection{The $p$-adic multiplier}
 For a prime of good reduction, we define the $p$-adic multiplier by 
 \begin{equation}\label{epsp1}
  \epsilon_p = \left(1-\tfrac{1}{\alpha}\right)^2 \,.
 \end{equation}
 For a prime of bad multiplicative reduction, we put
 \begin{equation*}
  \epsilon_p = 1-\tfrac{1}{\alpha} =
   \begin{cases} 0\quad &\text{if $p$ is split multiplicative and } \\
  2 &\text{ if $p$ is non-split.}
   \end{cases}
 \end{equation*}
 
 \subsection{Interpolation property}
 The $p$-adic $L$-function constructed above satisfies a desired interpolation property with respect to the complex $L$-function. For instance, we have that
 \begin{equation*}
  \LL_{\alpha}(E,0) = L_{\alpha}(E,1) = \int_{\ZZ_p^\times} d\mu_{\alpha} = \epsilon_p \cdot\frac{L(E,1)}{\OmegaE}\,.
 \end{equation*}
A similar formula holds when integrating nontrivial characters of
$\ZZ_p^\times$ against $\mu_\alpha$. If $\chi$ is the character on
$\Ginf$ sending $\gamma$ to a root of unity $\zeta$ of exact order
$p^n$, then

 \begin{equation*}
  \LL_{\alpha}(E,\zeta-1) = \frac{1}{\alpha^{n+1}}\cdot \frac{p^{n+1}}{G(\chi^{-1})}\cdot \frac{L(E,\chi^{-1},1)}{\OmegaE}\,.
 \end{equation*}
Here $G(\chi^{-1})$ is the Gauss sum and $L(E,\chi^{-1},1)$ is the
Hasse-Weil $L$-function of $E$ twisted by $\chi^{-1}$.
 
 \subsection{The good ordinary case}\label{e0_sec}
Suppose now that the reduction of the elliptic curve at the prime $p$
is good and ordinary, so $a_p$ is not divisible by $p$.  As mentioned
before, in this case there is a unique choice of root $\alpha$ of the
characteristic polynomial $x^2 - a_p x + p$ that satisfies
$\ord_p(\alpha) < 1$.  Since $\alpha$ is an algebraic integer, this
implies that $\ord_p(\alpha)=0$, so $\alpha$ is a unit in $\ZZ_p$. We
get therefore a unique $p$-adic $L$-function that we will denote
simply by $\LL_p(E,T) = \LL_{\alpha}(E,T)$. The following is proved
in~\cite{wuthkato}:
 \begin{prop}
  Let $E$ be an elliptic curve with good ordinary reduction 
  at a prime $p > 2$. Then the series $\LL_p(E,T)$ belongs to $\ZZ_p[\![T]\!]$.
 \end{prop}
Note that $\ord_p(\epsilon_p)$ is equal to $2\,\ord_p(N_p)$ where $N_p=p+1-a_p$ is the number of points in the reduction $\tilde E(\FF_p)$ at $p$. % even when p=2 !!
 
 
We wish to illustrate the above material with a few numerical
examples, one for each type of reduction. See
Section~\ref{numerical_sec} for more examples. Let $E_0/\QQ$ be the
curve
 \begin{equation}\label{e0}
  E_0\colon\quad y^2 \,+\, x\,y \,=\, x^3\, - \,x^2\, - \,4\,x \,+\, 4
 \end{equation}
which is labeled 446d1 in Cremona's tables~\cite{cremona:tables}. The
Mordell-Weil group $E_0(\QQ)$ is isomorphic to $\ZZ^2$ generated by
the points $(2,0)$ and $(1,-1)$. We consider the prime $p=5$ where
$E_0$ has good and ordinary reduction. As the number of points
$N_p=10$ is divisible by $p$, this is an \emph{anomalous} prime in the
terminology of~\cite{mazur72}. Using \cite{sage}, we compute an approximation to the
$p$-adic $L$-series as explained above with $n=5$ to find
 \begin{align*}
  \LL_5(E_0,T) \, = \,& \bigO(5^4)\cdot T + (5 + 5^2 + 3\cdot 5^3 + \bigO(5^4))\cdot T^2 \\
                  & + (2\cdot 5 + 3\cdot 5^2 + 3\cdot 5^3 + \bigO(5^4))\cdot T^3  + (4\cdot 5^2 + 4\cdot 5^3 + \bigO(5^4))\cdot T^4 \\
                  & + (4\cdot 5 + 4\cdot 5^2 + \bigO(5^3))\cdot T^5 \\
                  & + (1 + 2\cdot 5 + 5^2 + 4\cdot 5^3 + \bigO(5^4))\cdot T^6 + \bigO(T^7)
 \end{align*}
Note that we claim here directly that the order of vanishing is at
least to $1$. This follows from the interpolation formula that
$\LL_5(E_0,0) = 0$ as $[0]^{+} = 0$. We will give an explanation for
the vanishing of the term in $T^1$ later. We remark that the term in
$T^2$ has valuation $1$, but the coefficient of $T^6$ is a unit.

\subsection{Multiplicative case}\label{e1_sec}
We have to separate the case of split from the case of non-split
multiplicative reduction. In fact if the reduction is non-split, then
the description of the good ordinary case applies just the same. But
if the reduction is split multiplicative (the ``exceptional case''
in~\cite{mtt}), then the $p$-adic $L$-series must have a trivial zero,
i.e., $\LL_p(E,0) = 0$ because $\epsilon_p =0$. By a result of
Greenberg and Stevens~\cite{grste} (see also~\cite{koblp} for a simple
proof using Kato's Euler system), we know that
\begin{equation*}
  \left.\frac{d\, \LL_p(E,T)}{d\,T}\right\vert_{T=0}  = \frac{1}{\log_p\kappa(\gamma)}\cdot \frac{\log_p(\qE)}{\ord_p(\qE)} \cdot \frac{L(E,1)}{\OmegaE}
\end{equation*}
where $\qE$ denotes the Tate period of $E$ over $\QQ_p$.  This will
replace the interpolation formula.  Note that it is now known thanks
to~\cite{steph} that $\log_p(\qE)$ is nonzero. Hence we define the
$p$-adic $\Linv$-invariant as
\begin{equation}\label{epsp2}
  \Linv_p = \frac{\log_p(\qE)}{\ord_p(\qE)} \neq 0\,.
\end{equation}
We refer to~\cite{colmezlinvariant} for a detailed discussion of the
different $\Linv$-invariants and their connections.
 
 \subsection{The supersingular case}\label{e2_sec}
In the supersingular case, that is when $a_p\equiv 0\pmod{p}$, we have
two roots $\alpha$ and $\beta$ both of valuation $\tfrac{1}{2}$. A
careful analysis of the functions $\LL_{\alpha}$ and $\LL_{\beta}$ can
be found in~\cite{pollack}. The series $\LL_{\alpha}(E,T)$ will not
have integral coefficients in $\QQ_p(\alpha)$. Nevertheless one can
still extract two integral series $\LL_p^{\pm}(E,T)$. We will not need
this description.
 
There is a way of rewriting the $p$-adic $L$-series which relates more
easily to the $p$-adic height defined in the next section. We follow
Perrin-Riou's description in~\cite{pr00}.
 
As before $\omegaE$ denotes the chosen invariant differential on
$E$. Let $\etaE=x\cdot \omegaE$. The pair $\{\omegaE,\etaE\}$ forms a
basis of the Dieudonn\'e module 
$$D_p(E) = \QQ_p\otimes\HH^1_{\text{dR}}(E/\QQ).$$
This $\QQ_p$-vector space comes
equipped with a canonical Frobenius $\varphi$ acting on it
linearly. We normalise it in the following way which makes it equal to
$\tfrac{1}{p}\cdot F$ with $F$ being the Frobenius as used
in~\cite{mst} or in~\cite{kedlaya:counting_mw, kedlaya:counting-errata, kedlaya:mw2}. 
Let $t$ be any uniformiser at
$\ZeroE$, like $t=-\tfrac{x}{y}$. Let $\nu$ be a class in $D_p(E)$
represented by the differential $\sum c_n \cdot t^{n-1} \, dt$ with
$c_n\in\QQ_p$. Then $\varphi(\nu)$ can be represented by the
differential $\sum c_n \cdot t^{pn-1}\, dt$. In particular
$\varphi(dt) \equiv t^{p-1}\,dt$. The characteristic polynomial of
$\varphi$ is equal to $X^2 - p^{-1}\,a_p \, X + p^{-1}$.
 
 
 Write $\LL_{\alpha}(E,T)$ as $G(T) + \alpha \cdot H(T)$ with $G(T)$
 and $H(T)$ in $\QQ_p[\![T]\!]$. Then we define
 \begin{equation*}
  \LL_p(E,T) = G(T)\cdot \omegaE + a_p \cdot H(T)\cdot \omegaE - p\cdot H(T)\cdot \varphi(\omegaE)\,.
\end{equation*}
This is a formal power series with coefficients in $D_p(E)\otimes
\QQ_p[\![T]\!]$ which contains exactly the same information as
$\LL_{\alpha}(E,T)$. See~\cite{pr00} for a direct definition.  Since
the invariant differential $\omegaE$ depends on the choice of the
Weierstrass equation~\eqref{w_eq}, the expression $\LL_p(E,T)$ is also
dependent on this choice. However, if we write the series in the basis
$\{\omegaE,\phi(\omegaE)\}$ rather than in $\{\omegaE,\etaE\}$, then
the coordinates as above are independent.  The $D_p$-valued $L$-series
satisfies again certain interpolation properties,\footnote{%
  Perrin-Riou writes in~\cite{pr00} the multiplier as
  $(1-\varphi)^{-1}\cdot (1-p^{-1}\varphi^{-1})$ and she multiplies
  the right hand side with $L(E/\QQ_p,1)^{-1}=N_p\cdot p^{-1}$. It is
  easy to see that $(1-\varphi)\cdot (1-p^{-1}\varphi^{-1}) = 1
  -\varphi + (\varphi - a_p \cdot p^{-1}) + p^{-1} = N_p\cdot p^{-1}$.
} e.g.,
 \begin{equation*}
  (1-\varphi)^{-2} \, \LL_p(E,0) = \frac{L(E,1)}{\OmegaE}\cdot \omegaE \quad\in D_p(E)\,.
 \end{equation*}
We will present a numerical example in Section~\ref{ex_ss_subsec}.
 
%% ----------------------------------------------

\subsection{Additive case}\label{additive_sec}%
The case of additive reduction is much harder to treat, though we are
optimistic that such a treatment is possible.  We have not tried to
include the possibility of additive reduction in our algorithm
especially because the existence of the $p$-adic $L$-function is not
yet guaranteed in general.  Note that there are two interesting
papers~\cite{delbourgo98} and~\cite{delbourgo02} of Delbourgo on this
subject. Also Colmez has recently announced a new construction of the
$p$-adic $L$-function which would include the additive case.  We will
not refer to this case anymore throughout the paper.
 
%% -------------------------------------------------------------------------

\section{$p$-adic heights}\label{hp_sec}

The second term to be generalized in the Birch-Swinnerton-Dyer formula
is the real-valued regulator.  In $p$-adic analogues of the conjecture
it is replaced by a $p$-adic regulator, which is defined using a
$p$-adic analogue of the height pairing. We follow here the
generalized version~\cite{prbe} and \cite{pr00}.
 
Let $\nu$ be an element of the Dieudonn\'e module $D_p(E)$. We will
define a $p$-adic height function $h_\nu\colon E(\QQ)\rTo \QQ_p$ which
depends linearly on the vector $\nu$. Hence it is sufficient to define
it on the basis $\omega=\omegaE$ and $\eta=\etaE$.
 
 If $\nu=\omega$, then we define 
 \begin{equation*}
  h_\omega(P)=-\logE(P)^2
 \end{equation*}
where $\logE$ is the linear extension of the $p$-adic elliptic
logarithm $$\log_{\hat E}\colon \hat E(p\ZZ_p)\rTo p\ZZ_p$$ defined on
the formal group $\hat E$, by integrating our fixed differential
$\omegaE$.
 
For $\nu=\eta$, we define the $p$-adic sigma function of Bernardi
as in~\cite{bernardi} to be the solution $\sigma$ of the differential
equation
 \begin{equation*}
   - x  = \frac{d}{\omegaE}\left(\frac{1}{\sigma}\cdot\frac{d\sigma}{\omegaE}\right)
 \end{equation*}
such that $\sigma(\ZeroE)=0$, $\frac{d\sigma}{\omega}(\ZeroE) =1$, and
$\sigma(-P)=-\sigma(P)$. If we denote by $t=-\tfrac{x}{y}$ the
uniformiser at $\ZeroE$, we may develop the sigma-function as a series
in $t$:
 \begin{equation*}
  \sigma(t) = t + \frac{a_1}{2}\,t^2 + \frac{a_1^2+a_2}{3}\,t^3+\frac{a_1^3+2a_1a_2+3a_3}{4}\,t^4+\cdots  \in \QQ(\!(t)\!).
 \end{equation*}
As a function on the formal group $\hat E(p\ZZ_p)$, it converges for
all $t$ with $\ord_p(t) > \tfrac{1}{p-1}$.
 
We say that a point $P$ in $E(\QQ)$ has \emph{good reduction at a
  prime $p$} if $P$ reduces to the identity component of the special
fiber of the N\'eron model of $E$ at $p$.  Given a point $P$ in
$E(\QQ)$ there exists a multiple $m\cdot P$ such that $\sigma(P)$
converges and such that $m\cdot P$ has good reduction at all
primes. Denote by $e(m\cdot P)\in\ZZ$ the square root of the
denominator of the $x$-coordinate of $m\cdot P$.  Now define
  \begin{equation*}
   h_{\eta}(P) = \frac{2}{m^2} \cdot \log_p\left (\frac{\sigma(m\cdot P)}{e(m\cdot P)}\right )\,.
  \end{equation*}
It is proved in~\cite{bernardi} that this function is quadratic and
satisfies the parallelogram law.
 
Finally, if $\nu= a\, \omega+b\,\eta$ then put
  \begin{equation*}
   h_\nu(P) = a \, h_{\omega}(P) + b\, h_{\eta}(P)\,.
  \end{equation*}
Since this function is quadratic and satisfies the parallelogram law,
it induces a bilinear symmetric pairing
$\langle\cdot,\cdot\rangle_{\nu}$ with values in $\QQ_p$ defined by
  \begin{equation*}
   \langle P,Q\rangle_\nu = \frac{1}{2}\cdot\bigl( h_{\nu}(P+Q) - h_{\nu}(P) - h_{\nu}(Q) \bigr)\,.
  \end{equation*}
Note that all these definitions are dependent on the choice of the
Weierstrass equation. It is easy to verify that the pairing is zero if
one of the points is a torsion point.
  
  
  \subsection{The good ordinary case}
Since we have only a single $p$-adic $L$-function in the case that the
reduction is good ordinary, we have also to pin down a canonical
choice of a $p$-adic height function. This was first done by
Schneider~\cite{schneider1} and Perrin-Riou~\cite{pr82}. We refer
to~\cite{mt} and~\cite{mst} for more details.
  
Let $\nu_{\alpha}= a \, \omega + b\,\eta$ be an eigenvector of
$\varphi$ on $D_p(E)$ associated to the eigenvalue
$\tfrac{1}{\alpha}$. The value $e_2 =\mathbf{E}_2(E,\omegaE) =
-12\cdot \tfrac{a}{b}$ is the value of the Katz $p$-adic Eisenstein
series of weight $2$ at $(E,\omegaE)$.  Then, if a point $P$ has good
reduction at all primes and lies in the range of convergence of
$\sigma(t)$, we define the canonical $p$-adic height of $P$ to be
  \begin{align}
   \hat h_p (P) &= \frac{1}{b}\cdot h_{\nu_{\alpha}}(P) \notag\\ 
   				&= -\frac{a}{b} \cdot \logE(P)^2 +2\, \log\left (\frac{\sigma(P)}{e( P)}\right ) \notag\\
				&= 2\,\log_p \left ( \frac{\exp(\frac{e_2}{24} \logE(P)^2)\cdot \sigma(P)}{e(P)} \right) = 2\, \log_p \left ( \frac{\sigma_p(P)}{e(P)} \right)\,. \label{hp_eq}
\end{align} 

The function $\sigma_p$, defined by the last line, is called the
canonical sigma-function, see~\cite{mt}; it is known to lie in
$\ZZ_p[\![t]\!]$.  The $p$-adic height defined here is up to a
factor of $2$ the same as in~\cite{mst}.\footnote{This factor is
  needed if one does not want to modify the $p$-adic version of the
  Birch and Swinnerton-Dyer Conjecture~\ref{pbsd_ord_con}.}  It is
also important to note that the function $\hat h_p$ is now independent
of the Weierstrass equation.
  
We write $\langle \cdot,\cdot\rangle_p$ for the canonical $p$-adic
height pairing on $E(\QQ)$ associated to $\hat h_p$, and we write
$\Reg_p(E/\QQ)$ for the discriminant of the height pairing on
$E(\QQ)/E(\QQ)_{\tor}$.
  
\begin{conjecture}{Schneider~\cite{schneider1}}\label{conreg_con}
  The canonical $p$-adic height is non-de\-ge\-ne\-ra\-te on 
  $E(\QQ)/E(\QQ)_{\tor}$. In other words, the canonical $p$-adic regulator
  $\Reg_p(E/\QQ)$ is nonzero.
\end{conjecture}
  
Apart from the special case treated in~\cite{bertrand} of curves with
complex multiplication of rank $1$, there are hardly any results on
this conjecture. See also~\cite{wuth04}.

%ex
We return to our example $E_0$ from Section~\ref{e0_sec}. The methods
of~\cite{mst, harvey:padicheights} permit us to compute the $p$-adic
regulator of $E_0$ quite quickly.  We have
\begin{equation*}
 \mathbf{E}_2(E_0,\omegaE) = 3\cdot 5 + 4\cdot 5^2 + 5^3 + 5^4 + 5^5 + 2\cdot 5^6 + 4\cdot 5^7 + 3\cdot 5^9 + \bigO(5^{10}),
\end{equation*}
and the regulator associated to the canonical $p$-adic height is
\begin{equation*}
 \Reg_p(E_0/\QQ) = 2\cdot 5 + 2\cdot 5^2 + 5^4 + 4\cdot 5^5 + 2\cdot 5^7 + 4\cdot 5^8 + 2\cdot 5^9 + \bigO(5^{10}).
\end{equation*}

\subsection{The multiplicative case}\label{height_mult_subsec}
When $E$ has multiplicative reduction at $p$, we may use Tate's $p$-adic
uniformization (see for instance in~\cite{sil2}). We have an explicit
description of the height pairing in~\cite{schneider1}. If one wants
to have the same closed formula in the $p$-adic version of the Birch
and Swinnerton-Dyer conjecture for multiplicative primes as for other
ordinary primes, the $p$-adic height has to be changed slightly. We
use here the description of the $p$-adic regulator given in section
II.6 of~\cite{mtt}. Alas, their formula is not correct as explained by
Werner in~\cite{werner}.
  
Let $\qE$ be the Tate parameter of the elliptic curve over $\QQ_p$,
i.e., we have a homomorphism $\psi\colon \bar\QQ_p^\times \rTo
E(\bar\QQ_p)$ whose kernel is precisely $\qE^\ZZ$. The image of
$\ZZ_p^\times$ under $\psi$ is equal to the subgroup of points of
$E(\QQ_p)$ lying on the connected component of the reduction modulo $p$
of the N\'eron model of $E$. Now let $C$ be the constant such that $\psi^*(\omegaE) = C \cdot
\frac{du}{u}$ where $u$ is a uniformiser of $\QQ_p^\times$ at $1$. The
value of the $p$-adic Eisenstein series of weight~2 can then be
computed as
\begin{equation*}
   e_2 =\mathbf{E}_2(E,\omegaE) = C^2 \cdot\left ( 1- 24 \cdot \sum_{n\geq 1 } \sum_{d\mid n} d. \cdot \qE^n \right )\,.
\end{equation*}
Then we use the formula as in the good ordinary case to define the
canonical sigma function $\sigma_p(t(P)) = \exp(\frac{e_2}{24}
\logE(P)^2)\cdot \sigma(t(P))$. We could also have used directly the
formula
\begin{equation*}
 \sigma_p(u) = \frac{u - 1}{u^{1/2}}\cdot\prod_{n\geq 1} \frac{ (1-\qE^n\cdot u)(1-\qE^n /u)}{(1-q^n)^2}
\end{equation*}
where $u\in 1+p\ZZ_p$ is the unique preimage of $P\in
\widehat{E}(p\ZZ_p)$ under the Tate parametrization~$\psi$,
where $\widehat{E}$ is the formal group of $E$ at $p$.

If the reduction is non-split multiplicative, then we use the same
formula~\eqref{hp_eq} to define the $p$-adic height as for the good
ordinary case.
  
Suppose now that the reduction is split multiplicative.  Let $P$ be a
point in $E(\QQ)$ having good reduction at all finite places and with
trivial reduction at $p$. Then we define
\begin{equation*}
  \hat h_p(P) = 2 \log_p\left ( \frac{\sigma_p(t(P))}{e(P)} \right) + \frac{\log_p(u)^2}{\log_p(\qE)}
\end{equation*} 
with $u$ as above.  The $p$-adic regulator is
formed as before but with this modified $p$-adic height~$\hat h_p$.

\subsection{The supersingular case}
In the supersingular case, we cannot find a canonical $p$-adic height
with values in $\QQ_p$. Instead, the height will have values in the
Dieudonn\'e module $D_p(E)$.  The main references for this height
are~\cite{prbe} and~\cite{pr00}.
  
First, if the rank of the curve is $0$, we define the $p$-adic
regulator of $E/\QQ$ to be $\omega=\omegaE\in D_p(E)$. Assume for the
rest of this section that the rank $r$ of $E(\QQ)$ is positive.  Let
$\nu = a\,\omega + b\,\eta$ be any element of $D_p(E)$ not lying in
$\QQ_p\,\omega$, (so $b\neq 0$).  It can be easily checked that the
value of
\begin{equation*}
  H_p(P) = \frac{1}{b} \cdot ( h_{\nu}(P) \cdot\omega - h_{\omega}(P)\cdot \nu )\quad\in D_p(E)
\end{equation*}
is independent of the choice of $\nu$. We will call this the
$D_p$-valued height on $E(\QQ)$. But note that it depends on the
choice of the Weierstrass equation of $E$: If we change coordinates
by putting $x'=u^2\cdot x +r$ and $y'=u^3\cdot y +s \cdot x +t$, then
the $D_p$-valued height $H'_p(P)$ computed in the new coordinates
$x'$, $y'$ will satisfy $H'_p(P) = \tfrac{1}{u}\cdot H_p(P)$ for all
points $P\in E(\QQ)$.
  
On $D_p(E)$ there is a canonical alternating bilinear form
$[\cdot,\cdot]$ characterized by the property that
$[\omegaE,\etaE]=1$.  Write $\Reg_{\nu}\in\QQ_p$ for the regulator of
$h_{\nu}$ on $E(\QQ)/E(\QQ)_{\tor}$. Then we have the following lemma
which is the correction\footnote{The wrong normalization
  in~\cite{pr00} only influences the computations with curves of rank
  greater than 1. It seems that, by chance, the computations in~\cite{pr00}
  were done with a $\nu$ in $D_p(E)$ such that $[\omega,\nu]=1$, so
  that the normalization did not enter the end results.}  of Lemme~2.6
in~\cite{pr00}.
\begin{lem}\label{reg_lem}
  Suppose that the rank $r$ of $E(\QQ)$ is positive.
  There exists a unique element $\Reg_p(E/\QQ)$ in $D_p(E)$ such that
  for all $\nu\in D_p(E)$, we have
  \begin{equation}\label{reg_eq}
   [\Reg_p(E/\QQ),\nu] = \frac{\Reg_{\nu}}{[\omega,\nu]^{r-1}}
  \end{equation}
  Furthermore, if the rank $r$ is $1$, then $\Reg_p(E/\QQ) = H_p(P)$
  for a generator $P$.  If the Weierstrass equation is changed as
  above, the regulator $\Reg_p'(E/\QQ)$ computed in the new equation
  satisfies $\Reg_p'(E/\QQ)= \tfrac{1}{u}\cdot \Reg_p(E/\QQ)$.
\end{lem}
 We call $\Reg_p(E/\QQ)\in D_p(E)$ the $D_p$-valued regulator of
 $E/\QQ$, or better, of the chosen Weierstrass equation.
\begin{proof}
 Since $h_{\omega}$ is made out of the square of the linear function
 $\logE$, the matrix of the associated pairing on a basis $\{P_i\}$ of
 $E(\QQ)$ modulo torsion has entries of the form $-\logE(P_i)\cdot
 \logE(P_j)$ and hence has rank $1$. Therefore the regulator of the
 pairing associated to $\nu = a\cdot \omega + b\cdot \eta$ is equal to
 \begin{equation*}
  \Reg_{a\omega+b\eta} = a\cdot b^{r-1} \cdot X + b^r \cdot Y
 \end{equation*}
 for some constants $X$ and $Y$. Actually we have $Y = \Reg_{\eta}$
 and $X=\Reg_{\omega+\eta}-\Reg_{\eta}$. Therefore the expression on
 the right hand side of~\eqref{reg_eq} is linear in $\nu$. More
 explicitly, we may define
 \begin{equation*}
  \Reg_p(E/\QQ) = Y\cdot \omega - X\cdot \eta.
 \end{equation*}
 The formula for the case of rank $1$ is then also immediate. The
 variance of the regulator with the change of the equation can be
 checked just as for $H_p$.
\end{proof} 
  
Define the \emph{fine Mordell-Weil group} as in~\cite{wuthfine} to be the
kernel
\begin{equation*}
   \mathfrak{M}(E/\QQ) = \ker\left(E(\QQ)\otimes \ZZ_p\rTo E(\QQ_p)^{\text{$p$-adic completion}} \right)
\end{equation*}
which is a free $\ZZ_p$-module of rank $r-1$.  The bilinear form
associated to the normalized $p$-adic height
\begin{equation*}
 \frac{h_{\nu}(P)}{[\omega,\nu]},
\end{equation*}
 can be restricted to 
\begin{equation*}
 \langle\cdot,\cdot\rangle_0\colon \mathfrak{M}(E/\QQ) \times (E(\QQ)\otimes\ZZ_p) \rTo \QQ_p\,.
\end{equation*}
It is then independent of the choice of $\nu\not\in\QQ_p\omega$.  We
call the regulator of this bilinear form $\langle\cdot,\cdot\rangle_0$
on a basis of $\mathfrak{M}(E/\QQ)$ the fine regulator
$\Reg_0(E/\QQ)\in\QQ_p$, which is an element of $\QQ_p$ defined up to
multiplication by a unit in $\ZZ_p$.
  
\begin{lem}\label{finereg_lem}
 Let $Q$ be a generator of the orthogonal complement of $\mathfrak{M}(E/\QQ)$ in $E(\QQ)\otimes\ZZ_p$. Then
 \begin{equation*}
  \Reg_p(E/\QQ) \equiv \Reg_0(E/\QQ) \cdot H_p(Q) \pmod{\ZZ_p^\times}.
 \end{equation*}
\end{lem}
\begin{proof}
 Choose a $\ZZ_p$-basis of $E(\QQ)\otimes\ZZ_p$ containing $Q$ and a
 basis of $\mathfrak{M}(E/\QQ)$. Then $\Reg_{\nu}$ is, up to
 multiplication by a unit in $\ZZ_p$, equal to
 $\Reg_{\nu}(\mathfrak{M})\cdot h_{\nu}(Q)$, where
 $\Reg_{\nu}(\mathfrak{M})$ is the regulator of
 $\langle\cdot,\cdot\rangle_{\nu} = \langle\cdot,\cdot\rangle_0\cdot
 [\omega,\nu]$ on $\mathfrak{M}(E/\QQ)$. Hence
 \begin{equation*}
  \frac{\Reg_{\nu}}{[\omega,\nu]^{r-1}} \equiv \Reg_0(E/\QQ)\cdot h_{\nu}(Q)\pmod{\ZZ_p^\times}
 \end{equation*}
 and the statement follows from the previous lemma.
\end{proof}
    
In particular, the $D_p$-valued regulator is 0 if and only if the fine
regulator vanishes.
  
 \begin{conjecture}{Perrin-Riou~\cite[Conjecture 3.3.7.i]{prfourier93}}\label{conreg_ss_con}
   The fine regulator of $E/\QQ$ is nonzero for all primes $p$. In
   particular, $\Reg_p(E/\QQ)\neq 0$ for all primes where $E$ has
   supersingular reduction.
  \end{conjecture}
 
We have presented here how to compute the $p$-adic regulator in the
basis $\{\omega,\eta\}$, but in order to compare it later to the
leading term of the $p$-adic $L$-function, it is better to write it in
terms of the basis $\{\omega,\varphi(\omega)\}$. In particular, we would then
have a vector whose coordinates are independent of the chosen
Weierstrass equation.
 
On page 232 of~\cite{prbe}, there is an algorithm for computing
$\varphi$ by successive approximation using the developpment of
$\omega$ in terms of a uniformiser $t$. We can now replace this by the
computation of $\varphi$ using the cohomology of Monsky and Washnitzer
as explained in~\cite{kedlaya:counting_mw, kedlaya:counting-errata, kedlaya:mw2}.
 
\subsection{Normalization}
In view of Iwasawa theory, it is actually natural to normalize the
heights and the regulators depending on the choice of the generator
$\gamma$. In this way the heights depend on the choice of an
isomorphism $\Gamma\rTo\ZZ_p$ rather than on the $\ZZ_p$-extension
only.  This normalization can be achieved by simply dividing $\hat
h_p(P)$ and $h_{\nu}(P)$ by $\kappa(\gamma)$. The regulators will be
divided by $\log_p\kappa(\gamma)^r$ where $r$ is the rank of $E(\QQ)$.
Hence we write
  \begin{equation*}
   \Reg_{\gamma}(E/\QQ) = \frac{\Reg_p(E/\QQ)}{\log(\kappa(\gamma))^r}
  \end{equation*}
%In the case the curve has split multiplicative reduction we replace the $r$ in the exponent of the denominator of the above formula by $r+1$. %%change in the conjecture by dividing the L-invariant. 

%% -------------------------------------------------------------------------
\section{The $p$-adic Birch and Swinnerton-Dyer conjecture}\label{pbsd_sec}

 \subsection{The ordinary case}
The following conjecture is due to Mazur, Tate and
Teitelbaum~\cite{mtt}. Rather than formulating it for the function
$L_{\alpha}(E,s)$, we state it directly for the series
$\LL_p(E,T)$. It is then a statement about the development of this
function at $T=0$ rather than at $s=1$.
 
 \begin{conjecture}{Mazur, Tate and Teitelbaum~\cite{mtt}}\label{pbsd_ord_con}
Let $E$ be an elliptic curve with good ordinary reduction or with
multiplicative reduction at a prime $p$.
  \begin{itemize}
  \item The order of vanishing of the $p$-adic $L$-function
    $\LL_p(E,T)$ at $T=0$ is equal to the rank $r$, unless $E$ has
    split multiplicative reduction at $p$ in which case the order of
    vanishing is equal to $r+1$.
  \item The leading term $\LL_p^{\ast}(E,0)$ satisfies 
  \begin{equation}\label{pbsd_ord_eq}
 \LL_p^{\ast}(E,0) =  \epsilon_p\cdot \frac{\prod_\vu c_\vu\cdot \#\Sha(E/\QQ)}{(\#E(\QQ)_{{\tor}})^2}\cdot\Reg_{\gamma}(E/\QQ)
  \end{equation}
  unless the reduction is split multiplicative in which case the leading term is
  \begin{equation}
 \LL_p^{\ast}(E,0) =  \frac{\Linv_p}{\log(\kappa(\gamma))}\cdot \frac{\prod_\vu c_\vu\cdot \#\Sha(E/\QQ)}{(\#E(\QQ)_{{\tor}})^2}\cdot\Reg_{\gamma}(E/\QQ),
  \end{equation}
where $\Linv_p$ is as in Equation \eqref{epsp2}.
  \end{itemize}
 \end{conjecture}
 
The conjecture assert exact equality, not just equality up to a
$p$-adic unit.  However, the current approaches to the conjecture,
which go via the main conjecture of Iwasawa theory, all prove results
up to a $p$-adic unit, since the characteristic power series is only
defined up to a unit, as we will see in Section~\ref{mainconjecture_sec}. 
 
 %ex
Again, we consider the curve $E_0$ (see Equation~\eqref{e0}) for an example in the good ordinary
case. For this curve, we have $\prod c_\vu = 2$ and $E_0(\QQ)_{\tor} =
0$. So all the terms in the expression above can now be computed
except for the unknown size of $\Sha(E_0/\QQ)$. The $p$-adic Birch and
Swinnerton-Dyer conjecture predicts now that
 \begin{equation*}
  \#\Sha(E_0/\QQ) = 1+ \bigO(5^3)
 \end{equation*}
just as the complex Birch and Swinnerton-Dyer conjecture claims that
$\#\Sha(E_0/\QQ) = 1$.

\subsection{The supersingular case}
The conjecture in the case of supersingular reduction is given
in~\cite{prbe} and~\cite{pr00}. The conjecture relates here an
algebraic and an analytic value in the $\QQ_p$-vector space $D_p(E)$
of dimension 2. The fact of having two coordinates was used cleverly
by Kurihara and Pollack in~\cite{kuriharapollack} to construct global
points via a $p$-adic analytic computation.
 
We say that an element $a(T)\cdot\omegaE + b(T)\cdot\etaE$ in
$D_p(E)\otimes \QQ_p[\![T]\!]$ has order $d$ at $T=0$ if $d$ is equal
to the minimum of the orders of $a(T)$ and $b(T)$.
 
 \begin{conjecture}{Bernardi and Perrin-Riou~\cite{prbe}}\label{pbsd_ss_con}
  Let $E$ be an elliptic curve with supersingular reduction at a prime $p$.
  \begin{itemize}
  \item The order of vanishing of the $D_p$-valued $L$-series
$\LL_p(E,T)$ at $T=0$ is equal to the rank $r$ of $E(\QQ)$.
  \item The leading term $\LL_p^{\ast}(E,0)$ satisfies 
  \begin{equation}\label{pbsd_ss_eq}
   \left (1-\varphi\right)^{-2}\cdot\LL_p^{\ast}(E,0)  =  \frac{\prod_\vu c_\vu\cdot\#\Sha(E/\QQ)}{(\#E(\QQ)_{\tor})^2}\cdot \Reg_{\gamma}(E/\QQ)\quad \in D_p(E)\,.
  \end{equation}
  \end{itemize}
 \end{conjecture}
It should be emphasized that both sides of the
formula~\eqref{pbsd_ss_eq} are dependant of the Weierstrass equation.
But under a change of the form $x'=u^2\cdot x+r$, they both get
multiplied by $\tfrac{1}{u}$ and hence the conjecture is independent
of this choice.

%% -------------------------------------------------------------------------
\section{Iwasawa theory of elliptic curves}\label{iwasawa_sec}
We suppose from now on that $p>2$.  Let $\QQinf$ be the cyclotomic
$\ZZ_p$-extension of $\QQ$, which is a Galois extension of $\QQ$ whose
Galois group is $\Gamma$. It is the unique $\ZZ_p$-extension of
$\QQ_p$. Let $\Lambda$ be the completed group algebra
$\ZZ_p[\![\Gamma]\!]$.  We use a fixed topological generator $\gamma$
of $\Gamma$ to identify $\Lambda$ with $\ZZ_p[\![T]\!]$ by sending
$\gamma$ to $1+T$.  It is well known that any finitely generated
$\Lambda$-module admits a decomposition up to quasi-isomorphism as a
direct sum of elementary $\Lambda$-modules. Denote by $\QQn$ the
$n$-th layer of the $\ZZ_p$-extension, so $\QQn$ is a subfield
of $\QQinf$ and $\Gal(\QQn/\QQ)\isom \ZZ/p^n\ZZ$. 
As before, we may define the
$p$-Selmer group over $\QQn$ by the exact sequence
 \begin{equation*}
  0\rTo \Sel_p(E/\QQn)\rTo \HH^1(\QQn,E(p))\rTo \bigoplus_\vu \HH^1(\QQn_\vu,E)
 \end{equation*}
with the product running
over all places $\vu$ of $\QQn$. Moreover, we define
$\Sel_p(E/\QQinf)$ to be the direct limit $\liminj \Sel_p(E/\QQn)$ following
the maps induced by the restriction maps $\HH^1(\QQn,E(p))\rTo
\HH^1(\QQnplusone,E(p))$. The group $\Sel_p(E/\QQinf)$ contains
essentially the information about the growth of the rank of $E(\QQn)$
and of the size of $\Sha(E/\QQn)(p)$ as $n$ tends to infinity. We will
consider the Pontryagin dual
 \begin{equation*}
  X(E/\QQinf) = \Hom\left(\Sel_p(E/\QQinf),\QZ\right)
 \end{equation*}
which is a finitely generated $\Lambda$-module (see~\cite{coatessujatha}).
 
 \subsection{The ordinary case}
Assume now that the reduction at $p$ is either good ordinary or of
multiplicative type.  Kato's Theorem~17.4 in~\cite{kato}, which uses
the work of Rohrlich~\cite{rohrlich}, states that $X(E/\QQinf)$ is a
torsion $\Lambda$-module. Hence by the decomposition theorem, we may
associate to it a characteristic series 
 \begin{equation}\label{fE_eq}
 \fE(T)\in\ZZ_p[\![T]\!]
 \end{equation}
that is well-defined up to multiplication by a unit in $\ZZ_p[\![T]\!]^{\!\times}$. 
 
In analogy to the zeta-function of a variety over a finite field, one
should think of $\fE(T)$ as a generating function encoding the growth
of the rank and the Tate-Shafarevich group. For instance, the zeros of
$\fE(T)$ at $T=\zeta-1$ with $\zeta$ a root of unity whose order is a
power of $p$ describe the growth of the rank. Since a non-zero power
series with coefficients in $\ZZ_p$ can only have finitely many zeros,
one can deduce that the rank of $E(\QQn)$ has to stabilize in the
tower $\QQn$. In other words, the Mordell-Weil group $E(\QQinf)$ is
still of finite rank.
 
The following result is due to Schnei\-der~\cite{schneider2} and
Perrin-Riou~\cite{pr82}. The multiplicative case is due to
Jones~\cite{jones89}. Note that he uses the analytic and algebraic
$p$-adic height defined by Schneider in~\cite{schneider1}; with the
mentioned correction by Werner they agree with our definition in
Section~\ref{height_mult_subsec}.
\begin{thm}[Schneider, Perrin-Riou, Jones]\label{perrinriouschneider_thm}
 The order of vanishing of $\fE(T)$ at $T=0$ is at least equal to the rank $r$.
 It is equal to $r$ if and only if the $p$-adic height pairing is non-degenerate 
(Conjecture~\ref{conreg_con}) and the $p$-primary part of the Tate-Shafarevich group $\Sha(E/\QQ)(p)$ is finite (Conjecture~\ref{consha_con}). In this case the leading term of the series $\fE(T)$ has the same valuation as
 \begin{equation*}
  \epsilon_p\cdot\frac{ \prod_\vu c_\vu\cdot \#\Sha(E/\QQ)(p)}
  {(\#E(\QQ)(p))^2}\cdot\Reg_{\gamma}(E/\QQ)
 \end{equation*}
 unless the reduction is split multiplicative in which case the same formula holds with $\epsilon_p$ replaced by $\Linv_p/\log(\kappa(\gamma))$.
\end{thm}

%ex
Let us consider again the curve $E_0$. We have computed the $5$-adic
regulator and found that it is non-zero. The above claims now that the
order of vanishing of $f_{E_0}(T)$ is at least equal to the rank. The
finiteness of $\Sha(E_0/\QQ)(5)$ is now equivalent to the statement
that the order of vanishing is equal to the rank. If it is the case
then the leading coefficient has valuation equal to
 \begin{equation*}
  \ord_5(f_{E_0}^{\ast}(0)) = 1 + \ord_5(\#\Sha(E_0/\QQ)(5))\,. 
 \end{equation*}
If the valuation of the leading term of $f_{E_0}(T)$ is positive we
call $p$ an \emph{irregular} prime for $E$. For irregular primes
either the Mordell-Weil rank of $E$ over $\QQinf$ is larger than the
rank of $E(\QQ)$ or the Tate-Shafarevich group $\Sha(E/\QQinf)$ is no
longer finite. We will later determine exactly what happens for $E_0$.
 
 \subsection{The supersingular case}
 
The supersingular case is much more complicated, since the
$\Lambda$-module $X(E/\QQinf)$ is not torsion. A very beautiful
approach to the supersingular case has been found by
Pollack~\cite{pollack} and Kobayashi~\cite{kobayashi}. As mentioned
above there exists two $p$-adic series $\LL_p^{\pm}(E,T)$ to which
will correspond two new Selmer groups $X^{\pm}(E/\QQinf)$ which now
are $\Lambda$-torsion. Despite the advantages of this $\pm$-theory, we
are using the approach of Perrin-Riou here. See Section~3
in~\cite{pr00}.
 
Let $\Tp E$ be the Tate module and define $\Hinfloc$ to be the
projective limit of the cohomology groups $\HH^1(\QQn_{\mf p},\Tp E)$
with respect to the corestriction maps. Here $\QQn_{\mf p}$ is the
localization of $\QQn$ at the unique prime $\mf p$ above
$p$. Perrin-Riou~\cite{prcol} has constructed a $\Lambda$-linear
Coleman map $\Col$ from $\Hinfloc$ to a sub-module of
$\QQ_p[\![T]\!]\otimes D_p(E)$.
 
Define the \emph{fine Selmer group} to be the kernel
 \begin{equation*}
  \Rel(E/\QQn) = \ker\left ( \Sel(E/\QQn) \rTo E(\QQn_{\mf p})\otimes\QZ\right)\,.
 \end{equation*}
It is again a consequence of the work of Kato, namely Theorem~12.4
in~\cite{kato}, that the Pontryagin dual $Y(E/\QQinf)$ of
$\Rel(E/\QQinf)$ is a $\Lambda$-torsion module. Denote by $\gE(T)$ its
characteristic series.
 
Let $\Sigma$ be any finite set of places in $\QQ$ containing the
places of bad reduction for $E$ and the places $\infty$ and $p$. By
$G_{\Sigma}(\QQn)$, we denote the Galois group of the maximal
extension of $\QQn$ unramified at all places which do not lie above
$\Sigma$. Next we define $\Hinfglob$ as the projective limit of
$\HH^1(G_{\Sigma}(\QQn),\Tp E)$. It is a $\Lambda$-module of rank $1$
and it is actually independent of the choice of $\Sigma$.
 
By Kato again, the $\Lambda$-module $\Hinfglob$ is torsion-free and
$\Hinfglob\otimes\QQ_p$ has $\Lambda\otimes\QQ_p$-rank 1.  Choose now
any element $\cinf$ in $\Hinfglob$ such that $Z_c
=\Hinfglob/(\Lambda\cdot \cinf)$ is $\Lambda$-torsion. Typically such
a choice could be the ``zeta element'' of Kato, i.e. the image of his
Euler system in $\Hinfglob$.
%\william{Huh?}\christian{The Euler system elements in the $\HH^1$ are called zeta elements in Kato. Do you want me to omit the sentence or write more about it?  William -- I would like more, if it isn't too hard to write.} 
 Write $h_c(T)$ for the characteristic series of $Z_c$. Then we define an algebraic equivalent of the $D_p(E)$-valued $L$-series by
 \begin{equation*}
  \fE(T) = \Col(\cinf)\cdot \gE(T)\cdot h_c(T)^{-1} \in \QQ_p[\![T]\!]\otimes D_p(E)
 \end{equation*}
where by $\Col(\cinf)$ we mean the image under the Coleman map $\Col$
of the localization of $\cinf$ to $\Hinfloc$. The resulting series
$\fE(T)$ is independent of the choice of $\cinf$. Of course, $\fE(T)$
is again only defined up to multiplication by a unit in
$\Lambda^{\!\times}$.

Again we have an Euler-characteristic result due to
Perrin-Riou~\cite{prfourier93}:

\begin{thm}[Perrin-Riou]\label{perrinriou_thm}
The order of vanishing of $\fE(T)$ at $T=0$ is at least equal to the
rank $r$.  It is equal to $r$ if and only if the $D_p(E)$-valued
regulator $\Reg_p(E/\QQ)$ is nonzero (Conjecture~\ref{conreg_ss_con})
and the $p$-primary part of the Tate-Shafarevich group
$\Sha(E/\QQ)(p)$ is finite (Conjecture~\ref{consha_con}). In this case
the leading term of the series $(1-\varphi)^{-2}\,\fE(T)$ has the same
valuation as
 \begin{equation*}
 \prod_\vu c_\vu\cdot \#\Sha(E/\QQ)(p)\cdot  \Reg_{p}(E/\QQ)\,.
 \end{equation*}
\end{thm}
Note that the proof of this theorem in the appendix of~\cite{pr00} for
the supersingular case uses the formula in lemma~\ref{finereg_lem}
rather than the wrong definition of the regulator.
%\christian{To be
%  honest I don't know if this proof is correct, I really should give a
%  new proof of this.}

Also we simplified the right hand term in comparison
to~\eqref{pbsd_ss_eq}, because $N_p\equiv 1 \pmod{p}$ and hence
$\#E(\QQ)_{\tor}$ must be a $p$-adic unit, since the reduction at~$p$
is supersingular.
 
%% -------------------------------------------------------------------------
\section{The Main Conjecture}\label{mainconjecture_sec}

The main conjecture links the two $p$-adic power
series~\eqref{Lpser_eq} and~\eqref{fE_eq} of the previous sections. We
formulate everything now simultaneously for the ordinary and the
supersingular case, even if they are of quite different nature.  We
still assume that $p\neq 2$.

\begin{conjecture}{Main conjecture of Iwasawa theory for elliptic curves}\label{mainconjecture_con}
 If $E$ has good or non-split multiplicative reduction at $p$, then
 there exists an element $u(T)$ in $\Lambda^{\!\times}$ such that
 $\LL_p(E,T) = \fE(T)\cdot u(T)$. If the reduction of $E$ at $p$ is
 split multiplicative, then there exists such a $u(T)$ in $T\cdot
 \Lambda^{\!\times}$.
\end{conjecture}

The statement of the main conjecture for supersingular primes is known
to be equivalent to Kato's formulation in Conjecture~12.10
in~\cite{kato} and to Kobayashi's version in~\cite{kobayashi}. In the
notations of the previous section, it can be reformulated by saying
that $\gE(T)=h_c(T)$ when $c$ is Kato's zeta element.

Much is now known about this conjecture.  To the elliptic curve $E$ we
attach the mod-$p$ representation
\begin{equation*}
 \bar\rho_p\colon \Gal(\bar \QQ/\QQ)\rTo \Aut(E[p])\approx \Gl_2(\FF_p)
\end{equation*}
of the absolute Galois group of $\QQ$.  Serre proved that $\bar\rho_p$
is almost always surjective (note that by hypothesis $E$ does not have
complex multiplication) and that for semi-stable curves surjectivity
can only fail when there is an isogeny of degree $p$ defined over
$\QQ$. See~\cite{serregl2} and~\cite{serrewiles}.

\begin{thmkato}\label{katodiv_thm} 
 Suppose that $E$ has semi-stable reduction at $p$ and that
 $\bar\rho_p$ is either surjective or that its image is contained in a
 Borel subgroup. Then there exists a series $d(T)$ in $\Lambda$ such
 that $\LL_p(E,T) = \fE(T)\cdot d(T)$. If the reduction is split
 multiplicative then $T$ divides $d(T)$.
\end{thmkato}

The main ingredient for this theorem is in Theorem 17.4 in~\cite{kato}
for the good ordinary case when $\bar\rho_p$ is surjective, or
in~\cite{wuthkato} when there is a $p$-isogeny. For the exceptional
case we refer to~\cite{koblp}.
%\christian{I have to omit the reference to~\cite{kkt} as I still
%haven't seen this eternal well-hidden preprint}.

In particular, the theorem applies to all odd primes $p$ if $E$ is a
semi-stable curve.  For the remaining cases, e.g., if the image of
$\bar\rho_p$ is contained in the normalizer of a Cartan subgroup, one
obtains only a weaker statement:
\begin{thmkato}\label{ncartan_thm}
  Suppose the image of $\bar\rho_p$ is not contained in a Borel
  subgroup of $\Gl_2(\FF_p)$ and that $\bar\rho_p$ is not surjective.
  Then there is an integer $m\geq 0$ such that $\fE(T)$ divides
  $p^m\cdot\LL_p(E,T)$.
\end{thmkato}

Greenberg and Vatsal~\cite{grvat} have shown that in certain cases the
main conjecture holds. There is hope that the main conjecture will be
proved soon for primes $p$ subject to certain conditions. We are
awaiting the forthcoming paper of Skinner and Urban.
 
\subsection{The examples}
%ex
Consider again the curve $E_0$ (see Equation~\eqref{e0}) and the good ordinary prime $p=5$. The
theorem of Kato shows that $f_{E_0}(T)$ divides $\LL_p(E_0,T)$. Since
we have found two linearly independent points of infinite order on
$E_0(\QQ)$, we know that the rank of $E_0(\QQ)$ is at least $2$. Hence
the order of vanishing of $f_{E_0}(T)$ at $T=0$ is at least $2$ and,
by the above theorem, so is the order of vanishing for
$\LL_p(E_0,T)$. But we have computed an approximation to
$\LL_p(E_0,T)$ showing that the order of vanishing can not be larger
than $2$. Therefore the rank of $E_0(\QQ)$ is equal to the order of
vanishing of the $p$-adic $L$-series.

But we know more now. The fact that the order of vanishing of
$f_{E_0}(T)$ is equal to $2$ shows that the $5$-primary part of
$\Sha(E_0/\QQ)$ can not be infinite. Comparing the
leading term of $\LL_p(E_0,T)$, which has valuation $1$, and the leading
term of $f_{E_0}(T)$, which has valuation
$1+\ord_5(\#\Sha(E_0/\QQ)(5))$, shows that \emph{the $5$-primary part
  of $\Sha(E_0/\QQ)$ is trivial}.

Moreover, the series $f_{E_0}(T)$ and $\LL_p(E_0,T)$ have now the same
leading term which implies that the main conjecture holds,
i.e. $f_{E_0}(T) \in \LL_p(E_0,T)\cdot\Lambda^{\times}$. It can be
shown by analyzing the series $\LL_p(E_0,T)$ that
\begin{equation*}
 \fE(T) = T \cdot ( (T+1)^5 - 1)\cdot u(T)
\end{equation*}
for a unit $u(T)\in\Lambda^\times$.  Let ${}_1\QQ$ be the first layer
of the $\ZZ_5$-extension of $\QQ$. Unless the Tate-Shafarevich group
$\Sha(E/{}_1\QQ)(5)$ is infinite, Iwasawa theory predicts now that the
rank of the Mordell-Weil group $E_0({}_1\QQ)$ is $6$.  Doing a quick
search it is easy to find points of infinite order in $E({}_1\QQ)$
which are not defined over $\QQ$. Therefore, we know that the rank of
$E({}_1\QQ)$ and of $E(\QQinf)$ is $6$ and that $\Sha(E_0/{}_1\QQ)(5)$
and $\Sha(E_0/\QQinf)(5)$ are finite. For more examples of such
factorisations of $p$-adic $L$-series we refer
to~\cite{pollacktables}.
 
 
 
%% -------------------------------------------------------------------------
\section{If the $L$-series does not vanish}\label{rank0_sec}
Suppose the Hasse-Weil $L$-function $L(E,s)$ does not vanish at
$s=1$. In this case Kolyvagin proved that $E(\QQ)$ and $\Sha(E/\QQ)$
are finite. In particular Conjecture~\ref{consha_con} is valid; also,
Conjectures~\ref{conreg_con} and~\ref{conreg_ss_con} are trivially
true in this case.

Let $p>2$ be a prime of semi-stable reduction such that the
representation $\bar\rho_p$ is either surjective or has image
contained in a Borel subgroup of $\Gl_2(\FF_p)$. By the interpolation
property, we know that $\LL_p(E,0)$ is nonzero, unless~$E$ has split
multiplicative reduction.
 
 \subsection{The good ordinary case}
 In the ordinary case  we have
 \begin{equation*}
  \epsilon_p^{-1}\cdot \LL_p(E,0) = \frac{L(E,1)}{ \OmegaE} = [0]^{+},
 \end{equation*}
which is a nonzero rational number by~\cite{manin}.  In the following
inequality, we use Theorem\footnote{In the case of analytic rank
  0, the theorem is actually relatively easy and well explained
  in~\cite{coatessujatha}.}~\ref{perrinriouschneider_thm} of
Perrin-Riou and Schneider for the first equality and Kato's
Theorem~\ref{katodiv_thm} on the main conjecture for the inequality in
the second line.%\william{What does it mean ``in the first line''? ``In the second line'' ??}\christian{better ?}
 \begin{align*}
  \ord_p \left (\epsilon_p\cdot\frac{ \prod_\vu c_\vu\cdot \#\Sha(E/\QQ)(p)}{(\#E(\QQ)(p))^2}\right) =&
  	\ord_p(\fE(0)) \\
	\leq& \ord_p(\LL_p(E,0)) \\
	&= \ord_p \left (\frac{L(E,1)}{ \OmegaE} \right)
	 + \ord_p(\epsilon_p)
 \end{align*}
Hence, we have the following upper bound on the $p$-primary part of
the Tate-Shafarevich group, which is sharp under the assumption of the
main conjecture:
 \begin{align}
  \ord_p \left(\# \Sha(E/\QQ)(p) \right)  \leq & \ord_p\left(\frac{L(E,1)}{\OmegaE}\right)-\ord_p\left(\frac{\prod c_\vu}{(\#E(\QQ)_{\tor})^2}\right)\notag \\ 
                                               &  = \ord_p(\#\Sha(E/\QQ)_{\an}).\label{sha_bound_r0_eq}
 \end{align}
This bound agrees with the Birch and Swinnerton-Dyer conjecture.
  
\subsection{The multiplicative case}
If the reduction is not split, then the above holds just the same,
because in all the theorems involved the non-split case never differs
form the good ordinary case (only the split multiplicative case is
exceptional).  If instead the reduction is split multiplicative, we
have that $\LL_p(E,0) =0$ and
  \begin{equation*}
   \LL_p'(E,0)=\frac{\Linv_p}{\log\kappa(\gamma)}\cdot\frac{L(E,1)}{ \OmegaE} =\frac{\Linv_p}{\log\kappa(\gamma)}\cdot [0]^{+} \neq 0\,.
  \end{equation*}
Since the $p$-adic multiplier is the same on the algebraic as on the
analytic side, we can once again compute it as above to obtain the
same bound~\eqref{sha_bound_r0_eq} again.
 
 \subsection{The supersingular case}
For the supersingular $D_p(E)$-valued series, we have
  \begin{equation*}
   (1-\varphi)^{-2}\cdot\LL_p(E,0) = \frac{L(E,1)}{ \OmegaE} \cdot \omegaE= [0]^{+} \cdot \omegaE
  \end{equation*} 
which is a nonzero element of $D_p(E)$.  The $D_p(E)$-valued regulator
$\Reg_p(E/\QQ)$ is equal to $\omegaE$. We may therefore concentrate
solely on the coordinate in $\omegaE$. Write $\ord_p(\fE(0))$ for the
$p$-adic valuation of the leading coefficient of the
$\omegaE$-coordinate of $\fE(T)$.  Again we obtain an inequality by
using Theorem~\ref{perrinriou_thm}
 \begin{align*}
  \ord_p \left( \prod_\vu c_\vu\cdot \#\Sha(E/\QQ)(p) \right) =&
  	\ord_p((1-\varphi)^{-2}\,\fE(0)) \\
	\leq& \ord_p((1-\varphi)^{-2}\,\LL_p(E,0)) \\
	&= \ord_p \left (\frac{L(E,1)}{ \OmegaE} \right)\,.
	 \end{align*}
So we have once again that $\#\Sha(E/\QQ)(p)$ is bounded from above by
the highest power of $p$ dividing $\#\Sha(E/\QQ)_{\an}$.

 \subsection{Conclusion}
Summarizing the above computations, we have
\begin{thm}[Kato, Perrin-Riou, Schneider]
 Let $E$ be an elliptic curve such that $L(E,1)\neq 0$. Then
 $\Sha(E/\QQ)$ is finite and
  \begin{equation*}
   \# \Sha(E/\QQ) \,\,\, \Big| \,\,\, C\cdot\frac{L(E,1)}{\OmegaE}\cdot\frac{(\#E(\QQ)_{\tor})^2}{\prod c_\vu}
  \end{equation*}
where $C$ is a product of a power of $2$ and of powers of primes of
additive reduction and of powers of primes for which the
representation $\bar\rho_p$ is not surjective and there is no isogeny
of degree $p$ on $E$ defined over $\QQ$.
  
In particular, if $E$ is semi-stable, then $C$ is a power of $2$.
 \end{thm}

This improves Corollary~3.5.19 in~\cite{eulersystems}.
 
%% -------------------------------------------------------------------------
 \section{If the $L$-series vanishes to the first order}\label{rank1_sec}

We suppose for this section that $E$ has good and ordinary reduction
at $p$ and that the complex $L$-series $L(E,s)$ has a zero of order
$1$ at $s=1$. The method of Heegner points and the theorem of
Kolyvagin show again that $\Sha(E/\QQ)$ is finite and that the rank of
$E(\QQ)$ is equal to $1$. Let $P$ be a choice of generator of the free
part of the Mordell-Weil group (modulo torsion).  Suppose that the
$p$-adic height $\hat h_p(P)$ is nonzero.  Thanks to a theorem of
Perrin-Riou in~\cite{prheegner}, we must have the following equality
of rational numbers
  \begin{equation*}
   \frac{1}{\Reg(E/\QQ)}\cdot \frac{L'(E,1)}{\OmegaE} =\frac{1}{\Reg_p(E/\QQ)}\cdot \frac{\LL_p'(E,0)}{(1-\tfrac{1}{\alpha})^2\cdot \log(\kappa(\gamma))} 
  \end{equation*}
where, on the left hand side, we have the canonical real-valued
regulator $\Reg(E/\QQ)=\hat h(P)$ and the leading coefficient of
$L(E,s)$, while, on the right hand side, we have the $p$-adic
regulator $\Reg_p(E/\QQ)=\hat h_p(P)$ and the leading term of the
$p$-adic $L$-series. By the conjecture of Birch and Swinnerton-Dyer
(or its $p$-adic analogue), this rational number should be equal to
$\prod c_\vu\cdot \#\Sha(E/\QQ)\cdot (\#E(\QQ)_{\tor})^{-2}$. By
Kato's theorem, one knows that the characteristic series $\fE(T)$ of
the Selmer group divides $\LL_p(E,T)$; at least up to a power of
$p$. Hence the series $\fE(T)$ has a zero of order $1$ at $T=0$ and
its leading term divides the above rational number in $\QQ_p$ (here we
use that $E(\QQ)$ has rank $1$ so $T\mid f_E(T)$).  We thus arrive at
the following theorem.
  \begin{thm}[Kato, Perrin-Riou]
    Let $E/\QQ$ be an elliptic curve with good ordinary reduction at
    the odd prime $p$.  Assume that the $p$-adic regulator of $E$ is
    nonzero.  Suppose that the representation $\bar\rho_p$ is
    surjective onto $\Gl_2(\FF_p)$ or that the curve admits an isogeny
    of degree $p$ defined over $\QQ$.  If $L(E,s)$ has a simple zero
    at $s=1$, then the $p$-primary part of $\Sha(E/\QQ)$ is finite and
    its valuation is bounded by
	\begin{equation*}
	 \ord_p(\# \Sha(E/\QQ)(p) )\leq \ord_p\left( \frac{(\#E(\QQ)_{\tor})^2}{\prod c_\vu}\cdot \frac{1}{\Reg(E/\QQ)}\cdot \frac{L'(E,1)}{\OmegaE} \right)\,.
	\end{equation*}
  \end{thm}

In other words the upper bound asserted by the Birch and
Swinnerton-Dyer conjecture if true up to a factor involving only bad
and supersingular primes, and primes for which the representation is
neither surjective nor has its image contained in a Borel subgroup.

The above theorem is valid only under the assumption that the
reduction is good ordinary. This is only this case when we know a proof of
the $p$-adic Gross-Zagier formula. It would be very interesting to
obtain a generalisation of this formula to the supersingular case.
%See also recent work of Dimitar Jetchev that bounds $\Sha$ from
%above 
%\christian{That would be a place to add something about Dimitar's results}

%% -------------------------------------------------------------------------


\section{The algorithm for an upper bound of the rank}\label{rankalgorithm_sec}

%\william{The procedure described in this section is {\em NOT} an algorithm.   It
%depends on ``the $p$-adic Birch and Swinnerton-Dyer conjecture tells us exactly what the needed precision should be'', but my understanding is that we do not know enough of that
%conjecture to read off this precision.  Thus given current theorems, we would never
%know when we're done.  So this section is not about an algorithm -- or it is about
%an algorithm that is conditional on knowing the $p$-adic BSD conjecture. Please clarify.}

%\christian{I agree. So I changed it, but I am not very good in writing such things. Maybe a formal algorithm would be better}
%\old{
% Here is the old version.

%Let $E/\QQ$ be an elliptic curve.
%Suppose we are in the situation that we have found $n$ linearly independent points. We wish to prove that $n$ is equal to the rank $r=\rk(E(\QQ))$. 

%For this purpose, we choose a prime $p$ satisfying the following conditions
%\begin{itemize}
%  \item $p > 2$,
%  \item $E$ has good reduction at $p$.
%\end{itemize}
%By computing the analytic $p$-adic $L$-function $\LL_p(E,T)$ to a certain precision, we find an upper bound, say $b$, on the order of vanishing of $\LL_p(E,T)$ at $T=0$. Then
%\begin{equation*}
% b\,\geq \,\ord_{T=0} \LL_p(E,1) \,\geq\, \ord_{T=0} \fE(T)\, \geq\, r
%\end{equation*}
%by Kato's theorem~\ref{katodiv_thm} and by the theorems~\ref{perrinriouschneider_thm} and~\ref{perrinriou_thm}. Hence we have an upper bound on the rank $r$. In case $b$ is different from $n$, we can either increase the precision or we can change the prime $p$. Note that the $p$-adic Birch and Swinnerton-Dyer conjecture tells us exactly what the needed precision should be for being able to distinguish the leading coefficient from zero.
%}

Let $E/\QQ$ be an elliptic curve. We now have a possibility of
computing upper bounds on the rank $r$ of the Mordell-Weil group
$E(\QQ)$. For this purpose, we choose a prime $p$ satisfying the
following conditions:
\begin{itemize}
  \item $p > 2$,
  \item $E$ has good reduction at $p$.
\end{itemize}
By computing the analytic $p$-adic $L$-function $\LL_p(E,T)$ to a
certain precision, we find an upper bound, say $b$, on the order of
vanishing of $\LL_p(E,T)$ at $T=0$. Note that a theorem of
Rohrlich~\cite{rohrlich} guarantees that $\LL_p(E,T)$ is not
zero. Then
\begin{equation*}
 b\,\geq \,\ord_{T=0} \LL_p(E,T) \,\geq\, \ord_{T=0} \fE(T)\, \geq\, r
\end{equation*}
by Kato's Theorems~\ref{katodiv_thm} and~\ref{ncartan_thm} and by the
theorems~\ref{perrinriouschneider_thm} and~\ref{perrinriou_thm}. Hence
we have an upper bound on the rank $r$.

\begin{prop}
 The computation of an approximation of the $p$-adic $L$-series of $E$
 for an odd prime $p$ of good reduction produces an upper bound on the
 rank $r$ of the Mordell-Weil group $E(\QQ)$.
\end{prop}

By searching for points of small height on $E$ at the same time, one
obtains also a lower bound on the rank $r$. Simultaneously one can
increase the precision of the computation of the $p$-adic $L$-function
in order to try to lower the bound $b$. Eventually the lower bound is
equal to the upper bound, unless the $p$-adic Birch and
Swinnerton-Dyer Conjecture~\ref{pbsd_ord_con} or~\ref{pbsd_ss_con} is
false. This is very similar to the algorithm described in
Proposition~\ref{bsdalgorithm_prop}, except that we do know here that
our upper bounds are unconditional. But we do not know if the
algorithm terminates after finitely many steps. Summarizing we can
claim the following.

\begin{prop}
Let $E$ be an elliptic curve, and assume that there is a prime $p$ of
good reduction such that the $p$-adic Birch and Swinnerton-Dyer
conjecture is true. Then there is an algorithm that computes the rank
$r$ of $E$ using $p$-adic $L$-functions.
\end{prop}

Of course, the algorithm for computing bounds on the rank $r$ using
$m$-descents has the same properties: It tries to determine the rank
by searching for points and by bounding $r$ from above by the rank of the
various $m$-Selmer groups.  Unless all the $p$-primary parts of the
Tate-Shafarevich group are infinite this algorithm returns the rank~$r$ after a
finite number of steps.

But the two algorithms are fundamentally different, since the $m$-descent
algorithm is fast and there are optimized implementations for
$m=2,3,4$, but it would be extremely time-consuming for larger $m$,
e.g., $m \geq 7$.  (In fact, nobody has yet implemented and run a
program that computes general $7$-descents.)


\subsection{Technical remarks}
The second condition on the prime $p$ is too strict. We may actually
allow primes of multiplicative reduction, too. Of course in the
exceptional case, when $E$ has split multiplicative reduction, the
upper bound $b$ on the order of vanishing of the $p$-adic $L$-function
$\LL_p(E,T)$ at $T=0$ satisfies $b\geq r+1$.

Note that, assuming that the $p$-adic Birch and Swinnerton-Dyer
conjecture holds, it is easy to predict the needed precision in the
computation of the $p$-adic $L$-series. So one can actually compute
immediately with the precision which should be sufficient and
concentrate on the search of points of small heights.

For all practical purposes, one has to take $p$ as small as possible.
The computation of the leading term of $\LL_p(E,T)$ for curves of
higher rank $r$ is very time-consuming for large $p$. Also one should
avoid primes $p$ with supersingular or split multiplicative reduction
as there the needed precision is much higher and the computation of
$b$ is much slower.  

%\william{The magnitude of the conductor is much
%  more directly important here than in the descent case...}

Also the speed of the computation of $\LL_p(E,T)$ using modular
symbols depends on the size of the conductor. As the conductor grows,
the determination of the rank, when it is larger than $1$, using the
descent method becomes much more efficient than the use of $p$-adic
$L$-series.  However, using $p$-adic $L$-series may provide an
advantage when considering families of quadratic twists. 

%\william{A key point we haven't mentioned is that descent provides
%a powerful method for actually {\em searching} for points.  These
%$p$-adic methods don't provide that.}

Another advantage to the descent method is that the determination of
the $m$-Selmer group for some $m>1$ can be used for the search of
points of infinite order. If the elements of the Selmer group can be
expressed as coverings, it is much more efficient to search for
rational points on the coverings rather than on the elliptic curve
itself.



%------------------------------------------------------------------------
\section{The algorithm for the Tate-Shafarevich group}\label{shaalgorithm_sec}
%\christian{This is rewritten, too.}\old{
%Suppose now that $E$ is an elliptic curve and $p$ is a prime satisfying the following conditions
% \begin{itemize}
%   \item $p > 2$,
%   \item $E$ has good reduction at $p$.
%   \item The image of $\bar\rho_p$ is either the full group $\Gl_2(\FF_p)$ or it is contained in a Borel subgroup.
% \end{itemize}
% Note that these conditions apply to all but finitely many primes $p$.
% 
% Suppose further that the rank computation presented in the previous part of the algorithm was successful (for any prime not necessarily $p$). We may assume that we are able to compute a basis of the full Mordell-Weil group $E(\QQ)$ modulo torsion.
% 
% Using the explicit basis of $E(\QQ)$ we can compute the $p$-adic regulator of $E$ over $\QQ$ using the efficient algorithm in~\cite{mst}. 
% 
% We compute the leading coefficient $\LL_p^{\ast}(E,0)$ of the analytic $p$-adic $L$-function.
% If the order of vanishing of $\LL_p(E,T)$ at $T=0$ is equal to $r$ then we know already that the $p$-primary part of the Tate-Shafarevich group is finite. Moreover, we get an upper bound. 
% 
% \subsection{The ordinary case}
% If $E$ has ordinary reduction at $p$, good or multiplicative, then 
% \begin{align*}
%  \ord_p( \#\Sha(E/\QQ)(p) ) = &  \ord_p(\fE^{\ast}(0)) + \ord_p\left(\frac{(\#E(\QQ)(p))^2}{\epsilon_p\cdot \prod_\vu c_\vu}\cdot\frac{1}{\Reg_{\gamma}(E/\QQ)}\right)  \\
%   \leq& \ord_p(\LL_p^{\ast}(E,0)) + 2\cdot\ord_p(\#(E(\QQ)(p)) -  \ord_p (\epsilon_p)\\
%   &\ - \sum_\vu\ord_p(c_\vu)-\ord_p(\Reg_{\gamma}(E/\QQ))
% \end{align*}
% The inequality uses Kato's theorem~\ref{katodiv_thm}.
% 
%  Note that if the main conjecture holds this inequality will be an equality. It should also be mentioned that Grigorov~\cite{grigorov} has found 
%  a way to compute
%  lower bounds on the order of the Tate-Shafarevich group in certain cases.
%  One can also use congruences (i.e., visibility) to construct elements
%  (see \cite{papersonvisibility}\christian{which ones ?}).\christian{I don't think this remark should be here. Of course, there are many ways of giving lower bounds on Sha, but Grigorov's method uses exactly the inequality here.}
% 
% \subsection{The supersingular case}
% Suppose now that $E$ has supersingular reduction at $p$. Then we may use theorem~\ref{perrinriou_thm} and theorem~\ref{katodiv_thm} to obtain
% \begin{align*}
% \ord_p( \#\Sha(E/\QQ)(p) ) = &  \ord_p(
% (1-\varphi)^{-2}\,\fE^{\ast}(0)) - \ord_p(\Reg_p(E/\QQ)) - \ord_p(\prod_\vu c_\vu)  \\
%  \leq& \ord_p((1-\varphi)^{-2}\,\LL_p^{\ast}(E,0))  - \ord_p(\Reg_p(E/\QQ))  - \sum_{\vu}\ord_p(c_\vu) 
%\end{align*}
%where the convention on $\ord_p(d(T))$ for an element $d(T)\in\QQ_p[\![T]\!]\otimes D_p(E)$ is as before. 
%Again the inequality can be replaced by an equality if the main conjecture holds for $E$ at $p$.
%}

The second algorithm that we are presenting here takes as input an
elliptic curve $E$ and a prime $p$ and tries to compute an upper bound
on the $p$-primary part of $\Sha(E/\QQ)$.  To be able to apply the
results in the previous section, we need the following conditions on
$(E,p)$:
\begin{itemize}
  \item $p > 2$,
  \item $E$ does not have additive reduction at $p$,
  \item and the image of $\bar\rho_p$ is either the full group
    $\Gl_2(\FF_p)$ or it is contained in a Borel subgroup of $\Gl_2(\FF_p)$. 
\end{itemize}
Note that, for any given curve $E$, these conditions apply to all but
finitely many primes $p$.

\begin{algorithm}{} Given an elliptic curve $E/\QQ$ and a prime $p$
  satisfying the above conditions, this procedure eithers gives an
  upper bound for $\#\Sha(E/\QQ)(p)$ or terminates with an error. 
\begin{steps}
\item{}\label{mwgroup_item} Determine the rank $r$ and the full
  Mordell-Weil group $E(\QQ)$. Exit with an error if we fail to do
  this.
\item{}\label{preg_item} Compute the $p$-adic regulator of $E$ over
  $\QQ$ using the efficient algorithm in~\cite{mst}. Exit with an
  error if the $p$-adic height pairing can not be shown to be
  non-degenerate.
\item{}\label{lp_item} Using modular symbols, compute an approximation
  of the leading term $\LL_p^{\ast}(E,0)$ of the $p$-adic $L$-function
  $\LL_p(E,T)$. If the order of vanishing $$\ord_{T=0}\LL_p(E,T)$$ is
  equal to $r$ (or $r+1$ if $E$ has split multiplicative reduction at
  $p$), then we print that $\Sha(E/\QQ)(p)$ is finite, otherwise we
  have to increase the precision of the computation of
  $\LL_p(E,T)$. It this fails to prove that $\ord_{T=0}\LL_p(E,T) = r$
  (or $r+1$), then exit with an error.
\item{}\label{end_item} Now compute the remaining information,
  including the Tamagawa numbers $c_{\vu}$ and the $p$-adic multiplier
  $\epsilon_p$. If $p$ is an good ordinary prime or a prime at which
  $E$ has non-split multiplicative reduction, then let
  \begin{align*}
     b_p = & \ord_p(\LL_p^{\ast}(E,0)) + 2\cdot\ord_p(\#(E(\QQ)(p))) -  \ord_p (\epsilon_p) \\
           & - \sum_\vu\ord_p(c_\vu)-\ord_p(\Reg_{\gamma}(E/\QQ))\, ,
  \end{align*} 
  if $p$ is supersingular, let
  \begin{equation*}
    b_p = \ord_p((1-\varphi)^{-2}\,\LL_p^{\ast}(E,0))  - \ord_p(\Reg_p(E/\QQ))  - \sum_{\vu}\ord_p(c_\vu)\, ,
  \end{equation*}
  and finally if $E$ has split multiplicative reduction at $p$, let
  \begin{align*}
   b_p & = \ord_p(\LL_p^{\ast}(E,0)) + 2\cdot\ord_p(\#(E(\QQ)(p)) -  \ord_p (\Linv_p) \\
       & - \sum_\vu\ord_p(c_\vu)-\ord_p(\Reg_{\gamma}(E/\QQ))\,.
  \end{align*}
 \item{} Output that $\#\Sha(E/\QQ)(p)$ is bounded by $p^{b_p}$.
\end{steps}
\end{algorithm}

\begin{proof}
  When arriving at Step~\ref{end_item}, we have shown that
  Conjecture~\ref{conreg_con} (or Conjecture~\ref{conreg_ss_con} in
  the supersingular case) on the non-degeneracy of the $p$-adic
  regulator holds and that $\Sha(E/\QQ)(p)$ is indeed finite by
  Theorem~\ref{perrinriouschneider_thm} (or
  Theorem~\ref{perrinriou_thm} in the supersingular case). Moreover
  this theorem shows that
 \begin{equation*}
  \ord_p( \#\Sha(E/\QQ)(p) ) =   \ord_p(\fE^{\ast}(0)) + \ord_p\left(\frac{(\#E(\QQ)(p))^2}{\epsilon_p\cdot \prod_\vu c_\vu}\cdot\frac{1}{\Reg_{\gamma}(E/\QQ)}\right)
 \end{equation*}
 in the ordinary case (or the same formula where $\epsilon_p$ replaces
 by $\Linv_p$ in the split multiplicative case) and
 \begin{equation*}
  \ord_p( \#\Sha(E/\QQ)(p) ) =   \ord_p(
 (1-\varphi)^{-2}\,\fE^{\ast}(0)) - \ord_p(\Reg_p(E/\QQ)) - \ord_p\left(\prod_\vu c_\vu\right) 
 \end{equation*} 
 in the supersingular case. Finally use Kato's
 Theorem~\ref{katodiv_thm} stating that $$\ord_p(\fE^\ast(0))\leq
 \ord_p(\LL_p^\ast(E,0))$$  to prove that $b_p$ is indeed an upper bound
 on $\ord_p(\#\Sha(E/\QQ)(p))$.
\end{proof}

In the next proposition we summarize the discussion of this section.

\begin{prop}
 Let $E$ be an elliptic curve and $p>2$ a prime for which $E$ has
 semi-stable reduction.  If Conjectures~\ref{conreg_con}
 and~\ref{conreg_ss_con} hold and if we are able to determine the
 Mordell-Weil group of $E$, then there is a algorithm to verify that
 the $p$-primary part of $\Sha(E/\QQ)$ is finite. If moreover the
 representation $\bar\rho_p$ is either surjective or has its image
 contained in a Borel subgroup, then the algorithm produces an upper
 bound on $\#\Sha(E/\QQ)(p)$. If the main
Conjecture~\ref{mainconjecture_con} holds then the result of the
 algorithm is equal to the order of $\Sha(E/\QQ)(p)$.
\end{prop}

 
 \subsection{Technical remarks}
 
 In Step~\ref{mwgroup_item} we may use several ways to determine the
 rank and the Mordell-Weil group.  E.g., first compute the modular
 symbol $[0]^+$. If it is not zero, we have that $L(E,1)\neq 0$ and
 the rank has to be $0$. If the order of vanishing of $L(E,s)$ at
 $s=1$ is $1$, we may use Heegner points to find the full Mordell-Weil
 group, which then is of rank $1$. Otherwise we have to use descent
 methods or the algorithm in the previous section to bound the rank
 from above and a search of points to find a lower
 bound. When enough points are found to generate a group of finite
 index, one has to saturate the group using infinite descent in order
 to find the full group $E(\QQ)$. In practice this step does not
 create any problems as Step~\ref{lp_item} is usually computationally
 more difficult.
 

In Step~\ref{lp_item}, it is easy to determine the precision that will
be needed to compute the $p$-adic valuation of the leading term
$\LL_p^\ast(E,0)$ if one assumes the complex and the $p$-adic version
of the conjecture of Birch and Swinnerton-Dyer. Hence it is easy to
decide when to exit at this step.
 
The algorithm exits with an error only if the Mordell-Weil group could
not be determined (in Step~\ref{mwgroup_item}), if
Conjecture~\ref{conreg_con} or~\ref{conreg_ss_con} is wrong (in
Step~\ref{preg_item}), if the $p$-primary part of $\Sha(E/\QQ)$ is
infinite or if the main conjecture is false (both in
Step~\ref{lp_item}). Hence only weaker variants of the $p$-adic Birch
and Swinnerton-Dyer conjecture are needed.


Another application of the algorithm is the following remark. If, for
a given elliptic curve $E$ and a prime $p$, the algorithm yields the
answer that the $p$-primary part of $\Sha(E/\QQ)$ is trivial, then the
algorithm has actually also proved the main conjecture for $E$ and
$p$. Because we know by then that $\LL_p(E,T)$ and the
characteristic series $\fE(T)$ of the Selmer group have the same order
of vanishing at $T=0$ and the leading terms have the same
valuation. Since, by Kato's theorem $\fE(T)$ divides $\LL_p(E,T)$, we
know then that the quotient is a unit in $\ZZ_p[\![T]\!]$.  Such
calculations and especially this remark on how to verify the main
conjecture in special cases are already contained in~\cite{pr00} for
supersingular primes $p$. 

%% -------------------------------------------------------------------------
\section{Numerical results}\label{numerical_sec}

The algorithms described above are implemented in Sage (see \cite{sage}), which is 
a free open source mathematics software package.  All of the calculations
given below can be carried out using Sage. 

\subsection{A split multiplicative example}

To give an example of a curve with split multiplicative reduction, we
use the same curve as before (see Equation~\eqref{e0})
\begin{equation*}
  E_0\colon\quad y^2 \,+\, x\,y \,=\, x^3\, - \,x^2\, - \,4\,x \,+\, 4
\end{equation*}
but with the prime $p=223$. Of course, there is no hope in practice
that a $223$-descent could be used to compute the order of
$\Sha(E_0/\QQ)(223)$.  We can compute the $p$-adic regulator and the
$L$-invariant to high precision very quickly using Tate's
parametrization of $E$:
 \begin{align*}
  \Reg_p(E_0/\QQ) & = 153\cdot 223^2 + 125\cdot 223^3 + 124\cdot 223^4 + \bigO(223^5)\\
  \Linv           & = 179 \cdot 223 + 85\cdot 223^2 + 30\cdot 223^3 + \bigO(223^4)\\
 \end{align*}
The computation of the $p$-adic $L$-series is more time consuming. But
as we only need the first $p$-adic digit to prove the triviality of
$\Sha(E_0/\QQ)(223)$, we only need to sum over $222$ modular
symbols. This yields
\begin{equation*}
 \LL_p(E_0,T) =  \bigO(223^4) + \bigO(223^1)\cdot T + \bigO(223^1)\cdot T^2 + (139 + \bigO(223))\cdot T^3 + \bigO(T^4)
\end{equation*}
In fact, we know that the first three coefficients vanish as we are in
the exceptional case, so the leading term has valuation $0$. From
these computations, we see that the $p$-adic Birch and Swinnerton-Dyer
conjecture predicts that
\begin{equation*}
 \# \Sha(E_0/\QQ) \equiv 1 \pmod{223};
\end{equation*}
in particular we may conclude that $\Sha(E_0/\QQ)(223) = 0$.

\subsection{A supersingular example}\label{ex_ss_subsec}
Let $E$ be the elliptic curve
\begin{equation*}
 E\colon\quad y^2\, + \, x\,y\,=\ x^3\ +\ x^2\ +\ 2\cdot x\ +\ 2
\end{equation*} 
listed as curve 1483a1 in Cremona's tables. The curve has rank $2$
generated by $(-1,0)$ and $(0,1)$. The reduction of $E$ at $p=5$ is
supersingular. The $p$-adic $L$-function equals
\begin{align*}
 \LL_p(E,T) = & \bigl ( (1 + \bigO(5))\cdot T^2 + (1 + \bigO(5))\cdot T^3 + (3 + \bigO(5))\cdot T^4 + \bigO(T^5)\bigr)\cdot\omegaE \\
              &+ \bigl ( (4\cdot 5 + \bigO(5^2))\cdot T^2 + (4\cdot 5 + \bigO(5^2))\cdot T^3 + (3\cdot 5 + \bigO(5^2))\cdot T^4 + \bigO(T^5)\bigr)\cdot\varphi(\omega_E)
\end{align*}
where we have already taken in account that the first two terms
vanish. We compute the normalized $D_p$-valued regulator
\begin{align*}
\Reg_{\gamma}(E/\QQ) = & 
  \bigl (1 + 2\cdot 5 + 3\cdot 5^2 + 5^3 +  \bigO(5^5)\bigr)\cdot \omegaE \\
& + \bigl ( 4\cdot 5 + 4\cdot 5^2 + 4\cdot 5^3 + 5^4 + 2\cdot 5^5 + \bigO(5^6)\bigr) \cdot\varphi(\omegaE)\,.
\end{align*}
Hence the $p$-adic Birch and Swinnerton-Dyer conjecture predicts that
\begin{equation*}
 \bigl(1 + \bigO(5)\bigr)\,\omegaE +\bigl ( 4\cdot 5 + \bigO(5^2)\bigr)\,\varphi(\omegaE) =
 \#\Sha(E/\QQ)\cdot \Bigl (\bigl (1 + \bigO(5)\bigr)\,\omegaE +\bigl ( 4\cdot 5 + \bigO(5^2)\bigr)\,\varphi(\omegaE)\Bigr) 
\end{equation*}
In particular, we have shown that $\Sha(E/\QQ)(5)$ is trivial. It
follows from Iwasawa theoretic consideration as in~\cite{pr00} that,
if $ \#\Sha(E/\QQn)(5) = 5^{e_n}$ then
\begin{equation*}
 e_n = \frac{p}{p^2-1}\cdot p^n + \bigO(1)\,.
\end{equation*}

\subsection{An example whose  Tate-Shafarevich group is nontrivial}
Let $E$ be the elliptic curve given by
\begin{equation*}
 E\colon\quad y^2\, + \, x\,y\,=\,x^3\,+\,16353089\,x\,-\,335543012233
\end{equation*}
which is labeled 858k2 in \cite{cremona:tables}. The curve has rank
$0$ and is semi-stable, and the full Birch and Swinnerton-Dyer
conjecture predicts that the Tate-Shafarevich group $\Sha(E/\QQ)$
consists of two copies of $\ZZ/7\ZZ$.

We may compute the $7$-adic $L$-series, which yields
\begin{align*}
 \LL_7(E,T) =& 7^2\cdot ( 2\cdot 7^2 + 7^3 +7^4+3\cdot 7^5+\bigO(7^6) + ( 5\cdot 7^2 + \bigO(7^3))\cdot T \\
             &+ (3+4\cdot 7 +5\cdot 7^2+\bigO(7^3))\cdot T^2+\bigO(T^3))
\end{align*}
On the algebraic side, we find that the constant term of the
characteristic series of $E$ has valuation
$2+\ord_7(\#\Sha(E/\QQ))$. So our algorithm yields the correct upper
bound, that $\#\Sha(E/\QQ)(7)\leq 7^2$. Once again we learn even more
from the computation of the $p$-adic $L$-series. Since we know the
exact order of $\Sha(E/\QQ)$, we deduce that the main conjecture holds
We can change to the curve 858k1 with a $7$-isogeny and prove there
directly that the upper bound on the $7$-primary part of the
Tate-Shafarevich group is $1$, so by isogeny invariance of the Birch
and Swinnerton-Dyer conjecture it follows that $\#\Sha(E/\QQ)(7)=
7^2$.  Iwasawa theory tells us now that the order of the
Tate-Shafarevich group grows very quickly (for an ordinary prime) in
the $\ZZ_7$-extension. Namely if $\#\Sha(E/{}_n\QQ)=7^{e_n}$ then $e_n
= 2\cdot 7^n + 2\cdot n +\bigO(1)$.

\subsection{Future Tables}\label{tables_subsec}

We intend to write a follow-up paper to the present article that
contains extensive tables, analysis of the resulting data, and more
detailed discussion of computational complexity and implementation
issues.  These tables will include $p$-adic regulators, and the
$p$-adic analytic order of the Tate-Shafarevich group $\Sha(E/\QQ)$
for various small primes and a large number of curves of various
ranks.  In particular, we will compute the upper bound on the order of
$\Sha(E/\QQ)(p)$ for many pairs $(E,p)$ where we expect to have
nontrivial elements $\Sha(E/\QQ)(p)$.

%% -------------------------------------------------------------------------

\bibliographystyle{amsalpha}
\bibliography{shark}

\end{document}