The congruent number problem is the problem of figuring out whether a given positive integer $N$ is the area of a right-angled triangle with all side lengths rational. According to Dickson's "History of the theory of numbers" (volume 2 chapter 16) the problem was explicitly raised in an anonymous Arab manuscript which dates back to 972AD or before. Some relatively straightforward algebra shows that $N$ is a congruent number iff the elliptic curve $E_N:=y^2=x^3-N^2x$ has positive (algebraic) rank.

Tunnell in 1983 gave a relatively efficient algorithm for computing the special value of the $L$-function of $E_N$ at 1 (I don't know how efficient it is in practice but it's certainly going to run in time polynomial in $N$ which I know is atrocious if $N$ is very large, however I think our problems are going to start before then). If the value of this $L$-function at 1 is non-zero then by the Coates-Wiles theorem the curve has algebraic rank zero and hence $N$ is not congruent. If BSD is true then Tunnell's algorithm gives a necessary and sufficient condition for $N$ to be congruent.

However BSD is not yet known, and my guess is that as $N$ increases, the fact that we don't know BSD for $E_N$ will trouble us before Tunnell's algorithm starts slowing up. In theory there could exist some $N$ for which $E_N$ had analytic rank 2 or more, and algebraic rank zero. Tunnell would compute the special value at 1 to be zero and then we would be faced with the problem of computing the algebraic rank, which can very occasionally be hard in practice, especially if Sha is non-trivial etc etc. Even if the algebraic rank is positive, finding a non-torsion point can be hard in practice; the question is like Pell where relatively innocuous values of $N$ like 157 can give rise to elliptic curves for which the height of every non-torsion point is very large. In fact general theory can deal with 157 because the analytic rank is 1, but certainly the analytic rank can be higher than 1 in general (for example if $N=41$ then the analytic rank is 2).

Because of this issue, I think that (until a new major advance is made with this problem) there must surely be some explicit smallest positive integer $N$ for which we don't know whether or not $N$ is a congruent number. My guess is that this value of $N$ will actually be a congruent number in practice, and the elliptic curve $E_N$ will be computationally checked to have analytic rank at least 2, but no-one will be able to find a rational point (not because there isn't one, but because it's out of computational range).

My guess is that there will be papers containing results of the form "we have solved the congruent number problem for all $N\leq 10^{10}$" or some such statement -- but I have no idea what the state of the art is, and perhaps my google-fu is weak today. This does not change the fact that I am giving a talk on the congruent number problem tomorrow :-) and I thought that it might be nice to mention the state of the art, if I can find it out by then! Does anyone have any leads?

  • $\begingroup$ I thought Matsuno had the largest calculations, up to 300000 in 2005. At least that's what the ANTS-X paper (which is under BSD) on the subject says. link.springer.com/content/pdf/10.1007/978-3-642-14518-6_17.pdf $\endgroup$ May 20, 2016 at 10:33
  • $\begingroup$ Then Matsuno gave a seminar talk up to $10^6$ in 2006 using 4-descent. Probably Tom Fisher could hold the "record", if he bothered with the problem. nakano.math.gakushuin.ac.jp/html-files/seminar/English/… $\endgroup$ May 20, 2016 at 10:35
  • $\begingroup$ Many thanks for this -- this is a great start. So if we believe Matsuno then $10^6+1$ is a candidate! According to pari this has analytic rank 2. Is it provably a congruent number? magma seems to say that the algebraic rank is at least 1. Does this mean it's spotted a rational point? $\endgroup$ May 20, 2016 at 10:54
  • $\begingroup$ Of course, giving a talk entitled "The determination of the congruent numbers less than 10^6 and explicit 4-descents on elliptic curves" does not definitely imply that you've done what it says in the title :-) I have emailed Matsuno. $\endgroup$ May 20, 2016 at 10:58
  • $\begingroup$ Nope, I've done $10^6+1$: mwrank reports that there's a point of infinite order. Now on to $10^6+2$! This is exactly what I didn't want to do. There will surely be a smallest $N$ for which someone tried and got stuck... $\endgroup$ May 20, 2016 at 11:13

2 Answers 2


Kazuo Matsuno writes (personal communication):

"I verified (10 years ago) by using mwrank and magma that E_N:y^2=x^3-N^2x has a non-torsion point if N<=10^6 is congruent to 1,2,3 modulo 8 and the analytic rank of E_N is positive. For all N<=10^6 congruent to 5,6,7 modulo 8, Elkies proved rank(E_N)>0.

