%% Delete everything above this line and latex the resulting file. %%%
%%% LaTeX 2e

\documentclass[a4paper]{amsart}
\usepackage{geometry}
\usepackage{amscd,url}
\usepackage{latexsym}
\usepackage[colorlinks=true]{hyperref}
\usepackage{nicematrix}
\newcommand{\lb}{[\![}
\newcommand{\rb}{]\!]}
\DeclareMathOperator{\Res}{Res}
\DeclareMathOperator{\Disc}{Disc}


\geometry{
	includeheadfoot,
	margin = 2.54cm
}

\newfont{\cyr}{wncyr10 scaled \magstep1}
\newcommand{\Sha}{\hbox{\cyr Sh}}
% The following line is Toby's suggestion for getting the
% word "Section" into the section titles. Unfortunately,
% it messes up the numbering of the defns, thms, etc.
%\renewcommand{\thesection}{Section \arabic{section}}
% The following makes sure that the first section is section 0.
% \setcounter{section}{-1}
% The following works on my laptop, but not on University unix
% for getting the word "Section" into the section titles:
\makeatletter
\def\@seccntformat#1{Section \csname the#1\endcsname.\quad}
\makeatother

%% The following supresses bullet points in itemize:
%\renewcommand{\labelitemi}{}
{\makeatletter\gdef\reallynopagebreak{\par\nopagebreak\@nobreaktrue}}
%% If I want to get the bullets back later in the document:
%%\renewcommand{\labelitemi}{$\bullet$}
%%\begin{itemize}
%%\item Item 1.
%%\item Item 2.
%%\end{itemize}


