25
$\begingroup$

I am looking for algorithms on how to find rational points on an elliptic curve $$y^2 = x^3 + a x + b$$ where $a$ and $b$ are integers. Any sort of ideas on how to proceed are welcome. For example, how to find solutions in which the numerators and denominators are bounded, or how to find solutions with a randomized algorithm. Anything better than brute force is interesting.

Background: a student worked on the Mordell-Weil theorem and illustrated it on some simple examples of elliptic curves. She looked for rational points by brute force (I really mean brute, by enumerating all possibilities and trying them). As a continuation of the project she is now interested in smarter algorithms for finding rational points. A cursory search on Math Reviews did not find much.

Improve this question
$\endgroup$
3
  • 5
    $\begingroup$ My understanding is that there is no known algorithm which is guaranteed to find the rational points on an elliptic curve. Section 4.2 of Poonen's survey www-math.mit.edu/~poonen/papers/millennial.pdf briefly discusses what is known and has references. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 13, 2010 at 14:22
  • 7
    $\begingroup$ Qiaochu, you are right in principle. But if one is only interested in the practical matter of finding points, rather than the well-foundedness of the methods, then there are algorithms. More precisely, if you believe the Birch and Swinnerton-Dyer conjecture, then there are efficient algorithms that are guaranteed to terminate. The analytic rank (which is computable in practice) will tell you how many points you need to find and the regulator (on which you get a bound from the leading coefficient of the L-function at s=1) will tell you where to look for them, i.e. will give you height bounds. $\endgroup$
    – Alex B.
    Commented Oct 13, 2010 at 15:15
  • $\begingroup$ My answer to this question was non-sense, as kindly pointed out by Chris Wuthrich, so I deleted it, lest people get confused. I was talking about modular symbols, which were used by Cremona to generate his database of elliptic curves, but this has nothing to do with the present question. Sorry about that, I should stop posting so late at night! $\endgroup$
    – Alex B.
    Commented Oct 13, 2010 at 17:45

5 Answers 5

Reset to default
10
$\begingroup$

A good reference to get started from the algorithmic point of view is Chapter 3 of Cremona's Algorithms for Modular Elliptic Curves. It contains a good deal of pseudocode which explains how Cremona's C++ package mwrank computes rational points on elliptic curves.

Some of the more intricate details, such as second descents are left to Cremona's papers here. Given an elliptic curve with coefficients that aren't too big, your best bet to quickly find the points you're looking for will probably be to use mwrank as included in Sage.

As has been explained to me in the comments. Sage is not the only way to get access to mwrank and the other programs that make up Cremona's elliptic curve library (eclib), but it is arguably the easiest way to get it, and it contains much more elliptic curve functionality, such as the method E.analytic_rank() which if run on elliptic curve of reasonably sized conductor, will return an integer that is proBably the analytic rank of the curve.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Regarding "Sage over the standalone version of mwrank": In fact, Cremona has even deprecated the standalone version. See the note here: warwick.ac.uk/~masgaj/mwrank Also, it is worth mentioning Denis Simon's algebraic 2-descent code, which is also in Sage, and can be fast in certain case. $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:14
  • 5
    $\begingroup$ A late postscript to comment on William Stein's comment. The only thing deprecated is my distribution of mwrank independently, either as source code or as a binary, since the source code is 100% included in Sage's distribution, and to run it when you have Sage is as simple as typing "sage -mwrank" if you want to. This makes life simpler for me, which his a good thing (at least for me). I still use mwrank stand-alone myself (hardly surprising). Secondly, Jamie's remark about mwrank in Sage being more up to date is simply nonsensical. $\endgroup$
    – John Cremona
    Commented Feb 4, 2012 at 17:37
  • 1
    $\begingroup$ Thanks for clarifying that John. I'm sorry was confused about that. $\endgroup$
    – James Weigandt
    Commented Jul 5, 2012 at 19:10
  • $\begingroup$ @JamesWeigandt given link is not working $\endgroup$
    – Guruprasad
    Commented Dec 3 at 20:28
10
$\begingroup$

There is a whole industry devoted to this. The basic method is by descent, which is a formalized version of the infinite descent proofs of Fermat and Euler. It helps if there are rational 2-torsion points but it's not essential. Chapter X in Silverman's The Arithmetic of Elliptic Curves is called "Computing the Mordell-Weil group". It has lots of good information, but maybe isn't so easy for a beginner due to its heavy use of group cohomology.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ A beginner would be much better off starting off with "Rational Points on Elliptic Curves" by Silverman and Tate (aka Tate's Haverford Lectures). $\endgroup$
    – Victor Miller
    Commented Oct 14, 2010 at 1:32
  • 2
    $\begingroup$ Having seen many beginners learn about the descent algorithm, both from the perspective of Silverman-Tate and Galois cohomology, I think it's probably better for even a beginner to just learn Galois cohomology and learn descent the right way. All the notation and equations in the presentation in Silverman-Tate really obscure what is going on, in my experience. $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:37
10
$\begingroup$

