\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf
A Search for High Rank Congruent Number \\
\vskip .1in
Elliptic Curves} \\
{
\vskip 1cm
\large
Andrej Dujella \\
Department of Mathematics\\
University of Zagreb\\
Bijeni\v{c}ka cesta 30\\
10000 Zagreb \\
Croatia\\
\href{mailto:duje@math.hr}{\tt duje@math.hr}\\
\ \\
Ali S. Janfada\footnote{The second author was
partially financed by a grant No. 009/4/87 from Urmia University.}
and Sajad Salami \\
Department of Mathematics \\
University of Urmia\\
P.O. Box 165 \\
Urmia \\
Iran \\
\href{mailto:a.sjanfada@urmia.ac.ir}{\tt a.sjanfada@urmia.ac.ir} \\
\href{mailto:asjanfada@gmail.com}{\tt asjanfada@gmail.com} \\
\href{mailto: salami.sajad@gmail.com}{\tt salami.sajad@gmail.com}\\
}
\end{center}
\vskip .2in
\begin{abstract}
In this article, we describe a method for finding congruent number
elliptic curves with high ranks. The method involves an algorithm
based on the Monsky's formula for computing $2$-Selmer rank of
congruent number elliptic curves, and Mestre-Nagao's sum which is
used in sieving curves with potentially large ranks. We apply
this method for positive squarefree integers in two families of
congruent numbers and find some new congruent number elliptic
curves with rank $6$.
\end{abstract}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}
\newtheorem{note}[theorem]{Note}
\newenvironment{Note}{\begin{note}\normalfont\quad}{\end{note}}
\newcommand{\cd}{{$\cdot$}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\C}{{\mathbb C}}
\newcommand{\lra}{\longrightarrow}
\newcommand{\lr}{\rightarrow}
\newcommand{\sha}{{\amalg \hspace{-1.40mm}\amalg}}
\section{Introduction}
One of the major topics connected with elliptic curves is
construction of elliptic curves with high ranks. Several authors
considered this problem for elliptic curves with prescribed
properties and relatively high ranks. For instance, we cite
\cite{duje,kulst} for the curves with given torsion groups,
\cite{ACP2,elkis2} for the curves $y^2=x^3+ dx$,
\cite{elkis3,rgs2} for the curves $x^3+y^3=k$ related to the
so-called taxicab problem, \cite{duje2} for the curves
$y^2=(ax+1)(bx+1)(cx+1)(dx+1)$ induced by Diophantine quadruples
$\{a,b,c,d\}$, etc. Dujella \cite{duje} collected a list of known
high rank elliptic curves with prescribed torsion groups. The
largest known rank of elliptic curves, found by N. D. Elkies in
2006, is $28$.
In this work we deal with a family of elliptic curves which are
closely related to the classical Congruent Number problem. A
positive squarefree integer $n$ is called a {\it congruent
number} if it is the area of a right triangle with rational sides
\seqnum{A006991}, \seqnum{A003273}. The problem of determining
congruent numbers is closely related to the curves $E_n:
y^2=x^3-n^2x$, which are called {\it congruent number elliptic
curves} or {\it CN-elliptic curves}. In fact, the positive
squarefree integer $n$ is a congruent number if and only if the
Mordell-Weil rank $r(n)$ of $E_n$ is a positive integer
\cite[Chap. 1, Prop. 18]{kob1}.
In this case, we refer to $n$ itself as a CN-elliptic curve, which
corresponds to $E_n$. In 1972, Alter, Curtz, and Kubota \cite{Alter}
conjectured that $n \equiv 5,6,7 \pmod{8}$ are congruent numbers. In
1975, appealing to the Birch and Swinnerton-Dyer conjecture and
Shafarevich-Tate conjecture, Lagrange \cite{serf1} deduced a
conjecture on the parity of the $r(n)$ as follows:
$$ r(n) \equiv \left\{
\begin{array}{ll}
0 \ {\rm ( mod\ 2 ),} & {\rm if } \ n \equiv 1,2,3 \ {\rm ( mod\ 8 );}
\\
1 \ {\rm ( mod\ 2 ),} & {\rm if } \ n \equiv 5,6,7 \ {\rm ( mod\ 8 )}.
\end{array}
\right.
$$
\rm
The problem of constructing high rank CN-elliptic curves was considered by several authors.
In 1640, Fermat proved that $r(1)=0$, so $n=1$ is not a congruent
number. Billing \cite{biling} proved that $r(5)=1$.
Wiman \cite{wiman1} proved that $r(34)= 2$, $r(1254)=3$ and $r(29274)=4$
\seqnum{A062693}, \seqnum{A062694}, \seqnum{A062695} .
In 2000, Rogers \cite{rgs1}, based on an idea of Rubin and Silverberg \cite{rslb2}, found the first
integers $n=4132814070,\ 61471349610$ such that $r(n)=5,6$, respectively.
Later, in his PhD thesis \cite{rgs2}, Rogers
gave other integers with $r(n)=5,6$ smaller than those presented in \cite{rgs1}.
Also he found \cite{rgs2} the first integer $n=797507543735$ with $r(n)=7$.
During the preparation of this paper, Rogers informed us that the
smallest $n$ with $r(n)=5$ which he was aware is $48272239$, while
the smallest $n$ with $r(n)=6$ is $6611719866$.
This rank $6$ curve is known to be minimal \cite{htt}.
Here we give the complete list on $n$'s with $r(n)=6$
communicated to us by Rogers \cite{rgs}, other than those curves
which are noted above:
\\ $66637403074$, $94823967361$, $129448648329$, $179483163699$, $208645752554$,
$213691672290$, \linebreak $226713842409$, $248767798521$, $344731563386$,
$670495125874$, $797804045274$, $898811499201$.
In Section 2, we briefly describe the complete $2$-descents and $2$-Selmer rank
of CN-elliptic curves, denoted by $s(n)$, which is an upper bound
for $r(n)$. In Section 3, we describe Monsky's formula for computing
the value of $s(n)$. In Section 4, we study Mestre-Nagao's sum
method \cite{nag1, nag2, duje1} which is used as a sieving tool in
our algorithm. In Section 5, we design an algorithm to find high
rank CN-elliptic curves, based on the Monsky's formula for
$2$-Selmer rank CN-elliptic curves $s(n)$, and Mestre-Nagao's sum
$S(N,n)$.
We applied our algorithm for positive squarefree integers arisen from two specific families of congruent numbers.
We found a large number of curves with rank $5$ and twenty-four
new curves with rank $6$. We have not found any new curve
with $r(n)\geq 7$, although with some variants of our method we
have rediscovered Rogers' example with $r(n)=7$ (and some of
his examples with $r(n)=5$ and $6$). We have also found several
curves with $5\leq r(n)\leq 7$, where the upper bound is obtained
by MWRANK program (option {\tt -s}). It might be a challenging
problem to decide whether these curves have ranks equal to $5$ or $7$.
In our computations we used the PARI/GP
software (version 2.4.0) \cite{pari} and Cremona's MWRANK program \cite{crem} for computing the
Mordell-Weil rank of the CN-elliptic curves (using the method of descent via 2-isogeny).
\section{ Complete {\rm 2}-descent and {\rm 2}-Selmer rank }
In this section, we briefly describe an upper bound for
Mordell-Weil rank of CN-elliptic curves $r(n)$, which is based on
the cardinality of $2$-Selmer group $S^{(2)}(E_n/\Q)$. We denote
this group by $S^{(2)}$. For more details on the ($2$-)Selmer
groups and related topics, please see \cite[Chap. X]{slm1}. In the
following we will describe $2$-descents over $\Q$ for the
CN-elliptic curves. The number of $2$-descents is the order of
$S^{(2)}$. This is a power of $2$, and will be a multiple of $4$,
on account of the rational points of order $2$ on the curve $E_n$.
We shall therefore write $\# S^{(2)}=2^{s(n)+2}$. The exponent
$s(n)$ is called {\it $2$-Selmer rank}
of the curve $E_n$. Next we describe the $2$-descent
process on the curve $E_n$. For a similar argument of complete $2$-descent, please see
\cite[Chap. X, \S 1]{slm1}, \cite[Sec. 3]{serf1} and \cite[Sec.
2]{heath1}.
Let $p_1$, $\dots$, $p_t$ be the odd prime factors of the squarefree integer $n$,
and let $M_{\Q}$ be the set of all places of $\Q$. Define the
sets $S$ and $\Q(S,2)$ as follows.
$$ S= \{ \infty , 2, p_1, \dots, p_t \}, $$
$$\Q(S,2)=\left \{a\in {\Q}^*/{{\Q}^*}^2 | \upsilon_p(a)\equiv 0\ ({\rm mod}\ 2)\
\forall p\in M_{\Q} \backslash S \right \}.$$
\begin{theorem}
\label{desc}
Let $E_n$ be the elliptic curve $y^2=x^3-n^2x$ and let ${\cal O}$
be the identity element of the group $E_n (\Q)$.
With the above notation, we have:
\begin{description}
\item[{\rm (i)}]
There is an injective homomorphism
$$\theta : E_n (\Q)/2E_n(\Q) \longrightarrow \Q(S,2) \times \Q(S,2)$$
$$ P=(x,y) \mapsto \left \{
\begin{array}{ll}
(x, x-n), & {\rm if } \ P \neq {\cal O}, (0,0), (n,0);\\
(-1, -n), & {\rm if } \ P = (0,0);\\
(n, 2), & {\rm if } \ P = (n,0);\\
(1,1), & {\rm if } \ P ={\cal O}.
\end{array}
\right.
$$
\item[{\rm (ii)}]
Let $(a,b) \in \Q(S,2) \times \Q(S,2) \backslash \{(1,1),(-1,-n),(n,2) \}$.
Then $(a,b)$ is the image of a point
$P=(x,y) \in E_n (\Q)/2E_n(\Q)$ if and only if the following
system of equations have a common solution
$(X,Y,Z) \in \Q^* \times \Q^* \times \Q^* $.
$$(*) \ aX^2-bY^2=n, \ \ aX^2-abZ^2=-n.$$
If such a solution exist then one can take $P=(aX^2, abXYZ)=(bY^2+n, abXYZ)$.
\end{description}
\end{theorem}
For a proof of this theorem see \cite[Chap. X, \S 1]{slm1} or \cite[Sec. 3]{serf1} .
Note that the Mordell-Weil rank of the curve $E_n$ can be found by
$$r(n)=\log_2\left ( \frac{Image (\theta)}{4}\right );$$
Also, the cardinality of $S^{(2)}$ is equal to the number of the pairs $(a,b)$ such that the system $(*)$ is everywhere locally solvable.
If one take the set
$R=\left \{\pm 2^\alpha p_1^{\alpha_1} \cdots p_t^{\alpha_t} | \alpha, \alpha_1, \dots, \alpha_t \in \{0,1\} \right \}$
as representatives for $\Q (S,2)$, then it is immediate that $\#\Q (S,2)= 2^{t+2}$ and so
$$r(n)\leq s(n)\leq 2 w(n).$$
\section{Monsky's formula for {\rm 2}-Selmer rank}
In 1994, P. Monsky \cite{heath2} proved a
theorem on the parity of the $2$-Selmer rank of CN-elliptic curves.
He gave a formula for computation of the $s(n)$ through his proof
of this theorem.
\begin{theorem}
\label{mons}
Let $n$ be a positive squarefree integer. Then
$$ s(n) \equiv \left\{
\begin{array}{ll}
0 \ {\rm ( mod\ 2 ),} & {\rm if } \ n \equiv 1,2,3 \ {\rm ( mod\ 8 );}\\
1 \ {\rm ( mod\ 2 ),} & {\rm if } \ n \equiv 5,6,7 \ {\rm ( mod\ 8 )}.
\end{array}
\right.
$$
\end{theorem}
For a proof of this theorem see Appendix of
\cite{heath2}.
Let $n$ be a positive squarefree integer with odd prime factors
$p_1$, $\dots$, $p_t$. Define the diagonal
$t \times t$ matrix $D_l=(d_i)$, for $l \in \{-1,-2,2\}$ , and the square $t \times t$ matrix
$A=(a_{ij})$ as follows:
$$
\begin{array}{ll}
$$d_i=\left\{
\begin{array}{ll}
0, & {\rm if} \ (\frac{l}{p_i})=1; \\
1, & {\rm if} \ (\frac{l}{p_i})=-1,
\end{array}
\right.$$
\ \
$$a_{ij}=\left\{
\begin{array}{ll}
0, & {\rm if} \ (\frac{p_j}{p_i})=1, j\neq i; \\
1, & {\rm if} \ (\frac{p_j}{p_i})=-1, j\neq i,
\end{array}\right.$$
\end{array}
\ \ a_{ii}=\sum_{j \,:\, j\neq i}^{} a_{ij}.$$
Monsky showed that $s(n)$ can be computed as
$$s(n)= \left\{
\begin{array}{ll}
2t- {\rm rank}_{\F_2} (M_o), &{\rm if } \ n=p_1p_2\cdots p_t; \\
2t- {\rm rank}_{\F_2} (M_{e}), & {\rm if } \ n=2p_1p_2 \cdots p_t,
\end{array}
\right.$$ where $M_o$ and $M_e$ are the following $2t \times 2t$
matrices:
$$
\begin{array}{ll}
$$
M_o=\left [
\begin{array}{c|c}
A+D_2 & D_2 \\
\hline
D_2 & A+D_{-2}
\end{array}
\right],
$$
&
$$ M_{e}=\left [
\begin{array}{c|c}
D_2 & A+D_2 \\
\hline
A^T+D_2 & D_{-1}
\end{array}
\right].$$
\end{array}
$$
\section{Mestre-Nagao's sum} \rm
Now we describe a sieving method for finding the best candidates
for high rank CN-elliptic curves. For any elliptic curve $E:
y^2=x^3+ax+b$ over $\Q$, and every prime number $p$ not dividing
the discriminant $\Delta=-16(4a^3+27b^2)$ of $E$, we can reduce
$a$ and $b$ modulo $p$ and view $E$ as an elliptic curve over the
finite field $\F_p$. Let $\# E(\F_p)$ be the number of points on
the reduced curve:
$$\# E(\F_p)= 1+ \# \{0 \leq x,y\leq p-1 : y^2\equiv x^3+ax+b \ ({\rm mod}\ p)\}.$$
There is both theoretical and experimental evidence which suggests
that elliptic curves of high ranks have the property that $\# E(\F_p)$
is large for many primes $p$.
\begin{definition}\rm
Let $N$ be a positive integer and ${\bf P}_N$ be the set of all primes less than $N$.
Mestre-Nagao's sum is defined by
$$S(N,E)=\sum_{p\in {\bf P}_N}^{}(1- \frac{p-1}{\# E(\F_p)})\log p
=\sum_{p\in {\bf P}_N}^{} \frac{-a_p+ 2}{ \# E(\F_p)}\log p.$$
\end{definition}
Note that $S(N,E)$ can be computed efficiently with PARI/GP software \cite{pari}, provided $N$ is not too large.
It is experimentally known \cite{duje1,nag1,nag2} that we may
expect that high rank curves have large $S(N,E)$.
See \cite{camp} for a heuristic argument which connects this assertion with
the famous Birch and Swinnerton-Dyer conjecture.
For a positive squarefree integer $n$, we denote $S(N,E_n)$ by $S(N,n)$.
\section{An algorithm for finding high rank }
Now we are ready to exhibit our algorithm for finding high rank
CN-elliptic curves, based on Monsky's formula for $2$-Selmer rank
of CN-elliptic curves $s(n)$ and Mestre-Nagao's sum $S(N,n)$. In
this algorithm, first of all, a list of different positive
squarefree congruent number is considered. Next, for any integer
$n$ in this list, the value of $s(n)$ is computed by the
Monsky's formula which is described in the section 3. Selecting those
$n$'s with $s(n)\geq s$ for a given positive number $s$, a new
list of integers $n$ is scored by Mestre-Nagao sum $S(N,n)$ using
finitely many successive primes. Finally, the Mordell-Weil rank
$r(n)$ is computed by MWRANK for integers $n$ with $s(n)\geq s$
and large values of Mestre-Nagao sums. To be more precise, we write
our algorithm step by step as follows.
\begin{description}
\item[Step 1.] Let {\it s} be a positive integer. Choose a non-empty set $T$ of some squarefree congruent numbers.
For any $n\in T$ compute $s(n)$ by the Monsky's formula. Define the subset $T_s$ of $T$
containing all $n \in T$ with $s(n)={\it s}$. If $T_s$ is empty choose another set
$T$.
\item[Step 2.]
Let $k$ be a positive integer.
Choose the set ${\cal M}_s$ as follows:
$${\cal M}_s=\left \{(N_i, M_i): \ 0 < N_1<\cdots