http://arxiv.org/abs/math/0208056 "

If no-one can better this, then the answer to my question is hence $10^6+2$ (given that I (KB) just checked $10^6+1$ earlier today).

  • 1
    $\begingroup$ I hope there aren't $k > 1$ answers of the "the answer is $10^6+j$" for $j=2, ..., k+1$. $\endgroup$
    – Kimball
    May 20, 2016 at 22:46
  • $\begingroup$ $j=9$ has (analytic) rank 2 again, and the regulator is around 11000. Magma's 4-descent fairly easily found a point of height 113. $\endgroup$ May 21, 2016 at 4:14

This is a practical question rather than a theoretical one. My suspicion is that the smallest $N$ for which it is not feasible to determine whether $N$ is congruent is probably very large (maybe $N \approx 10^{9}$), for the following reason.

The curve $E_{N} : y^{2} = x^{3} - N^{2} x$ has CM, and as a consequence $\mathbb{Q}(E_{N}[\ell])/\mathbb{Q}$ is a much smaller extension than it would be otherwise. This makes it feasible to do higher descents on $E_{N}$. In particular, running a 3-descent on $E_{N}$ is feasible, and combining this with a 4-descent, one can write down 12-covers of $E_{N}$ explicitly using Magma, and then point search on them. To give one an idea of what is feasible in this manner, I computed a generator for $E_{N}(\mathbb{Q})$ with $N = 1508233$ (the curve has rank $1$) that has canonical height $1234$. The total computation time was about $90$ minutes.

If the analytic rank of $E_{N}$ is $\geq 2$ (and BSD is true), then in order for a curve to resist this approach, it would have to have rank $\geq 2$ and all of its generators have large canonical height. This suggests the regulator would have to be of size about $10^{6}$.

Note: There is some possibility that the harder cases would be those where the analytic rank is $1$. Once $N$ is large enough, the conductor of $E_{N}$ is big enough that computing $L'(E,1)$ becomes very time consuming (for $N = 1348439$ it takes about $5$ hours or so to compute $L'(E,1)$ and verify it is nonzero). However, something that could be tried in these cases would be to run the Heegner point method described by Elkies in his 1994 paper "Heegner Point Computations" (in the first ANTS proceedings). This is much better than the "standard one", and uses the fact that $E_{1} \cong X_{0}(32)$. If $N = 956693$, $E_{N}$ has rank one, and a generator has canonical height $1692$. I found this generator by using a variant of Elkies's method in 18 minutes.

  • $\begingroup$ If the analytic rank is 1 then it's a theorem that the algebraic rank is 1, right? So it's a theorem that $N$ is congruent. I don't care about the triangle. From the comments above it seems that the question "is the analytic rank is 0 or positive?" has been answered for $N$ up to $10^{12}$. So yes, the question is practical rather than theoretical; I was hoping that someone would pipe up with a comment of the form "I left my computer on for a year computing algebraic ranks, and at one point I noticed that it had spent 2 weeks stuck on one curve, so that's the record". $\endgroup$ May 20, 2016 at 13:45
  • $\begingroup$ Yes, if the analytic rank is $1$, the algebraic rank is $1$. What I was trying to say is that determining that the analytic rank is $1$ (rather than some larger odd number) may be a prohibitively long computation in some cases. $\endgroup$ May 20, 2016 at 13:57
  • 1
    $\begingroup$ Another practical difficulty (which may have dissuaded some from pursuing precisely the question you ask) is that most software is designed to compute the rank, rather than just determine if it is positive. In particular, there is no "early abort" option to Magma's MordellWeilShaInformation that makes it stop once a single point of infinite order is found. $\endgroup$ May 20, 2016 at 13:58
  • $\begingroup$ Yes I agree! In fact that was what dissuaded me this afternoon :-) I was just hoping that some other people over the last decade had more staying power :-) $\endgroup$ May 20, 2016 at 14:36
  • $\begingroup$ PS stupid question: if I run ellanalyticrank on $y^2=x^3-N^2x$ on pari, with $N=10^6+1$, it takes under a minute to tell me that the analytic rank is 2. I was expecting far more pain given you "prohibitively long" comment above. Is this curve special or have I missed your point? Is the point that the height of the Heegner point is much smaller in my case than in the cases you're worrying about? $\endgroup$ May 20, 2016 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.