\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