Integer points of an elliptic curve

[Jaakko Seppälä]

I read from http://mathoverflow.net/questions/7907/elliptic-curves-integer-points
than Sage can determine the integer points of an elliptic curve. What
commands will do the trick?

[Yann]

From the example you give:

2x**3+385x**2+256x-58195=3y**2 , over the rational field

it's not direct because sage does not handle general cubic equation
yet.
In sage, let's define:
{{{
sage: R.<x,y> = QQ[]
sage: P = 2*x**3 + 385*x**2 + 256*x - 58195 - 3*y**2
}}}
Given an equation

A6 + A4 x + A3 y + A2 x**2 + A1 xy + A5 y**2 + A7 x**3 = 0.

You can obtain do by hand the change of variables Q(x' , y' ) = P( -
x*A5*A7 , y * A7**2 * A5 ) / ( A5**3 * A7**4 )
a simplified equation:
{{{
sage: Q = P( x=-x*(-3)*2 , y=y*2**2*(-3) ) / ( (-3)**3*2**4 )
sage: Q
-x^3 - 385/12*x^2 + y^2 - 32/9*x + 58195/432
}}}

You can then define the elliptic curve and compute integral points
{{{
sage: E = EllipticCurve(Q)
sage: time pts = E.integral_model().integral_points()
CPU times: user 2.74 s, sys: 0.02 s, total: 2.76 s
Wall time: 7.58 s
}}}

at this point, you need to come back to the original curve, removing
solutions not integral after the inverse change of variables

{{{
sage: x_coords = [ x/6 for x,y,z in pts if 6.divides(ZZ(x)) ]
sage: x_coords
[-191, -157, -67, -49, -23, -19, 19, 23, 61, 103, 521, 817, 3857,
10687, 276251]
}}}

On Dec 6, 6:41 pm, Jaakko Seppälä <jaakko.j.sepp...@gmail.com> wrote:
> I read fromhttp://mathoverflow.net/questions/7907/elliptic-curves-integer-points

[Jaakko Seppälä]

I tried this. Do I need include some package in Sage. I have
sage3.0.5dfsg-4ubuntu1 installed via apt-get. I got this output

sage: time pts = E.integral_model().integral_points()

---------------------------------------------------------------------------
AttributeError Traceback (most recent call
last)

/home/jaakko/Desktop/<ipython console> in <module>()

/usr/lib/pymodules/python2.5/IPython/iplib.pyc in ipmagic(self, arg_s)
1180 else:
1181 magic_args = self.var_expand(magic_args,1)
-> 1182 return fn(magic_args)
1183
1184 def ipalias(self,arg_s):

/usr/lib/pymodules/python2.5/IPython/Magic.pyc in magic_time(self,
parameter_s)
1969 else:
1970 st = clk()
-> 1971 exec code in glob
1972 end = clk()
1973 out = None

/home/jaakko/Desktop/<timed exec> in <module>()

AttributeError: 'EllipticCurve_generic' object has no attribute
'integral_model'

[Alex Ghitza]

On Sun, Dec 06, 2009 at 04:23:35PM -0800, Jaakko Sepp�l� wrote:
> I tried this. Do I need include some package in Sage. I have
> sage3.0.5dfsg-4ubuntu1 installed via apt-get. I got this output

Hi Jaakko,

The version of Sage that's packaged in Debian in Ubuntu (3.0.5) is
quite old by now. The current stable version is 4.2.1, and in the
meantime there have been a lot of changes and additions, including to
elliptic curves. I suggest that you download a recent Ubuntu binary
from sagemath.org, or that you download the source code and build Sage
yourself (this takes some time though).

Definitely let us know if you're having any trouble installing a
recent version, or if there are other features that you would like to
have regarding elliptic curves.


Best,
Alex


--
Alex Ghitza -- Lecturer in Mathematics -- The University of Melbourne
-- Australia -- http://www.ms.unimelb.edu.au/~aghitza/

[Jaakko Seppälä]

Hello again!

Is that method general? I tried now to find the integer points of x^3
- 3*x*y^2-y^3-1 without success.

Jaakko

sage: R.<x,y> = QQ[]

sage: P = x^3 - 81/4 + y^2
sage: E=EllipticCurve(P)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call
last)

/home/jaakko/Matikka/sage-4.2.1-linux-Ubuntu_9.10-i686-Linux/<ipython
console> in <module>()

/home/jaakko/Matikka/sage-4.2.1-linux-Ubuntu_9.10-i686-Linux/local/lib/
python2.6/site-packages/sage/schemes/elliptic_curves/constructor.pyc
in EllipticCurve(x, y, j)
214 return EllipticCurve([a1, a2, a3, a4, a6])
215 except AssertionError:
--> 216 raise NotImplementedError, "Construction of an
elliptic curve from a generic cubic not yet implemented."
217
218 if rings.is_Ring(x):

NotImplementedError: Construction of an elliptic curve from a generic
cubic not yet implemented.
sage: P = x^3 - 3*x*y^2-y^3-1
sage: E=EllipticCurve(P)
---------------------------------------------------------------------------
NotImplementedError Traceback (most recent call
last)

/home/jaakko/Matikka/sage-4.2.1-linux-Ubuntu_9.10-i686-Linux/<ipython
console> in <module>()

/home/jaakko/Matikka/sage-4.2.1-linux-Ubuntu_9.10-i686-Linux/local/lib/
python2.6/site-packages/sage/schemes/elliptic_curves/constructor.pyc
in EllipticCurve(x, y, j)
186 elif len(f.parent().gens()) == 2 or len(f.parent().gens
()) == 3 and f.is_homogeneous():
187 # We'd need a point too...
--> 188 raise NotImplementedError, "Construction of an
elliptic curve from a generic cubic not yet implemented."
189 else:
190 raise ValueError, "Defining polynomial must be a
cubic polynomial in two variables."

NotImplementedError: Construction of an elliptic curve from a generic
cubic not yet implemented.

On Dec 7, 1:42 am, Yann <yannlaiglecha...@gmail.com> wrote:

[John Cremona]

The integer points function applies to elliptic curves which in Sage
are implemented via the EllipticCurve constructor. Note that elliptic
curves in Sage are always given by Weierstrass equations.

sage: E = EllipticCurve([0,0,1,-7,6])
sage: E.rank()
3
sage: E.integral_points()

[(-3 : 0 : 1),
(-2 : 3 : 1),
(-1 : 3 : 1),
(0 : 2 : 1),
(1 : 0 : 1),
(2 : 0 : 1),
(3 : 3 : 1),
(4 : 6 : 1),
(8 : 21 : 1),
(11 : 35 : 1),
(14 : 51 : 1),
(21 : 95 : 1),
(37 : 224 : 1),
(52 : 374 : 1),
(93 : 896 : 1),
(342 : 6324 : 1),
(406 : 8180 : 1),
(816 : 23309 : 1)]

Your example is a more general plane cubic. There is some
functionality for converting those into Weierstrass equations but
currently it just calls the appropriate Magma function (so only works
if you have Magma installed). But note that the change of model
changes the definition of "integral", so it would not be a solution to
your problem to find all the integer points on the W. model and map
them back.

I do not know of any implementation anywhere which applies to more
general models.

John Cremona

[John Cremona]

PS Your second example is a Weierstrass model but not integral:


sage: E = EllipticCurve([0,0,0,0,-81/4])
sage: E.integral_points()
---------------------------------------------------------------------------
...
ValueError: integral_points() can only be called on an integral model

But you can do this:

sage: E1 = E.integral_model(); E1
Elliptic Curve defined by y^2 = x^3 - 1296 over Rational Field
sage: E1.integral_points()
[(193 : 2681 : 1)]

and also this:

sage: E1.S_integral_points([2])
[(193 : 2681 : 1)]

which I think shows taht the only integral (or {2}-integral) solution
to your equation is x=193, y=2681. Does that help?