There are clever ways of speeding the brute force enumeration. An implementation of such is M. Stoll's ratpoints program: http://www.mathe2.uni-bayreuth.de/stoll/programs/index.html

A completely different way of generating points on elliptic curves is to use Heegner points, but it only works when the rank is one. This is technically more sophisticated but I believe there are also implementations. Google yields: http://www.math.mcgill.ca/darmon/programs/programs.html

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ I agree best with this answer. The descents (as in Robin's answer) tell us that in order to find rational points on an elliptic curve, we better search on one of its torsors. But in the end, we have to do some "brutal search" and that is where the crucial improvements in ratpoints are useful. ... and the only other known method to find rational points is by modularity, say by using Heegner points or variants of them, or (as Pollack and Kurihara do) using supersingular Iwasawa theory. But all of them only work when the analytic rank is 1. $\endgroup$
    – Chris Wuthrich
    Commented Oct 13, 2010 at 17:01
  • $\begingroup$ Finally one should add that it is easy to find the torsion points, if there are any. Most of this is implemented in magma and lots of it in sage. $\endgroup$
    – Chris Wuthrich
    Commented Oct 13, 2010 at 17:02
  • 1
    $\begingroup$ A very recent version of ratpoints is in Sage. Inputing "import sage.libs.ratpoints as r; r.ratpoints([46224, -3024, 0, 1], 200)" will output lots of points on the curve $y^2 = x^3 - 3024x + 46224$, such as [(1, 0, 0), (-60, 108, 1), (-60, -108, 1), (-32, 332, 1), ...] $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:20
  • 2
    $\begingroup$ Here's an example of finding a point on a rank one curve in Sage using Heegner points: "E = EllipticCurve('37a'); P = E.heegner_point(-7); P.point_exact()". The rank 1 curve $y^2=x^3+7823$ provides a spectacular example in which Heegner points fail in practice, but doing a FOUR descent succeeds. Michael Stoll wrote a paper about this, but I can't find it online anymore (it vanished from his website), so here is a temporary link: wstein.org/home/wstein/tmp/4-descent.pdf Also, having read the ancient Peter Green Heegner points program you link above, I do not recommend it. $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:28
  • $\begingroup$ @WilliamStein: I know this is an old comment, but I find your rank 1 curve $$y^2 = x^3+7823 = x^3+(48\times163-1)$$ very intriguing. Does the $163$ have anything to do with it? $\endgroup$
    – Tito Piezas III
    Commented Jan 8, 2018 at 15:21
5
$\begingroup$

The best practical solution is to have someone else do the work. You can look up the curve in Cremona's tables, if it is not too large. If it is larger than that, you can use mwrank, a free standing C++ program. I believe that SAGE and MAGMA also both have this functionality, although I couldn't find the syntax in a quick search.

Improve this answer
$\endgroup$
2
  • 3
    $\begingroup$ To compute generators of the Mordell-Weil group of $y^2+a_1xy + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6$, type EllipticCurve([a1,a2,a3,a4,a6]).gens(). If you type print(EllipticCurve([a1,a2,a3,a4,a6]).mwrank()), then you'll see what mwrank did. For more about elliptic curves over the rationals in Sage, see this page: sagemath.org/doc/reference/sage/schemes/elliptic_curves/… $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:16
  • $\begingroup$ @David E Speyer Given link is not working $\endgroup$
    – Guruprasad
    Commented Dec 3 at 20:33
2
$\begingroup$

It is misleading to say "algorithm", really. There are probabilistic algorithms, and then hard cases (evidence of a point of infinite order that is hard to find). See for example http://www.jstor.org/pss/2152939 . I think of Andrew Bremner as one of the experts on the highly numerical side, and you should add his name to John Cremona's.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Charles, there are deterministic algorithms. They often rely on unproven conjectures, but they happen to work very well in practice. Also, probabilistic algorithms are referred to as "algorithms", just as deterministic ones, and I don't quite see what is misleading about this terminology. $\endgroup$
    – Alex B.
    Commented Oct 13, 2010 at 15:18
  • $\begingroup$ You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable? Of course it is misleading here to mix up different kinds of algorithms. Brute force search will find a rational point on a curve if it is exists (partial correctness). A correct algorithm is what people generally mean by something being "algorithmic". A good probabilistic algorithm is typically what is sought in computational number theory, and a good algorithm with correctness proof conditional on some known conjecture is of real interest. $\endgroup$
    – Charles Matthews
    Commented Oct 13, 2010 at 15:52
  • 1
    $\begingroup$ "You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable?" Huh???! What the heck are you talking about? Assuming rank(E)<=1 or Sha(E)[p^oo] finite for one p, or BSD rank is true, then there is a deterministic algorithm to compute E(Q). Without making one of those assumptions, we still don't know. $\endgroup$
    – William Stein
    Commented Nov 20, 2010 at 21:33
  • $\begingroup$ It was something Manin included in an old paper in Russian Mathematical Surveys. Attributed to Shafarevich, if I recall correctly. Manin said "if this is a joke, it is a gloomy one", or suchlike. $\endgroup$
    – Charles Matthews
    Commented Nov 21, 2010 at 8:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .