How to find all integer points on an elliptic curve? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T17:13:11Z http://mathoverflow.net/feeds/question/7907 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve How to find all integer points on an elliptic curve? amateur algebraist 2009-12-05T22:09:21Z 2009-12-07T17:42:13Z <p>How can I determine the integer points of a given elliptic curve if I know its rank and its torsion group? </p> <p>I read same basic books on elliptic curves but as a non-professional I didn't understand everything. Is it true that if rank is 0 and torsion group is isomorphic to a group of order \$n\$ then the number of integer points is \$n-1\$? And what is a good reference to learn to determine the integer points if the rank is positive? </p> <p>I tried to read the book Rational Points on Elliptic Curves but I didn't found an explicit algorithm. I just heard something like take some point and use group law to find the rest. But how can I be sure that I have found every point?</p> <p>The curve I had on my mind is \$2x^3 + 385x^2 + 256x - 58195 = 3y^2\$. I'm not even sure if this is an elliptic curve. I mean why it is projective and why it is isomorphic to a closed subvariety of \$\mathbb{P}_{\mathbb{Q}}^2\$? And why it contain the priviledged rational point \$(0,1,0)\$? </p> http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve/7912#7912 Answer by Steve Huntsman for How to find all integer points on an elliptic curve? Steve Huntsman 2009-12-05T22:36:55Z 2009-12-05T22:36:55Z <p>No point reinventing the wheel. Use Cremona's table seven on</p> <p><a href="http://www.warwick.ac.uk/staff/J.E.Cremona/ftp/data/INDEX.html" rel="nofollow">http://www.warwick.ac.uk/staff/J.E.Cremona/ftp/data/INDEX.html</a></p> http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve/7973#7973 Answer by Kevin O'Bryant for How to find all integer points on an elliptic curve? Kevin O'Bryant 2009-12-06T07:03:46Z 2009-12-06T07:03:46Z <p>This is handled (with explicit examples) in Nigel Smart's "The algorithmic resolution of diophantine equations." Chapter VII.4, in particular, gives a method for producing finitely many Thue equations whose integer solutions contain the integer solutions to the given elliptic equation.</p> <p>Computationally, the bottleneck is finding a system of fundamental units for the splitting field.</p> http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve/7979#7979 Answer by Kevin Buzzard for How to find all integer points on an elliptic curve? Kevin Buzzard 2009-12-06T07:54:40Z 2009-12-06T14:40:21Z <p>Finding all the integral points on an elliptic curve is a non-trivial computational problem. You say you are a "non-professional" so here is a non-professional answer: get hold of some mathematical software that does it for you (e.g. MAGMA), and then let it run until it either finds the answer or runs out of memory. Alternatively, do what perhaps you should have done at the start if you just have one curve and want to know the answer: post the equation of the curve, and hope that someone else does it for you. Here's another example of an algorithm currently used in these sorts of software (a Thue one was mentioned above but here's a different approach): find generators for the group (already computationally a bit expensive at times, depending on your luck and/or the size of sha), invoke Baker-like theorems saying "if the coordinates of the point are integral then it must be of the form sum_i n_i P_i with the n_i at most ten to the billion", and then use clever congruence techniques to massively cut down the search space by giving strong congruences for all the n_i. Then just do a brute force search. </p> <p>Whether or not this will work for you, I cannot say, because it all depends on how big the coordinates of your curve are. The only clue you give so far is that the conductor is "bigger than 130000" [Edit: that was written before the OP edited the question to tell us which curve he was interested in] which of course does not preclude it being bigger than 10^10^10. Also, you need an expert to decide which of the algorithms is best for you. I'd rather do a massive amount of arithmetic in a field of tiny discriminant than a small amount of arithmetic in a field whose discriminant is so large that I can't even factor it, for example.</p> <p>So in short the answer is that you're probably not going to be able to do it with pencil and paper, but there are programs around that will do it, if all you want to know is the answer.</p> <p>EDIT: you posted the equation of the curve. Magma V2.15-10 says the integral points are</p> <p>[ &lt;-23, -196>, &lt;19, 182>, &lt;61, 784>, &lt;-191, 28>, &lt;103, -1442>, &lt;-19, -144>, &lt;-67, 592>, &lt;23, 242>, &lt;-49, -454>, &lt;-157, -742>, &lt;817, 21196>, &lt;521, 11364>, &lt;3857, 200404>, &lt;10687, -910154>, &lt;276251, -118593646> ]</p> <p>plus what you get if you change all the y's to -y's.</p> http://mathoverflow.net/questions/7907/how-to-find-all-integer-points-on-an-elliptic-curve/8119#8119 Answer by John Cremona for How to find all integer points on an elliptic curve? John Cremona 2009-12-07T17:42:13Z 2009-12-07T17:42:13Z <p>The following Sage code (which I ran with Sage 4.2.1) produces the solutions (and agrees with Magma!):</p> <pre><code>E = EllipticCurve([0, 1155,0,4608,-6285060]) E1 = E.minimal_model() pts1 = E1.S_integral_points([2,3]) iso = E1.isomorphism_to(E) pts = [iso(P) for P in pts1] solutions = [(x/6,y/18) for (x,y,z) in pts] solutions = [(x,y) for (x,y) in solutions if x.is_integral() and y.is_integral()] solutions </code></pre> <p>Before the first line I used pencil-and-paper to scale the equation to be in Weierstrass form (monic in both X and Y) which involves new variables 6X and 18Y; the solutions a rescaled at the end. In fact we found all S-integral solutions with S={2,3}, i.e. all solutions which are integral except at 2 and 3. (There are 32 of these, of which only 15 are really integral).</p> <p>John Cremona</p>