To see the documentation create an elliptic curve E (as above, say, or
try EllipticCurve? to see other ways), and then do
E.integral_points? or E.S_integral_points?

John Cremona

[Yann]

The general method is called Naggel's algorithm.

Take a look at http://www.math.mcgill.ca/connell/public/ECH1/c1.ps
(1.4)

[Yann]

You might also take a look at the full book www.ucm.es/BUCM/mat/doc8354.pdf

And of course, it's only a method to go from a general cubic equation
to a weierstrass form, net a general method th find integral points.

On Dec 7, 6:24 pm, Yann <yannlaiglecha...@gmail.com> wrote:
> The general method is called Naggel's algorithm.
>

> Take a look athttp://www.math.mcgill.ca/connell/public/ECH1/c1.ps

[Jaakko Seppälä]

On Dec 7, 7:21 pm, John Cremona <john.crem...@gmail.com> wrote:
> PS Your second example is a Weierstrass model but not integral:
>
> sage: E = EllipticCurve([0,0,0,0,-81/4])
> sage: E.integral_points()
> ---------------------------------------------------------------------------
> ...
> ValueError: integral_points() can only be called on an integral model
>
> But you can do this:
>
> sage: E1 = E.integral_model(); E1
> Elliptic Curve defined by y^2 = x^3 - 1296 over Rational Field
> sage: E1.integral_points()
> [(193 : 2681 : 1)]
>
> and also this:
>
> sage: E1.S_integral_points([2])
> [(193 : 2681 : 1)]
>
> which I think shows taht the only integral (or {2}-integral) solution
> to your equation is x=193, y=2681.  Does that help?

I think it might help but I don't know the theory of algebraic curves
so much that I can give a valid proof of the integer points. I found
the problem at http://www.mathlinks.ro/viewtopic.php?t=150659 where
one solution was given but I was wondering if there is some other way
to find the integer points. However, I haven't found any proof which
uses advanced methods.

Jaakko

[Yann]

If you want solution for this precise equation, look for "thue
equation".
The thue equations are some of the few for which there exists
efficient methods.

for example in PARI/GP (from sage with gp_console())

sage: gp_console()
GP/PARI CALCULATOR Version 2.3.3 (released)
[snip]
PARI/GP is free software, covered by the GNU General Public License,
and
comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 8000000, primelimit = 500000
? t = thueinit(x^3-3*x-1) \\ corresponds to the homogenized
x^3-3*x*y^2-y^3
? thue(t,1) \\ solve with rhs = 1
%2 = [[-3, 2], [-1, 1], [0, -1], [1, -3], [2, 1], [1, 0]]


PS: this might be wrapped in SAGE, I didn't checked.

[John Cremona]

The topic of integer points on elliptic curves is a big and
interesting one, which should probably be discussed in sage-nt rather
than sage-support (if one sage-* at all!). So I will be brief.

This is NOT about the Nagel-Lutz Theorem. That says that points of
finite order on elliptic curves (defined over Q by Weierstrass
equations with a mild restriction) are integral and also satisfy a
simple condition on the y-coordinate. but this does NOT tell you how
to find all integral points, since in general integral points may have
infinite order.

The fact that the number of integral points is finite is a special
case of a theorem of Siegel. There are essentially two ways to tackle
it: as a purely Diophantine problem (which leads to Thue equations
and the like); or, using Mordell-Weil bases and elliptic logarithms +
LLL. the latter works very well provided that the MW basis can be
found, and that is what has been implemented in Sage. (There is also
a more general method for finding all S-integral points.)

There is a huge literature on all this, which is not at all
elementary; the theory was mainly worked out in the 1990s, and is
mainly for elliptic curves given by integral Weierstrass models (with
also some work on equations of the form y^2=quartic). Note that it
only makes sense to ask about integral points on an affine curve, as
opposed to a projective one.

For a very clear treatment of the simplest case of integral points
over Q I would recommend section 8.7 in volume 1 of Henri Cohen's book
Number Theory (Vol 1: Tools and Diophantine Equations), GTM 239.

John Cremona