%\DeclareFontEncoding{OT2}{}{} % to enable usage of cyrillic fonts
%\newcommand{\textcyr}[1]{%
%  {\fontencoding{OT2}\fontfamily{wncyr}\fontseries{m}\fontshape{n}%
%   \selectfont #1}}
%\newcommand{\Sha}{{\mbox{\textcyr{Sh}}}}
\usepackage{amssymb}
\usepackage{amsfonts}
\def\hp{{\hat\phi}}
\def\hq{{\hat q}}
\def\bbbq{{\mathbb Q}}
\def\bbba{{\mathbb A}}
\def\adeles{{\bbba}_K}
\def\adelesQ{{\bbba}_\bbbq}
\def\bbbc{{\mathbb C}}
\def\bbbz{{\mathbb Z}}
\def\bbbn{{\mathbb N}}
\def\bbbr{{\mathbb R}}
\def\bbbf{{\mathbb F}}
\def\dd{\hbox{d}}
\def\ddd{\mathrm{d}}
\def\qp{{\bbbq_p}}
\def\notdiv{\not \hskip -.2pt | \,\ }
\def\notdivv{\not \hskip -1.2pt | \,\ }
\def\mod{\hbox{mod }}
\def\max{\mathrm{max }}
\def\gcd{\mathrm{gcd}}
\def\lcm{\mathrm{lcm}}
\def\P{{\mathbb P}}
\def\bb{{|\ \, |}}
\def\bp{{|\ \, |_p}}
\def\binf{{|\ \, |_\infty}}
\def\K{{K}}
\def\pp{{\mathfrak{p}}}
\def\m{{m}}
\def\a{{\bf a}}
\def\b{{\bf b}}
\def\c{{\bf c}}
\def\d{{\bf d}}
\def\e{{\bf e}}
\def\f{{\bf f}}
\def\u{{\bf u}}
\def\v{{\bf v}}
\def\w{{\bf w}}
\def\k{{\bf k}}
\def\Fl{{Fl}}
\def\B{{\hbox{B}}}
\def\o{\underline{\bf o}}
\def\uphi{\underline{\phi}}
\def\upsi{\underline{\psi}}

% The following decides whether to use style E_{ij} or E_{i,j} throughout:
\newcommand{\TJFP}{{\widetilde {\mathcal{J}}}({{\bbbf}_p})}
\newcommand{\TJKP}{{\widetilde {\mathcal{J}}}({{k}_\p})}
\newcommand{\KP}{K_\p}
\newcommand{\JKP}{{\mathcal{J}}({K_\p})}
\newcommand{\com}{,}
\newcommand{\fr}{\mathfrak}
\newcommand{\imp}{\Longrightarrow}
\newcommand{\lra}{\longrightarrow}
\newcommand{\non}{\nonumber}
%\newcommand{\tors}{\mbox{tors}}
\newcommand{\tors}{\mathrm{tors}}
%\newcommand{\log}{\mathrm{log}}
\newcommand{\im}{\mbox{im }}
\newcommand{\kker}{\mbox{ker }}
\newcommand{\nin}{ }
\newcommand{\eq}{equation}
\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\theenumii}{\alph{enumii}}
\renewcommand{\labelenumii}{(\theenumii)}
\renewcommand{\bigl}{\left}
\renewcommand{\bigr}{\right}
\renewcommand{\Bigl}{\left}
\renewcommand{\Bigr}{\right}

%\newcommand{\latop}[2]{{#1\atop#2}}
\newcommand{\latop}[2]{{\genfrac{}{}{0pt}{}{#1}{#2}}}
\newcommand{\lchoose}[2]{{#1\choose#2}}
\newcommand{\ttilde}{\lower4.5pt\hbox{$\widetilde{\ \ \ }$}}
\newcommand{\jqpaqo}{{J(\Q)/\phi_1\bigl(A_1(\Q)\bigr)}}
\newcommand{\jqpaqt}{{J(\Q)/\phi_2\bigl(A_2(\Q)\bigr)}}
\newcommand{\jtqpaqo}{{J_3(\Q)/\phi_1\bigl(A_1(\Q)\bigr)}}
\newcommand{\jfqpaqo}{{J_4(\Q)/\phi_1\bigl(A_1(\Q)\bigr)}}
\newcommand{\jfqpaqt}{{J_4(\Q)/\phi_2\bigl(A_2(\Q)\bigr)}}
\newcommand{\imq}{{\hbox{im}\,q}}
%%%
\def \neweij {(\ref{eq:neweij})}
\def \newpij {(\ref{eq:newepij})}
\def \newepaij {(\ref{eq:newep71ij})}
\def \newepbij {(\ref{eq:newep72ij})}
\def \topeaj {(\ref{eq:tope1j})}
\def \topebj {(\ref{eq:tope2j}) }
\def \refseq {\neweij,\newpij,\newepaij,\newepbij,\topeaj,\topebj}
%%%
\def \qsq {({\Q}^*)^2}
\def \qmsq {{\Q}^*/({\Q}^*)^2}
\def \qpmsq {{\Q_p}^*/({\Q_p}^*)^2}
\def \qtmsq {{\Q_2}^*/({\Q_2}^*)^2}
\def \qimsq {{\Q(i)}^*/({\Q(i)}^*)^2}
\def \qpimsq {{\Q_p(i)}^*/({\Q_p(i)}^*)^2}
\def \qipmsq {\Q(i)_p^*/(\Q(i)_p^*)^2}
\def \qtimsq {{\Q_2(i)}^*/({\Q_2(i)}^*)^2}
\newcommand{\two}{{1+i}}
\def \qitmsq {\Q(i)_\two^*/(\Q(i)_\two^*)^2}
\def \kmsq {{K}^*/({K}^*)^2}
\newcommand{\Lmodsq}{{L_1^*/(L_1^*)^2\times
                      L_2^*/(L_2^*)^2\times L_3^*/(L_3^*)^2}}
\newcommand{\bs}{{\underline s}}
\newcommand{\bt}{{\underline t}}
\newcommand{\bY}{{\underline Y}}
\newcommand{\bx}{{\underline x}}
\newcommand{\by}{{\underline y}}
\newcommand{\ZZ}{\bbbz}
\newcommand{\Z}{\bbbz}
\newcommand{\QQ}{\bbbq}
\newcommand{\Q}{\bbbq}
\newcommand{\R}{\bbbr}
\newcommand{\QA}{\bbbq(\alpha)}
\newcommand{\QB}{\bbbq(\beta)}
\newcommand{\FF}{\bbbf}
\newcommand{\C}{\mathcal{C}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\M}{\mathfrak{m}}
\newcommand{\X}{\mathcal{X}}
\newcommand{\twC}{\mathcal{C}^{\mathrm {tw}}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\fC}{\mathfrak{C}}
\newcommand{\fE}{\mathfrak{E}}
\newcommand{\fJ}{\mathfrak{J}}
\newcommand{\J}{\mathcal{J}}
\newcommand{\twJ}{{\J}^{\mathrm {tw}}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\SSS}{\mathcal{S}}
\newcommand{\tzeta}{{\tilde \zeta}}
\newcommand{\TE}{{\widetilde{\mathcal{E}}}}
\newcommand{\TC}{{\widetilde{\mathcal{C}}}}
\newcommand{\TJ}{{\widetilde{\mathcal{J}}}}
\newcommand{\TD}{{\widetilde{D}}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\G}{\mathcal{G}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\CQ}{\mathcal{C}(\bbbq)}
\newcommand{\DQ}{\mathcal{D}(\bbbq)}
\newcommand{\EOT}{\mathcal{E}_{1\com 2}}
\newcommand{\ETT}{\mathcal{E}_{2\com 2}}
\newcommand{\EQ}{\mathcal{E}(\bbbq)}
\newcommand{\EQP}{\mathcal{E}(\bbbq_p)}
\newcommand{\EQA}{\mathcal{E}(\bbbq(\alpha))}
\newcommand{\EQB}{\mathcal{E}(\bbbq(\beta))}
\newcommand{\EQAT}{\mathcal{E}(\bbbq(\alpha))_\mathrm{tors}}
\newcommand{\EPA}{\mathcal{E}_p^a}
\newcommand{\EPB}{\mathcal{E}_p^b}
\newcommand{\EPAQ}{\mathcal{E}_p^a(\bbbq)}
\newcommand{\EPBQ}{\mathcal{E}_p^b(\bbbq)}
\newcommand{\EPAQT}{\mathcal{E}_p^a(\bbbq)_\mathrm{tors}}
\newcommand{\EPBQT}{\mathcal{E}_p^b(\bbbq)_\mathrm{tors}}
\newcommand{\JQ}{\mathcal{J}(\bbbq)}
\newcommand{\fCQ}{\mathfrak{C}(\bbbq)}
\newcommand{\fEQ}{\mathfrak{E}(\bbbq)}
\newcommand{\fEQA}{\mathfrak{E}(\bbbq(\alpha))}
\newcommand{\fEQB}{\mathfrak{E}(\bbbq(\beta))}
\newcommand{\fEQAT}{\mathfrak{E}(\bbbq(\alpha))_\mathrm{tors}}
\newcommand{\fEPA}{\mathfrak{E}_p^a}
\newcommand{\fEPB}{\mathfrak{E}_p^b}
\newcommand{\fEPAQ}{\mathfrak{E}_p^a(\bbbq)}
\newcommand{\fEPBQ}{\mathfrak{E}_p^b(\bbbq)}
\newcommand{\fEPAQT}{\mathfrak{E}_p^a(\bbbq)_\mathrm{tors}}
\newcommand{\fEPBQT}{\mathfrak{E}_p^b(\bbbq)_\mathrm{tors}}
\newcommand{\fJQ}{\mathfrak{J}(\bbbq)}
\newcommand{\JQp}{\mathcal{J}(\bbbq_p)}
\newcommand{\JK}{\mathcal{J}(K)}
\newcommand{\JKp}{\mathcal{J}(K_\p)}
\newcommand{\JQT}{J(\bbbq)_\mathrm{tors}}
\newcommand{\CK}{\mathcal{C}(K)}
\newcommand{\EK}{\mathcal{E}(K)}
\newcommand{\ET}{\E_\mathrm{tors}}
\newcommand{\ETK}{\E_\mathrm{tors}(K)}
\newcommand{\EKT}{\E(K)_\mathrm{tors}}
\newcommand{\ETQ}{\E_\mathrm{tors}(\bbbq)}
\newcommand{\CTQ}{\mathcal{C}_\mathrm{tors}(\bbbq)}
\newcommand{\ETQP}{\E_\mathrm{tors}(\bbbq_p)}
\newcommand{\EQT}{\E(\bbbq)_\mathrm{tors}}
\newcommand{\JKT}{\mathcal{J}(K)_\mathrm{tors}}
\newcommand{\Pic}{\mathrm{Pic}}
\newcommand{\A}{{\bf A}}
\newcommand{\p}{{\mathbb P}}
\newcommand{\chari}{\mathrm{char}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{meth}[thm]{Method}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{qn}[thm]{Question}
\newenvironment{prf}{ {\it Proof}}{\hfill$\square$}
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{exs}[thm]{Examples}
\newtheorem{comm}[thm]{Comment}
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}	\renewcommand{\therem}{}
\newtheorem{rems}[thm]{Remarks}	\renewcommand{\therems}{}
\numberwithin{equation}{section}

%\theoremstyle{definition}
%\newtheorem{defn}{Definition}	\renewcommand{\thedefn}{}
%\newtheorem{question}{Question}	\renewcommand{\thequestion}{}

%\topmargin -0.3in
%\headsep 0.3in
%\oddsidemargin 0in
%\evensidemargin 0in
%\textwidth 6.5in
%\textheight 9in

%%% \renewcommand{\baselinestretch}{3}

\begin{document}
% The following [] suppress the title running header on the odd pages.
\title[]{Elliptic Curves 2025/26. Lecturer: James Newton}

% The following [] suppress the author running header on the even pages.
%\author[]{E.V.\ Flynn}
%\address{New College, Oxford OX1 3BN}
%\email{flynn@maths.ox.ac.uk}

%********************************************************************

\maketitle
\setcounter{tocdepth}{1} 
\tableofcontents
\normalsize
\Large
%\baselineskip=18pt
%********************************************************************
\setcounter{page}{1}

%\baselineskip = 18.615pt
%\baselineskip = 18.13pt
{{\it These notes are a slightly edited version of those written by Victor Flynn. Please send any typos or queries to} \url{newton@maths.ox.ac.uk}}

\textit{The first part of the lecture notes overlaps with the final part of the Preliminary Reading file. References with numbers $0.x$ refer to that file. }

\section{Geometric preliminaries}\label{sec:geometry}

\subsection*{Affine curves}

\begin{defn}\label{defn:affinespace}
	Let~$K$ be a field. We define $\A^n(K) = \{ (x_1,\ldots ,x_n): x_1,\ldots x_n \in K\}$, and refer to a point $P \in \A^n(K)$ as a {\it $K$-rational} point of the {\it affine $n$-space} $\A^n$. We also say that a point $P \in \A^n(K)$ is \emph{defined over $K$}.
\end{defn}
%\begin{ex}\label{ex:affinespace}
%	$(\frac{1}{2}, \frac{3}{4}) \in \A^2(\bbbq) \subset \A^2(\bbbc)$.
%	The point $(\frac{1}{2}, \frac{3}{4})$ is $\bbbq$-rational
%	(we can also say: it is a $\bbbq$-rational point, or that it
%	is defined over~$\bbbq$). Of course, it is also $\bbbr$-rational
%	and $\bbbc$-rational. The point $(\frac{1}{2}, 2 + i, \sqrt{2}) 
%	\in \A^3(\bbbc)$ but is not a member of~$\A^3(\bbbq)$.
%	The point $(\frac{1}{2}, 2 + i, \sqrt{2})$ is defined over~$\bbbc$,
%	but not defined over~$\bbbq$ (it is $\bbbc$-rational, but
%	not $\bbbq$-rational).
%\end{ex}
%\begin{defn}\label{defn:ratfn}
%	A {\it monomial} is a product of the form $k x_1^{m_1}\ldots x_\ell^{m_\ell}$,
%	where $x_1,\ldots ,x_\ell$ are variables, $k\in K$, $m_1,\ldots ,m_\ell
%	\geqslant 0$, which has {\it degree} $m_1 + \ldots + m_\ell$
%	[so that a polynomial is a sum of monomials; we also call
%	the monomials the {\it terms} of the polynomials].
%	A {\it rational function} is a quotient of two polynomials.
%\end{defn}
%For example, $\frac{1 + x^2}{4 + x + x^3}$ is a rational function
%in the variable~$x$, and $\frac{s + \sqrt{2}t^2}{1 + s + st^2}$ 
%is a rational function in the variables~$s,t$.
%Note that~$x^{1/2}$ is neither a polynomial nor a rational
%function (all exponents in a polynomial must be integers~$\geqslant 0$).
\begin{defn}\label{defn:definedoverK}
	An algebraic expression such as a curve, polynomial, rational function,
	is said to be {\it defined over~$K$} (or $K$-rational)
	if it can be described by an equation with coefficients in~$K$.
\end{defn}
%\begin{exs}\label{exs:definedoverK}\
%	\par {\bf (a)} $x^3 + 1$ is a polynomial in~$x$, defined over~$\bbbq$.
%	\par {\bf (b)} $\frac{s + \sqrt{2}t^2}{1 + s + st^2}$ is
%	a rational function in~$s,t$, defined over~$\bbbq(\sqrt{2})$.
%	We could also say that it is a $\bbbq(\sqrt{2})$-rational
%	rational function. Note the two different uses of the word rational
%	here: in the phrase $\bbbq(\sqrt{2})$-rational, which refers
%	to the fact that the coefficients are in~$\bbbq(\sqrt{2})$,
%	and in the phrase `rational function', which refers to the fact
%	that the expression is a quotient of two polynomials.
%\end{exs}
\begin{defn}\label{defn:affinecurve}
	A (non-constant) polynomial in two variables $f(x,y)$, with coefficients
	in~$K$, defines an (affine) {\it curve defined over~$K$}.
	For any field~$L$ with $K\subset L$, the set of $L$-rational
	points $\{(a,b) \in \A^2(L) : f(a,b)=0\}$ on a curve~$\C$ with equation $f(x,y)$ is denoted $\C(L)$. The field~$K$ is often
	called the {\it field of definition} (or the {\it ground field}).
\end{defn}
\begin{ex}\label{ex:affinecurve}
	Let $\C : f(x,y) = x^2 + y^2 = 0$. This defines an affine
	curve over~$\bbbq$.
	Of course, this same curve~$\C$ could be regarded as having
	field of definition (ground field) $\bbbq, \bbbq(\sqrt{2}), \bbbr, \bbbc$
	or indeed any field containing~$\bbbq$. When the field of definition
	is not stated explicitly, it is taken to be the smallest possible field
	over which the curve is defined (in this case, $\bbbq$). 
	The point $(0,0)$ is $\bbbq$-rational and it is the only $\bbbq$-rational point on~$\C$,
	so that $\CQ = \{ (0,0) \}$. It has many $\bbbc$-rational points,
	for example $(i,1) \in \C(\bbbc)$.
\end{ex}
\begin{comm}\label{comm:affinecurve}
	Our affine curves are by definition embedded in the plane $\A^2$, and cut out by a single polynomial equation. It is also possible to embed curves in higher dimensional
	space, as long as the number of `independent' polynomials defining the curve is one less than the number of variables; for example the~$2$
	equations: $y^2 + 4 x^2 - 1 = 0, z^2 - x^2 - x = 0$ define
	a curve in the variables $x,y,z$. However, we shall not concern ourselves
	with that here.
\end{comm}
\begin{defn}\label{defn:homog}
	The {\it degree} of a polynomial is the degree of its highest
	degree monomial. A {\it homogeneous} polynomial is a polynomial
	whose terms all have the same degree.
\end{defn}
\begin{ex}\label{ex:degree}
	$f(x,y) = x + y - 8 = 0$ defines a curve of degree~$1$ (a {\it linear} curve),
	$g(x,y) = xy + y^2 - y + 3 = 0$ defines a curve of degree~$2$
	(a {\it quadratic} curve) and
	$h(x,y) = x^3 + y^3 + y - 1$ defines
	a curve of degree~$3$ (a {\it cubic} curve).
	None of these polynomials are homogeneous.
\end{ex}
If you try drawing an accurate sketch of, for example, the three curves
$\C_1,\C_2,\C_3$ defined by $x^2 + y^2 = 1, y^2 = x^3, y^2 = x(x-2)^2$,
respectively, you will notice distinguishing features.
The first curve~$\C_1$ appears smooth at all points, and it
is easy to see that there is a unique tangent at each point.
The curve~$\C_2$ has a `sharp corner' at~$(0,0)$, and the third curve~$\C_3$
crosses itself at the point~$(2,0)$, when there is a plausible choice of
two distinct tangents. These sharp corners and crossing points
are typified by the fact that both partial derivatives of~$f$ vanish,
when the curve is written as~$f(x,y) = 0$.
\begin{defn}\label{defn:singular}
	Let $\C : f(x,y) = 0$ be an (affine) curve defined over a field $K$ and let $P = (x_0,y_0)$
	be a point in~$\C(\overline{K})$, where $\overline{K}$ is an algebraic closure of $K$. We say that $P$ is a {\it singular point}
	(or a {\it singularity}) on~$\C$ if $\frac{\partial f}{\partial x}(P) = 0$
	and $\frac{\partial f}{\partial y}(P) = 0$.
	Otherwise,~$P$ is a {\it smooth point} (or a {\it nonsingular point})
	on~$\C$. A curve~$\C$ is called {\it smooth} (or {\it nonsingular})
	if it does not contain any singular points (the curve is
	called {\it singular} if it contains at least one singular point).
\end{defn}
\begin{comm}\label{comm:tangents}
	There is a standard technique for computing all tangents to~$\C : f(x,y)=0$
	at a point~$P = (x_0,y_0)$, in which we first translate the curve
	by~$(-x_0,-y_0)$ (so that~$(x_0,y_0)$ is taken
	to~$(0,0)$), then use the fact that the lowest degree terms
	dominate near~$(0,0)$ and determine the tangent behaviour at~$(0,0)$,
	and then finally translate the curve back to its original position.
	This gives three steps.
	
	
	\begin{itemize}\item[\bf Step~1.] Consider~$f(x+x_0,y+y_0)$ (this is~$f(x,y)$
	translated by~$(-x_0,-y_0)$) which contains the point~$x=y=0$ and
	so has no constant term. We can write:
	$$ f(x+x_0,y+y_0) = R_k(x,y) + R_{k+1}(x,y) + \ldots + R_n(x,y),
	$$
	where $k \geqslant 1$ and where each $R_i(x,y)$ is homogeneous of degree~$i$
	(for $k\leqslant i \leqslant n$) and $R_k(x,y) \not= 0$.
	\item[\bf Step~2.] Consider $R_k(x,y)$, which is the lowest degree
	portion of $f(x+x_0,y+y_0)$, and factorise
	$R_k(x,y) = L_1(x,y) L_2(x,y)\ldots L_k(x,y)$
	over the algebraic closure, where $L_1,\ldots ,L_k$
	are linear.
	\item[\bf Step~3.] There are~$k$ tangents to
	$f(x+x_0,y+y_0)=0$ at~$(0,0)$ namely:
	$L_1(x,y) = 0, \ldots , L_k(x,y) = 0$. So, after reversing the translation
	of Step~1, there are~$k$ tangents to~$\C : f(x,y) = 0$ at $P = (x_0,y_0)$,
	namely:
	$$ L_1(x-x_0,y-y_0) = 0, \ldots , L_k(x-x_0,y-y_0) = 0.$$
	Note that the same tangent may be repeated more than once
	(e.g.\ $\C : f(x,y) = y^2 - x^3 = 0$ has~$2$ tangents at~$(0,0)$,
	namely: $y=0$ twice, in which case we can say that the tangent~$y=0$
	occurs with multiplicity~$2$).
\end{itemize}
\end{comm}
\newpage
\begin{comm}\label{comm:doublepoint}
	$P = (x_0,y_0)$ is a smooth point on~$\C$
	\par \ \ \ \ \ \ \ \ \ \ \ \ $\iff k=1$ in Step~1
	\par \ \ \ \ \ \ \ \ \ \ \ \ $\iff$ there is only one tangent to~$\C$ at~$P$.
	\par  When $k \geqslant 2$, the singularity at~$P$
	is called a {\it double point} ($k=2$), {\it triple point} ($k=3$), and so on.
\end{comm}
\begin{ex}\label{ex:sing1}
	Let $\C_1 : x^2 + y^2 = 1$ (a circle of radius~$1$ and centre~$(0,0)$).
	Then we can write: $\C_1 : f(x,y) = x^2 + y^2 - 1 = 0$, and so
	$\frac{\partial f}{\partial x} = 2x, \frac{\partial f}{\partial y} = 2y$.
	A point~$(x,y)$ is a singular point on~$\C_1$ exactly when: it lies
	on~$\C_1$ and both partial derivatives are zero, that is, when:
	$$ (1)\ x^2 + y^2 - 1 = 0,\ \ \ (2)\ 2x = 0,\ \ \ (3)\ 2y = 0.$$
	Assuming our ground field does not have characteristic $2$, equations (2),(3) force~$x=y=0$, but this does not satisfy~(1).
	We conclude that there are no singular points and that~$\C_1$ is smooth.
\end{ex}
\begin{ex}\label{ex:sing2}
	Let $\C_2 : y^2 = x^3$, that is: $\C_2 : f(x,y) = y^2 - x^3 = 0$.
	Then $\frac{\partial f}{\partial x} = -3x^2,
	\frac{\partial f}{\partial y} = 2y$.
	We can see that the only singular point is~$(0,0)$.
	For computing tangents at~$(0,0)$, we first take
	$f(x + 0, y + 0) = y^2 - x^3 = R_2(x,y) + R_3(x,y)$,
	where $R_2(x,y) = y^2$ and $R_3(x,y) = -x^3$.
	Then $R_2(x,y) = y^2 = L_1(x,y)L_2(x,y) = y\cdot y$,
	so there are two tangents to~$\C_2$ at~$(0,0)$, namely:
	$L_1(x-0,y-0) = 0$ and $L_2(x-0, y-0) = 0$, that is:
	$y=0$ and $y=0$ (i.e.\ $y=0$ with multiplicity~$2$).
	A double point singularity where the same tangent line has
	multiplicity~$2$ is called a~{\it cusp} (or a {\it cuspidal singularity}).
\end{ex}
\begin{ex}\label{ex:sing3}
	Let $\C_3 : y^2 = x(x-2)^2$, that is: $\C_3 : f(x,y) = y^2 - x(x-2)^2 = 0$.
	The point~$(x,y)$ on~$\C_3$ is singular when:
	$$ (1)\ y^2 - x(x-2)^2 = 0,\ \ \ 
	(2)\ \frac{\partial f}{\partial x} = -3x^2 + 8x - 4 = 0,\ \ \ 
	(3)\ \frac{\partial f}{\partial y} =2y = 0.$$
	Assuming our ground field does not have characteristic $2$, from~(3) we see that~$y=0$, and substituting this into~(1)
	gives: $x(x-2)^2 = 0$, so that~$x=0$ or~$2$. Now, $x=2$ satisfies~(2),
	but $x=0$ does not, giving $x=2$ as the only common solution. So, the
	only possible singular point is~$(2,0)$ (conversely, check that
	$x=2,y=0$ satisfies~(1),(2),(3) so that~$(2,0)$ is a singular point).
	We conclude that~$(2,0)$ is the only singularity on~$\C_3$.
	\par For the tangents at~$(2,0)$, first compute
	$f(x+2,y+0) = y^2 - (x+2)x^2 = y^2 - 2x^2 - x^3 = R_2(x,y) + R_3(x,y)$,
	where $R_2(x,y) = y^2 - 2x^2$ and $R_3(x,y) = -x^3$.
	Factorising~$R_2(x,y)$ into linear factors gives: 
	$R_2(x,y) = (y + \sqrt{2}x)(y - \sqrt{2}x) = L_1(x,y)L_2(x,y)$.
	The tangents to the curve~$\C_3$ at~$(2,0)$ are then:
	$L_1(x-2,y-0)=0$ and $L_2(x-2,y-0)=0$, that is:
	$y = -\sqrt{2}(x-2)$ and $y = \sqrt{2}(x-2)$.
	The point~$(2,0)$ is a double point with two distinct tangents;
	such a point is called a {\it node} (or a {\it nodal singularity}).
\end{ex}
Note that the system of equations satisfied by singular points
is over-represented, since there are~$3$ equations and only~$2$
variables. If you choose a curve `at random', you would expect
the first two of these equations to have only finitely many solutions,
and it is rather a fluke if one of these solutions also happens
to satisfy the third equation. So, a `typical' curve will be smooth.
\par
A useful tool, for computing singularities and other purposes,
is the idea of the resultant of two polynomials.
\newpage
\begin{defn}\label{defn:resultant}
	Let $f(x) = f_m x^m + \ldots + f_0$ and $g(x) = g_n x^n + \ldots + g_0$,
	where $f_m\not= 0$ and $g_n \not= 0$.
	The {\it resultant} of~$f(x)$ and~$g(x)$, denoted 
	$\Res\bigl( f(x), g(x) \bigr)$ or just $\Res( f, g )$,
	is the determinant of the following $(m+n) \times (m+n)$ matrix:
	\vspace{1cm}
	\[
	\begin{pNiceMatrix}
		0 & \cdots & 0 &f_m & f_{m-1} & \cdots & f_1 & f_0 \\
		0 & \cdots & f_m & f_{m-1} & f_{m-2} & \cdots & f_0 & 0 \\
		\vdots & \iddots &  & \iddots &  & && \vdots \\
		f_m & \cdots &  & 0 & 0 &\cdots & 0 & 0 \\ 
		% \hline
		0 & \cdots & 0 & g_n & g_{n-1} & \cdots & g_1 & g_0 \\
		0 & \cdots & g_n & g_{n-1} & g_{n-2} & \cdots & g_0 & 0 \\
		& \iddots &  & \iddots &  & && \vdots \\
		g_n & \cdots & g_2 & g_1 & g_0 &\cdots & 0 & 0 \\ 
		
		
		\CodeAfter
		\OverBrace{1-1}{8-3}{n-1}
		\OverBrace{1-4}{8-8}{m+1}
	\end{pNiceMatrix}
	\]
%	$$
%	\begin{array}{| c c c c c c c c c |}
%		& \langle n-1 & \hbox{$0$'s}\rangle &  & & f_m    & \ldots & \ldots & f_0\\
%		& \langle n-2 & \hbox{$0$'s}\rangle & & f_m & \ldots & \ldots &  f_0   &  0\\
%		&   &   &     &  \vdots   &  &        &        &   \\
%		&   &   &     &  \vdots   &  &        &        &   \\
%		f_m & \ldots & \ldots &  f_0   & &  & \langle n-1 & \hbox{$0$'s}\rangle &\\
%		& \langle m-1 & \hbox{$0$'s}\rangle &  & & g_n & \ldots & \ldots & g_0\\
%		& \langle m-2 & \hbox{$0$'s}\rangle & & g_n & \ldots & \ldots & g_0 &  0\\
%		&   &   &     &  \vdots   &  &        &        &   \\
%		&   &   &     &  \vdots   &  &        &        &   \\
%		g_n & \ldots & \ldots &  g_0 & &  & \langle m-1 & \hbox{$0$'s}\rangle & \\
%	\end{array}
%	$$
\end{defn}

The following are easy to show.
\begin{lem}\label{lem:resultant}
	Let~$f(x), g(x)\in R[x]$ be polynomials of degree~$m,n$, respectively,
	defined over a commutative ring~$R$.
	\par {\bf (a)} There exist polynomials $p(x)\in R[x]$, of degree at
	most~$n-1$, and~$q(x)\in R[x]$, of degree at most~$m-1$, such that:
	$p(x) f(x) + q(x) g(x) = {\Res}\bigl( f(x), g(x) \bigr)$.
	\par {\bf (b)} When~$R$ is a field, 
	${\Res}\bigl( f(x), g(x) \bigr) = 0
	\iff f(x) \hbox{ and } g(x)$ have a non-constant common factor.
\end{lem}
\begin{defn}\label{defn:discrim}
	The~{\it discriminant} of a degree~$n$ polynomial 
	$f(x) = f_n x^n + \ldots f_0$ is given by:
	${\Disc}(f) = {\Res}(f,f')/f_n$.
\end{defn}
\begin{comm}\label{comm:discrim}
	\par {\bf (a)} Given a monic polynomial $f(x) \in R[x]$,
	there exist polynomials $p(x),q(x)\in R[x]$
	such that $p(x) f(x) + q(x) f'(x) = {\Disc}(f)$.
	\par {\bf (b)}
	${\Disc}(f) = 0 \iff f \hbox{ and } f'\hbox{ have a common
		root} \iff f \hbox{ has a repeated root.}$
	For example, ${\Disc}(x^3 - 2x^2 + x) = 0$, 
	%[roots~$0,1,1$, so there is a repeated root],
	whereas ${\Disc}(x^2 + 1) \not= 0$.
\end{comm}
\begin{ex}\label{ex:quadresultant}
	Let~$f(x) = a x^2 + b x + c$. Then ${\Disc}(f) ={\Res}(f,f')/a$
	$$
	\begin{array}{c | c c c | c}
		& a & b & c &\\
		= {\Res}(ax^2+bx+c,2ax+b)/a 
		=\ \ \frac{1}{a}& 0 & 2a & b & \ \ = b^2 - 4ac,\\
		& 2a & b & 0 &\\
	\end{array}
	$$
	which is the discriminant you know from school,
	appearing under the square root sign in the quadratic formula.
\end{ex}
\begin{ex}\label{ex:cubresultant}
	Let~$f(x) = x^3 + Ax + B$. Then ${\Disc}(f) ={\Res}(f,f')$
	$$
	\begin{array}{c | c c c c c | c}
		& 0 & 1 & 0 & A & B &\\
		& 1 & 0 & A & B & 0 &\\
		= {\Res}(x^3 + Ax + B, 3x^2 + A) =\ \ 
		& 0 & 0 & 3 & 0 & A &\ \ = 4A^3 + 27 B^2.\\
		& 0 & 3 & 0 & A & 0 &\\
		& 3 & 0 & A & 0 & 0 &\\
	\end{array}
	$$
\end{ex}
\begin{ex}\label{ecdiscrim}
	An application of resultants to singularities is as follows.
	Consider the curve $\C : y^2 = x^3 + Ax + B$ (i.e.~$g(x,y) = x^3 + Ax + B - y^2 = 0$), where~$A,B \in K$,
	a field of characteristic not equal to~$2$. 
	Suppose $(x_0,y_0)$ is a singular point on~$\C$, so that:
	$$ (1)\ g(x_0,y_0) = 0,\ \ (2)\ \frac{\partial g}{\partial x}(x_0,y_0) = 0,
	\ \ (3)\ \frac{\partial g}{\partial y}(x_0,y_0) = 0,
	$$
	giving:
	$$ (1)\ y_0^2 = x_0^3 + Ax_0 + B,\ \ 
	(2)\ 3 x_0^2 + A = 0,
	\ \ (3)\ 2 y_0 = 0.
	$$
	Since the characteristic of~$K$ is not equal to~$2$, we know
	that~$2\not=0$, and so~(3) gives~$y_0 = 0$.
	Substituting this into~(1) tells us that~$x_0$ is a root
	of~$x^3 + Ax + B$, and~(2) tells us that~$x_0$ is a root
	of its derivative; this is possible exactly when~$x^3 + Ax + B$
	has a repeated root -- in other words, when ${\Disc}(x^3 + Ax + B) = 0$.
	We have already seen in Example~\ref{ex:cubresultant}
	that ${\Disc}(x^3 + Ax + B) = 4A^3 + 27 B^2$.
	\par In summary, the curve~$\C$ is smooth if and only if
	$4A^3 + 27 B^2 \not= 0$.
\end{ex}
Another basic idea in geometry applies to situations where
$f(x,y)$ itself has a proper factorisation, for example:
$\C : f(x,y) = x^2 - y^2 = 0$. This is a quadratic curve,
but it factors as $(x+y)(x-y) = 0$, and so the graph of~$\C$
is just the union of the graphs of the lines~$x+y=0$ and $x-y=0$.
This seems geometrically different from curve such as $x^2 - y^2 + 1 = 0$,
which has no such factorisation. This is formalised in the following
definition.
\begin{defn}\label{defn:irred}
	Let~$\C : f(x,y) = 0$ be a curve defined over~$K$, and let~$L$
	be any field containing~$K$.
	We say that~$\C$ is {\it irreducible over~$L$} if~$f(x,y)$ cannot
	be expressed as a product of two polynomials, both of degree~$\geqslant 1$
	and both defined over~$L$ (by the word~{\it irreducible} on its own,
	we mean irreducible over~$K$). For any~$\C : f(x,y) = 0$, we
	can write~$f$ uniquely (up to constants and reordering) as a 
	product $f = f_1 f_2 \ldots f_n$, where $f_1,\ldots ,f_n$
	are irreducible over~$L$. The curves 
	$\C_1 : f_1(x,y) = 0, \ldots , \C_n : f_n(x,y) = 0$
	are called the {\it irreducible components} of~$\C$ over~$L$.
\end{defn}
\begin{exs}\label{exs:irred}\
	\par {\bf (a)} $\C : f(x,y) = y^2 - 2x^2 = 0$, defined over~$\bbbq$.
	This is irreducible (by which we mean irreducible over~$\Q$),
	but it becomes reducible over~$\bbbc$, with irreducible
	components $\C_1 : y = \sqrt{2}x$ and $\C_2 : y = -\sqrt{2}x$.
	\par {\bf (b)} $\C : f(x,y) = y^4 - x^4 = 0$ is reducible.
	Its irreducible components (over~$\bbbq$) are: $y-x=0, y+x=0, y^2+x^2=0$.
	The last of these becomes reducible over~$\bbbc$ , and the 
	irreducible components over~$\bbbc$ are: $y-x=0, y+x=0, y+ix=0, y-ix=0$. 
	%\par {\bf (c)} It can be shown that $\C : y^2 - x^3 - 1$
	%is irreducible over~$\bbbc$. 
\end{exs}
It is also helpful to formalise the relationship between curves
such as $x^2 + y^3 - 5 = 0$ and $(x+1)^2 + y^3 - 5 = 0$,
where there are maps from one to the other.
In this case, one can map each curve to the
other with a linear map, but more generally we consider 
maps between curves described by rational 
functions (quotients of polynomials).
\begin{defn}\label{defn:birat}
	Let $\C : f(x,y) = 0$ and $\C' : g(x,y) = 0$ be curves over~$K$.
	A {\it rational map}~$\uphi$ over~$L$ from~$\C$ to~$\C'$
	is a map given by a pair $\phi_1,\phi_2$ of rational functions
	in~$x,y$, defined over~$L$ (i.e.\ $\phi_1, \phi_2$ are both
	of the form $\frac{\hbox{polynomial in $x,y$}}{\hbox{polynomial in $x,y$}}$
	and the coefficients of~$\phi_1, \phi_2$ are in~$L$), with the property that,
	given any point $P = (x_0,y_0)$ on~$\C$, then the point
	$\bigl( \phi_1(x_0,y_0), \phi_2(x_0,y_0) \bigr)$ lies on~$\C'$
	(for all but finitely many points~$(x_0,y_0)$ at which the denominators
	of~$\phi_1,\phi_2$ are~$0$). If there also exists a rational map
	$\upsi = \bigl( \psi_1(x,y), \psi_2(x,y) \bigr)$ from~$\C'$ to~$\C$
	such that $\upsi \ \uphi$ is the identity on~$\C$ and
	$\uphi \ \upsi$ is the identity on~$\C'$ then we say that~$\uphi$
	is a {\it birational transformation} over~$L$ from~$\C$ to~$\C'$
	and that~$\C$ and~$\C'$ are {\it birationally equivalent}
	over~$L$.
\end{defn}
\begin{exs}\label{exs:birat}\
	\par {\bf (a)} Let $\C : x^4 + y^4 = 1$ 
	(i.e.\ $f(x,y) = x^4 + y^4 - 1 = 0$) and let $\C' : x^4 + y^2 = 1$
	(i.e.\ $g(x,y) = x^4 + y^2 - 1 = 0$). 
	Define~$\uphi : \C \rightarrow \C'$ by $\uphi(x,y) = (x,y^2)$
	(in the notation of Definition~\ref{defn:birat}: $\phi_1(x,y)=x$ and
	$\phi_2(x,y) = y^2$). This is a rational map from~$\C$
	to~$\C'$ over~$\bbbq$ since, if~$(x,y)$ satisfies $\C : x^4 + y^4 = 1$
	then $x^4 + (y^2)^2 = 1$ and so $(x,y^2)$ lies on~$\C'$.
	This is a rational map from~$\C$ to~$\C'$, but it is not a birational
	transformation, since there is no inverse map ($\uphi$ is $2$-to-$1$).
	\par\smallskip {\bf (b)} Let $\C : x^2 + y^3 - 5 = 0$ and
	$\C' : (x+1)^2 + y^3 - 5 = 0$.
	If~$(x,y)$ is on~$\C$ then $x^2 + y^3 - 5= 0$ and 
	so $((x-1)+1)^2 + y^3 - 5 = 0$,
	giving that $(x-1,y)$ lies on~$\C'$. The
	map $\uphi(x,y) = \bigl( \phi_1(x,y), \phi_2(x,y)\bigr) = (x-1,y)$
	is then a rational map over~$\bbbq$ from~$\C$ to~$\C'$,
	and the inverse map is clearly $\upsi(x,y) = (x+1,y)$.
	The map $\uphi$ is a birational transformation from~$\C$ to~$\C'$ 
	over~$\bbbq$, and so~$\C$ and~$\C'$ are birationally equivalent
	over~$\bbbq$.
	\par Note that the rational map from~$\C$ to~$\C'$ is in the opposite
	direction to the variable replacement which transforms the equations.
	In the above example, $\uphi(x,y) = (x-1,y)$ is the map from~$\C$ to~$\C'$
	(in that it maps points on~$\C$ to points on~$\C'$; for example,
	the point~$(2,1)$ on~$\C$ maps to~$(1,1)$ on~$\C'$), but
	the variable replacement `replace~$x$ by~$x-1$ and~$y$ by~$y$'
	changes the equation for~$\C'$ into the equation for~$\C$.
	\par\smallskip  {\bf (c)} Let~$\C : x^2 - y^2 = 0$
	and $\C' : x^2 + y^2 = 0$. Clearly $\uphi : \C \rightarrow \C'$,
	defined by $\uphi(x,y) = (x,iy)$ is a rational map from~$\C$ to~$\C'$,
	with inverse~$\upsi(x,y) = (x,-iy)$. This shows that~$\C$ and~$\C'$
	are birationally equivalent over~$\bbbc$. However, $\C$ and~$\C'$
	are not birationally equivalent over~$\bbbq$, since any such
	map would take the infinitely many members of~$\CQ$ to infinitely
	many members of~$\C'(\bbbq)$, contradicting the fact that
	$\C'(\bbbq) = \{ (0,0) \}$.
	\par\smallskip  {\bf (d)} Let~$\C : y^2 = x^4 + 3x^2 + 5$
	and $\C' : y^2 = 5x^4 + 3x^2 + 1$. Define $\uphi(x,y) = 
	(\frac{1}{x}, \frac{y}{x^2})$. If $(x,y)$ is a point on~$\C$
	then $y^2 = x^4 + 3x^2 + 5$ and so $\frac{y^2}{x^4} = 1 + \frac{3}{x^2}
	+ \frac{5}{x^4}$, giving: 
	$\bigl( \frac{y}{x^2} \bigr)^2 = 1 + 3\bigl( \frac{1}{x}\bigr)^2 
	+ 5\bigl( \frac{1}{x}\bigr)^4$, so that 
	$\bigl(\frac{1}{x},\frac{y}{x^2}\bigr)$ is a point on~$\C'$.
	Our map~$\uphi$ is then a rational map (over~$\bbbq$)
	from~$\C$ to~$\C'$. The inverse map is $\upsi(x,y) = 
	(\frac{1}{x}, \frac{y}{x^2})$ (check that 
	$\upsi\bigl(\uphi(x,y)\bigr) = \upsi\bigl( \frac{1}{x}, \frac{y}{x^2} \bigr)
	= \bigl( \frac{1}{1/x} , \frac{y/x^2}{(1/x)^2} \bigr) = (x,y)$,
	so that $\upsi\ \uphi$ is the identity, as is $\uphi\ \upsi$). 
	Hence~$\uphi$ is a birational transformation over~$\bbbq$;
	the curves~$\C$ and~$\C'$ are birationally equivalent over~$\bbbq$.
	\par\smallskip  {\bf (e)} Let $\C : x^2 + y^2 = 1$ and $\C' : y = 0$.
	It might at first seem surprising that a circle should be birationally
	equivalent to a line, but we can establish the map first by fixing
	a specific point on~$\C$, say~$P_0 = (-1,0)$, and mapping a point
	on~$\C$ to~$s = \frac{y}{x+1}$, the slope of the line from~$P_0$
	to~$(x,y)$ (literally, we are mapping it to~$(s,0)$).
	Define: $\uphi(x,y) = ( \frac{y}{x+1} , 0 )$ from~$\C$ to~$\C'$
	(defined everywhere except at the point~$(-1,0)$, but this is
	allowed, since the definition of rational map allows
	us to have a finite number of points where the map is not defined).
	For the inverse, note that if the slope is~$s$, then the line
	through~$P_0$ and~$(x,y)$ has equation: $y = s(x+1)$;
	substituting this into~$\C$ gives $x^2 + s^2(x+1)^2 = 1$,
	and so: $(x + 1)( x - 1 + s^2(x + 1) ) = 0$. When~$x\not = -1$,
	this gives~$x = \frac{1 - s^2}{1 + s^2}$ and
	$y = s(x+1) = \frac{2s}{1 + s^2}$. This suggests
	that, for the inverse map, we should take:
	$\upsi(x,y) = \bigl( \frac{1 - x^2}{1 + x^2}, \frac{2x}{1 + x^2} \bigr)$.
	It is straightforward to check that this is indeed a map
	from~$\C'$ to~$\C$ (since $\bigl( \frac{1 - x^2}{1 + x^2} \bigr)^2
	+ \bigl( \frac{2x}{1 + x^2} \bigr)^2 = 1$  for any~$x$),
	that $\upsi \ \uphi =$ identity on~$\C$ and
	that $\uphi \ \upsi =$ identity on~$\C'$.
	Hence~$\C$ and~$\C'$ are birationally equivalent over~$\Q$.
\end{exs}
\begin{defn}\label{defn:param}
	A {\it parametrisation} of a curve~$\C$ is a birational equivalence
	between~$\C$ and a line.
\end{defn}
\begin{comm}\label{comm:param}
	The birational transformation in Example~\ref{exs:birat}(e)
	is a parametrisation of the circle~$x^2 + y^2 = 1$.
	Note that a parametrisation is an unusual type of birational
	transformation, in that it gives a map to a single variable;
	in this case, $\bigl( \frac{1 - s^2}{1 + s^2}, \frac{2s}{1 + s^2} \bigr)$
	gives a description of the points on~$\C$ in terms of the
	parameter~$s$. Since the maps~$\uphi$ and~$\upsi$ are defined over~$\bbbq$,
	this gives a way of describing all $\bbbq$-rational points on~$\C$,
	namely: $(x,y) \in \CQ \iff s \in \Q$. For example,
	$s=2$ gives $\bigl( -\frac{3}{5}, \frac{4}{5}\bigr) \in \CQ$. This parametrisation can be used to describe all Pythagorean triples.
\end{comm}
The curve~$x^2 + y^2 = 1$ is a special case of the following
class of curves.
\begin{defn}\label{defn:conic}
	A {\it conic} is a smooth quadratic curve. The general form of the equation is
	$a x^2 + 2 b x y + c y^2 + 2 d x + 2 f y + g = 0$, satisfying
	$$ 
	\begin{array}{ | c c c | c}
		a & b & d & \\
		b & c & f & \ \not= 0
		\ \ \ \hbox{(which guarantees that the curve is smooth).}\\
		d & f & g & \\
	\end{array}
	$$
\end{defn}
A conic is an ellipse, hyperbola or parabola; the name `conic'
refers to the fact that these are the curves which can be obtained
by intersecting a plane and a double-cone (two cones with the same
axis, placed apex to apex). The parametrisation of the circle
given in Example~\ref{exs:birat}(e) is a special case of
the following result.
\begin{thm}\label{thm:conic}
	Any conic~$\C$ (over~$K$) with a $K$-rational point is birationally
	equivalent to a line (i.e.\ it is parametrisable).
\end{thm}
\begin{proof}
	We are given that there exists a $K$-rational point $(x_0,y_0)$
	on the curve $\C : f(x,y) = 0$. Let $g(x,y) = f(x + x_0, y + y_0)$.
	This contains the point~$(0,0)$ so that we can write:
	$g(x,y) = g_1(x,y) + g_2(x,y)$, where~$g_1$ is homogeneous 
	\& linear, and~$g_2$ is homogeneous \& quadratic.
	Hence $g(x,tx) = x\phi_1(t) + x^2\phi_2(t) = 0$.
	Apart from~$x=0$, we can take $x = -\phi_1(t)/\phi_2(t),
	y = -t \phi_1(t)/\phi_2(t)$ (with inverse $t = y/x$)
	as a parametrisation of~$g(x,y) = 0$.
	The parametrisation of~$\C$ is then:
	$x = x_0-\phi_1(t)/\phi_2(t), y = y_0 -t \phi_1(t)/\phi_2(t)$ 
	(with inverse $t = (y-y_0)/(x-x_0)$).
\end{proof}
\begin{defn}\label{defn:intersect}
	The curves $\C : f(x,y) = 0$ and $\C' : g(x,y) = 0$
	{\it intersect} at~$P = (x_0,y_0)$ if~$P$ lies on
	both of~$\C$ and~$\C'$ [that is, $f(x_0,y_0) =
	g(x_0,y_0) = 0$]. 
	%The curves {\it intersect with multiplicity~$r>0$}
	%at~$P$ if both~$f(x_0,y_0) = g(x_0,y_0) = 0$ 
	%and $\frac{\ddd^i y}{\ddd x^i}(P) \hbox{ on~$\C$} = 
	%\frac{\ddd^i y}{\ddd x^i}(P) \hbox{ on~$\C'$}$ for 
	%all $1\leqslant i \leqslant r-1$ [if the tangents at~$P$ are vertical,
	%then use~$\frac{\ddd^i x}{\ddd y^i}$ instead of~$\frac{\ddd^i y}{\ddd x^i}$].
\end{defn}
\begin{defn}\label{defn:intersectmult}
	Suppose the curves $\C : f(x,y) = 0$ and $\C' : g(x,y) = 0$
	intersect at~$P = (x_0,y_0) \in \C(L)$ (with $L$ a field containing the field of definition of the curve). The curves {\it intersect with multiplicity~$r>0$}
	at~$P$ if the dimension of the quotient ring \[\dim_L L\lb x,y \rb/(f(x+x_0,y+y_0),g(x+x_0,y+y_0)) = r.\]
\end{defn}
The intersection multiplicity is $\infty$ if and only if $\C$ and $\C'$ have a common irreducible component containing $P$. We refer to Fulton \emph{Algebraic Curves} for details and proofs of the fundamental properties of the intersection multiplicity. You can also take a look at Part B Algebraic Curves for an approach via resultants. 

The proofs of the following two lemmas can be found in the preliminary reading file.
\begin{lem}\label{lem:curvelinemult}
	Consider a curve $\C : f(x,y) = 0$ over $K$ and a line $\D$ parameterised by $x = at + b$, $y = ct + d$, with $a,b,c,d \in K$ and $a,c$ not both zero. Then $\C$ and $\D$ intersect at the points $P = (a t_0 + b,ct_0+d)$ with $t_0$ a root of the polynomial $F(t) = f(at+b,ct+d)$. If $F(t)$ is identically $0$, then $\C$ contains the line $\D$. 
	
	Suppose $t_0 \in \overline{K}$ is a root of $F(t)$ and let $P = (a t_0 + b,ct_0+d)$. Then $\C$ and $\D$ intersect at $P$ with multiplicity equal to the multiplicity of $t_0$ as a root of $F(t)$. 
\end{lem}
%\begin{proof} The intersection property is clear, so we need to verify the assertion about multiplicities. We can apply an affine transformation and assume WLOG that $t_0 = 0$, so $P = (b,c)$. The line $\D$ has equation $g(x,y) = cx - ay +ad-bc = 0$. 
%	We have to compute the dimension of the $\overline{K}$-vector space 
%	\[\overline{K}\lb x,y\rb/(f(x+b,y+d),g(x+b,y+d)).\] It is not hard to check that the map
%	\begin{align*}
%		\overline{K}\lb x,y\rb/(g(x+b,y+d) &\to  \overline{K}\lb t \rb \\
%		x &\mapsto a t\\
%		y &\mapsto ct
%	\end{align*} is an isomorphism. So we need to compute the dimension of the $\overline{K}$-vector space 
%	\[\overline{K}\lb t\rb/(f(at+b,ct+d)) = \overline{K}\lb t\rb/(F(t)).\]
%	We claim that this is equal to the multiplicity of $0$ as a root of $F(t)$. Write $F(t) = t^r \tilde{F}(t)$, where $\tilde{F}(t)$ has non-zero constant term. It is a nice exercise to show that $\tilde{F}(t)$ has a multiplicative inverse in the formal power series ring $\overline{K}\lb t\rb$. So the ideal generated by $F(t)$ is equal to $(t^r)$. Finally, we see that $\overline{K}\lb t \rb/(t^r)$ has dimension $r$, since it has $1,t,\ldots,t^{r-1}$ as a basis.
%\end{proof}
\begin{lem}
	Suppose $\C$ and $\C'$ are two curves intersecting at a point $P \in \C(K) \cap \C'(K)$. Suppose moreover that $P$ is a nonsingular point on both curves. Then the intersection multiplicity at $P$ is $> 1$ if and only if the tangent lines to $\C$ and $\C'$ at $P$ coincide. 
\end{lem}
%\begin{proof}
%	Translating $x$ and $y$, we may assume that $P= (0,0)$. If $f(x,y)$ is the equation for $\C$, suppose WLOG that $\lambda = \frac{\partial f}{\partial y}(P) \ne 0$ (otherwise we can swap the roles of $x$ and $y$). Then the tangent line to $\C$ at $P$ has equation $y = -\lambda^{-1}\frac{\partial f}{\partial x}(P)x$. In this situation, the natural map $K\lb x\rb \to K\lb x,y\rb/(f(x,y))$ is an isomorphism, with inverse given by mapping $y$ to a power series $Y(x)$ of the form $Y(x) = -\lambda^{-1}\frac{\partial f}{\partial x}(P)x~+$ higher order terms. (This can be proved by a version of Hensel's lemma, which we will see in the course, and is the implicit function theorem for formal power series.) So we have to compute the dimension of the quotient $K\lb x \rb / (g(x,Y(x)))$. As in the proof of Lemma \ref{lem:curvelinemult}, this is given by the multiplicity of $0$ as a root of $g(x,Y(x))$. It is $> 1$ if and only if the linear part $ax+by$ of $g(x,y)$ satisfies $a - b\lambda^{-1}\frac{\partial f}{\partial x}(P) = 0$. On the other hand, the tangent to $\C'$ at $P$ has equation $ax + by = 0$. A short calculation shows that this tangent is the same as the tangent for $\C$ if and only if we do indeed have $a - b\lambda^{-1}\frac{\partial f}{\partial x}(P) = 0$.
%\end{proof}

\begin{ex}\label{ex:intersect}
	Let $\C : y^2 = x^3 + 2x + 1$ and $\D : y = x + 1$.
	On substituting~$\D$ into~$\C$ we see that the $x$-coordinate of
	any point of intersection must satisfy $(x + 1)^2 = x^3 + 2x + 1$,
	and so $x^2(x-1) = 0$, giving only~$x=0,1$ as possibilities.
	Substituting~$x=0$ in~$\D$ gives~$y=1$; substituting~$x=1$ in~$\D$
	gives~$y=2$. So, the only possible points of intersection
	are~$(0,1)$ and~$(1,2)$ [and these do indeed lie on~$\C$ and~$\D$]. It also follows from Lemma \ref{lem:curvelinemult} that the intersection multiplicities at these points are $2$ and $1$ respectively.
	%To find the multiplicity of intersection at~$(0,1)$, compute:
	%\par On~$\C$, $2y \frac{\ddd y}{\ddd x} = 3x^2 + 2$,
	%and so $\frac{\ddd y}{\ddd x}(0,1)  = \frac{3\cdot 0^2 + 2}{2\cdot 1} = 1$.
	%\par On~$\D, \frac{\ddd y}{\ddd x} = 1$ everywhere.
	%\par On~$\C$, $2\frac{\ddd y}{\ddd x}\frac{\ddd y}{\ddd x} 
	%+ 2y\frac{\ddd^2 y}{\ddd x^2}
	%= 6x$ gives $2 \frac{\ddd y}{\ddd x}(0,1)\frac{\ddd y}{\ddd x}(0,1) 
	%+ 2y\frac{\ddd^2 y}{\ddd x^2}(0,1) = 6\cdot 0$,
	%so $\frac{\ddd^2 y}{\ddd x^2}(0,1) = -1$.
	%\par On~$\D$, $\frac{\ddd^2 y}{\ddd x^2} = 0$ everywhere.
	%\par\noindent In summary,~$(0,1)$ lies on both~$\C$ and~$\D$,
	%and $\frac{\ddd y}{\ddd x}(0,1)$ on~$\C$ is equal to
	%$\frac{\ddd y}{\ddd x}(0,1)$ on~$\D$, but
	%$\frac{\ddd^2 y}{\ddd x^2}(0,1)$ in~$\C$ is not equal to
	%$\frac{\ddd^2 y}{\ddd x^2}(0,1)$ on~$\D$. Hence~$(0,1)$ is a point
	%of intersection of multiplicity~$2$.
	%\par The points~$(1,2)$ lies on both~$\C$ and~$\D$, but
	%$\frac{\ddd y}{\ddd x}(1,2) = \frac{3\cdot 1^2 + 2}{2\cdot 2} = \frac{5}{4}$
	%on~$\C$, which is not equal to $\frac{\ddd y}{\ddd x}(1,2) = 1$ on~$\D$,
	%so that~$(1,2)$ is a point of intersection of multiplicity~$1$.
	%\par In summary, we say that~$\C$ and~$\D$ have $3$ points
	%of intersection, namely: $(0,1)$ with multiplicity~$2$
	%and~$(1,2)$ with multiplicity~$1$.
\end{ex}
\begin{comm}\label{comm:resintersect}
	For more complicated examples, we cannot always find the points
	of intersection by a straightforward substitution of one equation
	into the other. Given two curves~$\C : f(x,y) = 0$ of degree~$m$
	and $\D : g(x,y) = 0$ of degree~$n$,
	a systematic approach to finding the points
	of intersection is possible via resultants. One initially picks
	one of the variables, $y$~say, and
	computes the resultant of~$f(x,y)$ and~$g(x,y)$, regarded as
	polynomials in~$y$, by writing them as:
	$f(x,y) = f_m(x)y^m + \ldots + f_0(x)$, and similarly for~$g(x,y)$.
	The matrix in Definition~\ref{defn:resultant} will have
	entries that are polynomials in~$x$, and consideration of the
	degrees of these polynomials shows that the resultant
	of~$f(x,y)$ and~$g(x,y)$ (regarded as 
	polynomials in~$y$) will be a polynomial in~$x$ of degree at
	most~$mn$. Any point of intersection of~$\C$ and~$\D$ must
	have $x$-coordinate  which is a root of the at-most-degree-$mn$
	polynomial. For each value of~$x$, one can then substitute back
	into~$\C$ and~$\D$ to find the corresponding $y$-coordinates.
\end{comm}
\medskip

\subsection*{Projective curves}

There are several respects in which affine space is unsatisfying.
Consider, for example, the true statement in affine space:
two distinct lines meet at exactly one point, except when parallel.
It would be much nicer to have a cleaner statement,
in which we remove `except when parallel'.
Intuitively, parallel lines intersect `at infinity', given
that the point of intersection shoots off to infinity as
two lines become closer and closer to parallel.


Similarly, consider the affine curves: $\C : y^2 = x^3 + 1$
and $D : y = x + 1$; these meet at the points~$(-1,0), (0,1),(2,3)$,
each with multiplicity~$1$. On trying other lines in place
of~$\D$, one typically finds again that there are 3~points
of intersection (when counted with multiplicity). An apparent exception
is~$\D : x = 0$, which intersects~$\C$ only at two points,~$(0,1)$ and~$(0,-1)$,
and this is true for any vertical line. We seem to have a rule:
any line intersects~$\C$ at exactly $3$~points (counted with
multiplicity) except when the line is vertical. Again, we
would like a cleaner statement, in which we remove `except
when the line is vertical'. Again, the third point
of intersection seems to be `at infinity'.
\par
Points at infinity are intuitively points~$(x,y)$ where there
is a denominator of~$0$. We cannot express this idea using only
pairs~$(x,y)$, where~$x,y$ lie in a field~$K$. A natural approach
is to write: $x = X/Z, y = Y/Z$ and identify the point~$(x,y)$
with the triple~$(X,Y,Z)$. As long as~$Z\not= 0$, we can
go in the other direction from the triple~$(X,Y,Z)$ to~$(x,y)$.
Note that, for any~$k\in K^*$, the triple~$(kX, kY, kZ)$
corresponds to~$(kX/kZ, kY/kZ) = (X/Z, Y/Z) = (x,y)$, and so
we impose a relation, that two triples are regarded 
as being the same if they
are nonzero scalar multiples of each other. Subject to this
relation, there is then a $1-1$ correspondence between~$(x,y)$
and triples~$(X,Y,Z)$ with~$Z\not=0$.
On the other hand, the triples~$(X,Y,Z)$ with~$Z=0$
do not correspond to any~$x,y\in K$, and such triples give
us a way of describing formally these new points at infinity.
\begin{defn}\label{defn:proj}
	Let~$K$ be a field.
	$\P^n(K) = \{ (x_0,\ldots ,x_n) : x_0,\ldots ,x_n \in K,
	\hbox{ not all }0\}$, subject to the relation that
	$(x_0,\ldots x_n) = (y_0,\ldots ,y_n)$ in~$\P^n(K)$
	if there exists~$r\in K, r\not=0$, such
	that $(y_0,\ldots ,y_n) = (r x_0,\ldots r x_n)$.
	$\P^n(K)$ is called {\it projective} $n$-space over~$K$.
\end{defn}
\begin{ex}\label{ex:proj}
	$(1,2,3) = (3,6,9)$ in $\P^2(\bbbq)$. (N.B.\ $(0,0,0)\not\in \P^2(\bbbq)$.) 
\end{ex}
\begin{defn}\label{defn:projpoly}
	A {\it polynomial in $n$ projective variables}
	is an $(n+1)$-variable homogeneous polynomial.
	%[recall: this means
	%that all terms have the same degree].
	% for example,
	%$X^3 - 3X Z^2 + Z^3$ is a polynomial in $1$~projective variable,
	%defined over~$\bbbq$.
	A {\it projective curve} in~$\P^2$ is defined by a homogeneous 
	polynomial in~$3$ variables~$F(X,Y,Z) = 0$, for example,
	$X^3 + Y^3 - Z^3 = 0$.
\end{defn}
\begin{defn}\label{defn:homogenisation}
	Let~$\C : f(x,y) = 0$ be an (affine) curve.
	The {\it homogenisation} of~$\C$ is the projective curve~$F(X,Y,Z) = 0$
	of the same degree as~$f(x,y)$, with the 
	property that~$F(x,y,1) = f(x,y)$. A point~$(X_0,Y_0,Z_0)$
	on~$F(X,Y,Z)=0$ with~$Z_0=0$ is called a {\it point at infinity} on~$\C$.
	When~$Z_0\not= 0$, the point~$(X_0,Y_0,Z_0)$ corresponds
	to~$(X_0/Z_0, Y_0/Z_0)$ on~$f(x,y) = 0$.
\end{defn}
\begin{ex}\label{ex:homog1}
	Let~$\C : y^2 = 4 x^2 + 1$, so that~$f(x,y) = y^2 - 4 x^2 - 1 = 0$.
	The associated projective curve (the homogenisation) is:
	$Y^2 = 4 X^2 + Z^2$ (so that $F(X,Y,Z) = Y^2 - 4 X^2 - Z^2$).
	The two points at infinity are: $(1,2,0)$ and~$(1,-2,0)$.
\end{ex}
\begin{ex}\label{ex:homog2}
	For the curve~$\C : y^2 = x^3 + 1$, the associated projective
	curve is~$Z Y^2 = X^3 + Z^3$. To find the points at infinity
	(the points where~$Z=0$),
	substitute~$Z=0$ into the equation, giving $X^3= 0$ and so~$X=0$.
	This forces~$Y\not= 0$ (since~$(0,0,0)$ is not allowed as
	a point in~$\P^2$). So, the points at infinity are of the
	form~$(0,Y,0)$, where~$Y\not= 0$. But these are all the
	same in~$\P^2$, since they are scalar multiples of each other;
	therefore this is exactly one point at infinity, which we
	can represent by~$(0,1,0)$, say.
\end{ex}
\begin{comm}\label{comm:parallel}
	Two distinct affine lines $a_1 x + b_1 y + c_1 = 0$
	and $a_2 x + b_2 y + c_2 = 0$ meet at exactly one point,
	except when parallel. For example, $x + y + 2 = 0$
	and $x + y + 3 = 0$ do not intersect.
	For projective lines, the rule is the same, but we
	can remove the phrase `except when parallel'.
	For example, the projective lines $X + Y  + 2Z = 0$
	and $X + Y + 3Z = 0$ have~$(1,-1,0)$ as the unique
	point of intersection.
\end{comm}
\begin{defn}\label{defn:projsing}
	A projective curve~$F(X,Y,Z) = 0$ has a {\it singularity}
	at~$(X_0,Y_0,Z_0)$ when:
	\par $F(X_0,Y_0,Z_0) = \frac{\partial F}{\partial X}(X_0,Y_0,Z_0) =
	\frac{\partial F}{\partial Y}(X_0,Y_0,Z_0) =
	\frac{\partial F}{\partial Z}(X_0,Y_0,Z_0) = 0$.
\end{defn}

\begin{lem}\label{lem:projtgt}
	Suppose $(X_0,Y_0,Z_0)$ is a nonsingular point on the projective curve $F(X,Y,Z) = 0$. Then the tangent line at the point $(X_0,Y_0,Z_0)$ has equation 
	\[\frac{\partial F}{\partial X}(X_0,Y_0,Z_0)X +\frac{\partial F}{\partial Y}(X_0,Y_0,Z_0)Y +
	\frac{\partial F}{\partial Z}(X_0,Y_0,Z_0)Z = 0.\]
\end{lem}
\begin{proof}
Permuting the coordinates and rescaling if necessary, we may assume that $Z_0 = 1$. Then our point lies on the affine curve $F(x,y,1) = 0$. We compute the tangent line as in Comment \ref{comm:tangents} and get equation \[\frac{\partial F}{\partial X}(X_0,Y_0,1)(x-X_0) + \frac{\partial F}{\partial Y}(X_0,Y_0,1)(y-Y_0) = 0.\] Homogenising gives the projective tangent line 
\[\frac{\partial F}{\partial X}(X_0,Y_0,1)(X-X_0Z) + \frac{\partial F}{\partial Y}(X_0,Y_0,1)(Y-Y_0Z) = 0.\]

Finally, we use the fact that 
\[\frac{\partial F}{\partial X}(X_0,Y_0,1)X_0 + \frac{\partial F}{\partial Y}(X_0,Y_0,1)Y_0 + \frac{\partial F}{\partial Z}(X_0,Y_0,1) = 0\] which is a consequence of Euler's identity (which can be checked on monomials): \[\frac{\partial F}{\partial X}(X,Y,Z)X + \frac{\partial F}{\partial Y}(X,Y,Z)Z + \frac{\partial F}{\partial Z}(X,Y,Z)Z = \deg(F)F(X,Y,Z).\]
\end{proof}


\begin{comm}\label{comm:projbirat}
	Note that, by multiplying through by denominators, we can take
	rational maps and birational transformations between projective
	curves to be of the form: 
	\[\uphi (X,Y,Z) = \bigl( \phi_1(X,Y,Z), \phi_2(X,Y,Z),
	\phi_3(X,Y,Z) \bigr),\]
	 where $\phi_1, \phi_2, \phi_3$ are homogeneous
	polynomials, rather than rational functions.
\end{comm}
\begin{comm}\label{projint}
	Suppose that two projective curves $F(X,Y,Z) = 0$
	and $G(X,Y,Z) = 0$ have a point of intersection~$(X_0,Y_0,Z_0)$.
	The multiplicity of intersection can always be computed by
	using some associated affine curve. 
	At least one of~$X_0,Y_0,Z_0$ must be nonzero, since~$(0,0,0)$
	is not allowed in~$\P^2$.
	If~$Z_0\not= 0$ then the
	multiplicity of intersection is the same as that
	of~$(X_0/Z_0, Y_0/Z_0)$ on the affine curves~$F(x,y,1) = 0$
	and $G(x,y,1) = 0$ (here, $x = X/Z, y = Y/Z$).
	If~$Y_0\not= 0$ then one can use~$F(x,1,z), G(x,1,z)$, where
	$x = X/Y, z = Z/Y$. If~$X_0 \not= 0$ then 
	one can use~$F(1,y,z), G(1,y,z)$, where $y = Y/X, z = Z/X$.
\end{comm}
We can now state one of the basic results in the projective geometry of curves, generalising the fact that two projective lines have a unique point of intersection.
\begin{thm}\label{thm:bezout}[B\'ezout's Theorem] Two projective curves, with no common component, of degrees~$m,n$ intersect at precisely~$mn$ points, counted
	with multiplicity.
\end{thm}
\begin{ex}\label{ex:bezout}
	The projective curves~$Z Y^2 = X^3 + Z^3$ and $X = 0$
	intersect at the points $(0,1,1), (0,-1,1), (0,1,0)$, 
	each with multiplicity~$1$.
\end{ex}
\subsection*{Elliptic Curves}
\par Curves can be classified according to a property called
{\it genus}, which is invariant under birational equivalence.
We shall not go into the technicalities of what precisely
is meant by genus, and its properties, which would be
an entire lecture course in its own right.
The simplest type are curves of genus~$0$, which can be defined
by quadratic and linear equations. 
Recall from Theorem~\ref{thm:conic} that any conic with
a rational point can be parametrised. 
%Arithmetic questions about
%curves of genus~$0$ are reasonably straightforward to answer;
%given a conic defined over~$\bbbq$, say, one can decide within
%a predetermined amount of time whether the curve has a rational
%point. If a rational point exists, then the parametrisation
%of Theorem~\ref{thm:conic} describes all the rational points.
\par
Curves of genus~$1$ are the next natural class of curves to
consider; they are, in a sense, the next `simplest' type
of curve after conics. 
Please don't confuse `elliptic curves' (which are
of genus~$1$) with ellipses (which are of genus~$0$).
The classical terminology comes from a relationship between cubic curves
and elliptic integrals, which were much studied in the 19th century.
It can be shown that a curve of genus~$1$
is not parametrisable.
An {\it elliptic curve} over~$K$ is defined to be a nonsingular projective
curve of genus~$1$, defined over~$K$, together with a $K$-rational point on the curve.
It can also be shown that any curve
of genus~$1$ is birationally equivalent over~$K$ to a nonsingular projective cubic curve. For the purposes of this lecture course, you can 
forget about the term `genus' and will simply take this as the definition
of an elliptic curve.
\medskip
\hrule

\newpage
\section{The Group Law on an Elliptic Curve}\label{sec:grouplaw}
%% The group law, associativity, examples, torsion, number of
%% points over a finite field [2 lectures].

\begin{defn}\label{defn:elliptic}
An elliptic curve over a field~$K$ is a nonsingular projective cubic curve, defined over~$K$, with a specified $K$-rational point. 
\end{defn}

This means that an elliptic curve is defined by a degree $3$ homogeneous polynomial, in 3 variables and with coefficients in $K$. 

\begin{rem}
We won't discuss this in the course, but elliptic curves over the complex numbers have a simple description following from the Weierstrass uniformization theorem (see Chapter VI in \cite{sil:AEC1} for more details). This says that for an elliptic curve $\C$ defined over $\mathbb{C}$, we can make an identification 
\[\C(\mathbb{C}) \cong \mathbb{C}/\Lambda \] where $\Lambda$ is a free rank two abelian group generated by two complex numbers $\omega_1, \omega_2$ which are linearly independent over $\R$. The identification sends the specified point of $\C$ to the coset $0 + \Lambda$. We deduce from this that $\C(\mathbb{C})$ has the structure of an abelian group. It turns out that this group law can be defined purely algebraically which is what we are going to do next.
\end{rem}

\begin{defn}\label{defn:grouplaw}
Let $\C : F(X,Y,Z) = 0$ be an elliptic curve $/ K$
(the notation $/ K$ means `defined over~$K$'; that is, all
of the coefficients of~$\C$ are in the field~$K$).
So,~$\C$ is a nonsingular projective cubic curve, with a $K$-rational
point, which we shall denote~$\o$.
For any two points~$\a,\b$ on~$\C$ (defined over a common extension field $L/K$), let~$\ell_{\a,\b}$
denote the line which meets~$\C$ at~$\a,\b$ (if~$\a,\b$ are distinct
then~$\ell_{\a,\b}$ is the unique line through~$\a,\b$;
if~$\a=\b$ then $\ell_{\a,\b}$ is the line tangent to~$\C$ at~$\a=\b$).

\begin{minipage}[c]{0.4\textwidth}
	\includegraphics[width=\textwidth]{add-1.png}
\end{minipage}\begin{minipage}[c]{0.6\textwidth}
Let $\ell_{\a,\b}$ denote the line which meets~$\C$ at~$\a,\b$.

Then~$\ell_{\a,\b}$ and~$\C$ have~$3$ points of intersection
(B\'ezout).

Let~$\d$ be the third point of intersection between~$\C$
and~$\ell_{\a,\b}$. 

Now, let~$\ell_{\o,\d}$ denote the line which meets~$\C$ at~$\o$
and~$\d$.

Let~$\c$ be the third point of intersection between~$\C$ and~$\ell_{\o,\d}$.

Define~$\a + \b = \c$.
\end{minipage}
%\vskip 20pt
%\newpage
%\hskip 120 pt \vrule width 1 pt depth 2 pt height 130 pt
%\reallynopagebreak
%\vskip-150pt
%\hskip 37 pt {\lower 6.8pt \hbox{\a}} \hskip 28 pt 
%{\lower 6.8pt \hbox{\b}}
%\par  $\ell_{\a,\b}$ \hskip 30 pt {\lower 3pt\hbox{$|$}} 
%\hskip 30 pt {\lower 3pt\hbox{$|$}}
%\hskip 40 pt $\d$
%\hrule width 150 pt depth 1 pt height 1 pt
%\vskip 30 pt \hskip 117 pt --- \c
%\vskip 20 pt \hskip 117 pt --- \o
%\vskip 20 pt \hskip 123 pt $\ell_{\o,\d}$
%\reallynopagebreak
%\vskip-125pt

\begin{minipage}[c]{0.4\textwidth}
	\includegraphics[width=\textwidth]{add-2.png}
\end{minipage}\begin{minipage}[c]{0.6\textwidth}
Let~$\ell_{\o,\o}$ be the line tangent to~$\C$ at~$\o$.

Let~$\k$ be the third point of intersection between~$\C$ and~$\ell_{\o,\o}$.

Now, let~$\ell_{\a,\k}$ be the line which meets~$\C$ at~$\a$ and~$\k$.

Let~$\overline\a$ be the third point of intersection between~$\C$ and~$\ell_{\a,\k}$.

Define~$-\a$ to be~$\overline\a$.
\end{minipage}
\end{defn}
%\hskip 120 pt \vrule width 1 pt depth 2 pt height 125 pt
%\reallynopagebreak
%\vskip-145pt
%\hskip 37 pt {\lower 6.8pt \hbox{\a}} \hskip 28 pt 
%{\lower 6.8pt \hbox{$\overline\a$}}
%\reallynopagebreak
%  $\ell_{\a,\k}$ \hskip 30 pt {\lower 3pt\hbox{$|$}} 
%\hskip 30 pt {\lower 3pt\hbox{$|$}}
%\hskip 40 pt $\k$
%\reallynopagebreak
%\hrule width 150 pt depth 1 pt height 1 pt
%\reallynopagebreak
%\vskip 50 pt \hskip 114 pt $\Biggr)$ \hskip-9pt --- \o
%\reallynopagebreak
%\vskip 16 pt \hskip 123 pt $\ell_{\o,\o}$
%\reallynopagebreak
%%\vskip-126pt
%\reallynopagebreak 
%\hskip 178 pt Let~$\ell_{\o,\o}$ be the line tangent to~$\C$ at~$\o$.
%\reallynopagebreak 
%\hskip 178 pt Let~$\k$ be the third point of intersection between~$\C$
%and~$\ell_{\o,\o}$.
%\reallynopagebreak 
%\hskip 178 pt Now, let~$\ell_{\a,\k}$ be the line which meets~$\C$ at~$\a$
%and~$\k$.
%\reallynopagebreak 
%\hskip 178 pt Let~$\overline\a$ 
%be the third point of intersection between~$\C$
%and~$\ell_{\a,\k}$.
%\reallynopagebreak 
%\hskip 178 pt Define~$-\a$ to be~$\overline\a$.
%\reallynopagebreak
%\vskip 30 pt
%\end{defn}
%\reallynopagebreak
%\vspace{20pt}

We shall soon show that $\a + \b$ is a commutative 
group law on the points on~$\C$, with identity~$\o$ and
the inverse of~$\a$ given by~$-\a$. A priori, the various new points we constructed in the above diagrams will be defined over a chosen algebraic closure $\overline{L}$ of the field of definition for the points $\a,\b$. But we will show that these points are all $L$-rational.


First we need the
following technical lemma.
\par
\begin{lem}\label{lem:pregplaw}
Let~$P_1,\ldots , P_8$ be such that no~$4$ points lie on
a line and no~$7$ points lie on a conic. Then there exists
a unique point~$P_9$ which is
a 9th point of intersection of any two cubics passing
through~$P_1,\ldots ,P_8$.
\end{lem}
%  {\it Optional Proof}\ \ See \ref{lem:pregplaw0}.
  {\it Optional Proof}. See 0.140.
\begin{thm}\label{thm:gplaw}
Let~$\C$ be an elliptic curve~$/K$, with $K$-rational point~$\o$.
Then \[(\a,\b)\mapsto\a + \b,\] as in Definition~\ref{defn:grouplaw},
gives a commutative group law on the points of~$\C$, with
identity~$\o$. The inverse of~$\a$ is given by the point $-\a$,
constructed in Definition~\ref{defn:grouplaw}.

Furthermore, the $K$-rational points~$\C(K)$ form a group under this group law,
called the~{\it Mordell-Weil group}\footnote{Typically this name is reserved for the case where $K$ is a number field.}. More generally, for any extension field $L/K$ the $L$-rational points $\C(L)$ form a group under the group law.
% N.B. Could verbally recall here that the notation $\C(K)$ (defined in the
% Preliminary Reading) means the set of all points on $\C$
% which have all coordinates in $K$.
\end{thm}
\begin{proof}
% N.B. During this proof, after drawing the diagram, 
% ask the class what is $\a + \b$ (and later: $\b + \c$).
It is easy to show commutativity, the fact that~$\o$ is the identity, and the
fact that~$-\a$ is the inverse of~$\a$.
The only difficult problem is associativity. In order
to prove associativity, consider the following diagram:

\begin{center}
\includegraphics[width=10cm]{assoc-diag}
\end{center}
%\newpage
%\hskip 50 pt \vrule width 1 pt depth 2 pt height 240 pt \hskip 60 pt
%\vrule width 1 pt depth 2 pt height 240 pt \hskip 60 pt
%\vrule width 1 pt depth 2 pt height 240 pt 
%\reallynopagebreak
%\vskip-230pt \hskip 127 pt {\lower 5.5pt \hbox{\bf w}} \vskip -5 pt
%\hskip 53 pt {\bf a} \hskip 67 pt {\lower 3pt\hbox{$|$}} 
%\hskip 36 pt {\bf v} \hskip 60 pt $r$ \vskip -2.5 pt
%\hrule width 240 pt depth 1 pt height 1 pt \vskip 15 pt
%\hskip 98 pt {\bf f} \hskip -2 pt --- \vskip 28 pt
%\hskip 52.5 pt {\bf b} \hskip 50 pt {\bf c} \hskip 50 pt {\bf u}
%\hskip 60 pt $s$ \vskip 2pt
%\hrule width 240 pt depth 1 pt height 1 pt \vskip 65 pt
%\hskip 52.5 pt {\bf d} \hskip 50 pt {\bf e} \hskip 51 pt \o
%\hskip 62 pt $t$ \vskip 1pt
%\hrule width 240 pt depth 1 pt height 1 pt \vskip 60 pt
%\hskip 49 pt $\ell$ \hskip 51 pt $m$ \hskip 48 pt $n$


Here, $r,s,t,\ell,m,n$ are lines. On each line, the labelled points
are the points of intersection between~$\C$ and that line.
From the construction of Definition~\ref{defn:grouplaw}, 
{$\a + \b = \e$,} and so 
{$(\a + \b) + \c $ is the 3rd point of intersection on~$\ell_{\o,\f}$.}

Similarly, {$\b + \c = \v$,}
and {$\a + (\b + \c)$ is the 3rd point of intersection on~$\ell_{\o,\w}$.}

To show $(\a + \b) + \c = \a + (\b + \c)$, it
is therefore sufficient to show that~$\f = \w$. Let $F_1 = \ell m n$
and $F_2 = rst$, both of which are cubic curves (recall that each line corresponds to a degree one homogeneous polynomials, so their product is a degree three polynomial defining a cubic curve).

Now we observe that $\C$ and~$F_1$ has the following $8$ points in common: $\a,\b,\c,\d,\e,\u,\v,\o$ ($\f$ is the 9th common point). $\C$ and~$F_2$ also have same~$8$ 
 points in common, together with $\w$. From Lemma~\ref{lem:pregplaw}, the 9th point of intersection of~$\C$ and~$F_1$ must be the same as the 9th
point of intersection of~$\C$ and~$F_2$; that is, $\f = \w$,
as required. Hence, $+$ is a commutative group law.

It remains to show that~$\CK$ forms a group under $+$. We are given that
$\o \in \CK$. Let~$\a,\b \in \CK$. It is sufficient to
show that~$\a + \b \in \CK$ and that~$-\a\in \CK$.
\par Let~$\a = (x_1,y_1)$ and $\b = (x_2,y_2)$,
where~$x_1,y_1,x_2,y_2\in K$. Then the line through~$\a,\b$
is (in affine form) $\ell_{\a,\b} : y = \ell x + m$, where 
$\ell = \frac{y_1 - y_2}{x_1 - x_2}\in K$
and $m = \frac{x_1 y_2 - x_2 y_1}{x_1 - x_2} \in K$.
Substitute $y = \ell x + m$ into the cubic equation for~$\C$
to get; $\phi(x) = x^3 + c_2 x^2 + c_1 x + c_0 = 0$, defined over~$K$.
Let~$\phi(x) = (x - x_1)(x-x_2)(x-x_3)$ be the factorisation of~$\phi(x)$.
Then~$x_1,x_2,x_3$ are the $3$~roots of~$\phi$ and so~$x_1+x_2+x_3 = -c_2$,
giving: $x_3 = -c_2 - x_1 - x_2 \in K$ and $y_3 = \ell x_3 + m \in K$.
The line~$\ell_{\a,\b}$ then meets~$\C$ at 
$\a,\b,\d = (x_3,y_3) \in \CK$.
The same argument shows that the line $\ell_{\o,d}$ through~$\o,\d$
has 3rd point of intersection~$\c$ which is also in~$\CK$.
But $\c = \a+\b$ and so we have shown that~$\a + \b \in \CK$.
A similar argument shows that if $\a \in \CK$ then $-\a \in \CK$.
Hence $\CK$ is a group, as required. The same argument applies when we replace $K$ by any extension field $L/K$. 
\end{proof}
\par
% N.B. Can omit the following aside in lectures.
{\it Aside: It is apparent that, in the above proof, we have dealt
with the `typical' case, where none of our points are repeated
(for the proof of associativity),
and none are at infinity (for the proof that~$\CK$ is a group,
since the points were written in affine form). It
is straightforward to check these special cases; we shall not
bother to do so here.}
\par\par\par
\begin{comm}\label{comm:birathom} When two nonsingular cubics
$\C_1, \C_2$ are birationally equivalent over~$K$
(under $\phi : \C_1 \longrightarrow \C_2$), with $\phi(O_1) = O_2$, it can be shown that $\phi$ induces a group isomorphism between $\C_1(K)$ and $\C_2(K)$. If $\phi$ is just a rational map, still sending $O_1$ to $O_2$, it induces a group homomorphism.

(\textit{For those who have learned some more algebraic geometry.}) A rational map from a nonsingular curve to a projective variety always extends to a morphism of varieties. In particular, it can be defined at every point of the curve, so the birational transformation $\phi$ automatically induces a bijection between the sets of $K$-rational points.
\end{comm}
% N.B. The term `birationally equivalent' is defined
% in the Preliminary Reading.
\par
\begin{comm}\label{comm:affineell}
By an elliptic curve, we shall always mean a projective curve,
but often write the equation in affine form. Note that,
whichever way it is written, we are always referring to the
projective curve. For example, if we say `let $\C : y^2 = x^3 + 3$
be an elliptic curve', it should be understood that
this is a shorthand notation for the corresponding
projective curve $Z Y^2 = X^3 + 3 Z^3$.
\end{comm}
\begin{thm}\label{thm:wform}
Let~$K$ be a field satisfying $\chari(K) \not= 2,3$ (recall -- this
means that $1 + 1\not= 0$ and~$1+1+1\not=0$).
Then any elliptic curve over~$K$ is birationally equivalent over~$K$
to a curve of the form $y^2 = x^3 + A x + B$, with the birational transformation sending the identity $\o$ to the point at infinity ($(0:1:0)$ in projective coordinates).
\par
When~$K = \Q$, we can birationally transform any~$y^2 = \hbox{cubic in }x$
to a curve of the form~$y^2 = x^3 + A x + B$, with~$A,B\in \bbbz$,
using only maps of the form~$(x,y) \mapsto (ax+b,cy)$.
\end{thm}
\begin{comm}\label{comm:quartic}
Let~$K$ be a field satisfying $\chari(K) \not= 2,3$,
and let~$g(x)$ be a quartic polynomial over~$K$ with nonzero discriminant.
It can be shown that any affine curve \[\D : y^2 = g(x)\] with a $K$-rational point, is birationally equivalent over $K$ to an elliptic curve $\C$ of the form $y^2 = x^3 + A x + B$ (see p.~35 of \cite{cas:ell}). Note that the point at infinity $(0:1:0)$ in the homogenisation of $\D$ is singular. The affine curve $\D$ is sometimes called an `affine model' for the elliptic curve $\C$. 
% N.B. See the Preliminary Reading for the defn of discriminant.
\end{comm}
\begin{comm}\label{comm:wform}
	When $\chari(K) \neq 2,3$, we shall typically take our elliptic curves to have the form
	$$ \E : y^2 = x^3 + Ax + B, \hbox{ where } A,B \in K,$$
	which should be regarded as shorthand for the projective
	curve $Z Y^2 = X^3 + A X Z^2 + B Z^3$. Sometimes it will
	be convenient to include an $x^2$ term. 
	Since~$\E$ is nonsingular, we must have~$\Delta = 4 A^3 + 27 B^2 \not= 0$, as was shown in Example~\ref{ecdiscrim} (note the assumption there that $\chari(K)\neq 2$).
The notation~$\Delta = 4 A^3 + 27 B^2$ is standard.
\par It is conventional to choose~$\o = (0,1,0)$, the point
at infinity, as the identity (we shall always take $\o = (0,1,0)$
unless otherwise stated). Note that the line~$Z = 0$ meets~$\E$
at~$\o$ three times (such a point is called an~{\it inflexion}).
Given a point~$\a = (X,Y,Z)$, if we take the line through~$\a$
and~$\o = (0,1,0)$ then the third point of intersection is
$(X,-Y,Z)$, which must then be~$-\a$. In affine form: 
\[-(x,y) = (x,-y).\]

This gives an easy rule for finding the inverse of a point,
under the group law, namely: the inverse of~$\a$ is its
reflection in the $x$-axis.
\par So, for an elliptic curve~$\E$ written in the form 
$y^2 = \hbox{cubic in }x$, the points are $\o$ (the
point at infinity) and the affine points $(x,y)$, and
the group law has a simpler description:
\par Let $\d = (x_3,y_3)$ the 3rd point of intersection of~$\E$
and~$\ell_{\a,\b}$.
\par Then $\a + \b = (x_3,-y_3)$, the reflection of~$\d$ in
the $x$-axis.
% N.B. Could draw a diagram here.
\end{comm}
We illustrate the group law with the following computation.
\begin{ex}\label{ex:gplaw}
Let $\E : y^2 = x^3 + 1$. Let us compute $\a + \b$, where 
$\a = (x_1,y_1) = (-1,0)$
and $\b = (x_2,y_2) = (0,1)$.
\par 
The line through $\a,\b$ is $\ell_{\a,\b} : y = x + 1$.
Substituting this into~$\E$, we see that the $x$-coordinate
of any point of intersection satisfies: $(x + 1)^2 = x^3 + 1$,
and so:
$$ x^3 - x^2 - 2x = 0. \ \ \ \ \ \ \ \ (*) $$
We are looking for~$(x_3,y_3)$, the 3rd point of intersection
of~$\E$ and $\ell_{\a,\b}$. We first find~$x_3$; note that
$x_1,x_2,x_3$ must be the roots of~$(*)$.
\par  {\bf Method A} (for finding~$x_3$). 
Since the roots of~$(*)$ are $x_1,x_2,x_3$, it follows
that $x^3 - x^2 - 2x = (x - x_1)(x - x_2)(x - x_3)$;
equating coefficients of~$x^2$ gives that:
$$ x_1 + x_2 + x_3 = -(\hbox{coefficient of $x^2$ in $(*)$}) 
= - (-1) = 1,$$
so that~$(-1) + 0 + x_3 = 1$, giving $x_3 = 2$.
\par  {\bf Method B} (for finding~$x_3$).
Factorise~$(*)$ to give: $x(x+1)(x-2)$, whose roots are: $0,-1,2$.
Two of these are the already known $x_1 = -1, x_2 = 0$,
and so~$x_3$ must be the remaining root: $x_3 = 2$.
\par Having found~$x_3$ (by either method), we use the equation
of $\ell_{\a,\b}$ to compute $y_3 = x_3 + 1 = 3$.
In summary: $\E$ and $\ell_{\a,\b}$ intersect at: $(-1,0),(0,1),(2,3)$,
and so $(-1,0) + (0,1) + (2,3) = \o$.
\par Finally, this gives: $(-1,0) + (0,1) = -(2,3) = (2,-3)$,
using the rule that negation is given by reflection in the $x$-axis.
\end{ex}
One can also obtain an explicit general formula for the group law.
\begin{lem}\label{lem:expl}
Let $\E : y^2 = x^3 + A x + B$, where~$A,B\in K$, with
(as usual) $\o = $ the point at infinity. Let~$(x_3,y_3) = (x_1,y_1)
+ (x_2,y_2)$.
\par  {\bf Case 1.} When $x_1\not= x_2$ then:
$$ x_3 = \frac{x_1 x_2^2 + x_1^2 x_2 + A(x_1 + x_2) + 2B - 2 y_1 y_2}
{(x_1 - x_2)^2},\ \ \ y_3 = -\ell x_3 - m, $$
$$ \hbox{where: }\ell = \frac{y_1-y_2}{x_1-x_2},\ \ 
m = \frac{x_1 y_2 - x_2 y_1}{x_1 - x_2}.
$$
 {\bf Case 2.} When $(x_1,y_1) = (x_2,y_2)$ then  
$(x_3,y_3) = (x_1,y_1) + (x_1,y_1)$ 
(which can be written as~$2(x_1,y_1)$), and:
$$ x_3 = \frac{x_1^4 - 2 A x_1^2 - 8 B x_1 + A^2}{4 y_1^2}
= \frac{x_1^4 - 2 A x_1^2 - 8 B x_1 + A^2}{4(x_1^3 + A x_1 + B)},
\ \ \ y_3 = -\ell x_3 - m, $$
$$ \hbox{where: }\ell = \frac{3x_1^2+A}{2y_1},\ \ 
m = \frac{-x_1^3 + A x_1 + 2B}{2y_1}.
$$
\end{lem}
% {\it Optional Proof}\ \ See \ref{lem:expl0}.
 {\it Optional Proof}\ \ See 0.147.


% N.B. The following sentence can just be given verbally in lectures:
The above formulas give an alternative
method for computing the group law, although in practice it
often turns out to be easier to compute the group law
from first principles, as in Example~\ref{ex:gplaw}.
\begin{comm}\label{ell:degen}
When $\Delta = 4A^3 + 27B^2 \not= 0$, all~$3$ roots of
$x^3 + Ax + B$ are distinct, guaranteeing that $y^2 = x^3 + A x + B$
has no singularities and is an elliptic curve (if $\chari(K) \neq 2$).
\par When~$\Delta = 0$, then this is no longer an elliptic
curve and at least two roots of the cubic are
repeated: $y^2 = (x - \alpha)^2(x-\beta)$. It is still
the case that the set of nonsingular points on~$\E$, denoted~$\E_{ns}$,
forms a group (see pp.~39--41 of \cite{cas:ell}). When
$\beta \not= \alpha$ the singularity at~$(\alpha,0)$ is
a node. When $\beta = \alpha$ the singularity is a cusp.
In either case, the curve can be written: 
$\bigl( \frac{y}{x-\alpha} \bigr)^2 = x - \beta$, and so
is birationally equivalent to the conic $w^2 = x - \beta$.
% N.B. I might consider sketching these in the lecture (both node and cusp).
\end{comm}
\begin{defn}\label{defn:tors}
Let~$\E$ be an elliptic curve and let~$P$ be a point on~$\E$.
For any positive integer~$m$, let~$mP$ denote~$P + \ldots + P$ ($m$~times).
We say that~$P$ is an {\it $m$-torsion} point if $m P = \o$.
The $m$-torsion group of~$\E$, denoted~$\E[m]$, is the set of 
all $m$-torsion points (defined over a fixed algebraic closure $\overline{K}$ of the field of definition $K$). 

We also say that~$P$ has {\it order~$m$}
(or that~$P$ is a {\it point of order~$m$}) if~$m$ is the
smallest positive integer for which~$mP = \o$.
When such~$m$ exists, $P$ is a {\it torsion point}
($P$ {\it has finite order}).
If no such~$m$ exists, then~$P$ is a non-torsion point
($P$ has {\it infinite order}).
The group of all $K$-rational torsion points on~$\E$
is denoted $\ETK$ (or sometimes $\EKT$).
\end{defn}
\begin{exs}\label{exs:tors}\
\par {\bf (a)} Let $\E : y^2 = x^3 - x$,
and let~$P = (1,0)$ so that $-P = (1,-0) = (1,0) = P$,
so that $2 P = P + P = P - P = \o$. But $1\cdot P = P \not= \o$,
and so~$2$ is the smallest~$m>0$ such that~$m P = \o$.
$P$ has order~$2$ and $P \in \ETQ$. 
% N.B. Just give a very brief summary of the computation for the following.
\par {\bf (b)} Let $\E : y^2 = x^3 + 1$,
and let~$P = (0,1)$. First compute~$P+P$.
Using $2 y y' = 3 x^2$ at~$(0,1)$ gives $2\cdot 1\cdot y' = 3\cdot 0^2$
and so the tangent line~$\ell_{P,P}$ to~$\E$ at~$P$
has slope~$0$ and equation of form~$y = 0\cdot x + m$.
But the line goes through~$(0,1)$ and so $m=1$ and the
tangent line is $y = 1$. Substituting $y=1$ into $y^2 = x^3 + 1$
gives $x^3 = 0$, with roots~$0,0,0$. So,~$\E$ meets~$\ell_{P,P}$
at~$(0,1)$ with multiplicity~$3$, and $(0,1) + (0,1) + (0,1) = \o$.
Hence: $(0,1) + (0,1) = -(0,1) = (0,-1)$. In summary:
\par $ 1\cdot (0,1) = (0,1),\ \ 2\cdot (0,1) = (0,-1),\ \
3\cdot (0,1) = \o.$

So $(0,1)$ has order~$3$ and $(0,1)\in \ETQ$.
\end{exs}
When~$K = \bbbf_p$, a finite field with~$p$ elements,
there are of course only finitely many members of~$\E(\bbbf_p)$.
\par
% N.B. The following aside can just be given verbally in the lecture:
{\it Aside: Each of the $p$ possible~$x$-coordinates $0,\ldots ,p-1$
has about
a 50\% chance of making $x^3 + A x + B$ a square modulo~$p$.
When $x^3 + A x + B$ is not a square, there are no corresponding
$y$-coordinates. When $x^3 + A x + B$ is a square,
there are at most two corresponding $y$-coordinates.
So, one might expect `on average' about~$p$ affine points, that is,
about~$p+1$ points, including the point at infinity.}
\par
The following result gives a bound within which
the number of points must lie.
\begin{thm}\label{thm:hasse} (Hasse). 
Let~$\E$ be an elliptic curve over~$\bbbf_p$.
Let~$N_p = \# \E(\bbbf_p)$ where, as usual, $\E(\bbbf_p)$ should be
taken to including~$\o$
(so that~$N_p$ is the number of affine points~$(x,y)$ 
on~$\E$ with~$x,y\in \bbbf_p$,
plus~$1$, to include the point at infinity~$\o$). Then:
$$ | N_p - (p + 1) | \leqslant 2\sqrt{p},
\hbox{ that is, } N_p \in [(p+1) - 2\sqrt{p}, (p+1) + 2\sqrt{p}].
$$
Similarly, any curve $y^2 = Q(x)$, where $Q(x) = f_4 x^4 + \ldots + f_0$
has nonzero discriminant, has at least $p - 1 - 2\sqrt{p}$
affine points.
\end{thm}
\begin{proof} See p.~118 of \cite{cas:ell} or p.~131 of \cite{sil:AEC1}.
\end{proof}
\begin{ex}\label{ex:hasse}
Let~$\E : y^2 = x^3 + 4x + 1$, defined over~$\bbbf_{13}$. Then:
$$ \# \E(\bbbf_{13} ) \geqslant 13 + 1 - 2\sqrt{13} > 13 + 1 - 2\cdot 4 = 6,
\hbox{ so that } \# \E(\bbbf_{13} ) \geqslant 7. $$
$$ \# \E(\bbbf_{13} ) \leqslant 13 + 1 + 2\sqrt{13} < 13 + 1 + 2\cdot 4 = 22,
\hbox{ so that } \# \E(\bbbf_{13} ) \leqslant 21.$$
Note that at most~$4$ of the points on~$\E(\bbbf_{13} )$ can
be~$\o$ and points of the form~$(x,0)$, so there must exist
at least~$3$ affine points $(x,y)\in \E(\bbbf_{13} )$ with~$y\not=0$. 
%\par Similarly,
%let~$\D : y^2 = g(x) = 2x^4 - 7$, defined over~$\bbbf_{13}$.
%Then $\D(\bbbf_{13} )$ has greater than $13 - 1 - 2\sqrt{13} > 
%13 - 1 - 2\cdot 4 = 4$, at most~4 of which are of the
%form~$(x,0)$, so there must exist at least~$1$ affine 
%point $(x,y)\in \E(\bbbf_{13} )$ with~$y\not=0$.
\end{ex}
%\begin{ex}\label{ex:hassequartic}
%Let~$\D : y^2 = g(x) = 2x^4 - 7$, defined over~$\bbbf_{13}$.
%Imagine that~$\D(\bbbf_{13}) = \emptyset$. Then, for all
%$x = 0,\ldots ,12$, $g(x)$ must be a quadratic non-residue mod~$13$,
%and so~$\alpha g(x)$ must be a nonzero quadratic residue mod~$13$,
%where~$\alpha$ is a fixed quadratic non-residue modulo~$13$. 
%This gives rise to at least~$2\times 13$\ $\bbbf_{13}$-rational
%points on the curve\ $\D_\alpha : y^2 = \alpha g(x)$, contradicting
%the fact that $\D_\alpha$ must be an elliptic curve [by
%Comment~\ref{comm:quartic}] and so must satisfy the same bounds
%as in the previous example. 
%\par From this contradiction, we deduce that~$\D$ has
%an $\bbbf_{13}$-rational point and so must be an elliptic curve
%[again, using Comment~\ref{comm:quartic}]. Therefore
%$\# \D(\bbbf_{13} )$ lies in the same interval as the previous example.
%\end{ex}
\medskip
\hrule

\newpage
\section{The $p$-adic Numbers $\bbbq_p$}\label{sec:padics}
%% Introductory properties, basic analysis [2 lectures].
For~$\bbbq$, let~$\binf$ denote the
standard absolute value (e.g.\ $| -5 |_\infty = | 5 |_\infty = 5$).
Consider the sequence:
$x_1 = 1.4, x_2 = 1.41, x_3 = 1.414,\ldots $, where
$x_n$ is the largest decimal to~$n$ decimal places satisfying
$x_n^2 < 2$. Then $| x_m - x_n |_\infty \rightarrow 0$
as $m,n\rightarrow \infty$, so that the sequence is
Cauchy in~$\bbbq, \binf$. The sequence $x_n$ cannot be convergent,
since if $x_n \rightarrow \alpha$ then clearly $\alpha^2 = 2$
and no such~$\alpha$ exists in~$\bbbq$.
% N.B. I might add here the verbal comment: So, if you were living
% in rational-only world, and you saw this sequence, you'd
% feel that something was missing in your life.
We say that~$(\bbbq, \binf)$ is~{\it incomplete} (since
not every Cauchy sequence is convergent) and the real numbers~$\bbbr$
give the {\it completion} of~$(\bbbq, \binf)$.
The absolute value $\binf$ is a special case of the following.
\begin{defn}\label{defn:valuation}
Let~$K$ be a field. A {\it valuation} on~$K$
is a function $\bb : K \rightarrow \bbbr$ satisfying:
\par $(1)\ |x| \geqslant 0$ for all~$x\in K$, with
equality if and only if~$x=0$.
\par $(2)\ |xy| = |x|\cdot |y|$ for all~$x,y\in K$.
\par $(3)\ |x + y| \leqslant |x| + |y|$
for all~$x,y\in K$ (the {\it triangle inequality}).
\par  If a valuation also satisfies the stronger property:
\par $(3)'\ |x + y| \leqslant \max (|x|,|y|)$, for all~$x,y\in K$,
\par  then we say that it is
a {\it non-Archimedean valuation}; otherwise it is
an {\it Archimedean valuation}.
\end{defn}
For example, $\bbbq, \binf$ (or $\bbbr, \binf$)
is a valuation. It is Archimedean since, for example,
$| 1 + 1 |_\infty \not\leqslant \max(| 1 |_\infty, | 1 |_\infty)$.
We shall now introduce another valuation on~$\bbbq$,
which gives a different notion of size and distance.
\begin{defn}\label{defn:padicval}
Fix a prime~$p$. Let~$x = \frac{m}{n}\in \bbbq$.
Write $\frac{m}{n} = p^r\frac{a}{b}$, where~$p\nmid a, p\nmid b$.
Then the {\it $p$-adic valuation} (or {\it $p$-adic absolute value}
or {\it $p$-adic size}) is defined to be:
\[| x |_p = | \frac{m}{n} |_p = p^{-r}\]

so~$x$ is `smaller' the higher the power of~$p$ dividing~$x$.

\par  We also define $| 0 |_p = 0$. For any~$x,y\in\bbbq$,
the {\it $p$-adic distance} between~$x$ and~$y$ is defined
to be: $d_p(x,y) = | x - y |_p$. (Note that $d_p$ is a metric)
\end{defn}
\begin{ex}\label{ex:padicval} 
In~$\bbbq, \bb_3$, we have: $|\frac{4}{3}|_3 = |3^{-1}\frac{4}{1}|_3
= (3^{-(-1)}) = 3,  | 9 |_3  
= | 3^2\frac{1}{1} |_3 = 3^{-2} = \frac{1}{9}$,
and $| 7 |_3 = | 3^0 \frac{7}{1} |_3 = 3^{-0} = 1$.
  
Also, $d_3(-5,3) = | -5-3|_3 = |-8|_3 = 1, d_3(-5,19) =|-5-19|_3 = |-24|_3 = 3^{-1}$,
and $d_3(\frac{1}{2}, \frac{1}{5}) = |\frac{3}{10}|_3 = 3^{-1}$.
 For integers $m,n$, $m\not\equiv n\ (\mod 3) \iff
d_3(m,n) = 1$,\ $m\equiv n\ (\mod 3) \iff d_3(m,n) \leqslant \frac{1}{3}$,
\ $m\equiv n\ (\mod 3^2) \iff d_3(m,n) \leqslant \frac{1}{3^2}$, and so on.
The integers~$m,n$ are $3$-adically closer when they are
congruent modulo a higher power of~$3$.
\end{ex}
\begin{lem}\label{lem:padicval}
The function~$\bp$ of Definition~\ref{defn:padicval} is
a non-Archimedean valuation on~$\bbbq$.
\end{lem}
\begin{proof} $(1),(2),(3)'$ are trivially true when~$x$ or~$y = 0$.
Let~$x,y\in \bbbq$, $x,y\not=0$,
and write $x = p^r\frac{a}{b},
y = p^s\frac{c}{d}$, where~$p \nmid a,b,c,d$.
\par\medskip {\bf (1)} $| x |_p = p^{-r} > 0$.
\par\medskip {\bf (2)} 
$| xy |_p = | p^r\frac{a}{b}\ p^s\frac{c}{d} |_p
= | p^{r+s}\ \frac{ac}{bd} |_p = p^{-(r+s)} 
\hbox{\ (since $p\nmid ac,bd$)\ } = p^{-r}p^{-s} = |x|_p |y|_p$.
\par\medskip  $\hbox{\bf (3)}'$ 
Wlog $r \leqslant s$, giving: $| x + y |_p 
= | p^r\frac{a}{b} + p^s\frac{c}{d} |_p
= | p^r\bigl( \frac{a}{b} + p^{s-r}\frac{c}{d}\bigr) |_p
= | p^r \frac{ad + p^{s-r}bc}{bd} |_p$
\par $= | p^r \frac{p^k \ell}{bd} |_p$ for some $k \geqslant 0$ and
$\ell \in \bbbz$ with $p\nmid \ell$ (since $ad + p^{s-r}bc \in \bbbz$)
\par $= p^{-(r+k)} \leqslant p^{-r} = |x|_p = \max( |x|_p,|y|_p)$.
% N.B. Might mention verbally that the above "= p^{-(r+k)}" step
% is due to p not dividing \ell and p not dividing bd.
% Note that this relies on p being prime.
\end{proof}
\begin{comm}\label{comm:maxcomm}
By induction, $|a_1 + \ldots + a_n |_p \leqslant 
\max( |a_1|_p, \ldots , |a_n|_p )$.
It is also a good exercise to show that $|x|_p \not= |y|_p \implies
|x + y|_p = \max( |x|_p, |y|_p )$. We will use this fact repeatedly.
% N.B. Might mention verbally that it is amazing how often
% this last implication is useful in p-adic arguments.
Furthermore,
if $|a_k|_p > |a_i|_p$ for all~$i$, $1 \leqslant i \leqslant n, i\not= k$,
then $|a_1 + \ldots + a_n |_p = \max( |a_1|_p, \ldots , |a_n|_p )
= |a_k|_p$.
\end{comm}
\begin{defn}\label{defn:converge}
Let~$K, \bb$ be a field with valuation. For $a_n, \ell \in K$,
we say that the sequence
$a_n$ {\it converges} to~$\ell$ (denoted $a_n \rightarrow \ell$) in~$(K,\bb)$
when $| a_n - \ell | \rightarrow 0$ in~$(\bbbr, \binf)$
as $n \rightarrow \infty$. 

That is: for any~$\epsilon > 0$ there exists $N\in \bbbn$ such
that, $| a_n - \ell | < \epsilon$ for all~$n > N$.

Given a sequence $a_n \in K$, if there exists $\ell\in K$ such that
$a_n \rightarrow \ell$ in~$K,\bb$ then we say that~$a_n$
{\it converges} in~$K,\bb$, or that it is {\it convergent} in~$K,\bb$.
It is {\it Cauchy} if $| a_m - a_n | \rightarrow 0$ in~$\bbbr,\binf$
as~$m,n\rightarrow \infty$.
That is: for any~$\epsilon > 0$ there exists $N\in \bbbn$ such
that, $| a_m - a_n | < \epsilon$ for all~$m,n > N$. We say that~$K, \bb$ is {\it complete} if every Cauchy
sequence is convergent.

All of these definitions coincide with the usual definitions for metric spaces, when we equip $K$ with the metric $d(x,y) = |x-y|$.
\end{defn}
\begin{exs}\label{exs:convpadic}\
\par {\bf (a)} Let~$a_n = 6^n$. Then~$|a_n - 0|_3
= |6^n|_3 = 3^{-n} \rightarrow 0$ as~$n\rightarrow \infty$.
So $a_n\rightarrow 0$ in~$\bbbq, \bb_3$.
\par {\bf (b)} Let $a_1 = 1,\ a_2 = 11,\ a_3 = 111,\ldots$
so that $9 a_n = 999\ldots 9$ ($n$~times) and
$9 a_n + 1 = 10^n$. Then $|9 a_n - (-1)|_5 = | 10^n |_5 = 5^{-n}
\rightarrow 0$, giving $9 a_n \rightarrow -1$ in~$\bbbq, \bb_5$.
It follows that $a_n \rightarrow -\frac{1}{9}$ in~$\bbbq, \bb_5$.  
\par {\bf (c)} Let $x_0 = a_0 = 3$. 
Then $a_0^2 = 9 \equiv 2 (\mod 7)$, 
and $|x_0^2 - 2|_7 = |a_0^2 - 2|_7 = |7|_7 = 7^{-1} < 1$. 
We want to find $a_1\in \{0,\ldots ,6\}$ such that 
$(a_0 + a_1 7)^2 \equiv 2 \ (\mod 7^2)$.
\par This is satisfied
$\iff a_0^2 + 2 a_0 a_1 7 + a_1^2 7^2 \equiv 2 \ (\mod 7^2)$
\par $\iff 6 a_1 7 \equiv 2 - 9 = -7 \ (\mod 7^2)
\iff 6 a_1 \equiv -1 \ (\mod 7) \iff a_1 \equiv 1\ (\mod 7),$
\par  so we can take 
$a_1 = 1$. 

Let~$x_1 = a_0 + a_1 7 = 3 + 1 \times 7 = 10$. 
Then $x_1^2 = 100 \equiv 2\ (\mod 7^2)$ and $|x_1^2 - 2|_7 = 7^{-2}$.
\par  {\it Aside: note how the solvability
of the last congruence is affected by $| 2 a_0 |_7 = | f'(a_0) |_7$,
where $f(x) = x^2 - 2$. We will see this more generally in the statement of Hensel's lemma.}
% N.B. I might abbreviate the following paragraph,
% and similary abbreviate the computations in (d).
\par When we similarly solve for $a_2\in \{ 0,\ldots ,6\}$
such that $(a_0 + a_1 7 + a_2 7^2)^2 \equiv 2\ (\mod 7^3)$
we find that~$a_2 = 2$, giving $x_2 = a_0 + a_1 7 + a_2 7^2 = 3+7+98 = 108$.
Check: $x_2^2 \equiv 2\ (\mod 7^3)$ and $|x_2^2 - 2|_7 \leqslant 7^{-3}$.
% N.B. I might verbally add (for both (c) and (d)): You might
% like to satisfy yourselves that this process can be performed inductively.
\par We can inductively find 
$x_n = a_0 + a_1 7 + \ldots + a_n 7^n$ such that 
$x_n^2 \equiv 2\ (\mod 7^{n+1})$, that is, 
$| x_n^2 - 2 |_7 \leqslant 7^{-(n+1)}$. Hence $x_n^2 \rightarrow 2$
in~$\bbbq, \bb_7$.
\par Intuitively, $(3 + 1\cdot 7 + 2\cdot 7^2 + \ldots )^2 = 2$
in~$\bb_7$. The sequence~$x_n$ is easily seen to be Cauchy 
in~$\bbbq, \bb_7$. The sequence is not convergent
since if $x_n \rightarrow \alpha$ in~$\bbbq,\bb_7$ then
$\alpha^2 = 2$, which is impossible for $\alpha\in\bbbq$.
\par {\bf (d)} Again, let $a_0 = 3$, but now
define $a_{n+1} = a_n - \frac{f(a_n)}{f'(a_n)}$, for $n\geqslant 0$,
where $f(x) = x^2 - 2$ (the Newton--Raphson formula).
Then:
\par $a_0 = 3,\ a_1 = 3 - \frac{3^2 - 2}{2\cdot 3} = \frac{11}{6},\
a_2 = \frac{11}{6} - \frac{ (\frac{11}{6})^2 - 2 }{ 2 \frac{11}{6} }
= \frac{193}{132}$, and so on.
\par  Check that: $| a_0^2 - 2 |_7 = 
| 3^2 - 2 |_7 \leqslant 7^{-1}$,\ $| a_1^2 - 2 |_7 = 
| (\frac{11}{6})^2 - 2 |_7 = |\frac{49}{36}|_7 \leqslant 7^{-2}$,  
and that~$a_n$ satisfies the same properties as~$x_n$ of Example~(c),
namely: $| a_n^2 - 2 |_7 \leqslant 7^{-(n+1)}$ so that $a_n^2 \rightarrow 2$
in~$\bbbq, \bb_7$, again forcing~$a_n$ to be Cauchy 
but not convergent.
% N.B. For (d) above, I might verbally
% add: that a_0 is an initial approximation, that we shall soon
% prove a lemma which has this example as a special case,
% and I might make a quick sketch of y=x^2 and one application
% of Newton-Raphson: put a cross at the point a_0=2 on the x-axis,
% tangent at (2,4), which cuts the x-axis at a_1.
\end{exs}
The last two examples show that~$\bbbq$ is incomplete with respect
to the valuation~$\bb_7$, and indeed $\bbbq$ is incomplete
with respect to any~$\bp$. We now define an extension of~$\bbbq$
which performs the same role with respect to~$\bp$ that~$\bbbr$
performs with respect to~$\binf$.
% N.B. I might verbally add: See the Preliminary Reading on the webpage
% (in fact, Definition\ref{defn:completion0}[0.87]) for the 
% formal definition of completion.
\begin{defn}\label{defn:padics}
The set of {\it $p$-adic numbers} $\qp$ is the completion
of~$\bbbq$ with respect to the valuation~$\bp$,
and is the smallest field containing~$\bbbq$ which is
complete with respect to~$\bp$.


For any $\alpha, \beta \in \bbbq_p$, we say that
$\alpha \equiv \beta\ (\mod p^n) 
\iff | \alpha - \beta |_p \leqslant p^{-n}$
(`$\alpha$ is congruent to~$\beta$ modulo~$p^n$').
A member of~$\qp$ 
(a {\it $p$-adic number})~$x$ can be written uniquely in the following form
(the {\it $p$-adic expansion} of~$x$):
$$ x = \sum_{n=N}^\infty a_n p^n,\hbox{ where } N\in \bbbz,
a_N \not= 0 \hbox{ and each } a_n\in \{0,\ldots ,p-1\},
$$
in which case $| x |_p = p^{-N}$, and the~$a_n$ are
the {\it digits} of~$x$. We might use the shorthand notation
$a_N\ldots a_0 , a_1 a_2 \ldots$ to represent the above sum.
Note that, as for decimal expansions in $(\R,|~|_\infty)$, $x\in\bbbq$ exactly when the $p$-adic digits are
eventually periodic.
% N.B. I might verbally add that the topology of Q_p is dramatically
% different from R: lots of sets which are both closed and open,
% for example, any {x in Q_p : |x|_p < 1} = {x in Q_p : |x|_p <= p^{-1}}.
% I might also mention the Chinese Remainder Theorem, that the set:
% of eqns: x \equiv a1 (mod p1^n1), .... , x \equiv ak (mod pk^nk}
% has a unique solution mod n = p1^n1...pk^nk, and so having solutions in
% Q_p for all primes p is equivalent to having solutions for all congruences.
\end{defn}
\begin{exs}\label{exs:padicexp}\
% N.B. An alternative easier version of (d) is: w = 1 + 5 + 5^2 + ...
% = 1,\overline{1}, so that \frac{1}{5}(w-1)=w, giving: w-1=5w, 
% so that: w = -\frac{1}{4}.
\par  {\bf (a)} $w = 4 \cdot 5^{-2} + 1 \cdot 5^{-1}
+ 4 \cdot 5^0 + 1\cdot 5^1 + 4\cdot 5^2 + \ldots \in \bbbq_5$
and $| w |_5 = 5^2$.
This can be denoted $414,\overline{14}$.   
\par  {\bf (b)} $\alpha = 3\cdot 7^0 +  1\cdot 7^1 + 2\cdot 7^2
+ \ldots  \in \bbbq_7$ from Example~\ref{exs:convpadic}(c)
satisfies~$\alpha^2 = 2$. 
\par On the other hand, there is
no~$\beta\in\bbbq_7$ such that~$\beta^2 = 3$ since any such~$\beta$
would satisfy $| \beta |_7^2 = |\beta^2|_7 = |3|_7 = 1$
and so would have $7$-adic expansion $\beta = b_0 + b_1 7 + b_2 7^2 + \ldots$ 
and would satisfy $(b_0 + b_1 7 + b_2 7^2 + \ldots)^2 = 3$.
This would give: $b_0^2 \equiv 3\ (\mod 7)$, which is impossible,
since~$3$ is not a quadratic residue mod~$7$ (none of
$0^2,1^2,2^2,3^2,4^2,5^2,6^2$ are $\equiv 3\ (\mod 7)$).
\par  {\bf (c)} In~$\bbbq_5$: $27 = 2 + 5^2 =
2\cdot 5^0 + 0\cdot 5^1 + 1\cdot 5^2 = 2,01$
(the $5$-adic expansion of~$27$).
\par  {\bf (d)} Let us find the $5$-adic expansion of~$-1/4$.
We have $|-1/4|_5 = 1$ so that the $5$-adic expansion of~$-1/4$ must
be of the form
$\alpha = a_0 + a_1 5 + a_2 5^2 + \ldots$, each $a_i\in\{0,1,2,3,4\}$
and $a_0\not= 0$.  This satisfies $-1 = 4(a_0 + a_1 5 + a_2 5^2 + \ldots)$
which gives $-1 \equiv 4 a_0\ (\mod 5)$ and so $a_0 = 1$.
Then $-1 = 4(1 + a_1 5 + a_2 5^2 + \ldots)$
gives $-5 \equiv 4 a_1 5\ (\mod 5^2)$, giving $-1 \equiv 4 a_1\ (\mod 5)$,
and so~$a_1 = 1$. Similarly, we find that $a_2 = 1, a_3 = 1, \ldots$
and we suspect that $-1/4 = 1,\overline{1}$.
\par Let $\alpha = 1,\overline{1}$. Then $\alpha - 1 = 0,\overline{1}
= 5\alpha$, so that $4\alpha = -1$, giving $\alpha = -1/4$,
proving that we have the correct $5$-adic expansion.
%\par  {\bf (d)} Let us find the $5$-adic expansion of~$3/2$.
%We have $|3/2|_5 = 1$ so that the $5$-adic expansion of~$3/2$ must
%be of the form
%$\alpha = a_0 + a_1 5 + a_2 5^2 + \ldots$, each $a_i\in\{0,1,2,3,4\}$
%and $a_0\not= 0$.  This satisfies $3 = 2(a_0 + a_1 5 + a_2 5^2 + \ldots)$
%which gives $3 \equiv 2 a_0\ (\mod 5)$ and so $a_0 = 4$.
%Then $3 = 2(4 + a_1 5 + a_2 5^2 + \ldots)$
%gives $-5 \equiv 2 a_1 5\ (\mod 5^2)$, giving $-1 \equiv 2 a_1\ (\mod 5)$,
%and so~$a_1 = 2$. Similarly, we find that $a_2 = 2, a_3 = 2, \ldots$
%and we suspect that $3/2 = 4,\overline{2}$.
%\par Let $\alpha = 4,\overline{2}$ and let $\beta = \alpha - 4 = 
%0,\overline{2} = 2\cdot 5 + 2\cdot 5^2 + \ldots$, giving:
%$(\beta - 2\cdot 5)/5 = \beta$, which has solution $\beta = -\frac{5}{2}$. 
%Hence $\alpha = \beta + 4 = \frac{3}{2}$, proving that we have
%the correct $5$-adic expansion.
\end{exs}
\begin{comm}\label{comm:localglobal}
The field~$\bbbq$ is often referred to as a {\it global field}
and its completions with respect to valuations, namely~$\bbbr$
and $\bbbq_p$, for any prime~$p$, are its {\it local fields}
(or {\it localisations}).
An equation defined over~$\bbbq$ which has points in~$\bbbr$
and every~$\bbbq_p$,
but not in~$\bbbq$, is said to
{\it violate the Hasse Principle.} 
\end{comm}
\begin{defn}\label{defn:residuefield}
Let~$K$ be a field with a non-Archimedean valuation~$\bb$.
We say that~$x\in K$ is an {\it integer}
(with respect to the valuation) when $| x | \leqslant 1$,
and $R = \{ x \in K : | x | \leqslant 1\}$
is the {\it ring of integers} (or {\it valuation ring}) of~$K$. 
The set~$\M = \{ x \in K : | x | < 1\}$ is the {\it maximal
ideal}, and $k = R/\M$ is the {\it residue field}.
The {\it valuation group} is the set $G_K = \{ |x| : x \in K^*\}$ 
under multiplication. 

We say that the valuation is {\it discrete}
if there exists~$\delta > 0$ such that
$1 - \delta < |x| < 1 + \delta \implies |x| = 1$.
When the valuation is discrete, there exists an element
$\varpi \in \M$ such that $\M = (\varpi)$ is principal with generator $\varpi$. We say that such an element is
a \textit{uniformizer} or {\it prime element} for the valuation.
\end{defn}
The ring of integers for~$\bbbq_p$ is often denoted
$\bbbz_p = \{ x\in \bbbq_p : | x |_p \leqslant 1\}$.
The valuation group $G_{\bbbq_p} = \{ p^r : r \in \bbbz \}
= \{ \ldots , p^{-2}, p^{-1}, p^0, p^1, p^2, \ldots \}$,
so that $\bbbq_p$ is discrete, and we can take~$p$ as
a prime element (or indeed any element with valuation $p^{-1}$).
The maximal ideal is
$\M = p \bbbz_p = \{ x\in \bbbq_p : |x|_p \leqslant p^{-1}\}$
and the residue field~$\bbbz_p/p\bbbz_p$
is isomorphic to~$\bbbf_p$, the finite field with~$p$ elements.
\par The following result show how, in some respects,
analysis is simpler for non-Archimedean valuations. 
\begin{thm}\label{thm:series}
Let~$K$ be a field, complete with respect
to a non-Archimedean valuation~$\bb$, and
let~$x_n$ be a sequence in~$K$.
Then:
$x_n \rightarrow 0\hbox{ in }K
\iff \sum x_n\hbox{ is convergent in }K$.
\end{thm}
% N.B. I might verbally add here: so, all those mistakes first
% students make in real analysis by wrongly using x_n \rightarrow 0
% implies \sum x_n convergent, would all be fine now (so maybe
% it would be better to start in the first year with Q_p rather than R).
\begin{proof} Let $S_N = \sum_{n=1}^N x_n$.


{$\bf \Rightarrow$ :}\ Assume that~$x_n \rightarrow 0$ in~$K$.
Then:
\par\ \ \ $| S_N - S_M | = | x_{M+1} + \ldots + x_N |
\leqslant \max\bigl( |x_{M+1}|, \ldots , |x_N| \bigr)
\rightarrow 0$ as $M,N\rightarrow \infty$.
\par\ \ \
$S_N$ is Cauchy and so convergent
(since~$K$ is complete), giving that
$\sum x_n$ is convergent.

{$\bf \Leftarrow$ :}\ Assume that $\sum x_n$ is convergent, that is,
$S_N \rightarrow \ell$ for some $\ell \in K$. Then: 
\[| x_n - 0 | = | x_n | = | S_n - S_{n-1} |
= | S_n - \ell + \ell - S_{n-1} |
\leqslant | S_n - \ell | + | S_{n-1} - \ell | \rightarrow 0\]
as $n \rightarrow \infty$, so that $x_n \rightarrow 0$ in~$K, \bb$.
\end{proof}


% N.B. I might verbally mention: note that the forward direction
% uses the non-Archimedean property, the reverse direction
% is true for any valuation (whether Archimedean or non-Archimedean).
For example, $\sum n!$ converges in any~$\bbbq_p$,
since $| n! |_p \rightarrow 0$ (it is unknown whether the limit of this sequence in any $\bbbq_p$ is in $\bbbq$).
% N.B. I might verbally mention that it seems rather remarkable
% that it is still unknown whether in any \bbbq_p, \sum n! \in \bbbq,
% given that, for example, it is quite easy to show in R that \sum 1/n!
% is not in \bbbq.
\par The above result applies to~$\bbbq_p$ (since it is non-Archimedean),
but not to~$\bbbr$ (where, for example, $x_n = \frac{1}{n}$
is a standard counterexample).
\begin{comm}\label{comm:maxseries}
It is not too hard to check that the rules for finite sums
in Comment~\ref{comm:maxcomm} also apply to
infinite series. In other words, when $\sum a_n$ converges,
$| \sum a_n | \leqslant \max | a_n |$.
Furthermore, if there exists~$a_k$ such that
$|a_k| > |a_i|$ for all~$i \not= k$,
then $|\sum a_n | = |a_k|$; in particular, it is then
impossible for $\sum a_n = 0$.
\end{comm}
\par {\it Aside: Recall Example~\ref{exs:convpadic}(d), where
$x_0 = 3$, and
$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$,
where $f(x) = x^2 - 2$, defined a sequence, which is
Cauchy (but not convergent) in~$\bbbq, \bb_7$, and which
is convergent in~$\bbbq_7$ to a root of~$f(x)$.
The following describes when an initial approximation~$a_0$
gives a solution to~$f(x)$.}
\begin{thm}\label{thm:hensel} (Hensel's Lemma).
Let~$K$ be a field, complete with respect to a non-Archimedean
valuation~$\bb$, with valuation ring~$R = \{ x\in K : |x| \leqslant 1\}$.

Let $f(x) \in R[x]$ and let $a_0\in R$ satisfy:
\[| f(a_0) | < | f'(a_0) |^2 \ \ \ \ \ \ \ (*)\]
\par  Then there exists a unique $a\in R$ such that
$f(a) = 0$ and $| a - a_0 | < |f'(a_0)|$. This solution moreover satisfies $|a - a_0|\leqslant | f(a_0) |/ | f'(a_0) |$. 
\end{thm}
% N.B. I might verbally add: note that this is in contrast
% with Newton-Raphson in R, where we need to know something
% about f(x) for all x in an interval about the initial approximation.
\begin{proof} Define polynomials $f_j(x)$ by
\[f(x + y) = f_0(x) + f_1(x) y + f_2(x) y^2 + \ldots.\]
so that $f_0(x) = f(x)$ and $f_1(x) = f'(x)$. If $f(x) = x^n$, then $f_j(x) = \left(\begin{smallmatrix}
	n \\ j
\end{smallmatrix}\right)x^{n-j}$. It follows from this that $f_j(x) \in R[x]$ for arbitrary $f(x)$. 

Define
$b_0 = -f(a_0)/f'(a_0)$. By $(*)$, $|b_0| < 1$. Define $a_1 = a_0 + b_0 = a_0 - f(a_0)/f'(a_0)$.  We are going to show that $a_1$ is a better approximation to a root of $f(x)$ than $a_0$. We compute: 
\[| f'(a_1) - f'(a_0) | = | f'(a_0+b_0) - f'(a_0) |
= | f'_1(a_0) b_0 + f'_2(a_0) b_0^2 + \ldots |\]
\[\leqslant | b_0 | < | f'(a_0) | \text{ (by } (*)\text{)},\]
so that $| f'(a_1) | = | f'(a_0) |$. Also, 
\[| f(a_1) | = | f(a_0 + b_0) | =
| f_0(a_0) + f_1(a_0)b_0 + f_2(a_0)b_0^2 + \ldots | = | f_2(a_0)b_0^2 + \ldots |\]
since $f_0(a_0) + f_1(a_0)b_0 = 0$.

We deduce that \[|f(a_1)| \le \hbox{max}_{j\geqslant 2} |f_j(a_0)| |b_0|^j
\leqslant | b_0 |^2 = \frac{ |f(a_0 )|^2}{|f'(a_0 )|^2}
= \rho | f(a_0) | < | f(a_0) |,\]
where $\rho = \frac{ |f(a_0 )|}{|f'(a_0 )|^2} < 1$.
\par Summarising: $ |f'(a_1) | = |f'(a_0)|$ and
$| f(a_1) | \leqslant \rho | f(a_0) | < | f(a_0) |$, where
\[\rho = \frac{ |f(a_0 )|}{|f'(a_0 )|^2} < 1.\]

We proceed by iterating this procedure. So, assume we are given $a_0,\ldots,a_n \in R$ such that \[|f'(a_n)| = \ldots = |f'(a_1)| = |f'(a_0)|\]
and \[ | f(a_n) | \leqslant \rho |f(a_{n-1})| \leqslant \ldots 
\leqslant \rho^n |f(a_0)|.\]

Define
$b_n = -f(a_n)/f'(a_n)$ and $a_{n+1} = a_n + b_n = a_n -f(a_n)/f'(a_n)$.
%\par As above: $|f'(a_{n+1})| = \ldots |f'(a_1)| = |f'(a_0)|$.
%\ \ \ \ \ \ (1)

Then, as in the case $n=0$, we have $|f'(a_{n+1})| = |f'(a_n)|$ and \[| f(a_{n+1}) | \leqslant |b_n|^2 = \frac{ | f(a_n) |^2 }{ | f'(a_n) |^2 }
= \frac{ | f(a_n) |^2 }{ | f'(a_0) |^2 }\le \frac{ | f(a_0) | }{ | f'(a_0) |^2 } |f(a_n)| = \rho | f(a_n) | \leqslant \rho^{n+1} | f(a_0) |.\]

In conclusion, we have defined an infinite sequence $(a_n)_{n \ge 0}$ with 
$|f'(a_n)|=|f'(a_0)|$ and
$ | f(a_{n}) | \le \rho^n | f(a_0) |$ which $\rightarrow 0$
as $n\rightarrow \infty$.

We also have $| b_n | = | f(a_n) |/|f'(a_n)|
= | f(a_n) |/|f'(a_0)| \rightarrow 0$, so
by Theorem~\ref{thm:series}
\[a_n = a_0 + b_0 + b_1 + \ldots + b_n\]
converges to a limit ~$a \in R$. 

By continuity of polynomials,
$f(a) = \lim f(a_n) = 0$. Furthermore: 
\[| a - a_0 | = | \sum b_n | \leqslant 
\max | b_n | = \max \frac{| f(a_n) |}{|f'(a_n)|}
= \max \frac{| f(a_n) |}{|f'(a_0)|} 
= \frac{| f(a_0) |}{|f'(a_0)|},\] as required.

For uniqueness, imagine $\hat a \not= a$ also satisfied
$f(\hat a) = 0$ and $| \hat a - a_0 | < | f'(a_0) |$.
Let $\hat b = \hat a - a \not= 0$. Then \[0 = f(\hat a) - f(a) = f(a + \hat b) - f(a) 
= {\hat b} f_1(a) + {\hat b}^2 f_2(a) + \ldots\]

But $| \hat b | = | \hat a - a_0 + a_0 - a |
\leqslant \max( | \hat a - a_0 |, | a - a_0 | )
 $
$< | f'(a_0) |
= | f_1(a_0) | = | f_1(a) |$ (by continuity of $|f'(x)|$).
 
This gives $|{\hat b}^j f_j(a)| \leqslant
|{\hat b}^j| \leqslant |{\hat b}^2| < |{\hat b} f_1(a)|$
% N.B. I might omit the next line:
(since $|{\hat b}| \not= 0$ \& $|{\hat b}| < |f_1(a)|$)
for~$j\geqslant 2$, so that the leading term of the sum in~(3)
has valuation strictly greater than the valuations of the other terms,
which is inconsistent with the sum being~$0$. Hence~$a$
is unique.
\end{proof}
\begin{ex}\label{ex:hensel} Let $f(x) = x^3 - 7$ and $a_0 = 3$.
Then $| f(a_0) |_5 = | 3^3 - 7 |_5 = 5^{-1}$
and $| f'(a_0) |_5 = | 3\cdot 3^2 |_5 = 1$. So 
$| f(a_0) |_5 < | f'(a_0) |_5^2$ and by Hensel's Lemma there
exists $a\in \bbbz_5$ such that $f(a) = 0$, that is: $a^3 = 7$.
\end{ex}
\begin{cor}\label{cor:squares}
Let $\alpha \in \bbbq_p$ with $|\alpha|_p = 1$. 
When $p\not= 2$, $\alpha$ is a square in~$\bbbq_p$ iff
it is a square modulo~$p$.
When~$p=2$, $\alpha$ is a square in~$\bbbq_p$ iff 
$\alpha \equiv 1\ (\mod 8)$.
\end{cor}
\begin{ex}\label{ex:squares}
$23 \in \bigl( \bbbq_7^* \bigr)^2$ since $|23|_7 = 1$
and $23 \equiv 2 \equiv 3^2\ (\mod 7)$.
However, $24 \not\in \bigl( \bbbq_7^* \bigr)^2$ since $|24|_7 = 1$
and $24 \equiv 3\ (\mod 7)$, which is not a quadratic residue mod~$7$.
% N.B. I might omit the next sentence:
\par The corollary does not apply to decide the status of~$14$,
but in fact we can see that
$14 \not\in \bigl( \bbbq_7^* \bigr)^2$, since if $14 = \gamma^2$
for some $\gamma\in\bbbq_7$ then
$|\gamma|_7^2 = |\gamma^2|_7 = |14|_7 = 7^{-1}$,
contradicting the fact that $|\gamma|_7 = 7^r$
for some $r\in\bbbz$.
\end{ex}
\medskip
\hrule

%********************************************************************
\newpage
\section{The Reduction Map on an Elliptic Curve}\label{sec:red}
%% Hensel's Lemma and special cases. The reduction map and lifting.
%% [2 lectures]
Throughout this section, $K$ denotes a complete non-Archimedean field,
with valuation ring~$R = \{ x : | x | \leqslant 1 \}$,
maximal ideal $\M = \{ x : |x| < 1\}$ and residue field
$k = R/\M$.
\begin{defn}\label{defn:reduction} Then natural mod~$\M$
map $R \rightarrow k = R/\M : r \mapsto r + \M$, is a surjection and is
denoted $a \mapsto \tilde a$ (or sometimes $\bar a$).
For example in $\bbbz_5$, if $a = 3 + 2\cdot 5^1 + \ldots$
then $\tilde a = 3$; also $\widetilde{17/3} = 2/3 = 2\cdot 2 = 4$.
\par Let $a = (a_0,\ldots , a_n) \in \P^n(K)$.
We define the reduction map to~$\P^n(k)$ as follows.
\par  Step 1. There exists $i_0$ such
that $| a_{i_0} | \geqslant | a_i |$ for $i = 0,\ldots ,n$.
We replace each~$a_i$ by $a_i/a_{i_0}$ (which leaves~$a$
unchanged) so that now the largest valuation is~$1$
({\it normalised} form).
\par  Step 2. Define $\tilde a = (\tilde a_0,\ldots ,\tilde a_n)$
(easy to check that this is well defined).
\end{defn}
\par In affine space, if $a = (a_1,\ldots ,a_n)$ 
then $\tilde a = (\tilde a_1,
\ldots , \tilde a_n)$ , provided that all $| a_i | \leqslant 1$.
\par When $K = \bbbq_p$, this is just the `mod~$p$' map, where
the coordinates are reduced modulo~$p$. 
\begin{ex}\label{ex:reduction}  
In~$\P^2(\bbbq_5)$, let $a = (1/5, 2/15, 2)$.
Dividing through by~$a_0=1/5$ gives $a = (1,2/3,10)$
so that $\tilde a = (\tilde 1, \widetilde{2/3}, \widetilde{10})
= (1,4,0)\in \P^2(\bbbf_5)$. For $b = (2/3, 25)$
in affine space~$A^2(\bbbq_5)$ (an affine point with
no denominators of~$5$), then $\tilde b = (4,0)\in A^2(\bbbf_5)$.
\par For the point $P = (1/4, 7/8) \in \EQ \subset \E(\bbbq_2)$
on the elliptic curve~$\E : y^2 = x^3 - x + 1$, 
we should first write~$P$ in projective form: $(1/4,7/8,1)
= (2/7,1,8/7)$ (after dividing through by~$7/8$), which
reduces modulo~$2$ to~$(0,1,0)$, the point at infinity
on~$\TE (\bbbf_2)$. Clearly any $(x,y) \in \E(\bbbq_p)$
will reduce mod~$p$ to the point at infinity iff
$|x|_p > 1$ and~$|y|_p > 1$.
\end{ex}
\begin{defn}\label{defn:curvereduc}
Let~$\C : F(X,Y,Z) = 0$ be a projective curve, defined over~$K$.
Let~$\{ f_i \}$ be the set of all coefficients of~$\C$. The
curve is unchanged if we multiply all the~$f_i$ by a nonzero constant,
so after dividing through by $f_{i_0}$ such that
$| f_{i_0} | \geqslant | f_i |$ for all~$i$,
we can assume that $\max(|f_i|) = 1$.

The reduction of~$\C$ mod~$\M$ is then $\TC : \widetilde F(X,Y,Z) = 0$,
defined over~$k = R/\M$,
where every coefficient has been reduced mod~$\M$.
When $K = \bbbq_p$, this is again just a matter of reducing
the coefficients mod~$p$.
\end{defn}
\par Clearly, $a$ lies on~$\C \implies \tilde a$ lies on $\TC$,
when we say that~$a$ reduces to~$\tilde a$.
\begin{defn}\label{defn:lift}
Let~$b\in{\TC}(k)$. If there 
exists~$a\in \C(K)$ such that~$\tilde a = b$, we say
that~$b$ {\it lifts} to~$\C$ (or that~$b$ {\it lifts}
to a point on~$\C$).
\end{defn}
% N.B. In the following example, omit the proof and just say:
% $(0,0,1) \in \TE(\bbbf_p)$ does not lift to a point
% in \E(\bbbq_p)$ (on a Problem Sheet).
% If we had represented the above curves with
% the affine shorthand: $\E : y^2 = x^3 + p$ and $\TE : y^2 = x^3$,
% then the above would be expressed by saying that~$(0,0)\in \TE(\bbbf_p)$
% does not lift.
\begin{ex}\label{ex:lift}
Let $\E : Z Y^2 = X^3 + p Z^3$, defined over $\bbbq_p$,
and $\TE : Z Y^2 = X^3$, defined over~$\bbbf_p$.
Consider~$(0,0,1)\in \TE(\bbbf_p)$. Does it lift to
a point in~$\E(\bbbq_p)$? Imagine $(X,Y,Z) \in \E(\bbbq_p)$
reduces mod~$p$ to~$(0,0,1)\in \TE(\bbbf_p)$.
Then~$p | X, p | Y, p \nmid Z$, that is,
$| X |_p < 1, | Y |_p < 1, | Z |_p = 1$.
But all $p$-adic values are of the form: $\ldots , p^{-2},p^{-1}, p^0, p^1,
\ldots $ so that $| X |_p \leqslant p^{-1}, | Y |_p \leqslant p^{-1}$,
and $| X^3 |_p \leqslant p^{-3}$.
Furthermore, $| p Z^3 |_p = | p |_p | Z |_p^3 = p^{-1}$.
\par Since $| X^3 |_p \not= | p Z^3 |_p$ we must have
$| X^3 + p Z^3 |_p = \max\bigl( | X^3 |_p, | p Z^3 |_p \bigr)
= p^{-1}$. But then $ | Y^2 |_p = | Z Y^2 |_p
= | X^3 + p Z^3 |_p = p^{-1}$, a contradiction. We conclude
that $(0,0,1) \in \TE(\bbbf_p)$ does not lift to
a point in~$\E(\bbbq_p)$.
%{\it In fact: need not do proof; just refer to Problem Sheet~3.}{JN 2024 not sure what this is referring to!}
\par If we had represented the above curves with
the affine shorthand: $\E : y^2 = x^3 + p$ and $\TE : y^2 = x^3$,
then the above would be expressed by saying that~$(0,0)\in \TE(\bbbf_p)$
does not lift.
\end{ex}
On the other hand, the following result shows that we can
guarantee lifting a nonsingular point on~$\TE$.
\begin{thm}\label{thm:lifting}
Let $\C$ be defined over~$K$, written so that the coefficients
lie in~$R$. Let~$\TC$, defined over~$k$, be the reduction
of~$\C$ modulo~$\M$. Let~$b \in \TC(k)$ be a nonsingular point.
Then~$b$ lifts to~$\C$; that is, there exists~$a\in\CK$
such that $\tilde a = b$.
\end{thm}
\begin{proof} 
Write $\C : F(X_0, X_1, X_2) = 0$ (normalised), so that 
$\TC : \widetilde F( X_0, X_1, X_2) = 0$. Let
$b = (b_0, b_1, b_2) \in \TC(k)$ be a nonsingular point.
Then at least one of 
the $\frac{\partial {\widetilde F}}{\partial X_i}(b) \not= 0$;
wlog say that $\frac{\partial {\widetilde F}}{\partial X_0}(b) \not= 0$.
% N.B. I might replace the three sentences:
%   Let $\alpha_0 , \alpha_1, \alpha_2 \in R$ be such that each 
%   $\tilde \alpha_i = b_i$ under the natural surjection from $R$ to 
%   $k = R/\M$. Then $\alpha = (\alpha_0, \alpha_1, \alpha_2)$ satisfies
%   $\tilde \alpha = b$; however, we have no guarantee that~$\alpha$ lies 
%   on~$\C$.  We shall construct an adjustment of~$\alpha$ which lies
%   on~$\C$, and which has the same reduction as~$\alpha$.
% by:
%   Let $\alpha_0 , \alpha_1, \alpha_2 \in R$, 
%   $\alpha = (\alpha_0 , \alpha_1, \alpha_2)$, be such that each
%   $\tilde \alpha_i = b_i$ under the natural surjection from $R$ to
%   $k = R/\M$. 
Let $\alpha_0 , \alpha_1, \alpha_2 \in R$ be such that each 
$\tilde \alpha_i = b_i$ under the natural surjection from $R$ to 
$k = R/\M$. Then $\alpha = (\alpha_0, \alpha_1, \alpha_2)$ satisfies 
$\tilde \alpha = b$; however, we have no guarantee that~$\alpha$ lies 
on~$\C$. We shall construct an adjustment of~$\alpha$ which lies
on~$\C$, and which has the same reduction as~$\alpha$.
%\par 
Let $f(t) = F(t, \alpha_1, \alpha_2)$.
Then $\widetilde{f(\alpha_0)} = \widetilde F(b) = 0$
so that $| f(\alpha_0 ) | < 1$. Furthermore, $\widetilde{ f'(\alpha_0) }
= \frac{\partial {\widetilde F}}{\partial X_0}(\tilde \alpha)
= \frac{\partial {\widetilde F}}{\partial X_0}(b) \not= 0$,
so that $| f'(\alpha_0) | = 1$. By Hensel's Lemma, there
exists $a_0 \in R$ such that $f(a_0) = 0$ and $| a_0 - \alpha_0 | < 1$,
so that $a = (a_0, \alpha_1, \alpha_2)$ is a point on~$\C$
and $\tilde a = \tilde \alpha = b$, as required.  
\end{proof}
\par
We wish to see under what circumstances the reduction
map is a homomorphism on an elliptic curve.
\begin{thm}\label{thm:redhom}
Let~$\C : F(X_0,X_1,X_2) = 0$ be a cubic curve defined over~$K$,
written so that coefficients of~$F$ have maximum valuation~$1$.
Suppose the line $\LL : L(X_0,X_1,X_2) = 0$ meets~$\C$ at~$a,b,c$.
Then either:
\par (1) ${\widetilde \LL} \subset {\widetilde \C}$, that is,
${\widetilde F}(X_0,X_1,X_2) = {\widetilde L}{\widetilde M}$,
for some~$M$.
\par  or:
\par (2) $\widetilde \LL$ meets $\TC$ precisely
at $\tilde a, \tilde b, \tilde c$.
\end{thm}
% N.B. I should replace the following with an abbreviated proof:
% Let $L : \ell_0 X_0 + \ell_1 X_1 + \ell_2 X_2$, written so that 
% $\max(|\ell_0|, |\ell_1|, |\ell_2|) = 1$, wlog $|\ell_0| = 1$; after 
% dividing through by~$\ell_0$ (and relabelling $\ell_1/\ell_0, \ell_2/\ell_0$
% as $\ell_1, \ell_2$), we can take 
% $\LL : X_0 = - \ell_1 X_1 - \ell_2 X_2$, where $\ell_1,\ell_2 \in R$. 
% Consider ${\widetilde F}(-\tilde\ell_1 X_1 - \tilde\ell_2 X_2, X_1, X_2)$.
% If this is 0 then $\widetilde L$ is a factor of $\widetilde F$
% giving case (1), otherwise (2) clearly follows.
\begin{proof} 
Let $L : \ell_0 X_0 + \ell_1 X_1 + \ell_2 X_2$,
written so that $\max(|\ell_0|, |\ell_1|, |\ell_2|) = 1$,
wlog $|\ell_0| = 1$; after dividing through by~$\ell_0$
(and relabelling $\ell_1/\ell_0, \ell_2/\ell_0$
as $\ell_1, \ell_2$),
we can take $\LL : X_0 = - \ell_1 X_1 - \ell_2 X_2$, where 
$\ell_1,\ell_2 \in R$. 
Write $a = (a_0,a_1,a_2),
b = (b_0,b_1,b_2), c = (c_0,c_1,c_2)$ with
$\max | a_i | = \max | b_i | = \max | c_i | = 1$.
Note that, since $a,b,c$ lie on~$\LL$, we must then
have $\max(| a_1 |, | a_2 | ) 
= \max( | b_1 |, | b_2 | ) = \max( | c_1 |, | c_2 | ) = 1$.  
\par Now, substitute $L$ into $F$ to get:
$G(X_1, X_2) = F(- \ell_1 X_1 - \ell_2 X_2, X_1, X_2 ) \in R[X_1,X_2]$.
Since the points $a,b,c$ lie on both~$\LL$ and~$\C$,
the roots of the projective polynomial~$G$
are~$(a_1,a_2), (b_1,b_2), (c_1,c_2) \in \P^1(K)$, so that: 
\par $G(X_1, X_2) = F(- \ell_1 X_1 - \ell_2 X_2, X_1, X_2 ) 
 = \lambda (a_2 X_1 - a_1 X_2)(b_2 X_1 - b_1 X_2)(c_2 X_1 - c_1 X_2),$
\par  for some~$\lambda\in R^*$.  
Now consider 
${\widetilde F}(- \tilde \ell_1 X_1 - \tilde \ell_2 X_2, X_1, X_2)$.
If this is~$0$ then~$\widetilde L$ is a factor of~${\widetilde F}$,
giving case~(1). Otherwise, this is a nonzero projective
polynomial, defined over~$k$, equal to
$\tilde \lambda ( \tilde a_2 X_1 - \tilde a_1 X_2)
(\tilde b_2 X_1 - \tilde b_1 X_2)(\tilde c_2 X_1 - \tilde c_1 X_2)$,
with $(\tilde a_1,\tilde a_2), (\tilde b_1,\tilde b_2), 
(\tilde c_1,\tilde c_2) \in \P^1(k)$ as roots,
so that $\tilde a, \tilde b, \tilde c$ lie on~$\widetilde \LL$ 
and~$\widetilde \C$.
Since $\widetilde L$ and ${\widetilde F}$ have no common
factor, these must be precisely the points of intersection
of~$\widetilde \LL$ and~$\widetilde \C$. 
\end{proof}
\par
% N.B. The following paragraph should be replaced by the
% following abbreviated form:
% When $\E : y^2 = x^3 + A x + B$ ($A,B \in R$), the reduction $\widetilde \E$ 
% will still be of the form $y^2 = x^3 + \ldots$. This cannot contain a line,
% since any $(y + r x + \ldots)(y - x^2/r + \ldots)$ would
% have an $x^2 y$ term and so would not give $y^2 - \hbox{cubic in }x$.  
% Since the group law is constructed by finding intersections
% between the curve and lines, and since only option~(2) applies,
% the construction of the group law respects the reduction map, giving the
% following result.
When we have an elliptic curve written, not as a general cubic,
but birationally transformed to the form $\E : y^2 = x^3 + A x + B$ 
with $A,B \in R$ (which, as usual, is shorthand for the projective curve
$Z Y^2 = X^3 + A X Z^2 + B Z^3$),
the reduction $\widetilde \E$ will still be of the form
$y^2 = x^3 + \ldots$. This cannot contain a line,
since any $(y + r x + \ldots)(y - x^2/r + \ldots)$ would
have an $x^2 y$ term and so would not give $y^2 - \hbox{cubic in }x$.  
For such a curve, only option~(2) can apply in the previous
theorem. Even though~$\E$ is an elliptic curve
(and therefore nonsingular), the reduction $\TE$ might be
singular (for example, when $p | \Delta \in \bbbz$ so
that $\widetilde \Delta = 0$ in~$\bbbf_p$), but even in that
case we still have the group $\TE_{ns}(k)$ of nonsingular points
(see Comment~\ref{ell:degen}).
Since the group law is constructed by finding intersections
between the curve and lines, and since only option~(2) applies,
the construction of the group law respects the reduction map, giving the
following result.
% N.B. In the following corollary, I might remove:
% "let $\E_0(K)$ denote the set of points in~$\E(K)$ which reduce 
% to members of~$\TE_{ns}(k)$, that is,"
\begin{cor}\label{cor:redhom}
Let~$\E : y^2 = x^3 + A x + B$ be an elliptic curve, with $A,B\in R$,
with reduction~$\TE$. Let~$\TE_{ns}(k)$ denote the group
of nonsingular points in~$\TE(k)$, and let $\E_0(K)$ denote the
set of points in~$\E(K)$ which reduce to members of~$\TE_{ns}(k)$,
that is, define: 
$\E_0(K) = \{ P \in \E(K) : \widetilde P \in \TE_{ns}(k)\}$.
Then the reduction map $P \mapsto \widetilde P$
is a homomorphism from~$\E_0(K)$ to~$\TE_{ns}(k)$.
\end{cor}
\begin{defn}\label{defn:kerred}
Let~$\E_0(K)$ and~$\TE_{ns}(k)$ be
as in~Corollary~\ref{cor:redhom}. The {\it kernel of reduction},
denoted $\E_1(K)$, is the kernel of the reduction map
from $\E_0(K)$ to $\TE_{ns}(k)$. That is:
% N.B. In the following displayed equation,
% I might verbally comment that it doesn't matter whether we put
% \E(K) or \E_0(K) (on the inside of the set in the defn)
% as $\underline{\bf o}$ is always nonsingular [in $\TE_{ns}(k)$] and so
% any $P \in \E(K)$ with ${\widetilde P} = {{\underline{\bf o}}}$
% will automatically be in $\E_0(K)$.
$$ \E_1(K) = \{ P \in \E(K) : {\widetilde P} = 
{{\underline{\bf o}}} \}, $$
% N.B. I could just remove: 
% "where, as usual, ........ under the reduction map."
% If so, I should also remove the "as already observed",
% as in two comments from now.
where, as usual, $\o$ is the identity element,
%of~$\E(K)$ [so that~$\tilde{\underline{\bf o}}$ 
%is the identity element of~$\TE_{ns}(k)$],
usually taken to be the point at infinity, in which case
$$\E_1(K) = \{ P = (x,y) \in \E(K) : |x| > 1,\ |y| > 1 \},$$
since these are the points that map to the point at infinity
under the reduction map.
\end{defn}
We can summarise what we know so far by the following
exact sequence:
$$
\begin{CD}
0 @>>> \E_1(K) @>{i}>> \E_0(K) @>{\widetilde{\ \ }}>> \TE_{ns}(k) @>>> 0,\\
\end{CD}
$$
where~$i$ is the inclusion map.
% N.B. I might comment in the above exact sequence that $\widetilde{\ \ }$
% is surjective by Theorem\ref{thm:lifting}[3.6] and is a homomorphism
% by Corollary\ref{cor:redhom}[3.8].
\par
We now wish to look more closely at how we can describe
the group law inside~$\E_1(K)$, the kernel of reduction,
for an elliptic curve:
$$ \E : y^2 = x^3 + A x + B,\ \ \hbox{ where } A,B\in R.$$
\par
We adopt the usual convention that the identity is~$\o$,
the point at infinity so that, 
% N.B. Can remove the following "as already observed"
% if I have removed the "where, as usual ...", as in two comments ago.
as already observed,
$\E_1(K) = \{ (x,y) \in \E(K): |x| > 1,\ |y| > 1\}$.
The members of $\E_1(K)$ are in a neighbourhood of~$\o$,
and it is natural to try to describe the
group law as a power series. 
% N.B. I might remove the sentence 
% "This will be more transparent .... than large, valuation."
This will be more transparent
if we write our equation in a form where the points in the neighbourhood
have coordinates with small, rather than large, valuation.
We therefore perform the following birational transformation:
$$ z = -x/y,\ w = -1/y,\ \hbox{ with inverse } x = z/w,\ y = -1/w.$$
This transforms $\E$ to:
$$ \frac{1}{w^2} = \frac{z^3}{w^3} + A \frac{z}{w} + B, $$
giving the equation
$$ \E' : w = f(z,w) = z^3 + A w^2 z + B w^3.$$
% N.B. I might observe that, under this transformation:
% z = -x/y,\ w = -1/y, with inverse x = z/w,\ y = -1/w,
% lines map to lines, since y = \ell x + m maps to
% -1/w = \ell z/w  + m, which is:  -1 = \ell z + m w.
Note that the point at infinity~$\o$ on~$\E$ maps to
the point~$(0,0)$ on~$\E'$, which we take as our
group identity on~$\E'$. The condition $|x|>1, |y|>1$
corresponds to $|z|<1, |w|<1$, so that the kernel of reduction
for~$\E'$ is:
$$ \E'_1(K) = \{ (z,w) \in \E'(K) : |z| < 1,\ |w| < 1\}.$$  
We now recursively substitute $w = f(z,w)$ into itself.
For the first step:
$$
w = f(z,w) = f(z, f(z,w)) = z^3 + A(z^3 + A w^2 z + B w^3)^2 z
+ B(z^3 + A w^2 z + B w^3)^3
$$
$$
= z^3 + A z^7 + \ldots 
$$ 
Inductively define $f_n(z,w)$ by: $f_1(z,w) = f(z,w)$
and $f_{n+1}(z,w) = f_n( z, f(z,w) )$. Define
$$ w(z) = \lim_{n\rightarrow \infty} f_n(z,0) \in \bbbz[A,B]\lb z\rb.$$
The following is then easy to show.
\begin{lem}\label{lem:wz}
The power series $w(z) = z^3( 1 + \ldots ) \in \bbbz[A,B]\lb z\rb$
defined above is the unique power series satisfying
$w(z) = f\bigl( z, w(z) \bigr)$.
\end{lem}
This means that $\bigl( z, w(z) \bigr)$ satisfies~$\E'$.
% N.B. Can delete the next two sentences: 
% "Since we are working ... so $|A|,|B| \leqslant 1$]."
Since we are working in a non-Archimedean field~$K$,
we can appeal to the fact (see Theorem~\ref{thm:series})
that a series converges iff its terms converge to~$0$.
When we are in the kernel of reduction $|z|<1, |w|<1$,
this applies to the above series~$w(z)$ (since $A,B\in R$ and
so $|A|,|B| \leqslant 1$). 
Any~$(z,w)$
in the kernel of reduction must satisfy $w = w(z)$ (by the uniqueness part of Hensel's lemma),
and so is uniquely determined by~$z$, which is called
a {\it local parameter}.
\begin{comm}\label{comm:laurent}
We can recover~$x,y$ on~$\E$ as formal Laurent series:
$$
x(z) = \frac{z}{w(z)} = \frac{z}{z^3(1 + \ldots)} = \frac{1}{z^2} + \ldots
$$
$$
y(z) = -\frac{1}{w(z)} = -\frac{1}{z^3(1 + \ldots)} = -\frac{1}{z^3} + \ldots 
$$
which gives a formal solution to~$\E$.
\end{comm}
\par Let us now perform the addition 
$ (z_1,w_1) + (z_2,w_2)$. As usual, we first write
the line $w = \lambda z + \mu$ through the points,
given by $\lambda = (w_1 - w_2)/(z_1 - z_2)$
and $\mu = (z_1 w_2 - z_2 w_1)/(z_1 - z_2)$.
As long as we are in the kernel of reduction,
$w_1 = w(z_1)$
and $w_2 = w(z_2)$, and so:
$$
\lambda = \lambda(z_1,z_2) = \frac{w(z_1) - w(z_2)}{z_1 - z_2}
= \frac{z_1^3(1 + \ldots) - z_2^3(1 + \ldots)}{z_1 - z_2}
\in \bbbz[A,B]\lb z_1,z_2\rb,$$
with all terms being of degree $\geqslant 2$, and:
$$
\mu = \mu(z_1,z_2) = \frac{z_1 w(z_2) - z_2 w(z_1)}{z_1 - z_2}
\in \bbbz[A,B]\lb z_1,z_2\rb.$$
Substituting $w = \lambda z + \mu$ into $\E'$ gives
$\lambda z + \mu = z^3 + A(\lambda z + \mu)^2 z + B (\lambda z + \mu)^3$,
and so:
$$(1 + A \lambda^2 + B \lambda^3) z^3 
 + ( 2 A \lambda \mu + 3 B \lambda^2 \mu ) z^2 + \ldots = 0.$$
Let $(z_3, w(z_3))$ be the third point of intersection of
$\E'$ and the line $w = \lambda z + \mu$, so that $z_1,z_2,z_3$
are the roots of the above cubic, giving
that $z_1 + z_2 + z_3 = -(\hbox{coeff of }z^2)/(\hbox{coeff of }z^3)$,
so:
$$ z_3 = -z_1 - z_2 - \frac{2 A \lambda \mu + 3 B \lambda^2 \mu}
{1 + A \lambda^2 + B \lambda^3} \in \bbbz[A,B]\lb z_1,z_2\rb,
$$
since the denominator is of the form $1 + \phi(z_1,z_2)$,
where $\phi(z_1,z_2)$ has no constant term (and so is an invertible
power series, with $1/(1 + \phi(z_1,z_2)) 
= 1 - \phi(z_1,z_2) + \phi(z_1,z_2)^2 + \ldots$).
\par The sum $(z_1,w_1) + (z_2,w_2) + (z_3,w_3) =$ the identity,
and so $(z_1,w_1) + (z_2,w_2) = -(z_3,w_3)$.
Negation $(x,y) \mapsto (x,-y)$ induces $(z,w)\mapsto (-z,-w)$
(since $z=-x/y, w=-1/y$), so that the
$z$-coordinate of $(z_1,w_1) + (z_2,w_2)$ is given
by $F_\E(z_1,z_2)$, where:
$$
F_\E(z_1,z_2)
= z_1 + z_2 + (\hbox{terms of degree }\geqslant 2) \in \bbbz[A,B]\lb z_1,z_2\rb.
$$
We summarise this as follows.
\begin{lem}\label{lem:ellformal}
Any point $(x,y)$ on~$\E$ ($\leftrightarrow (z,w)$ on~$\E'$)
in the kernel of reduction (explicitly: $|x| > 1, |y| > 1
\leftrightarrow |z|<1, |w|<1$)
is uniquely determined by~$z$, with 
$w = w(z) \in \bbbz[A,B]\lb z\rb$. The group law is completely
described by the above $F_\E(z_1,z_2) \in \bbbz[A,B]\lb z_1,z_2\rb$, 
which converges
to the $z$-coordinate of the sum of $(z_1,w(z_1))$
and $(z_2,w(z_2))$.
\end{lem}
We have already observed that $F_\E(z_1,z_2) = z_1 + z_2 +$ terms
of higher degree. The associativity and commutativity properties of 
the group law on $\E$ also induce the properties:
$$ 
 F_\E (X, F_\E(Y,Z) ) = F_\E (F_\E(X,Y), Z ),\ \ 
 F_\E ( X, Y) = F_\E ( Y, X).
$$
% N.B. I could just say verbally (and not write down) the following paragraph:
Of course, the power series $F_\E(z_1,z_2) \in \bbbz[A,B]\lb z_1,z_2\rb$
can be derived for any~$\E$ defined over any ring, regardless
of convergence considerations. In the next section, we shall
consider power series~$F(X,Y)$ which satisfy the above properties,
and then apply the results to the special case of~$F_\E(X,Y)$.

\medskip
\hrule

%********************************************************************
\newpage
\section{Formal Groups}\label{sec:formalgroups}
%% General 1-parameter formal groups and their properties, inv diff,
%% the formal group of an elliptic curve [2 lectures]
Let~$R$ be any ring (by {\it ring} I shall alway mean 
a commutative ring with~1).
\begin{defn}\label{defn:formalgroup}
A (one-parameter, commutative)  {\it formal group}
defined over~$R$ is a power series $F(X,Y) \in R\lb X,Y\rb$
satisfying:
\par (1)\ $F(X,Y) = X + Y + \hbox{ terms of degree } \geqslant 2$.
\par (2)\ $F(X, F(Y,Z)) = F(F(X,Y),Z)$.
\par (3)\ $F(X,Y) = F(Y,X)$.
\end{defn}
% N.B. I might verbally comment that two power series in R\lbX,Y\rb are
% equal iff all coefficients are equal [just regard them as formal power
% series; don't worry about functions they might give for special cases of R. 
\begin{ex}\label{ex:formalgroup} The following are all formal groups.
\par The formal group $F_\E(X,Y)$ of an elliptic curve defined
over~$R$, as described in Section~\ref{sec:red}.
\par The formal additive group $F(X,Y) = \widehat{\mathbb{G}}_a(X,Y) = X + Y$.
\par The formal multiplicative group $F(X,Y) = \widehat{\mathbb{G}}_m(X,Y)
= X + Y + XY$.
\par  Note: the last of these is just $XY$, but translated
one unit to the left: $(1 + X)(1 + Y) - 1$ so that the
identity is changed from~$1$ to~$0$.
\end{ex}
% N.B. I might also verbally give here a summary of some of the surprising 
% facts we'll deduce from these simple axioms: commutativity axiom is 
% redundant (with R is an integral domain of characteristic 0), all formal 
% groups are isomorphic (when R is a field of characteristic 0),
% and we shall describe a log map, a description of the multiplication-by-m
% map, and look at induced groups and restrictions on torsion elements.
% N.B. The following aside (like most asides) should just be verbal.
{\it Aside: A formal group does not necessarily induce an actual 
nontrivial commutative group, since there is no guarantee that 
the power series will converge for any nonzero $X,Y$; indeed,
our arbitrary ring~$R$ may not even come together with any
structure (such as a valuation or metric) that provides
a definition of convergence. It is merely a power series
satisfying properties analogous to associativity and commutativity. 
The definition appears to be missing properties analogous
to the existence of an identity element and inverses. In fact,
the following result shows these can be deduced from the given axioms.}
\begin{lem}\label{lem:formalinv}
Let~$F(X,Y)$ be a formal group over a ring~$R$.
\par (1) There is a unique power series $i(T) \in T R\lb T\rb$
such that $F\bigl( T, i(T) \bigr) = 0$.
\par (2) $F(X,0) = X$ and $F(0,Y) = Y$.
\end{lem}
\begin{proof} (1) Let $Z_1 = -T \in T R\lb T\rb$; then the terms
of~$F(T,Z_1)$ all have degree~$\geqslant 2$.
Suppose we have $Z_n \in T R\lb T\rb$ of degree $\le n$ such that
$F(T,Z_n) = a_{n+1} T^{n+1} + \ldots$ has terms
all of degree~$\geqslant n+1$.
Define $Z_{n+1} = Z_n - a_{n+1}T^{n+1}$; then:
$$ 
\begin{array}{rl}
F(T,Z_{n+1}) &= F(T,Z_n - a_{n+1}T^{n+1})
= T + (Z_n - a_{n+1}T^{n+1}) + \ldots\\
&= F(T,Z_n) - a_{n+1}T^{n+1} + \hbox{ (terms of degree~$\geqslant n+2$)}\\
% N.B. This last step is since: any f_{ij}T^i(Z_n - a_{n+1}T^{n+1})^j
% = f_{ij}T^i Z_n^j + higher degree terms.
&= a_{n+1} T^{n+1} - a_{n+1}T^{n+1} +
\hbox{ (terms of degree~$\geqslant n+2$)},
\end{array}
$$
which has terms all of degree~$\geqslant n+2$. Moreover $Z_{n+1}$ is the unique polynomial of degree $\le n+1$ with this property. 

This defines a sequence $(Z_n)_{n \ge 1}$ with $Z_{n+1} = Z_n$ mod $T^{n+1}$. Letting $n$ tend to infinity, we can define a power series $i(T)$ whose first~$n$ terms give~$Z_n$ for each~$n$. It satisfies $F\bigl( T, i(T) \bigr) = 0$ (since $F\bigl( T, i(T) \bigr) = F\bigl( T, Z_n \bigr) = 0$ mod $T^{n+1}$ for every $n$).
Furthermore, if $i(T)$ satisfies $F\bigl(T,i(T)\bigr) = 0$ and we look at the degree $n$ part of $i(T)$ (discarding terms of degree $\ge n+1$), we must get the uniquely determined polynomial $Z_n$. We deduce that~$i(T)$ is unique.
\par  (2) By a similar argument to~(1), there exists
a unique $j(T)\in T R\lb T\rb$ such that $F(j(T), i(T)) = 0$.
By~(1) we can take $j(T) = T$.
By associativity $F(F(0,T),i(T)) = F(0,F(T,i(T))) = F(0,0) = 0$,
so that we can also take $j(T) = F(0,T)$.
Since $j(T)$ is unique, it follows that $F(0,T) = T$.
Similarly for $F(T,0) = T$.
\end{proof}
\begin{defn}\label{defn:formalhom}
Let~$F,G$ define formal groups over~$R$. A power series
$f(T)\in T R\lb T\rb$ is a {\it homomorphism}
from~$F$ to~$G$ if it satisfies 
$f\bigl( F(X,Y) \bigr) = G\bigl( f(X), f(Y) \bigr)$.
When there also exists an inverse~$g(T)\in T R\lb T\rb$
(that is: $f(g(T)) = g(f(T)) = T$), then $f(T)$
is an {\it isomorphism}. 
\end{defn}
% N.B. The condition that f(T) is in T R\lb T\rb is required, since
% f(T) is in R\lb T\rb with nonzero constant term, then G(f(x),f(Y))
% wouldn't make sense.
\begin{ex}\label{ex:homgmga}
If $\chari(R)=0$ and $\frac{1}{n} \in R$ for all~$n$,
then $f(T) = T - T^2/2 + T^3/3 - \ldots$ (i.e.~the power series expansion of $\log(1+T)$) is a homomorphism
from~$\widehat{\mathbb{G}}_m$ to~$\widehat{\mathbb{G}}_a$.
\end{ex}
\begin{defn}\label{defn:formalmultm}
Let~$F$ define a formal group over~$R$. Define 
the {\it multiplication by~$m$ map} $[m](T)\in R\lb T\rb$,
for $m\in\bbbz$,
inductively by: $[0](T) = 0$, $[m+1](T) = F([m](T),T)$ and
$[m-1](T) = F([m](T), i(T))$. This is clearly a homomorphism
from~$F$ to~$F$, and is of the form:
$[m](T) = m T + \hbox{ terms of degree }\geqslant 2$.
\end{defn}
\begin{lem}\label{lem:psinv}
Let $a \in R^*$ (that is: $a\in R$ and $a^{-1}\in R$), and
let $f(T) \in T R\lb T\rb$ be of the form $f(T) = a T + \ldots$
Then there exists a unique $g(T) \in T R\lb T\rb$ such
that $f(g(T)) = T$. Furthermore, $g$ satisfies $g(f(T)) = T$.
\end{lem}
\begin{proof} We shall construct $g(T) = b_1 T + b_2 T^2 + \ldots$,
the limit of $g_1(T) = b_1 T$, $g_2(T) = b_1 T + b_2 T^2, \ldots$,
first defining $g_1(T) = a^{-1} T$, so that the terms
of $f(g_1(T)) - T$ all have degree~$\geqslant 2$.
Suppose we have~$g_n(T)$ of degree~$n$ such that
$f(g_n(T)) - T = b T^{n+1} + \ldots$ and define 
$g_{n+1}(T) = g_n(T) - a^{-1} b T^{n+1}$.
Then 
$$ f(g_{n+1}(T)) - T = f(g_n(T)) - a a^{-1} b T^{n+1} 
+ (\hbox{terms of degree~$\geqslant n+2$}) - T,
$$
% N.B. This last step is justified by:
% if f(T) = a_1 T + a_2 T^2 + ... (where a_1 = a), then:
% f( g_n(T) - W ) = a_1 ( g_n(T) - W ) + a_2 ( g_n(T) - W )^2 + ...
% = a_1 g_n(T) + a_2 g_n(T)^2 + ... - a_1 W + (terms of degree in T bigger
% than the degree of T that occurs in W)
% = f(g_n(T)) - a_1 W + (...) = f(g_n(T)) - a_1 W + (...) [since a_1 = a].
whose terms are all of degree~$\geqslant n+2$.
The resulting $g(T)$ then satisfies $f(g(T)) = T$
and is unique, since each choice of coefficient was forced.
\par There similarly exists $h(T) \in R\lb T\rb$
such that $g(h(T)) = T$, and so $f(g(h(T))) = f(T)$,
giving $h(T) = f(T)$. Substituting this into $g(h(T)) = T$
gives $g(f(T)) = T$, as required. 
\end{proof}
\par
{\it Aside: The arguments in Lemma \ref{lem:formalinv} and Lemma \ref{lem:psinv} can be rewritten as an application of an appropriate version of Hensel's Lemma. We can equip the ring $R\lb T\rb$ with valuation $|f(T)| = \rho^n$,
where $\rho$ is a fixed real number satisfying $0 < \rho < 1$  
and $n$ is the degree of the smallest nonzero degree term
(for example, $| 2 T^3 + 5 T^4 + \ldots | = \rho^3$).
Here~$T$ takes on a similar role for~$R\lb T\rb$ to that performed
by~$p$ for~$\bbbz_p$. See Examples 10.10 and 10.11 in  \url{https://kconrad.math.uconn.edu/blurbs/gradnumthy/hensel.pdf}.}
\begin{lem}\label{lem:multmiso}
The homomorphism $[m] : F \rightarrow F$ of 
Definition~\ref{defn:formalmultm} is an isomorphism
whenever~$m\in R^*$.
\end{lem}
\begin{proof} Since $[m](T) = m T + \hbox{ terms of degree }\geqslant 2$,
we have from the previous lemma that the homomorphism
$[m]$ has an inverse, and so is an isomorphism. 
\end{proof}
\par
{\it Aside: You might have wondered in school about the connection between
the two properties of log, that it is the integral of $1/x$,
and that $\log(ab) = \log(a) + \log(b)$ (a homomorphism
from multiplication to addition). One way of seeing the connection
is to define $\log(T) = \int v(T)$ (with $\log(1) = 0$), where 
$v(T) = \frac{1}{T}\dd T$, and note that (regarding~$T$ as a variable
and~$S$ as a constant) $v(TS) = \frac{1}{TS}\dd (TS) = v(T)$,
that is, $v$ remains invariant under replacing~$T$ by~$TS$.
Therefore $\log(TS) = \log(T) + f(S)$, where~$f(S)$ is
a constant; setting~$T=1$ gives~$f(S) = \log(S)$.
If we were to adjust the multiplicative group, translating by~$-1$,
so that the identity is~$0$: $F(X,Y) = (1+X)(1+Y)-1 = X+Y+XY$,
then $\omega(T) = \frac{1}{1+T}\dd T = (1 - T + T^2 - \ldots)\dd T$ 
would have the property that $\omega \circ F(T,S) = \omega(T)$
(and $\int \omega(T)$ would give a homomorphism from ${\widehat{\mathbb{G}}}_m$
to ${\widehat{\mathbb{G}}}_a$).
It is natural to ask whether~$\omega$ is unique (up to constants),
and how we would construct~$\omega$ for a general choice
of~$F(X,Y)$.}
% N.B. Might mention verbally: the aim is to get a log map
% from from F to {\widehat G}_a; this will be in two parts:
% we first find omega, and then term-by-term integrate
% to get the log map - the last step only possible when the
% ring R includes 1/n for all n in N. So, we first want to see what
% generalises the above 1/(1+T) dT, which worked for F = {\widehat G}_m.
\begin{defn}\label{defn:invdiff}
A differential form on~$R\lb T\rb$
is an expression of the form $\sum_{i=1}^m P_i(T) \dd Q_i(T)$,
where each~$P_i(T), Q_i(T) \in R\lb T\rb$, and
these satisfy the natural rules:
$$
\dd\bigl( P(T) \bigr) = P'(T)\dd T, \hbox{ where
$P'(T) = \sum_{n=1}^\infty a_n n T^{n-1}$, for any }
P(T) = \sum_{n=0}^\infty a_n T^n,
$$
%from which it follows that:
$$ \dd \bigl( P(T) + Q(T) \bigr) = \dd P(T) + \dd Q(T),\ \
   \dd \bigl( P(T) Q(T) \bigr) = P(T) \dd Q(T) + Q(T) \dd P(T).
$$

We can see from the first rule that each differential form can be written uniquely as $\omega(T) = P(T)\dd T$ with $P(T) \in R\lb T\rb$.

More formally, the space of {\it differential forms} on~$R\lb T\rb$
is defined to be the quotient of the free $R\lb T\rb$-module spanned by the symbols $\{ \dd f : f \in R\lb T\rb\}$
by the submodule spanned by $\{\dd f - f' \dd T : f \in R\lb T\rb \}$. This is a free $R\lb T\rb$-module with basis element $\dd T$.
% N.B. I might omit the above formal (module) definition.
% I might verbally mention that all standard product rules,
% chain rules, etc, are true for power series, with formal P'(T).
% (Note that, from the defn: f dg = h dg if, and only if, f = h,
% which gets implicitly used later. Note that the above definition
% is a quotient modulo an equivalence relation/submodule, and so we
% represent the elements as above, but subject to the given natural
% relations we would expect from the $\dd$ symbol.


An {\it invariant differential} on a formal group~$F$, defined over~$R$,
is a differential form:
$$ \omega(T) = P(T)\dd T \in R\lb T\rb \dd T,\hbox{ satisfying }
\omega \circ F(T,S) = \omega(T).
$$
% N.B. I might mention verbally that for the purpose of
% defining \omega \circ F(T,S), we are regarding \omega as
% a differential form on (R_S)_T, i.e. as above, but
% with R'_T, where the ring R' is R_S.
Note that $\omega \circ F(T,S)$ is the same as
$P( F(T,S) ) \dd ( F(T,S) ) = P( F(T,S) ) F_X (T,S) \dd T$,
where~$F_X(X,Y)$ denotes the partial derivative
of~$F(X,Y)$ with respect to~$X$. 
% N.B. I might mention verbally that by F_X(X,Y), above, we just mean
% a formal replacement in the power series of each X^n by n X^{n-1} 
% (including n=0).
So, the above condition
on~$\omega$ is equivalent to:
$$ \omega(T) = P(T)\dd T \in R\lb T\rb \dd T,\hbox{ satisfying }
P\bigl( F(T,S) \bigr) F_X (T,S) = P(T).
$$
An invariant differential $\omega(T) = P(T)\dd T$
is said to be {\it normalised} if $P(0) = 1$. 
\end{defn}
\begin{ex} On~$\widehat{\mathbb{G}}_a$, the formal group defined
by $F(X,Y) = X + Y$, we can take $\omega(T) = \dd T$ as
a normalised invariant differential.
On~$\widehat{\mathbb{G}}_m$, the multiplicative formal group defined
by $F(X,Y) = X + Y + XY$, we can take 
$\omega(T) = (1 + T)^{-1} \dd T = (1 - T + T^2 - \ldots)\dd T$.
\end{ex}
\begin{thm}\label{thm:invdiffunique}
Let~$F$ be a formal group over~$R$. There exists a unique
normalised invariant differential given by
$\omega(T) = F_X(0, T)^{-1}\dd T \in R\lb T\rb \dd T$.
Every invariant differential is of the form $a\omega$
for some $a\in R$.
\end{thm}
\begin{proof} Let $P(T) = F_X(0, T)^{-1}$.
Note that $F_X(0, T) = 1 + \ldots$ is invertible, so
that $P(T)$ is indeed a member of~$R\lb T\rb$.
Furthermore, $P(0) = 1$, so that it is normalised.
\par We need to show that $\omega$ is an invariant differential.
Recall from Definition~\ref{defn:invdiff} that this is equivalent to:
$P\bigl( F(T,S) \bigr) F_X (T,S) = P(T)$ so, in our case,
it is sufficient to show:
$$ F_X\bigl( 0, F(T,S) \bigr)^{-1} F_X(T,S) = F_X(0,T)^{-1}, $$ 
which is true iff:
$$ F_X\bigl( 0, F(T,S) \bigr) = F_X(T,S) F_X(0,T). $$
But this last statement is immediate from differentiating
$F\bigl( U, F(T,S) \bigr) = F\bigl( F(U,T), S \bigr)$
(associativity)
with respect to~$U$ to get: 
$F_X\bigl( U, F(T,S) \bigr) = F_X\bigl( F(U,T), S\bigr) F_X(U,T)$
and setting~$U = 0$. Hence~$\omega$ is an invariant differential. 
\par Suppose that $\hat \omega(T) = Q(T)\dd T \in R\lb T\rb \dd T$ is also an 
invariant differential, so that $Q(T)$ satisfies
$Q\bigl( F(T,S) \bigr) F_X(T,S) = Q(T)$.
Substituting~$T=0$ gives $Q(S) F_X(0,S) = Q(0)$, so
that $Q(S) = Q(0) F_X(0,S)^{-1}$. It follows that
$\hat \omega = a \omega$, where $a = Q(0)$.
\end{proof}
\begin{cor}\label{cor:invdiffs}
Let~$f$ be a homomorphism over~$R$ from the formal group~$F$
to the formal group~$G$. Let~$\omega_F, \omega_G$ be
the normalised invariant differentials on~$F,G$, respectively.
Then $\omega_G \circ f = f'(0)\ \omega_F$.
\end{cor}
\begin{proof} First, note that $\omega_G \circ f\bigl( F(T,S) \bigr)
= \omega_G \bigl( G( f(T), f(S) ) \bigr) = \omega_G \circ f (T)$,
% N.B. I might mention verbally that this last step is
% due to to the invariant differential property of \omega_G.
so that $\omega_G \circ f$ is an invariant differential
on~$F$. From the previous result, it follows
that $\omega_G \circ f = a\ \omega_F$, for some~$a\in R$.
Since~$\omega_F,\omega_G$ are normalised,
$(1 + \ldots ) \dd f(T)  = a (1 + \ldots )\dd T$,
and so $(1 + \ldots ) f'(T) \dd T  = a (1 + \ldots )\dd T$; 
% N.B. the fact that \omega_G \circ f [of T] becomes (1 + \ldots ) \dd f(T)
% (above) is due both to the fact that \omega_G is normalised
% and that f has no constant term.
equating constant terms gives $a = f'(0)$, as required.
\end{proof}
\begin{cor}\label{cor:multp}
Let~$F$ be a formal group over~$R$ and let, as usual, 
$[m](T) \in R\lb T\rb$ denote the multiplication by~$m$ map on~$F$,
as in Definition~\ref{defn:formalmultm}. Let~$p$ be prime.
Then there exist $f,g\in R\lb T\rb$ ($f(T) = T + \ldots$),
such that $[p](T) = p f(T) + g(T^p)$.
\end{cor}
\begin{proof}
Let~$\omega$ be the normalised invariant differential on~$F$.
Since $[p](T) = p T + \dots$, it satisfies $[p]'(0) = p$.
Applying the previous result to~$[p]$, a homomorphism from~$F$
to itself, gives: $\omega \circ [p] = [p]'(0) \omega = p \omega$,
and so
$$ p \omega(T) = \omega \circ [p](T)
= (1 + \ldots ) \dd ( [p](T) ) = (1 + \ldots ) [p]'(T) \dd T.$$
Hence $[p]'(T) \in p\, R\lb T\rb$. 
% N.B. This last step uses the fact that 1 + \ldots is invertible in R\lb T\rb.
Each term $a_n T^n$ in $[p](T)$
must then satisfy 
$p | n a_n$ in~$R$, and so $p | n$ in~$\bbbz$ or $p | a_n$ in~$R$,
as required. 
% N.B. This last line should be interpreted as:
% $ p | n a_n$ in $R$ and so $p | n$ in $\bbbz$ or $p | a_n$ in $R$.
% The "and so" is since: if p divides n a_n in R and p does not divide n
% in \bbbz then there exist lambda, mu such that lambda p + mu n = 1, 
% and so: p divides (in R) p( lambda a_n + mu ( n a_n / p ) ) = a_n.
% Note also that the conclusion "p | n in \bbbz or p | a_n in R"
% is sufficient for the final result, since we can absorb into p f(T)
% all of the terms with p | a_n, (which includes p T) and then
% the remaining terms all have p | n and so give g(T^p).
\end{proof}
\begin{defn}\label{defn:formallog}
Let~$\omega(T) = P(T) \dd T = (1 + c_1 T + c_2 T^2 + \ldots) \dd T$
be the normalised invariant differential for the formal group~$F$
over~$R$.
For the special case when our ring~$R$ is a field
of characteristic~$0$,
we can define the {formal logarithm} by:
$\log_F(T) = \int \omega(T) 
= \int P(T) \dd T = T + \frac{c_1}{2} T^2 + \frac{c_2}{3} T^3 + \ldots $ 
% N.B. I might mention verbally that when we write $\int$ for a power 
% series, we mean the term-by-term replacement of $T^n$ 
% with (1/(n+1))T^{n+1} for each n.
and the {\it formal exponential function} $\exp_F(T)$  
as the unique member of~$R\lb T\rb$ satisfying
$\log_F (\exp_F (T)) = \exp_F (\log_F (T)) = T$,
which exists by Lemma~\ref{lem:psinv}.
\end{defn}
\begin{thm}\label{thm:formallog}
Let~$R$ be a field of characteristic~0; then
$\log_F$ (as in the previous definition)
is an isomorphism from~$F$ to~$\widehat{\mathbb{G}}_a$, the additive group~$X+Y$.
\end{thm}
\begin{proof} Differentiating $\log_F \bigl( F(T,S) \bigr) - \log_F(T)$
with respect to~$T$ gives: 
\par  $P\bigl( F(T,S) \bigr) F_X (T,S) - P(T)$
(and this $= 0$, since $\omega(T) = P(T) \dd T$ is an invariant
differential),
\par  
and so $\log_F \bigl( F(T,S) \bigr) - \log_F(T)$ is a power series
purely in~$S$, which we denote~$f(S)$; that is:
$\log_F \bigl( F(T,S) \bigr) = \log_F(T) + f(S)$.
Putting~$T=0$ forces $f(S) = \log_F(S)$.
Hence $\log_F$ is a homomorphism; the inverse is $\exp_F$,
and so $\log_F$ is an isomorphism.
\end{proof}
%\begin{proof} Integrating $\omega \bigl( F(T,S) \bigr) = \omega(T)$
%with respect to~$T$: $\log_F \bigl( F(T,S) \bigr)
%= \log_F(T) + f(S)$, where~$f(S)$ is constant with respect to~$T$.
%Putting~$T=0$ forces $f(S) = \log_F(S)$.
%Hence $\log_F$ is a homomorphism; the inverse is $\exp_F$,
%and so $\log_F$ is an isomorphism.
%\end{proof}
\begin{comm}\label{comm:exp}
Note that our proof of the existence
of the invariant differential required no appeal to the
commutativity axiom $F(X,Y) = F(Y,X)$.
If our formal group~$F$ is defined over
any integral domain~$R$
of characteristic~$0$
(such as $\bbbz$ or any $\bbbz_p$), we can
define $\log_F, \exp_F$ over~$K$, the field of fractions of~$R$,
and see that $F(X,Y) = \exp_F\bigl( \log_F(X) + \log_F(Y) \bigr)$,
which forces~$F$ to be commutative. 
% N.B. The rest of this comment, "So, at least ... unusual rings"
% can just be given verbally. Also, might note that the log
% map shows every formal group over a field of characteristic 0
% is isomorphic (since they are all isomorphic to {\widehat G}_a).
So, at least when~$F$ is defined over an integral domain
of characteristic~$0$, we have the somewhat
surprising fact that the commutativity axiom is redundant;
it can be deduced from:
$F(X,Y) = X + Y + \hbox{terms of degree }\geqslant 2$
and associativity. It is possible to construct non-commutative
formal groups, but only when defined over unusual rings.
\end{comm}
\begin{defn}\label{defn:fm}
Let $K$ be a field, complete with respect to a discrete
non-Archimedean valuation, $R = \{ x\in K : |x| \leqslant 1\}$
be the valuation ring, $\M = \{ x\in K : |x| < 1\}$ 
be the maximal ideal, and assume that $k = R/M$ (the residue field) is
of characteristic~$p$ (for example, $K = \bbbq_p$,
$R = \bbbz_p$, $\M = p\bbbz_p$, $k = \bbbf_p$). 
Let~$F$ be a formal group defined over~$R$.
The {\it group on~$\M$ associated to} $F(X,Y)$,
denoted~$F(\M)$, is the set~$\M$ together with the
group operation: $x \oplus y = F(x,y)$ (which converges
for any~$x,y\in \M$). The identity element is~$0$, and
the inverse of~$x$ is given by~$i(x)$ of Lemma~\ref{lem:formalinv}.
Similarly, for any~$n \geqslant 1$, define~$F(\M^n)$
to be the set~$\M^n$ with the same group operation.
% N.B. I might verbally comment that F(\M^n) is an actual
% group, and formal homomorphisms/isomorphisms become actual
% group homomorphisms/isomorphisms. Note also that the coefficients
% are in R, and so the terms of all power series go to 0,
% and so, since it is a non-Archimedean valuation, the power series converge.
\end{defn}
\begin{comm}
	To check that $(F(\M),\oplus)$ is indeed a group requires checking that various identities between formal power series imply equalities when substituting arguments in $\M$ for the variables. You can refer to Question 10 on Problem Sheet 3 if you want to see an example of a general result showing that this is valid.
\end{comm}

\begin{lem}\label{lem:torfm}
Let~$F, K, R, \M, k$ (with $\chari(k) = p$)
be as in Definition~\ref{defn:fm}.
\par  (a) The identity map: $F(\M^n)/F(\M^{n+1}), \oplus \rightarrow
\M^n / \M^{n+1}, +$ is an isomorphism.
% N.B. In the above, I might verbally mention that we
% are regarding F(\M^n)/F(\M^{n+1}) as a group under \oplus
% and \M^n / \M^{n+1} as a group under normal addition in the field K,
% with "isomorphism" here meaning group isomorphism.
\par  (b) Every torsion element of $F(\M)$ has order
a power of~$p$.
\end{lem}
\begin{proof}
\par  (a) For any~$x,y\in \M^n$, $x \oplus y =
x + y + \ldots \equiv x + y\ (\mod \M^{2n})$, and
so is $\equiv x + y\ (\mod \M^{n+1})$.
\par  (b) It is sufficient to show there does not
exist a point of finite order~$m$ for any $m>1$ with $p \nmid m$
(since any $w$ of order $m p^n$ gives $p^n w$ of order~$m$). 
But, since $\chari(k) = p$, and $p \nmid m$, we
have $|m| = 1$ and so $m\in R^*$.
By Lemma~\ref{lem:multmiso}, $[m]$ is an isomorphism from~$\M$
to~$\M$, which must then have trivial kernel:
$[m] z = 0 \implies z = 0$, as required.
\end{proof}
% N.B. Again, note that [m] is clearly convergent on \M, since
% [m] is defined over R (so that the terms go to 0).
\begin{thm}\label{thm:ptors}
Let~$F, K, R, \M, k$ (with $\chari(k) = p$)
be as in Defn~\ref{defn:fm}.
Suppose that~$z\in F(\M)$ has exact order~$p^n$, for some~$n\geqslant 1$,
so that $[p^n](z) = 0$, but $[p^{n-1}](z) \not= 0$.
Then: 
$$ | z | \geqslant | p |^{\frac{1}{p^n - p^{n-1}}}.$$
\end{thm}
\begin{proof} If $\chari(R) \not= 0$ then $|p| = 0$,
% N.B. No need to mention this, but note that, if char(R) \not= 0
% say char(R) = q (q prime, since R an integral domain), then we 
% deduce the above |p|=0 as follows:
% char(k) = char(R/\M) = p, so p is in \M, giving |p| < 1.
% Imagine char(R) = q \not= p, then (p,q) = 1 so p has an inverse
% lambda mod q, giving: 1 = p + ... + p (lambda times),
% and so: |1| \leqslant |p| < 1, a contradiction.
% Deduce (by reductio) that char(R) = p, so p=0, giving |p| = 0.
so assume that $\chari(R) = 0$. We have from 
Corollary~\ref{cor:multp} that $[p](T) = p f(T) + g(T^p)$
for some $f(T) = T + \ldots \in R\lb T\rb$ and $g(T) \in R\lb T\rb$.
We shall proceed by induction on~$n$.
\par Suppose $z\not= 0$, $z\in \M$
and $[p](z) = 0$.
Then $0 = p f(z) + g(z^p) = p(z + \ldots) + g(z^p)$. We cannot
have $|pz| > |z^p|$, since then the term $pz$ would have
valuation strictly greater than the valuations all other terms.
Hence $|pz| \leqslant |z^p| = |z|^p$, and so $|p| \leqslant |z|^{p-1}$,
giving $|z| \geqslant |p|^{ \frac{1}{p^1 - p^0} }$, proving
the result for~$n=1$.
\par Now, assume the result is true for~$n$, and let   
$z\in F(\M)$ have order~$p^{n+1}$. Then $[p](z)$ has
order~$p^n$, and by the induction hypothesis,
$| [p](z) | \geqslant | p |^{\frac{1}{p^n - p^{n-1}}}$. Hence:
$$ | p |^{\frac{1}{p^n - p^{n-1}}} \leqslant
| [p](z) | = | p f(z) + g(z^p) | \leqslant \max\bigl( |p z|, |z^p| \bigr).
$$
But $|z| < 1, |p| < 1$, so that $| p |^{\frac{1}{p^n - p^{n-1}}}
\geqslant |p| > |p z|$, giving $| p |^{\frac{1}{p^n - p^{n-1}}}
\leqslant |z^p|$, 
% N.B. The last inequality comes from combining:
% | p |^{\frac{1}{p^n - p^{n-1}}} \leqslant \max\bigl( |p z|, |z^p| \bigr)
% (from the previous displayed equation) and
% $| p |^{\frac{1}{p^n - p^{n-1}}} > |p z|$
% (from this same sentence).
and so 
$| z | \geqslant | p |^{\frac{1}{p^{n+1} - p^{n}}}$,
as required.
\end{proof}
\par
This has immediate consequences for elliptic curves.
\begin{cor}\label{cor:elltor}
Let~$\E : y^2 = x^3 + A x + B$, be an elliptic curve,
where~$A,B\in \bbbz_p$.
The kernel~$\E_1(\bbbq_p)$ of the
reduction map $\ttilde : \E_0(\bbbq_p) \rightarrow 
\TE_{ns}(\bbbf_p)$ has no torsion (apart from~$\o$).
Any $(x,y) \in \E_\tors(\bbbq_p)$ satisfies $|x|_p\leqslant 1,
|y|_p\leqslant 1$. When~$\TE$ is non-singular, $\ETQP$
is isomorphic to a subgroup of $\TE(\bbbf_p)$.
\end{cor}
\begin{proof} Let $\o \not= (x,y)\in \E(\bbbq_p)$ be in the kernel
of reduction, that is, $|x|_p, |y|_p > 1$.
Then, from the equation for~$\E$, $|y|_p = |x|_p^{3/2}$
and $|z| = |-x/y|_p = |x|_p^{-1/2} < 1, |w| = |-1/y|_p < 1$.
If~$(x,y)$ were torsion, then~$z$ would be a torsion
point in $F_\E(\M) = F_\E(p\bbbz_p)$. By Lemma~\ref{lem:torfm}(b)
it must be of order~$p^n$, and so  
by Theorem~\ref{thm:ptors} must satisfy
$1 > | z |_p \geqslant | p |_p^{\frac{1}{p^n - p^{n-1}}}$.
%[corresponding to
%$1 < | x |_p \leqslant | p |_p^{\frac{-2}{p^n - p^{n-1}}}$
%and $1 < | y |_p \leqslant | p |_p^{\frac{-3}{p^n - p^{n-1}}}$].
Note that, since~$|p|_p = p^{-1}$, any~$p^n$ apart from~$2^1$
(so that $p^n - p^{n-1} > 1$)
would force $1 > |z|_p > p^{-1}$, contradicting the fact
that $|z|_p$ is $p^r$ for some integer~$r$.
The only remaining possibility is that $(x,y)$ is
of order~$2$; but then $y=0$ and~$x$ is a root of~$x^3 + Ax + B$;
this is incompatible with $|x|_p > 1$ (which makes $x^3$ have
strictly larger valuation than $Ax$ and $B$).
We conclude that $x,y$ cannot be torsion, and that there
is no torsion (apart from~$\o$) in the kernel of reduction.
\par
When~$\TE$ is non-singular, $\E_0(\bbbq_p) = \E(\bbbq_p)$, $\TE_{ns}(\bbbf_p) = \TE(\bbbf_p)$, and the kernel of the
reduction map $\ttilde : \E(\bbbq_p) \rightarrow \TE(\bbbf_p)$
contains no nontrivial torsion. So it is injective
when restricted to~$\ETQP$; hence
$\ETQP$ is isomorphic to a subgroup of $\TE(\bbbf_p)$.
\end{proof} 
\medskip
\hrule
\newpage
\section{Global Torsion}\label{sec:torsion}
%% Injectivity of the reduction map, Nagell-Lutz. [1 lecture]
{\it Aside: We now turn to elliptic curves defined over~$\bbbq$,
initially concentrating on the group $\ETQ$ of points of
finite order. Any elliptic curve $\E : y^2 = x^3 + A x + B$,
defined over~$\bbbq$ can be transformed with a map
of the form $(x,y) \mapsto ( k^2 x, k^3 y )$ so that $A,B\in \bbbz$.
% N.B. I might just say the following sentence verbally:
The following result is a consequence over~$\bbbq$ of the $p$-adic
results of the last section.}
\begin{lem}\label{lem:inj}
Let~$\E : y^2 = x^3 + A x + B$,
where~$A,B\in \bbbz$, be an elliptic curve
(so that $\Delta = 4 A^3 + 27 B^2 \not= 0$).
Let~$p$ be a prime satisfying: $p\not= 2$ and $p\nmid \Delta$
(such a prime is said to be of {\it good reduction},
since $\TE$ mod~$p$ is still an elliptic curve over~$\bbbf_p$).
Then $\ETQ$ is isomorphic to a subgroup of~$\TE (\bbbf_p)$,
and so $\# \ETQ \ | \ \# \TE (\bbbf_p)$.
\end{lem}
\begin{proof} Since~$\bbbq \subset \bbbq_p$, for any~$p$,
$\EQ \leqslant \EQP$ and $\ETQ \leqslant \ETQP$.
Since~$p \nmid \Delta$ we have $\widetilde \Delta \not= 0$
in~$\bbbf_p$; since $\chari(\bbbf_p) \not= 2$, this
is enough to guarantee that $\TE$ is non-singular, and
so $\TE_{ns}(\bbbf_p) = \TE(\bbbf_p)$. By the last result
of the previous section (Corollary~\ref{cor:elltor}),
$\ETQP$ is isomorphic to a subgroup of $\TE(\bbbf_p)$,
as must also be~$\ETQ$ (since $\ETQ \leqslant \ETQP$).
Lagrange's Theorem then tells us that $\# \ETQ \ | \ \# \TE (\bbbf_p)$.  
\end{proof}
\par
Note that, in particular, the above result tells us
that $\ETQ$ is always finite. 
% N.B. I might mention verbally that this fact (that \ETQ is finite)
% was not at all obvious in advance; after all, it is possible in general
% for an Abelian group to have infinitely many points of finite order.
In practice, we can use
reductions modulo finite fields to try to determine $\ETQ$.
\begin{ex}\label{ex:torsff}
Let $\E : y^2 = x^3 + 3$, defined over~$\bbbq$.
Then $\Delta = 4 A^3 + 27 B^2 = 4\cdot 0^3 + 27\cdot 3^2 = 3^5$.
We can choose any prime $p\not= 2, p\nmid \Delta$, that is,
$p\not= 2,3$.
\par  $p=5$.\ \ $\TE : y^2 = x^3 + 3$, defined over~$\bbbf_5$.
% N.B. I might comment here: we can find all of $\TE(\bbbf_5)$,
% as you were doing on Problem Sheet 1.
Then $\TE(\bbbf_5)$ consists of: $\o, (1,\pm 2), (2,\pm 1),
(3,0)$, giving~$6$ points. So $\# \ETQ \ | \ \# \TE(\bbbf_5)$,
that is: $\# \ETQ \ | \ 6$.
\par  $p=7$.\ \ $\TE : y^2 = x^3 + 3$, defined over~$\bbbf_7$.
Then $\TE(\bbbf_7)$ consists of: 
\par  $\o, (1,\pm 2), (2, \pm 2),
(3, \pm 3), (4, \pm 2), (5, \pm 3), (6, \pm 3)$, giving~$13$ points.
So $\# \ETQ \ | \ 13$.
\par The only possibility is: $\# \ETQ = 1$, and so
$\ETQ = \{ \o \}$. Note that $(1,2)\in \EQ$, but we know that~$(1,2)$
is not of finite order, so that $(1,2), 2(1,2), 3(1,2), \ldots$
are all distinct, and can conclude that $\EQ$ is infinite.
\par Note that, if we are given (for example)
$\F : y^2 = x^3 + \frac{3}{5^6}$, we can apply $(x,y) \mapsto 
(5^2 x, 5^3 y)$
[with inverse $(x,y) \mapsto (\frac{x}{5^2}, \frac{y}{5^3})$]
to transform~$\F$ to~$\E$ and so deduce that~${\F_\mathrm{tors}(\bbbq)}
= \{ \o \}$ also.
\end{ex}
{\it Aside: Another consequence of the $p$-adic results of the last
section is the integrality of the coordinates of
any torsion point.}
\begin{lem}\label{lem:torsint}
Let~$(x_1,y_1)\not=\o$ be a $\Q$-rational torsion point
on $\E : y^2 = x^3 + Ax + B$, where $A,B\in \Z$. Then
$x_1,y_1\in\Z$.
\end{lem}
\begin{proof} For any prime~$p$, we have~$A,B\in \bbbz \subset \bbbz_p$.
Furthermore, $(x_1,y_1)\in \ETQ \subset \ETQP$.
By the last result of the previous section (Corollary~\ref{cor:elltor}) 
we know that $|x_1|_p\leqslant 1, |y_1|_p\leqslant 1$.
In summary: $x_1,y_1\in \bbbq$ and $x_1,y_1\in \bbbz_p$ for all primes~$p$.
\par Imagine that $x_1\not\in \bbbz$, that is, $x_1 = \frac{m}{n}$,
where $m,n\in \bbbz$, $\gcd(m,n) = 1$, $n\not= \pm 1$.
Then some prime~$p$ must divide~$n$ (and not divide~$m$),
giving $| x_1 |_p = | \frac{m}{n} |_p = p^r$ (for some~$r>0$),
which is~$ > 1$. This contradicts~$x\in \bbbz_p$, 
and so we conclude that~$x_1\in \bbbz$. 
% N.B. I might mention verbally that this last part repeats the question on 
% Problem Sheet 2, showing that if x is in Q, 
% then x is in Z iff x is in Z_p for all p.
Similarly $y_1\in \bbbz$.
\end{proof}
\par
For example, this tells us immediately that the point
$(\frac{1}{4}, \frac{7}{8})$ is of infinite order
on the elliptic curve~$\E : y^2 = x^3 - x + 1$,
\par 
{\it Aside: Reduction to finite fields usually works well enough
in practice, but there is the potential problem that
it might leave us with~$\ETQ$ undetermined. For example,
suppose that, after trying several primes, we repeatedly
find that $3\ | \ \# \TE(\bbbf_p)$, but a search has
not found a point of order~$3$. In that case, the
group $\ETQ$ would be unresolved. It would be nice
to have a finite search area within which the members
of $\ETQ$ must lie. This is provided by the following result.} 
% N.B. I might embellish the above aside, by mentioning
% that in the above case, you might keep trying new primes
% and searching, until you eventually go completely nuts
% (or at least mildly exasperated).
\begin{thm}\label{thm:nagelllutz} (Nagell-Lutz).
Let~$\o \not= (x_1,y_1)\in \ETQ$, where 
$\E : y^2 = x^3 + Ax + B$, and $A,B\in \Z$. Then
$x_1,y_1\in\Z$ and either $y_1 = 0$ 
or $y_1^2 \ | \ \Delta$, where $\Delta = 4A^3 + 27B^2$. 
\end{thm}
\begin{proof} From the last lemma,
$x_1,y_1\in \Z$. If $y_1 = 0$ then the result is satisfied; otherwise,
$(x_1,y_1)$ is not $2$-torsion and we can consider $(x_2,y_2) = 2(x_1,y_1)$,
with $(x_2,y_2) \not= \o$, and so $x_2,y_2\in \Q$. But~$(x_2,y_2)$
is also a torsion point, so $x_2 , y_2 \in \Z$. The line
tangent to~$\E$ at~$(x_1,y_1)$ has slope $\lambda = (3x_1^2+A)/(2y_1)$; 
as usual, substituting $y = \lambda x + \mu$ into~$\E$ 
gives $(\lambda x + \mu)^2 = x^3 + Ax + B$ and so
$x^3 - \lambda^2 x^2 + \ldots = 0$, giving
$x_1 + x_1 + x_2 = -(\hbox{coeff of }x^2)/(\hbox{coeff of }x^3) = \lambda^2$,
that is:
$$ x_2 = \Bigl( \frac{3x_1^2+A}{2y_1} \Bigr)^2 - 2x_1 \in \bbbz.$$
Now, we know $x_1, x_2\in \Z$ and so
$\bigl( \frac{3x_1^2+A}{2y_1} \bigr)^2\in \Z$.
It follows that $4y_1^2 \ | \ (3x_1^2+A)^2$ and 
so $y_1^2 \ | \ (3x_1^2+A)^2$.
Also, $y_1^2 = x_1^3 + Ax_1 + B$
and so trivially $y_1^2\ |\ (x_1^3 + Ax_1 + B)$.
Applying Euclid's Algorithm
to $(3x^2+A)^2$ and $x^3 + Ax + B$ gives the identity
$$\phi_1(x) \psi_1(x) + \phi_2(x) \psi_2(x) = 4A^3 + 27B^2,$$
where $\phi_1(x)= 3x^2+4A$,\ \ $\psi_1(x) = (3x^2+A)^2$,\ \
$\phi_2(x)= -27(x^3 + Ax - B)$,\ \ $\psi_2(x) = x^3 + Ax + B$.
% N.B. I might mention here that it should not be a 
% surprise, given $\psi_1(x) = (3x^2 + A)^2$
% and $\psi_2(x) = x^3 + Ax + B$, that such $\phi_1,\phi_2$ exist, since
% $Res(\psi_1,\psi_2) = 0$ iff $\psi_1 = (\psi_2')^2, \psi_2$ 
% have a common factor iff $\psi_2', \psi_2$ have a common factor
% iff $\Delta = 0$, and so we expect $Res(\psi_1,\psi_2) = \Delta$
% (or some power of Delta). And we can always write the resultant
% of two polynomials $\psi_1,\psi_2$ as a polynomial linear combination
% of $\psi_1,\psi_2$ by Euclid's Algorithm for polynomials (see the
% section on resultants in the preliminary reading).
Since $y_1^2\ |\ \psi_1(x_1)$ and $y_1^2\ |\ \psi_2(x_1)$ we must have 
$y_1^2 \ | \ (\phi_1(x_1)\psi_1(x_1) + \phi_2(x_1)\psi_2(x_1))
= \Delta$, as required.
\end{proof}
% N.B. I might mention here that this result is somewhat
% tarnished in my eyes, as I wasted the first few months of my DPhil
% in a futile attempt at generalising Nagell-Lutz to Jacobians of 
% higher genus curves, but I guess I shouldn'y hold that against
% it; it's still a nice result.
\begin{ex}\label{ex:nagellutz}
Let~$\E : y^2 = x^3 + 3 x + 1$.
Then $\Delta = 4\cdot 3^3 + 27\cdot 1^2 = 135 = 5\cdot 3^3$.
If~$(x,y)\in \ETQ$, $(x,y)\not= \o$, then~$x,y\in\bbbz$
and either~$y=0$ or~$y^2\ | \ 5\cdot 3^3$, giving only
$y = 0,\pm 1,\pm 3$ as possibilities.
\par  {\it Case $y = \pm 1$.} 
From~$\E$, $(\pm 1)^2 = x^3 + 3x + 1$ and so $x(x^2 + 3) = 0$.
The only solution in~$\bbbz$ is~$x=0$, giving~$(0,\pm 1)$
as the only possibilities.
\par  {\it Case $y = \pm 3$.} 
In this case, $x\in\bbbz$ satisfies $(\pm 3)^2 = x^3 + 3x + 1$ and
so $x^3 + 3 x - 8 = 0$. Let $f(x) = x^3 + 3 x - 8$.
Any integer root~$x$ of~$f(x)$
must satisfy $x | (\hbox{constant term}) = (-8)$,
giving $x = \pm 1, \pm 2, \pm 4, \pm 8$ as the only possibilities.
When we substitute these, we find that $f(1),f(-1),\ldots,f(-8)$
are all nonzero, so there are no points
on~$\E$ with $x\in\bbbz$ and $y = \pm 3$.
\par  {\it Case $y = 0$.}
In this case, $x\in\bbbz$ satisfies $0 = x^3 + 3 x + 1$,
and we only need to check $x = \pm 1$. neither of which
are roots of~$x^3 + 3 x + 1$. So, there are no points on~$\E$
with $x\in\bbbz$ and $y=0$.
\par In summary, $\o,(0,1),(0,-1)$ are the only possible
torsion points. Is $(0,1)\in\ETQ$? If it were then
so would be $2(0,1)$. But $2(0,1) = (0,1) + (0,1) = 
(\frac{9}{4}, -\frac{35}{8})$; the coordinates are not in~$\bbbz$
and so this is not a torsion point. Hence~$(0,1)$ must
have infinite order. The same must be true for~$(0,-1)$,
since it is the inverse of~$(0,1)$. Conclusion: $\ETQ = \{ \o \}$.
\end{ex}
% N.B. I might abbreviate the details in the above example.
The previous method of reductions modulo finite fields is
usually quicker in practice, but the Nagell-Lutz method
is an effective procedure.
% N.B. I might mention that usually best is a mixed strategy.
% First start with noting obvious torsion points and finite
% field reductions. If the number of known torsion points matches
% the bound, then you're in torsion-finding paradise and you're done.
% Otherwise, you can always resort to the mild purgatory of
% a Nagell-Lutz enumeration, which is guaranteed to work.
\begin{comm}\label{comm:torsgenform}
It was merely to ease the algebra in previous sections
that we used only the form $y^2 = x^3 + A x+ B$,
and all of the previous arguments apply equally well
to any elliptic curve $\E : y^2 = x^3 + a x^2 + b x + c$,
where~$a,b,c\in \bbbz$, with~$\Delta$ now taken to be the discriminant
of $x^3 + a x^2 + b x + c$, which has the formula: 
$$ \Delta = 4 a^3 c + 27 c^2 + 4 b^3 - a^2 b^2 - 18 a b c. $$
So, it remains true that, for any prime~$p \nmid 2\Delta$,
$\ETQ$ is isomorphic to a subgroup of~$\TE(\bbbf_p)$,
that $\# \ETQ \ | \ \# \TE(\bbbf_p)$, and
that any $(x,y) \in \ETQ$ ($(x,y)\not= \o$) satisfies
$x,y\in\bbbz$, with~$y=0$ or $y^2\ | \ \Delta$.
\end{comm}
\medskip
\hrule
\newpage
\section{A $2$-isogeny on an Elliptic Curve}\label{sec:2isog}
%% Basic properties of 2-isogenies, including the 
%% $q$ map. [4 lectures] 
(In the following, we shall use upper case letters $X,Y,\ldots$
for variables, and lower case letters $x,y,\ldots$ for 
a point $(x,y)$.)
\par
Suppose that~$\E$ is an elliptic curve over~$\bbbq$, together
with a $\bbbq$-rational point of order~$2$: $(x_0,0)$.
After a birational transformation $(x,y) \mapsto (x-x_0,y)$
(inverse $(x,y) \mapsto (x+x_0,y)$) we can assume that
$(0,0)\in\EQ$, so that $Y^2 = \hbox{cubic in }X$, with no
constant term. As usual,  after mappings of the form
$(x,y) \mapsto (k^2 x, k^3 y)$, we can assume that the
coefficients are in~$\bbbz$. So, our elliptic curve can be taken
to have the form
$$ \C : Y^2 = X(X^2 + a X + b), \ \ a,b\in \bbbz,\ b(a^2 - 4b)\not= 0,$$
the last condition ensuring that the curve is non-singular.
The point~$(0,0)$ is of order~$2$ on~$\C$.
\par
Let $P = (x,y)$ be a point on~$\C$, and let 
$P_1 = (x,y) + (0,0) = (x_1, y_1)$.
Define $T_{(0,0)}$ by:
$$ T_{(0,0)} : \C \rightarrow \C : (x,y) \mapsto (x,y) + (0,0) = (x_1,y_1).
$$
That is, $P \mapsto P + (0,0)$. What are $x_1,y_1$ in terms
of $x,y$?
% Sometime about here, before the formulas for $x_1,y_1$,
% I might mention that this first part is essentially just repeating 
% the question on Problem Sheet 1, describing addition by a
% points of order 2.
\par
When $(x,y) = (0,0)$, then $T_{(0,0)} : (0,0) \mapsto \o$,
since $(0,0)$ is of order~$2$.
When $x\not= 0$, we first find the line through $(0,0)$ and
$(x,y)$, which is: $Y = \frac{y}{x} X$. Substituting this
into~$\C$ gives:
\begin{align*}
\Bigl( \frac{y}{x} \Bigr)^2 X^2 &= X(X^2 + a X + b)\\
y^2 X^2 &= x^2 X^3 + a x^2 X^2 + b x^2 X\\
x(x^2 + a x + b) X^2 &= x^2 X^3 + a x^2 X^2 + b x^2 X
\hbox{ [since $(x,y)$ is on $\C$]}\\
0 &= x X^3 - (x^2 + b) X^2 + b x X,
\hbox{ [since $x\not= 0$]}
\end{align*}
and so $X(X - x)(x X - b) = 0$. The roots of this cubic are:
$X = 0, X = x, X = b/x$. 
The line $Y = \frac{y}{x} X$ and~$\C$ intersect at:
$$ (0,0), (x,y)\hbox{ and } \Bigl( \frac{b}{x}, \frac{by}{x^2} \Bigr)
\hbox{ (since $X = \frac{b}{x}$ gives 
$Y = \frac{y}{x}\frac{b}{x} = \frac{by}{x^2}$)}
$$
and so $(x,y) + (0,0) = \Bigl( \frac{b}{x}, -\frac{by}{x^2} \Bigr) 
= (x_1, y_1)$, where $x_1 = \frac{b}{x},\ y_1 = -\frac{by}{x^2}$.
\par We want to construct a $2$-to-$1$
map~$\phi$ from~$\C$ to another
curve~$\D$ such that $\phi\bigl( P + (0,0) \bigr) = \phi(P)$
for any~$P$. 
%We want expressions in $x,y$ which are invariant
%under~$T_{(0,0)}$, call them $\lambda (x,y),\ \mu(x,y)$.
We want expressions in $x,y$, call them $\lambda (x,y),\ \mu(x,y)$, such 
that $P = (x,y)$ and $P+(0,0)=(x_1,y_1)$ map to the same $(\lambda,\mu)$.
Natural attempts are: $x + x_1 = x + \frac{b}{x}$ and
$y + y_1 = y - \frac{by}{x^2}$. It turns out to be more convenient
to choose $x + x_1 + a$ instead of $x + x_1$.
$$
\hbox{Define: } \lambda = x + x_1 + a = x + \frac{b}{x} + a
= \frac{x(x^2 + a x + b)}{x^2} 
= \frac{y^2}{x^2} = \Bigl( \frac{y}{x}\Bigr)^2.
$$
$$
\hbox{Define: } \mu = y + y_1 = y - \frac{by}{x^2}.
$$
Both $\lambda, \mu$ are invariant under $T_{(0,0)}$.
We have a map from~$\C$, given by $(x,y) \mapsto
(\lambda, \mu) =
\Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{by}{x^2} \Bigr)$,
which we shall call~$\phi$.
We want to find the new curve~$\D$ which this map is to,
that is, we want the equation satisfied by~$\lambda$ and~$\mu$. Try:
$$
\mu^2 = \Bigl(  y - \frac{by}{x^2} \Bigr)^2
= \Bigl( \frac{y}{x}\bigl( x - \frac{b}{x} \bigr) \Bigr)^2
= \Bigl( \frac{y}{x} \Bigr)^2 \Bigl( x - \frac{b}{x} \Bigr)^2
= \lambda \Bigl( x^2 - 2b + \frac{b^2}{x^2} \bigr)
$$
$$
= \lambda \Bigl(  x^2 + 2b + \frac{b^2}{x^2} - 4b \bigr)
=  \lambda \Bigl( \bigl( x + \frac{b}{x} \bigr)^2 - 4b \Bigr)
= \lambda \Bigl( (\lambda - a)^2 - 4b \Bigr)
=  \lambda ( \lambda^2 - 2a\lambda + a^2 - 4b ).
$$
So $(\lambda, \mu)$ is a point on the
curve $\D : V^2 = U(U^2 + a_1 U + b_1)$,
where $a_1 = -2a$ and $b_1 = a^2 - 4b$.
Our map~$\phi$ is a rational map (but not a birational
transformation, since it is $2$-to-$1$). It is easy to
check that it is a homomorphism, with kernel
$\{ \o, (0,0) \}$; such a map~$\phi$ is a {\it $2$-isogeny}
on~$\C$.
\par
We can apply the same process to~$\D$, taking
$(u,v) \mapsto \Bigl( \bigl( \frac{v}{u} \bigr)^2, 
v - \frac{b_1 v}{u^2} \Bigr)$ from~$\D$ to the curve
$Y^2 = X(X^2 - 2a_1 X + a_1^2 - 4 b_1)$,
which is the same as $Y^2 = X(X^2 + 4a X + 16 b)$
(since $-2(-2a) = 4a$ and $a_1^2 - 4b_1 = (-2a)^2 - 4(a^2 - 4b) = 16b$),
that is:
$$ \frac{Y^2}{64} = \frac{X}{4}\Bigl( \frac{X^2}{16}
+ \frac{4aX}{16} + \frac{16 b}{16} \Bigr)
= \frac{X}{4} \Bigl( \frac{X^2}{16}
+ \frac{aX}{4} + b \Bigr),
$$
and so $\Bigl( \frac{Y}{8} \Bigr)^2
= \frac{X}{4} \Bigl( \bigl( \frac{X}{4} \bigr)^2 + a \bigl( \frac{X}{4} \bigr)
+ b \Bigr)$. So, the map $\hp : (u,v) \mapsto
\Bigl( \frac{1}{4} \bigl( \frac{v}{u} \bigr)^2,
\frac{1}{8} \bigl( v - \frac{b_1 v}{u^2}\bigr) \Bigr)$
is a map from~$\D$ back to~$\C$ (the {\it dual isogeny}).
The properties are the same as for~$\phi$, namely:
$\hp$ is a homomorphism with kernel~$\{ \o, (0,0) \}$.
\par 
Note also that, if we let $\alpha_1 = \frac{-a + \sqrt{a^2 - 4b}}{2},
\ \alpha_2 = \frac{-a - \sqrt{a^2 - 4b}}{2}$ denote the roots
of $X^2 + aX + b$, then $\phi \bigl( (\alpha_1, 0) \bigr)
= \phi \bigl( (\alpha_2, 0) \bigr) = (0,0)$, and
so the kernel of~$\hp \circ \phi$ consists precisely
of the $2$-torsion of~$\C$, namely:
$\{ \o, (0,0), (\alpha_1, 0), (\alpha_2, 0)\}$.
Indeed, it is easy to show that $\hp \circ \phi$ is
the multiplication by~$2$ map on~$\C$. We summarise as follows.
\begin{lem}\label{lem:phi}
Let $\C : Y^2 = X(X^2 + aX + b)$, where $a,b\in\bbbz, b \not= 0,
a^2 - 4b \not= 0$, and let $\D : V^2 = U(U^2 + a_1 U + b_1)$,
where $a_1 = -2a$ and $b_1 = a^2 - 4b$.
\begin{align*} 
&\hbox{Define }\ \phi : \C \longrightarrow \D \ \hbox{ by }\
\phi(x,y) = 
\Bigl( \Bigl( \frac{y}{x} \Bigr)^2, y - \frac{by}{x^2} \Bigr).\\
&\hbox{Define }\ \hp : \D \longrightarrow \C \ \hbox{ by }\
\hp(u,v) = 
\Bigl( \frac{1}{4} \Bigl( \frac{v}{u} \Bigr)^2,
\frac{1}{8} \Bigl( v - \frac{b_1 v}{u^2}\Bigr) \Bigr).\\
\end{align*}
Then the $2$-isogenies $\phi, \hp$ are $2$-to-$1$ homomorphisms, each with
kernel $\{ \o , (0,0) \}$. Since $\phi, \hp$ are defined over~$\bbbq$,
we also have $\phi : \CQ \rightarrow \DQ$ and $\hp : \DQ \rightarrow \CQ$.
The compositions $\hp \circ \phi$ and $\phi \circ \hp$ are
the multiplication by~$2$ maps $[2]$ on $\C$ and $\D$, respectively.
\end{lem}
We shall concentrate for the moment on~$\phi : \C \rightarrow \D$.
Note that we can formally invert $(u,v) = \phi(x,y)
= \Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{by}{x^2} \Bigr)$,
as follows.
Since $u = \bigl( \frac{y}{x} \bigr)^2$, we have
$\frac{y}{x} = \pm u^{1/2}$. For the moment, say
$\frac{y}{x} = u^{1/2}$.
We also have
\begin{align*}
u^{-1/2} v &= \frac{x}{y}\Bigl( y - \frac{by}{x^2} \Bigr)
= x - \frac{b}{x},\\
u &= \bigl( \frac{y}{x} \bigr)^2 = \frac{y^2}{x^2}
= \frac{x(x^2 + a x + b)}{x^2} = x + a + \frac{b}{x},
\end{align*}
and so: $u^{-1/2} v + u = 2 x + a$.
Solving for $x,y$ then gives the following preimages.
\begin{lem}\label{lem:preimages}
Let $\C,\D,\phi$ be as in Lemma~\ref{lem:phi},
and let $(u,v)$ be a point on~$\D$ with $u\not= 0$.
Let
\begin{align*}
x_1 &= \bigl( u + u^{-1/2} v - a \bigr)/2,\ \
y_1 = u^{1/2} x_1 = u^{1/2}\bigl( u + u^{-1/2} v - a \bigr)/2,\\
x_2 &= \bigl( u - u^{-1/2} v - a \bigr)/2,\ \
y_2 = - u^{1/2} x_2 = - u^{1/2}\bigl( u - u^{-1/2} v - a \bigr)/2.
\end{align*}
Then $\phi(x_1,y_1) = \phi(x_2,y_2) = (u,v)$.
\end{lem}
We shall shortly make use of these to define helpful maps
on $\CQ$ and $\DQ$. First, we recall the notation $\Q^*$
%and $\qmsq$ [see also Example~\ref{exs:quotients}(b)].
and $\qmsq$ (see also Example~0.30(b)).
\begin{def}\label{def:qmsq}
As usual, let $\Q^*$ denote the group of nonzero members
of~$\Q$ under multiplication, so that $\qmsq$ is
$\Q^*$ modulo squares.
\end{def}
For example, $\frac{12}{49} = 3$ in $\qmsq$
since $\frac{12}{49} = 3\frac{4}{49} = 3\bigl( \frac{2}{7} \bigr)^2
= 3$ in~$\qmsq$. Note that any member of $\qmsq$ can be written
uniquely as a square free integer (that is, as an integer not divisible
by any square except~$1$).
\par {\it Aside: Our main aim here is to show the Weak Mordell-Weil
Theorem, that $\CQ/2\CQ$ is finite, which we shall achieve by showing
that $\DQ/\phi(\CQ)$ and $\CQ/\hp(\DQ)$ are finite, and then
using the fact that $\hp \circ \phi = [2]$.}
\par From now on, we denote $\CQ$ by $\G$ and $\DQ$ by $\HH$
(both groups under addition~$+$ given by the group law
on elliptic curves, with identity~$\o$).
\begin{lem}\label{lem:phiG}
Let $(u,v)\in \HH$. Then:
$$ (u,v) \in \phi(\G) \iff u \in \qsq \hbox{ or }
(u = 0 \hbox{ and } a^2 - 4b \in \qsq).
$$
\end{lem}
\begin{proof}
{\bf Case 1}\ $u \not= 0$.
From the expressions in Lemma~\ref{lem:preimages}
for $(x_1,y_1),(x_1,y_1)$ such that $\phi(x_1,y_1)
= \phi(x_2,y_2) = (u,v)$, which are in terms of~$u,v,u^{1/2}$,
we see that:
\[(u,v) \in \phi(\G) \iff u^{1/2} \in \Q
\iff u \in \qsq.\]
\par  {\bf Case 2}\ $u = 0$.
The expressions in Lemma~\ref{lem:preimages}
do not apply here, since they include $u^{-1/2}$. But
we know that $\phi(\alpha_1,0) = \phi(\alpha_2,0) = (0,0)$,
where \[\alpha_1 = \frac{-a + \sqrt{a^2 - 4b}}{2},
 \alpha_2 = \frac{-a - \sqrt{a^2 - 4b}}{2}\] denote the roots
of $X^2 + aX + b$. Hence:
\[(0,0) \in \phi( \G ) \iff \alpha_1\hbox{ or }\alpha_2 \in \Q
\iff a^2 - 4b \in \qsq\] as required.
\end{proof}
\par
This suggests the following map on~$\HH$.
\begin{defn}\label{defn:qmap}
Define the map~$q : \HH \rightarrow \qmsq$ by:
\[q(u,v) = \begin{cases} u & \hbox{ when $u\not= 0$} \\
b_1 = a^2 - 4b & \hbox{ when $u=0$.}\end{cases}\]

We also define $q(\o) = 1$.
\end{defn}
Note that we can equivalently define
$q(u,v)$ to be~$d$ such that the preimages of~$(u,v)$
under~$\phi$ are defined over~$\Q(\sqrt{d})$.
% N.B. I might mention verbally that this last sentence
% gives a more unified definition of the q map.
\begin{lem}\label{lem:qhom}
The map $q : \HH \rightarrow \qmsq$ of Definition~\ref{defn:qmap}
is a homomorphism with kernel~$\phi(\G)$
(so that the induced map $q : \HH/\phi(\G) \rightarrow \qmsq$ is an
injective homomorphism).
\end{lem}
\begin{proof}
We only
show that $q(P+Q) = q(P)q(Q)$ in the typical case when none
of $P,Q,P+Q$ are $(0,0)$ or {\bf o}.

Let~$(u_1,v_1),
(u_2,v_2),(u_3,v_3)$ be~3 points on~$\HH = \D(\Q)$ which sum to~$\o$,
(so that $(u_1,v_1) + 
(u_2,v_2)= (u_3,-v_3)$).
Then these are the~3 points of intersection between~$\D$
and some line defined over~$\Q$: 
$V = \ell U + m$, say. 

Substituting~$V = \ell U + m$
into $\D$ gives: $U(U^2 + a_1 U + b_1) - (\ell U + m)^2$,
whose 3~roots must be~$u_1,u_2,u_3$.  
So \[U(U^2 + a_1 U + b_1) - (\ell U + m)^2
= (U-u_1)(U-u_2)(U-u_3).\] Equating constant terms gives:
$u_1 u_2 u_3 = m^2 = 1$ in $\qmsq$, and so $u_1 u_2 = 1/u_3 = u_3$
in $\qmsq$. (Note $u_1 u_2 u_3 \ne 0$, by our assumption.)

Therefore, by the definition of~$q$ we have:
\[q\bigl( (u_1,v_1) \bigr) q\bigl( (u_2,v_2) \bigr)
= q\bigl( (u_3,-v_3) \bigr)= q\bigl( (u_1,v_1) + (u_2,v_2) \bigr),\]
so that~$q$ is a homomorphism.
\par 
The fact that $\kker q = \phi(\G)$ is an immediate consequence
of Lemma~\ref{lem:phiG}.
\end{proof}
\begin{lem}\label{lem:imqfinite}
The map $q : \HH \rightarrow \qmsq$ of Definition~\ref{defn:qmap}
has finite image. Moreover, if $r\in \qmsq$ is written
as a square free integer, then $r\in \im q \implies r | b_1$.


Under~$q$, $\HH/\phi(\G)$ is isomorphic to the
subgroup of $\qmsq$ consisting of all square free integers~$r|b_1$
such that there is are solutions $\ell, m, n \in \Z$, not all $0$, with $\gcd(\ell,m) = 1$ to the equation:
$$
W_r : r \ell^4 + a_1 \ell^2 m^2 + (b_1/r) m^4 = n^2.
$$

When this is satisfied, there is a point $(u,v) \in \HH$
such that $q(u,v) = r$, satisfying $u = r \bigl( \frac{\ell}{m} \bigr)^2$.
\end{lem}
\begin{proof}
Let $r \in \qmsq, r \in \hbox{im}\, q,
r \in \Z, r$ square free. We want to prove that $r | b_1$.
Suppose $r = q(u,v)$, where $(u,v)\in \D (\Q)$, which must
exist since $r \in \hbox{im}\, q$. Then: $r = q(u,v) = u = u^2 + a_1 u + b_1$
in $\qmsq$ (since $u(u^2 + a_1 u + b_1) = v^2$). 
So, $r, u, u^2 + a_1 u + b_1$ are all the same modulo squares,
which means we can write:
$$ u^2 + a_1 u + b_1 = rs^2 \hbox{ and } u = rt^2 \hbox{ for some } s,t \in \Q.
$$
Hence: $ (rt^2)^2 + a_1 (rt^2) + b_1 = rs^2$. Let $t = \ell/m$,
where $\ell, m \in \Z$ and gcd$(\ell,m) = 1$.
Then: $ r^2 \ell^4 / m^4 + a_1 r \ell^2 / m^2 + b_1 = rs^2$,
and so: $ r^2 \ell^4 + a_1 r \ell^2 m^2 + b_1 m^4 = r(m^2s)^2$.
Now, $a_1, b_1, r,\ell, m \in \Z$, so the LHS of this last equation
is in~$\Z$, and so the RHS is also in~$\Z$; that is: $r(m^2s)^2\in \Z$.
Since $r$ is square free, we must therefore have $m^2 s \in \Z$.
Define: $n = m^2 s \in \Z$. Then our equation becomes:
$$
r^2 \ell^4 + a_1 r \ell^2 m^2 + b_1 m^4 = r n^2, \hbox{ for some } \ell, m, n \in \Z \hbox{ with } \gcd(\ell,m) = 1
\eqno (*)
$$
(from which we have $W_r$ in the statement of the lemma,
after dividing both side by~$r$).
% N.B. I might mention verbally that, at this stage, we already
% have that r satisfies W_r and u = r(\ell/m)^2, and it only
% remains to show that r | b_1.
We want to show that $r | b_1$, and we know that $r$ is square free.
It is sufficient to show, for any prime~$p$, that $p | r \Rightarrow p | b_1$.

Suppose, for a contradiction, that $p | r$ and $p \nmid b_1$, for some prime~$p$.
Then \[p | r^2 \ell^4, a_1 r \ell^2 m^2,\text{ and } r n^2\] and so by $(*)$,
$p | b_1 m^4$, which in turn gives: $p | m$ (since $p \nmid b_1$).
% N.B. "Imagine $p | r$ and $p \nmid b_1$ ... a contradiction, ..."
% I might mention verbally that, like one of the questions on a recent
% problem sheet, each term has its moment of glory as the centre
% of attention. Later on in the proof ... it does come to an end eventually.
Hence, since now $p | r$ and $p | m$, we have: 
$p^2 | r^2 \ell^4, a_1 r \ell^2 m^2,
b_1 m^4$, and so by $(*)$, $p^2 | r n^2$, which in turn
gives: $p | n$ (since~$r$ is square free). Hence, since now  
$p | r,m,n$, we have: $p^3 | a_1 r \ell^2 m^2, b_1 m^4, r n^2$,
and so by $(*)$, $p^3 | r^2 \ell^4$, which in turn
gives: $p | \ell$ (since~$r$ is square free). This is a contradiction,
since $p | \ell$ and $p | m$ but $\gcd(\ell,m) = 1$. We deduce that $p | r \Rightarrow p | b_1$ for
any prime~$p$, so $r | b_1$ as desired.

We finally note that if~$r$ satisfies $W_r$, then
$\bigl( r (\ell/m)^2 \bigr)^2 + a_1 r (\ell/m)^2 + b_1 = r (n/m^2)^2$,
so \[r(\ell/m)^2
\bigl( \bigl( r (\ell/m)^2 \bigr)^2 + a_1 r (\ell/m)^2 + b_1 \bigr)
= (r\ell n/m^3)^2.\] This tells us that 
$(u,v) = ( r(\ell/m)^2, r\ell n/m^3 )$ is in $\HH$; we have $q(u,v) = r$, which gives $r \in \im q$.
\end{proof}
\begin{comm}\label{comm:imhqfinite}
If we similarly define $\hq : \G \rightarrow \qmsq$ by:

\[\hq(x,y) = \begin{cases} x & \hbox{ when $x\not= 0$} \\
b = a_1^2 - 4b_1 & \hbox{ when $x=0$,}\end{cases}\]
and $\hq(\o) = 1$, then, by the same argument, $\hq$ has finite image. 
If $r\in \qmsq$ is written
as a square free integer, then $r\in \im \hq \implies r | b$.
Under~$\hq$, $\G/\hp(\HH)$ is isomorphic to the
subgroup of $\qmsq$ consisting of all square free integers~$r|b$
such that
$$
{\widehat W}_r : r \ell^4 + a \ell^2 m^2 + (b/r) m^4 = n^2, \hbox{ for some } \ell, m, n \in \Z, 
\hbox{ not all $0$, with }\gcd(\ell,m) = 1.
$$
When ${\widehat W}_r$ is satisfied, there is a point $(x,y) \in \G$
such that $q(x,y) = r$, satisfying $x = r \bigl( \frac{\ell}{m} \bigr)^2$.
\end{comm}
% N.B. The following sentence could just be said verbally:
Since $\HH/\phi(\G)$ and $\G/\hp(\HH)$ have been shown to
be isomorphic to finite groups, we can immediately deduce
one of our main goals.
\begin{thm}\label{thm:HphiGfinite}
Both $\G/\hp(\HH)$ and $\HH/\phi(\G)$ are finite.
\end{thm}
% N.B. I might mention verbally that the above theorem follows immediately 
% from Lemma\ref{lem:qhom}[6.5], that q : \HH/\phi(\G) \rightarrow \qmsq
% and Lemma\ref{lem:imqfinite}[6.6], that the same map has
% finite image, giving that \HH/\phi(\G) is finite, and
% similarly for \G/\hp(\HH).
\begin{cor}\label{cor:weakmw}
(The Weak Mordell-Weil Theorem, for an elliptic curve
$\C$ which has a rational point of order~$2$).
$\G/2\G = \CQ/2\CQ$ is finite.
\end{cor}
\begin{proof} We know from Theorem~\ref{thm:HphiGfinite}
that $\G/\hp(\HH)$ and $\HH/\phi(\G)$
are finite, so let $\G/\hp(\HH) = \{ g_1, \ldots , g_k\}$
and $\HH/\phi(\G) = \{ h_1,\ldots ,h_\ell\}$.
Let $g\in \G$. We can write~$g$ as:
\begin{align*}
g &= g_i + \hp(h), \hbox{ for some } g_i \in \{ g_1,\ldots ,g_k\},\ h\in \HH\\
  &= g_i + \hp\bigl( h_j + \phi(g')\bigr),
     \hbox{ for some } h_j \in \{ h_1,\ldots ,h_\ell\},\ g'\in \G\\
  &= g_i + \hp(h_j) + \hp(\phi(g'))\ \
     (\hbox{since $\hp$ is a homomorphism})\\
  &= g_i + \hp(h_j) + 2g'\ \ (\hbox{since } \hp \circ \phi = [2])\\
  &= g_i + \hp(h_j)\ \ \hbox{ in } \G/2\G.
\end{align*}
Hence $\G/2\G$ is a subset of 
$\{ g_i + \hp(h_j) : 
1 \leqslant i \leqslant k,\ 1 \leqslant j \leqslant \ell \}$,
which is finite, and so $\G/2\G$ is finite.
\end{proof}
\par
The above proves the Weak Mordell-Weil Theorem,
that $\CQ/2\CQ$ is finite, for
the case when $\C : Y^2 = X(X^2 + aX + b)$ has a $\Q$-rational
point of order~$2$. In fact, the same result can be proved for
any elliptic curve~$\E : Y^2 = F(X)$, regardless of whether it has
a $\Q$-rational point of order~$2$ (see Chapter VIII of \cite{sil:AEC1}),
giving:
\begin{thm}\label{thm:weakmw} (The Weak Mordell-Weil Theorem).
Let $\E$ be any elliptic curve over~$\Q$.
Then $\EQ/2\EQ$ is finite.
\end{thm}
% N.B. I might just give the following sentence verbally.
The proof of the more general version
is in a similar spirit, but requires some algebraic
number theory, working in the number field $\Q(\alpha)$, where
$\alpha$ is a root of~$F(X)$.
\begin{comm}\label{comm:bool}
A {\it Boolean} group is defined to be a group such that
$g * g$ is the identity, for any element~$g$.
A finite Boolean group, generated by the independent elements
$g_1,\ldots ,g_n$, has $2^n$ elements.
Given any Abelian group~$G$, the quotient group $G/2G$
is always Boolean. When $G/2G$ is finite, $\# G/2G$
is always a power of~$2$ and is isomorphic 
to $C_2 \times \ldots \times C_2$.
\end{comm}
Suppose we are give an elliptic curve of the form
$\C : Y^2 = X(X^2 + a X + b)$, and we derive the associated
objects already described, namely $\D : V^2 = U(U^2 + a_1 U + b_1)$,
where $a_1 = -2a, b_1 = a^2 - 4b$, with $\G = \CQ, \HH = \DQ$,\
$\phi : \G \rightarrow \HH$,\
$\hp : \HH \rightarrow \G$,\
$q : \HH/\phi(\G) \rightarrow \qmsq$,\
$\hq : \G/\hp(\HH) \rightarrow \qmsq$.
% N.B. I might just say $q, \hq$ above, rather than
% q : \HH/\phi(\G) \rightarrow \qmsq, \hq : \G/\hp(\HH) \rightarrow \qmsq.
Then the above results and their proofs give a method
for trying to compute $\G / 2\G$.
\par  {\bf Step 1.}\ Try to find $\HH/\phi(\G)$ by finding all
square free integers $r | b_1$ satisfying $W_r$.
\par  {\bf Step 2.}\ Try to find $\G/\hp(\HH)$ by finding all
square free integers $r | b$ satisfying ${\widehat W}_r$.
\par  {\bf Step 3.}\ Combine $\G/\hp(\HH)$
and $\hp\bigl( \HH/\phi(\G) \bigr)$ to generate $\G/2\G$.
\par 
%% N.B. The following is a slightly shorter example, if I
%% am running short of time, although Example\ref{ex:isogdesc2}
%% doesn't seem to take too long, and gives a better preparation 
%% for the problem sheets.
%% Note that, if I were to change from Example\ref{ex:isogdesc2}
%% to Example\ref{ex:isogdesc2}[6.12], then I would also in Section 7
%% have to change from Example\ref{ex:rank2}[7.6] to Example\ref{ex:rank1},
%% which is currently also commented-out in notes.tex.
%\begin{ex}\label{ex:isogdesc1}
%Let $\C : Y^2 = X(X^2 + X + 2)$.
%Then $\G / 2\G = \CQ/2\CQ \cong C_2 \times C_2$.
%\end{ex}
%\begin{proof} Here, $a=1, b=2$ and so $a_1 = -2a = -2,\
%b_1 = a^2 - 4b = -7$, giving
%$\D : V^2 = U(U^2 - 2U - 7)$. The isogeny
%$\phi : \C \rightarrow \D$ is given by
%$\phi(x,y) = \Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{by}{x^2} \Bigr)
%= \Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{2y}{x^2} \Bigr)$.
%The isogeny $\hp : \D \longrightarrow \C$
%is given by
%$\hp(u,v) =
%\Bigl( \frac{1}{4} \bigl( \frac{v}{u} \bigr)^2,
%\frac{1}{8} \bigl( v - \frac{b_1 v}{u^2}\bigr) \Bigr)
%= \Bigl( \frac{1}{4} \bigl( \frac{v}{u} \bigr)^2,
%\frac{1}{8} \bigl( v + \frac{7 v}{u^2}\bigr) \Bigr)$.
%\par  {\bf Step 1.} Find $\HH /\phi(\G)$.
%We need to consider $r | b_1 = -7, r\in \bbbz$, $r$ square free,
%that is, $r = \pm 1, \pm 7$, so that
%$\im q \leqslant \{ \pm 1, \pm 7\}$.
%But $q(\o) = 1,\ q(0,0) = b_1 = -7,\ q(-1,2) = -1,\ q(7,14) = 7$
%[note that $(7,14)$ can be found as $(0,0) + (-1,2)$ without
%needing to search],
%so that $\im q = \{ \pm 1, \pm 7\}$
%and $\HH / \phi(\G) = \{ \o, (0,0), (-1,2), (7,14) \}
%= \langle (0,0), (-1,2) \rangle$.
%\par  {\bf Step 2.} Find $\G /\hp(\HH)$.
%We need to consider $r | b = 2, r\in \bbbz$, $r$ square free,
%that is, $r = \pm 1, \pm 2$.
%Also, $\hq(\o) = 1,\ \hq(0,0) = b = 2$, so
%that $\{ 1,2\} \leqslant \im \hq \leqslant \{ \pm 1, \pm 2\}$.
%Note that $-1 \in \im \hq \iff -2 \in \im \hq$,
%and so it is only necessary to check one member of
%the coset $\{ -1, -2\}$. 
%\par Choose $r=-1$. Then ${\widehat W}_{-1}$,
%$r \ell^4 + a \ell^2 m^2 + (b/r) m^4 = n^2$ becomes:
%$$
%{\widehat W}_{-1} : - \ell^4 + \ell^2 m^2 - 2 m^4 = n^2,\ \
%\hbox{ for some } \ell, m, n \in \Z, 
%\hbox{ not all $0$, with gcd}(\ell,m) = 1.
%$$
%On multiplying both sides by~$4$ and completing the square, we obtain:
%$$ -( 2\ell^2 - m^2 )^2 - 7 m^4 = 4 n^2.\ \ \ \ \ (1)$$
%This gives $-( 2\ell^2 - m^2 )^2 \equiv 4 n^2$~(mod~$7$).
%\par Imagine $7 \nmid ( 2\ell^2 - m^2 )$; then $2\ell^2 - m^2$ 
%would have an inverse~$\alpha$ mod~$7$, and so
%$-1 \equiv (2\alpha n)^2$~(mod~$7$), contradicting the fact
%that $-1$ is not a quadratic residue mod~$7$.
%\par Hence, by reductio, $7 | ( 2\ell^2 - m^2 )$
%and so $7 | n$ [since $7 | 4n^2$ and $7 \nmid 4$], giving also
%that $7^2 | ( 2\ell^2 - m^2 )^2$ and $7^2 | 4 n^2$,
%so that, from~(1), $7^2 | 7 m^4$, and so $7 | m$.
%But combining $7 | m$ with $7 | 2\ell^2 - m^2$ gives
%$7 | 2\ell^2$, so that $7 | \ell$. We have shown
%that $7 | \ell$ and $7 | m$, contradicting $\gcd(\ell,m) = 1$.
%Hence there are no solutions to ${\widehat W}_{-1}$, giving that
%$-1 \not\in \im \hq$ [indeed, we have shown that there are
%no solutions in $\Q_7$].
%\par We conclude that $\im \hq = \{ 1, 2\}$
%and $\G / \hp(\HH) = \{ \o, (0,0) \}
%= \langle (0,0) \rangle$.
%\par 
%{\bf Step 3.} Find $\G/2\G$. This is by
%$\G / \hp (\HH) = \{ \o, (0,0) \}$,
%together with $\hp\bigl( \HH/\phi(\G) \bigr)
%= \{ \hp( \o), \hp (0,0), \hp(-1,2), \hp(7,14) \}$
%$$ = \{ \o, \o, \Bigl( \frac{1}{4} \bigl( \frac{2}{-1} \bigr)^2,
%\frac{1}{8} \bigl( 2 + \frac{7 \cdot 2}{(-1)^2}\bigr) \Bigr),
%\Bigl( \frac{1}{4} \bigl( \frac{14}{7} \bigr)^2,
%\frac{1}{8} \bigl( 14 + \frac{7 \cdot 14}{7^2}\bigr) \Bigr)\}
%$$
%$ = \{ \o, \o, (1,2), (1,2) \} = \{ \o, (1,2) \}$.
%Therefore, $\G/2\G = \{ \o , (0,0), (1,2), (0,0) + (1,2) = (2,-4)\}
%= \langle (0,0), (1,2) \rangle \cong C_2 \times C_2$.
%\end{proof}
\par 
\begin{ex}\label{ex:isogdesc2}
Let $\C : Y^2 = X(X^2 - X + 6)$.
Then $\G / 2\G = \CQ/2\CQ \cong C_2 \times C_2$.
\end{ex}
\begin{proof} Here, $a=-1, b=6$ and so $a_1 = -2a = 2,\
b_1 = a^2 - 4b = -23$, giving
$\D : V^2 = U(U^2 + 2U - 23)$. The isogeny
$\phi : \C \rightarrow \D$ is given by
\[\phi(x,y) = \Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{by}{x^2} \Bigr)
= \Bigl( \bigl( \frac{y}{x} \bigr)^2, y - \frac{6y}{x^2} \Bigr)\]
The isogeny $\hp : \D \longrightarrow \C$
is given by
\[\hp(u,v) =
\Bigl( \frac{1}{4} \bigl( \frac{v}{u} \bigr)^2,
\frac{1}{8} \bigl( v - \frac{b_1 v}{u^2}\bigr) \Bigr)
= \Bigl( \frac{1}{4} \bigl( \frac{v}{u} \bigr)^2,
\frac{1}{8} \bigl( v + \frac{23 v}{u^2}\bigr) \Bigr)\]
\par  {\bf Step 1.} Find $\HH /\phi(\G)$.
We need to consider $r | b_1 = -23, r\in \bbbz$, $r$ square free,
that is, $r = \pm 1, \pm 23$, and
$q(\o) = 1,\ q(0,0) = b_1 = -23$, so that:
$\{ 1,-23 \} \leqslant \im q \leqslant \{ \pm 1, \pm 23\}$.
Note that $-1 \in \im q \iff 23 \in \im q$,
and so it is only necessary to check one member of
the coset $\{ -1, 23\}$.
\par Choose $r=-1$. Then equation $W_r$,
$r \ell^4 + a_1 \ell^2 m^2 + (b_1/r) m^4 = n^2$ becomes:
$$
W_{-1} : - \ell^4 + 2 \ell^2 m^2 + 23 m^4 = n^2,\ \
\hbox{ for some } \ell, m, n \in \Z, 
\hbox{ not all $0$, with gcd}(\ell,m) = 1.
$$
On completing the square, we obtain:
$$ -( \ell^2 - m^2 )^2 + 24 m^4 = n^2.\ \ \ \ \ (1)$$
This gives $-( \ell^2 - m^2 )^2 \equiv n^2$~(mod~$3$).
\par Imagine $3 \nmid ( \ell^2 - m^2 )$; then $\ell^2 - m^2$
would have an inverse~$\alpha$ mod~$3$, and so
$-1 \equiv (\alpha n)^2$~(mod~$3$), contradicting the fact
that $-1$ is not a quadratic residue mod~$3$.
\par We deduce that $3 | ( \ell^2 - m^2 )$,
and so $3 | n$ (since $3 | n^2$), giving
that $3^2 | ( \ell^2 - m^2 )^2$ and $3^2 | n^2$. Then, from~(1), $3^2 | 24 m^4$, and so $3 | m^4$ and hence $3 | m$.

But combining $3 | m$ with $3 | (\ell^2 - m^2)$ gives
$3 | \ell^2$, so that $3 | \ell$. We have shown
that $3 | \ell$ and $3 | m$, contradicting $\gcd(\ell,m) = 1$.
Hence there are no solutions to $W_{-1}$, giving that
$-1\not\in \im q$ (indeed, we have shown that there are no
solutions $(\ell,m,n)\not= (0,0,0)$ in $\bbbq_3$).
\par This gives $\im q = \{ 1, -23 \}$
and $\HH / \phi(\G) = \{ \o, (0,0) \}
= \langle (0,0) \rangle \cong C_2$.
\par  {\bf Step 2.} Find $\G /\hp(\HH)$.
We need to consider $r | b = 6, r\in \bbbz$, $r$ square free,
that is, $r = \pm 1, \pm 2, \pm 3, \pm 6$.
Also, $\hq(\o) = 1,\ \hq(2,4) = 2,\ \hq(3,-6) = 3,\ \hq(0,0) = b = 6$, 
% N.B. I might mention verbally that if we have already found (2,4) and (0,0)
% then we can get (3,-6) without any further searching
% from: (2,4) + (0,0) = (3,-6).
so that $\{ 1,2,3,6\} \leqslant \im \hq \leqslant \{ \pm 1, \pm 2,
\pm 3, \pm 6\}$.
Note that $-1 \in \im \hq \iff -2 \in \im \hq
\iff -3 \in \im \hq \iff -6 \in \im \hq$,
and so it is only necessary to check one member of
the coset $\{ -1, -2, -3, -6\}$. 
\par Choose $r=-1$. Then ${\widehat W}_{-1}$,
$r \ell^4 + a \ell^2 m^2 + (b/r) m^4 = n^2$ becomes:
$$
{\widehat W}_{-1} : - \ell^4 - \ell^2 m^2 - 6 m^4 = n^2,\ \
\hbox{ for some } \ell, m, n \in \Z, 
\hbox{ not all $0$, with gcd}(\ell,m) = 1.
$$
For any $\ell,m,n\in \bbbz$, $\ell^4, \ell^2 m^2, 6 m^4 \geqslant 0$,
so $- \ell^4 - \ell^2 m^2 - 6 m^4 \leqslant 0$,
and
$$ \hbox{LHS} = - \ell^4 - \ell^2 m^2 - 6 m^4 = 0
\iff \ell^4 =  \ell^2 m^2 =  6 m^4 = 0 \iff \ell = m = 0.$$
Also, RHS $ = n^2 \geqslant 0$ and $n^2 = 0 \iff n = 0$.
Both sides are equal $\iff$ both sides are~$0$
$\iff \ell = m = n = 0$, but we require $\ell,m,n$ to
be not all~$0$.
Hence there are no solutions to ${\widehat W}_{-1}$, giving that
$-1 \not\in \im \hq$ (indeed, we have shown that there are
no solutions $(\ell,m,n)\not= (0,0,0)$ in $\R$).
\par   We conclude that $\im \hq = \{ 1, 2, 3, 6\}$
and $\G / \hp(\HH) = \{ \o, (0,0), (2,4), (3,-6) \}
= \langle (0,0), (2,4) \rangle$.
\par 
{\bf Step 3.} Find $\G/2\G$. This is generated by
$\G / \hp (\HH) = \{ \o, (0,0), (2,4), (3,-6) \} 
= \langle (0,0), (2,4) \rangle$,
together with $\hp\bigl( \HH/\phi(\G) \bigr)
= \{ \hp( \o), \hp (0,0) \}
= \{ \o\}$, which gives nothing new that wasn't already in $\G/\hp(\HH)$.
Therefore, $\G/2\G = \{ \o , (0,0), (2,4), (3,-6) \}
= \langle (0,0), (2,4) \rangle \cong C_2 \times C_2$, as required.
Note that $(0,0), (2,4)$ are independent in 
$\G / \hp (\HH)$ and so are independent in $\G/2\G$
(since $2\G = \hp ( \phi (\G )) \le \hp (\HH)$).
\end{proof}
% N.B. The following comment is optional.
\begin{comm}\label{comm:sha}
The equations
\begin{align*}
W_r &: r \ell^4 + a_1 \ell^2 m^2 + (b_1/r) m^4 = n^2,\\
{\widehat W}_r &: r \ell^4 + a \ell^2 m^2 + (b/r) m^4 = n^2,
\end{align*}
(which can also be expressed as: $r X^4 + a_1 X^2 + b_1/r = Y^2$
and $r X^4 + a X^2 + b/r = Y^2$, for $X,Y\in \bbbq$)
are called {\it homogeneous spaces}. Finding $\CQ/2\CQ$,
as in the last example, comes down to deciding,
for each $r | b_1$, whether $W_r$ has a solution
$\ell,m,n\in \bbbz$, not all~$0$, with $\gcd(\ell,m) = 1$,
and for each $r | b$, whether ${\widehat W}_r$ has such a solution.
\par In the last example, it turned out that each $W_r, {\widehat W}_r$
either had a solution $\ell,m,n$, or we were able to show such a
solution was impossible with a modulo-power-of-$p$ argument
(a $p$-adic argument) or that it was impossible in~$\R$.
That is, each $W_r,{\widehat W}_r$ either had a point
or it was impossible in $\R$ or some $\Q_p$.
\par This doesn't always happen. It is possible in some examples
for $W_r$ or ${\widehat W}_r$ to have solutions 
in $\R$ and every $\Q_p$, but not in $\Q$ (that is, for
there to be a violation of the Hasse Principle).
For example, consider $\C : Y^2 = X^3 + 17 X$.
Here, $a = 0, b = 17$, so that $a_1 = 0, b_1 = - 68$,
giving $\D : Y^2 = X^3 - 68 X$.
When computing $\HH / \phi(\G)$, we consider $r | b_1 = -68$
and so $r = \pm 1, \pm 2, \pm 17, \pm 34$.
For the case $r=2$, the homogeneous space 
$r \ell^4 + a_1 \ell^2 m^2 + (b_1/r)m^4 = n^2$ becomes
$2 \ell^4 - 34 m^4 = n^2$.
Note that the equation forces $n$ to be even; setting $n = 2k$
and dividing both sides by~$2$ gives the
slightly simpler form: $\ell^4 - 17 m^4 = 2 k^2$.
As shown on Problem Sheet~3, this has no solutions $k,\ell,m\in\Z$
(not all~$0$, $\gcd({\ell,m}) = 1$),
and so $2\not\in \im q$,
even though there exist solutions in $\R$ and every $\Q_p$
(and so proving $2\not\in \im q$ requires an argument different
to those in the last example).
Instances of such $W_r$ (or ${\widehat W}_r$) correspond to
members of a structure known as the {\it Tate--Shafarevich group}, $\Sha(\C/\Q)$.
\end{comm}
% N.B. The following comment is optional.
\begin{comm}\label{comm:galcoh}
There is another approach to the Weak Mordell-Weil Theorem,
using Galois cohomology. Recall that the map \[q : \D(\Q)/\phi(\C(\Q)) \rightarrow \qmsq\]
is given by $q(Q) = d$, where $\Q(\sqrt{d})$ is the field
over which the pre-images $P,P'$ of $Q$ under $\phi$ are defined.
Since $\kker \phi = \{ \o , (0,0) \}$, we must have $P' = P + (0,0)$.
Furthermore, if $\mathrm{Gal}(\Q(\sqrt{d})/\Q) = \langle\sigma\rangle$ has order two (i.e.~$d$ is not a square), then $P' = \sigma(P)$. 

So, we have a group homomorphism \[c_Q : \mathrm{Gal}(\Q(\sqrt{d})/\Q)  \to \ker\phi\] given by sending $\sigma$ to $\sigma(P) - P$. It has the property that, for any member of $\{ P, P'\}$, the effect of applying $\gamma \in \mathrm{Gal}(\Q(\sqrt{d})/\Q)$ is the same as adding $c_Q(\gamma)$.
We then have a map $Q\mapsto c_Q$ which takes a member of $\D(\Q)/\phi(\C(\Q))$ to a homomorphism between a Galois group and $\ker \phi$. 

As we
have seen, 
there are two main elements required to prove the Weak Mordell-Weil
Theorem: showing that $q$ is a homomorphism and that
$\im q$ is finite. We deal with them both in turn. For showing that $q$ is a homomorphism,
suppose that $q(Q_1) = d_1$ and $q(Q_2) = d_2$.
Then, by definition, $P_1,P_1'$ (such that $\phi(P_1) = \phi(P_1') = Q_1$)
are defined over $\Q(\sqrt{d_1})$, and
$P_2,P_2'$ (such that $\phi(P_2) = \phi(P_2') = Q_2$)
are defined over $\Q(\sqrt{d_2})$. Since $\phi$
is a homomorphism, \[\phi(P_1 + P_2) = Q_1 + Q_2\]
and $P_1 + P_2$ is defined over $\Q(\sqrt{d_1},\sqrt{d_2})$.
But $\sqrt{d_1} \mapsto -\sqrt{d_1},\ \sqrt{d_2} \mapsto -\sqrt{d_2}$
has the same effect as adding $(0,0)$ to each of $P_1, P_2$
and so leaves $P_1 + P_2$ unchanged. This means that $P_1 + P_2$
is in fact defined over $\Q(\sqrt{d_1 d_2})$. Hence $q(Q_1 + Q_2)
= d_1 d_2 = q(Q_1)q(Q_2)$, giving that $q$ is a homomorphism
(without needing to work explicitly with the group law).


For the finiteness of $\im q$, let $q(Q) = d$, a
square free integer, and imagine that an odd prime $p$
of good reduction 
%[i.e.\ such that the curve is still an elliptic curve mod~$p$] 
is a factor of~$d$.
By the definition of~$q$, there are $P,P'$, defined over $\Q(\sqrt{d})$
such that $\phi(P) = \phi(P') = Q$.
But, on reduction modulo~$\sqrt{p}$, conjugation $\sqrt{d} \mapsto -\sqrt{d}$
has no effect modulo~$\sqrt{p}$. This shows that $P' - P$ is in the kernel of the reduction map. On the other hand, we know that $P'-P$ is a $2$-torsion point. So it follows from Lemma \ref{lem:torfm} that $P' = P$ which is a contradiction. Hence $d$ has only
primes dividing the discriminant as factors, and so has
only finitely many possibilities. We note in passing that we can regard each $c_Q$ as a homomorphism
\[c_Q: \mathrm{Gal}(L/\Q) \to \ker \phi \] where $L$ is the composite of the quadratic fields $\Q(\sqrt{p})$ with $p = 2$ or a prime of bad reduction. 

This approach is cleaner, and more amenable to generalisation, since it does not require getting our
hands dirty with explicit group law manipulations. On the other
hand, it is often worth a more from-first-principles proof
(as given previously), as it provides us with an explicit method
for trying to compute $\CQ/2\CQ$.
\end{comm}
\medskip
\hrule
\newpage
%********************************************************************
%\baselineskip=28.5pt
\section{The Mordell-Weil Theorem}\label{sec:mw}
%% Heights and the MW Theorem. [1 lecture]
When $\E$ is an elliptic curve over~$\Q$, we've seen that
$\ETQ$ and $\EQ/2\EQ$ are finite.
But $\EQ$ may sometimes be infinite (if $P \in \EQ$
and $P\not\in \ETQ$ then $P$ is of infinite order
and so $\EQ$ is infinite).
We shall show that $\EQ$ (whether finite or infinite)
is always finitely generated. That is, we aim to show that,
for any elliptic curve $\E$,
there exists finite number of elements $P_1,\ldots ,P_k\in\EQ$
such that every $P\in\EQ$ can be written as:
$$ P = m_1 P_1 + \ldots + m_k P_k, \ \ m_1,\ldots ,m_k \in \bbbz. $$
This will be achieved via height functions; we first describe
the general properties of a height function on a general
Abelian group.
\begin{defn}\label{defn:heightfunction}
Let~$A$ be an Abelian group with
group operation~$+$. 
\par We say that $h : A \longrightarrow \R$ is a {\it height function}
if it satisfies:
\par 
(1) For any $Q\in A$, there exists $C_1 = C_1(Q)$
such that $h(P+Q) \le 2h(P) + C_1$ for all $P\in A$.
\par 
(2) There exists $C_2$, independent of~$P$, such that
$h(2P) \ge 4h(P) - C_2$ for all $P\in A$.
\par 
(3) For any~$C_3$, the set $\{ P\in A : h(P) \le C_3\}$ is finite.
\end{defn}
\begin{thm}\label{thm:fgA}
Let~$A$ be an Abelian group which has a height function~$h$,
and suppose that $A/2A$ is finite. Then $A$ is
finitely generated.
\end{thm}
\begin{proof}
We are given that $A/2A$ is finite,
so let $A/2A = S = \{ Q_1,\ldots Q_r \} \subset A$.
Let~$P$ be any element of~$A$. Then $P = Q_{i_1}$ in $A/2A$
for some $Q_{i_1} \in S$ and so we can write:
$P = 2P_1 + Q_{i_1}$, for some $P_1 \in A$.
Inductively, continue to write:
$P_1 = 2P_2 + Q_{i_2}, P_2 = 2P_3 + Q_{i_3}, \ldots$,
where each $P_j \in A$
and each $Q_{i_j}\in S$. Now:
\[h(P_j) \le \frac{1}{4}\bigl( h(2P_j) + C_2 \bigr) \overset{\text{by }(2)}{=} \frac{1}{4}\bigl( h(P_{j-1}-Q_{i_j}) + C_2 \bigr)
\overset{\text{by }(1)}\le \frac{1}{4}\bigl( 2h(P_{j-1}) + C_1' + C_2 \bigr),\] where $C_1' = \hbox{max}\{ C_1(-Q) : Q\in S\}$.

So, if $h(P_{j-1}) > (C_1' + C_2)/2$ then:

\[h(P_j) < \frac{1}{4} \bigl( 2h(P_{j-1}) + 2h(P_{j-1}) \bigr) = h(P_{j-1}).\]

Imagine that $h(P) > (C_1' + C_2)/2$ and 
$h(P_j) > (C_1' + C_2)/2$ for all~$j$. Then
the sequence $h(P), h(P_1), h(P_2),\ldots$ would be strictly decreasing,
giving infinitely many distinct members of~$A$
with height $\le h(P)$, which would contradict~(3).
This contradiction shows that there must exist an~$n$
such that $h(P_n) \le (C_1' + C_2)/2$. So, we can write:
\[P = 2P_1 + Q_{i_1} = 2(2P_2 + Q_{i_2}) + Q_{i_1} = \ldots,\]
and after~$n$ steps $P$ will be written as a linear combination
of~$P_n$ and members of~$S$. 

Let
$T = \{ Q \in A : h(Q) \le (C_1' + C_2)/2\}$. We have
shown (since $P_n\in T$) that any $P\in A$ is a linear
combination of members of~$S \cup T$. Furthermore,
$T$ is finite, by~(3). In conclusion: $A$ is generated
by the finite set $S \cup T$,
and so is finitely generated.
\end{proof}

A height function on $\EQ$ can be obtained as follows.
\begin{lem}\label{lem:ECht}
Let $\E$ be an elliptic curve, defined over~$\Q$.
Define $h_x : \EQ \rightarrow \R$ by:
$$ h_x\bigl( (x,y) \bigr) = \log \max \bigl( | a |, | b | \bigr),\ \
\hbox{where } x = \frac{a}{b},\ a,b\in \Z,\ \gcd(a,b) = 1,
$$
and define $h_x(\o) = 0$.
Then $h_x$ is a height function on~$\EQ$.
Indeed, there exists a constant~$C$, independent of~$P,Q$, such that
$ | h_x(P+Q) + h_x(P-Q) - 2 h_x(P) - 2 h_x(Q) | \le C $,
for all $P,Q \in \EQ$, from which properties~(1),(2)
can be deduced (property~(3) is trivially true).
\end{lem}
For the proof (optional) see, for example, p.~235 of \cite{sil:AEC1}.
\par {\it Aside: The proof uses
the explicit group law; for example, $x' = a'/b'$, the $x$-coordinate
of $2P = 2(x,y)$ is given by $(\hbox{quartic in }x)/(\hbox{cubic in }x)$,
and so $\max(|a'|,|b'|)$ is `approximately' $\max(|a|,|b|)^4$,
giving that $\log\max(|a'|,|b'|)$ is `approximately'
$4\log\max(|a|,|b|)$, that is $h_x(2P)$ is `approximately'
$4h_x(P)$. It is only necessary to control the amount of cancellation
occurring, when writing the $x$-coordinate of $2P$ in
lowest terms.}
\begin{thm}\label{thm:mw} (The Mordell-Weil Theorem).
Let $\E$ be any elliptic curve over~$\Q$. Then $\EQ$
is finitely generated.
\end{thm}
\begin{proof}
This follows immediately from Theorem~\ref{thm:weakmw},
Theorem~\ref{thm:fgA}
and Lemma~\ref{lem:ECht}.
\end{proof}
% N.B. For the above, I might recall verbally that 
% Theorem\ref{thm:weakmw}[6.10] (from the last section) is the 
% Weak Mordell-Weil Theorem that $\EQ/2\EQ$ is finite,
% Theorem~\ref{thm:fgA[7.2] is the theorem that any Abelian group~A
% is finitely generated if it has a height function and $A/2A$ is finite,
% and Lemma~\ref{lem:ECht}[7.3] is the fact that $h_x$ is
% a height function on $\EQ$.
% I might also mention that Mordell (who was the PhD supervisor of Cassels,
% who was my PhD supervisor) proved this result entirely himself,
% and later Weil generalised it to number fields and Jacobians
% of curves of any genus. I should say that Mordell went completely
% mental if anyone called this the Mordell-Weil Theorem, insisting
% that E/Q be called Mordell's Theorem, and the generalisation
% Weil's Theorem, but everyone ignored his protests and calls
% both of them the Mordell-Weil Theorem.
\begin{comm}\label{comm:rank}
This means that we know what $\EQ$ looks like:
$$ \EQ \cong \ETQ \times \bbbz^r,
\hbox{ for some } r \geqslant 0, r \in \bbbz.
$$
The number~$r$ is called the {\it rank} of $\EQ$
(or just the rank of~$\E$). Clearly:
$$ \EQ \hbox{ has finitely many points } \iff
\hbox{ rank}\Bigl( \EQ \Bigr) = 0.
$$
To solve $\EQ$, we want to know: $\ETQ$ and~$r$ (the rank).
Note that: 
$$ \EQ / 2\EQ \cong \ETQ/2 \ETQ \times \Bigl( \bbbz/2\bbbz \Bigr)^r,
$$
so that:
$$ \EQ / 2\EQ \cong \EQ[2] \times C_2^r,
$$
where $\EQ[2]$ denotes the 2-torsion subgroup of $\EQ$
%(see Comment~\ref{comm:Gm}).
(see Comment~0.40).
% N.B. I might recall verbally that Comment\ref{comm:Gm}[0.40] was:
% When $G$ is a finite Abelian group, $G/2G$ is isomorphic to $G[2]$.
\end{comm}
%% Use this one if the shorter Example~\ref{ex:isogdesc1} was
%% used in the isogeny section.
%\begin{ex}\label{ex:rank1}
%Let $\C : Y^2 = X(X^2 + X + 2)$.
%In Example~\ref{ex:isogdesc2}, we found that
%$\CQ/2\CQ = \langle (0,0), (1,2) \rangle \cong C_2 \times C_2$.
%Also, $\C(\bbbc)[2] = \{ \o \} \cup \{ \hbox{points of order~$2$} \}
%= \{ \o, (0,0), \bigl( \frac{1 + \sqrt{-7}}{2} , 0 \bigr),
%\bigl( \frac{1 - \sqrt{-7}}{2} , 0 \bigr) \}$,
%so that $\CQ[2] = \{ \o, (0,0) \} \cong C_2$.
%Since $\CQ / 2\CQ \cong \CQ[2] \times C_2^r$,
%we deduce that $C_2 \times C_2 \cong C_2 \times C_2^r$
%and so the rank $r = 1$ [$\CQ$ is infinite, but is
%generated by $\CTQ$ and one element of infinite order].
%\end{ex}
\begin{ex}\label{ex:rank2}
Let $\C : Y^2 = X(X^2 - X + 6)$.
In Example~\ref{ex:isogdesc2}, we found that
$\CQ/2\CQ 
% = \langle (0,0), (2,4) \rangle
\cong C_2 \times C_2$.
Also, \[\C(\bbbc)[2] = \{ \o \} \cup \{ \hbox{points of order~$2$} \}
= \{ \o, (0,0), \bigl( \frac{1 + \sqrt{-23}}{2} , 0 \bigr),
\bigl( \frac{1 - \sqrt{-23}}{2} , 0 \bigr) \},\]
so that $\CQ[2] = \{ \o, (0,0) \} \cong C_2$.
Since $\CQ / 2\CQ \cong \CQ[2] \times C_2^r$,
we deduce that $C_2 \times C_2 \cong C_2 \times C_2^r$
and so the rank $r = 1$ ($\CQ$ is infinite, but is
generated by $\CTQ$ and one element of infinite order).
\end{ex}
\medskip
\hrule
\newpage
%********************************************************************
\section{Factorising integers using elliptic curves}\label{sec:crypto}
%% Public keys; Pollard's p-1 method; 
%% the EC method [1.5 lectures].
%% That leaves 1 lecture for general review.
% N.B. For the following example at the very beginning of this Section,
% rather than Person A and B, I might use Kate (Middleton)
% and William, not wanting the message to be intercepted
% and understood by Clive (Goodman, from the News of the World).
% I might also draw the diagram with arrows of A, B and 
% evil person C (or Kate, William and Clive).
\subsection*{Public key cryptography (see also ASO Number Theory)}
~\newline Public keys allow message to be encoded (not decoded).
Suppose A wants to send the integer X to B safely; we assume
that everything transmitted can be intercepted.
\par  {\bf Step 1.} B (in private) takes 2 large prime
numbers $p,q$ (usually about 250 digits) and multiplies them
together to give $N = pq$, chooses an exponent~$d$,
and publicises $N,d$ to the world.
\par  {\bf Step 2.} A (in private) computes
$Y \equiv X^d$ (mod~$N$) and sends the message Y to B.
\par  {\bf Step 3.} B privately computes $\phi(N) 
= \phi(p)\phi(q) = (p-1)(q-1)$ and also computes (by Euclid's Algorithm)
$e$ such that $de \equiv 1$~(mod~$\phi(N)$). Note that:
$$ Y^e \equiv (X^d)^e \equiv X^{de} = X^{1 + k\phi(N)}
\hbox{ (for some~$k\in\bbbz$) } \equiv X(X^{\phi(N)})^k \equiv X,$$
since $X^{\phi(N)} \equiv 1$ (mod~$N$) by Euler's Theorem,
provided that $X,N$ are coprime. Assuming $X < N$, this decodes
the message.
\par Note that computing $X^d$ (mod~$N$) (and $Y^e$ (mod~$N$))
is fast even when $d$ is large, by writing $d$ in base~$2$
as $d = 2^{k_1} + \ldots + 2^{k_m}$ ($k_1 < \ldots < k_m$).
One then obtains $X^{2^0} \equiv X,\ X^{2^1} \equiv (X^{2^0})^2,\
X^{2^2} \equiv (X^{2^1})^2,\ldots , X^{2^{k_m}}$, by
$k_m$ squaring operations, after which:
$$ X^d \equiv X^{2^{k_1}} X^{2^{k_2}}\ldots X^{2^{k_m}}\hbox{ (mod~$N$),}
$$
which takes roughly log~$d$ operations.
\par
Anyone wishing to crack the code must be able to compute $\phi(N)$,
which requires finding $p,q$ from $N = pq$. A naive (and very slow)
approach is
trial division: checking for each $c = 2, \ldots , [ \sqrt{N}\ ]$
whether $c | N$. 


\subsection*{Pollard's $p-1$ factorisation method} Much better is Pollard's $p-1$ method. One chooses base~$a$
and exponent $k = $ product of powers of small primes.
Compute $a^k$ (mod~$N$) (as usual, after first writing $k$ in binary),
and then $\gcd(a^k - 1,N)$ using Euclid's Algorithm.
If there exists prime $p | N$ such that $p-1 | k$
($k = (p-1)s$, say) then:
$$ a^k \equiv \bigl( a^{p-1} \bigr)^s \equiv 1^s \equiv 1
\hbox{ (mod~$p$) (by Fermat)},$$
provided that $p \nmid a$. This gives $p | (a^k - 1)$
and so $p | \gcd(a^k - 1, N)$. Unless we have bad luck,
$\gcd(a^k - 1,N) \not= N$, and so
$\gcd(a^k - 1, N)$ will be a proper factor of~$N$.
\begin{ex}\label{ex:pollard}
A four-letter word $L_1L_2L_3L_4$ has been divided
into two pairs: $L_1L_2$ and $L_3L_4$.
Each of these pairs has been converted into an integer (of at most 4 digits)
via the standard map: $A \mapsto 01 , B \mapsto 02, \ldots ,
Z \mapsto 26$. These integers have been encoded by taking each to the
power of $d=6587$, modulo $N=10123$. The encoded message reads:
$$ 4268,\, 5744.$$ 
 
We shall factorise $N$ by applying Pollard's ``$p-1$'' method,
using base~$2$ and exponent~$52$,
and then use the factorisation of~$N$ to decode the message.
\par
Write $52$ as a sum of powers of 2: $52 = 4 + 16 + 32$.
First compute (modulo $N=10123$):
$2^1 \equiv 2$, $2^2 \equiv (2^1)^2 \equiv 4$, 
$2^4 \equiv (2^2)^2 \equiv 16$, $2^8 \equiv (2^4)^2 \equiv 256$,
$2^{16} \equiv (2^8)^2 \equiv 4798$, 
$2^{32} \equiv (2^{16})^2 \equiv 4798^2 \equiv 1102$ (where each of these
was obtained be squaring the previous one, and reducing modulo~$N$). 
Since $52 = 4 + 16 + 32$, we have:
$2^{52} \equiv 2^4 2^{16} 2^{32} \equiv 
16\cdot 4798 \cdot 1102 \equiv 5907 \cdot 1102 \equiv
425$ modulo~$N$, 
so that $2^{52} - 1 \equiv 424$ modulo~$N$.
\par
Now, compute $\hbox{gcd}(424, N)$ by Euclid's Algorithm:
\par
$10123 = 23 \cdot 424 + 371$; $424 = 1\cdot 371 + 53$;
$371 = 7\cdot 53 + 0$. 
\par  So, $53$ is a factor of $N$.
Compute $10123/53 = 191$, giving the factorisation
$N = 10123 = 53 \cdot 191$.
\par
Since $N = 53 \cdot 191$, we have
$\phi (N) =52 \cdot 190 = 9880$. Compute the gcd of 
$\phi (N) = 9880$ and $d=6587$ we see:

\par $ \bigl( \latop{1}{0} \ \latop{0}{1} \ | \ \latop{9880}{6587} \bigr)
\rightarrow^{R_1 - R_2}
\bigl( \latop{1}{0} \ \latop{-1}{1} \ | \ \latop{3293}{6587} \bigr)
\rightarrow^{R_2 - 2R_1}
\bigl( \latop{1}{-2} \ \latop{-1}{3} \ | \ \latop{3293}{1} \bigr)
\rightarrow^{R_1 - 3293 R_2}
\bigl( \latop{*}{-2} \ \latop{*}{3} \ | \ \latop{0}{1} \bigr)$,
\par  where the $*$ entries need not be computed.
This gives us, all in the same computation, that
$\gcd(9880,6587) = 1$, and the bottom row of the last matrix
gives $\gcd(9880,6587)$ as a linear combination of~$9880,6587$,
namely: $1 = -2\cdot 9880 + 3\cdot 6587$.
Hence $3\cdot 6587 \equiv 1$~(mod~9880), that is, $3$ is the inverse of
$6587$ modulo~$\phi(N) = 9880$.
\par
The decoding operation is therefore $Y \mapsto Y^{3} \hbox{ mod }N$.
Computing $4268^3 = 4268^2\cdot 4268 \equiv 4547 \cdot 4268\equiv
805$ (modulo~$N = 10123$). Also: $5744^3 = 5744^2 \cdot 5744
\equiv 2679 \cdot 5744 \equiv 1216$ (modulo~$N = 10123$). The decoded
message is therefore: $0805,\, 1216$; that is: HELP.
% N.B. I might mention verbally:
% It's not very specific about the kind of HELP required,
% but I guess it still might be useful to know.
\end{ex}
\par The exponent~$k$ is typically chosen to be a product
of powers of the first~$r$ primes, for some~$r$.
Pollard's $p-1$ Method is fast when there exists at least
one prime $p | N$ such that $p-1 = \# \bbbf_p^*$ 
is only divisible by small primes, so that 
$\hbox{order}(a) | \# \bbbf_p^* | k$.
\par When Pollard's $p-1$ method is slow for some $N$, we can
replace `powers of an integer base~$a$' with
multiples $kP$ of a point~$P$ on an elliptic curve~$\E$.

We hope that, there exists prime $p | N$ such that
$\# \TE (\bbbf_p) | k$, which would guarantee
that $k P = \o$ (the point at infinity) mod~$p$; that is to say,
a denominator divisible by~$p$, in which case, taking the
gcd of the denominator and~$N$ will reveal the factor~$p$.
This will be fast if there exists $p | N$ such that
$\# \TE (\bbbf_p)$ is only divisible by small primes.
Each new choice of elliptic curve gives a new chance
of this happening. 
\par   {\bf The Elliptic Curve Method (ECM)}
for attempting to factor an integer~$N$ is as follows.
Choose an elliptic curve~$\E$ mod~$N$, some point~$P$
on~$\E$, and some choice of~$k$ (normally a product of
powers of small primes). Attempt to compute $kP$ (mod~$N$)
and hope that, in performing one of the additions $kP = k_1 P + k_2 P$,
a denominator will have gcd with~$N$ that is a nontrivial
factor of~$N$ ($\not= 1$ and $\not= N$). See Section XI.2 in \cite{sil:AEC1} (only in the 2nd edition) for more details.
\begin{ex}\label{ex:ecmethod}
Let $N = 10123$, as in Example~\ref{ex:pollard}.
We shall factorise $N$ by applying the Elliptic Curve Method,
using the curve $\E : Y^2 = X^3 + 5X - 5$ and~$4P$, where~$P=(1,1)$.
\par The line tangent to~$\E$ at $P=(1,1)$
has slope $y'$ given by $2yy' = 3x^2 + 5$, with $x=1,y=1$;
that is, the slope is $8/2 = 4$. This tangent line also goes
through $(1,1)$ and so has equation: $Y = 4X - 3$.
The $x$-coordinate of $2P$ is therefore $4^2 - (1+1) = 14$,
and the $y$-coordinate is: $-(4\cdot 14 - 3) = -53\equiv 10070$,
so that $Q = 2P = (14 , 10070)$ (modulo~$N=10123$). We now wish
to double the point $Q = 2P$, and so again the first step
is to find the line tangent to~$\E$ at $Q$. This has
slope $y'$ given by $2\cdot 10070 \cdot y' = 3\cdot 14^2 + 5$,
and so we need to compute $(3\cdot 14^2 + 5) / (2\cdot 10070)$
(modulo~$N=10123$), for which the first step is to find the
inverse of $2\cdot 10070 \equiv 10017$ (modulo~$N=10123$).
Using Euclid's Algorithm: 
\par $10123 = 1\cdot 10017 + 106$;
$10017 = 94 \cdot 106 + 53$; $106 = 2\cdot 53 + 0$. 
\par  So, we cannot
find the inverse of $10017$ (modulo~$N=10123$), and this
step has given us our factor~$53$ of~$N$. As in the previous example,
compute $10123/53 = 191$, giving the factorisation
$N = 10123 = 53 \cdot 191$.
\end{ex}
\medskip
\hrule

% N.B. I might mention at the very end of the section that these
% advances, although they are a considerable improvement on
% trial division, are not sufficiently fast to endanger
% public key cryptography, provided that we are slightly careful
% about how we choose our primes (for example primes of the
% form 2^n + 1 would be a very bad idea, and would be quickly
% cracked by Pollard's p-1 method!). Just choosing "random"
% large primes should be fine (so, you're still fine for
% shopping over the internet).
\vfil\eject
%********************************************************************
\begin{thebibliography}{29}
%
%\bibitem{cas:localfields}
%J.W.S.\ Cassels.
%\newblock {\em Local Fields.}
%\newblock LMS--ST~{\bf 3}. Cambridge University Press, Cambridge, 1986.

\bibitem{cas:ell}
J.W.S.\ Cassels.
\newblock {\em Lectures on Elliptic Curves.}
\newblock LMS--ST~{\bf 24}. Cambridge University Press, Cambridge, 1991.

\bibitem{sil:AEC1}
J.H.\ Silverman.
\newblock {\em The Arithmetic of Elliptic Curves}, 2nd edition.
\newblock GTM {\bf 106}. Springer-Verlag, 2009.
%
%\bibitem{siltate:ellcurves}
%J.H.\ Silverman and J.\ Tate.
%\newblock {\em Rational Points on Elliptic Curves}.
%\newblock UTM. Springer-Verlag, 1992.

\end{thebibliography}
\end{document}
