\documentclass{article} 

\bibliographystyle{amsalpha} 

\voffset=-0.2\textheight  \textheight=1.4\textheight
%\hoffset=-0.2\textwidth \textwidth=1.4\textwidth
%\voffset=-0.05\textheight \textheight=1.1\textheight
\hoffset=-0.05\textwidth \textwidth=1.1\textwidth

\include{macros}

\usepackage{pdfsync}
\usepackage{hyperref}


\title{Chow Heegner Thoughts}

\author{William Stein\footnote{The work was supported by NSF grants...}}


\begin{document}
\maketitle

\begin{abstract} 
\end{abstract}

\section{Algorithm}


Let $E$ and $F$ be elliptic curves of conductor $N$.

For $B>0$, let $\vphi_{F,B} = \sum_{n=1}^B \frac{a_n}{n} q^n$ be the 
degree $B$ approximation to the modular parametrization attached
to $F$, where we have $\vphi_{F}:\h\to \C$ induces by composition
with $\C\to\C/\Lambda_F = F(\C)$ the map $X_0(N)(\C)\to F(\C)$.

Given a point $P \in F(K)$, with $K$ a quadratic extension of $\Q$,
our task it to numerically approximate, to any requested precision,
{\em some} $z \in \h$ such that $\vphi_F(z) = P$.  We are not required
to compute representative orbits for {\em all} such $z$ modulo the
action of $\Gamma_0(N)$, though of course that would be interesting.
(There may be a trick to do that via translation and finding a generic
fiber?)

Write $z=x+iy$.  We have
\begin{align*}
  \vphi_{F,B}(z) &= \sum_{n=1}^B \frac{a_n}{n} e^{2\pi i n (x+iy)}\\
               &= \sum_{n=1}^B \frac{a_n}{n} e^{-2\pi y n} e^{2\pi i x}
\end{align*}

Thus using that $|a_n| \leq n$, and letting $c = |e^{-2\pi y}|$, we have
\begin{align*}
 |\vphi_{F,B}(z) - \vphi_F(z)| &= 
    \left|\sum_{n=B+1}^\infty \frac{a_n}{n} e^{-2\pi y n} e^{2\pi i x}\right|\\
  &\leq \sum_{n=B+1}^\infty |e^{-2\pi y n}|
 = \sum_{n=B+1}^\infty c^n
 = c^{B+1}\sum_{n=0}^\infty c^n
 = \frac{c^{B+1} }{1-c}.
\end{align*}

Let $B=B(y,\epsilon)$, be
an integer
such that $|\vphi_{F,B}(z) - \vphi_F(z)| < \epsilon$.
\begin{proposition}
We may take
$$
 B(y,\epsilon) 
 = \left\lceil \frac{\log(\epsilon\cdot (1-e^{-2\pi y}))}{-2\pi y} \right\rceil.
$$
\end{proposition}
\begin{proof}
We solve for $B$ in the above equation.
If
$$
\frac{c^{B+1} }{1-c} = \epsilon,
$$
then
$$
(B+1)\log(c) - \log(1-c) = \log(\epsilon),
$$
so
$$
B = \frac{\log(\epsilon) + \log(1-c)}{\log(c)} - 1.
$$
\end{proof}


Strategy to find root.

\begin{enumerate}
\item Compute $\vphi_{F,B}$ with $B$ small, find all roots
using a double precision numerical root finder, and choose
the best root, i.e., one corresponding to point in upper
half plane with largest imaginary part.
\item Refine this root to one of higher precision of
$\vphi_{F,B}$ with $B$ larger, using improved bound on $B$
coming from knowing imaginary part $y$ of root. 

\end{enumerate}



Using Newton-Raphson one can refine a low precision point to a high
precision point.  Pretty insane, but this works really, really well
in practice.  I can't believe how well.


\bibliography{biblio}
\end{document}

