Enrique,
This can easily be done at the moment, assuming that you want to count
integral points up to a certain height N. If you are looking for all of the
points of something you know has only finitely many, I am not so sure.
I hope the following ramble helps.
sage: A,B,C,D,E,F=[1,0,0,0,0,-1] # integers
sage: R.<x,y>=PolynomialRing(ZZ,2)
sage: f=A*x^2+B*x*y+C*y^2+D*x+E*y+F # C:f=0
sage: X=AffineSpace(ZZ,2)
sage: Y=X.subscheme(f)
sage: bound=100
sage: points=Y.rational_points(ZZ,bound)
sage: len(points)
402
This uses sage's internal method. However, depending on what you need
it for, the following might work better.
The function lazy_rational_points() simply goes through all possible
values a of x, and factors f(a,y) to get the points. Then,
it does the same for the bounded values of y. Note that while this
guarantees enumeration of all of the points of bounded height,
there may be points of greater height in the return.
sage: def lazy_rational_points(f,bound):
... r'''
... Given a polynomial in two variables over ZZ, returns all points
... of bound less <= bound, and the possibly some more points.
... '''
... points=[]
... for a in [(-bound)..(bound)]:
...
xroots=R(f(a,y)).univariate_polynomial().roots(multiplicities=False)
... for b in xroots:
... if points.count([a,b]) < 1:
... points.append([a,b])
...
yroots=R(f(x,a)).univariate_polynomial().roots(multiplicities=False)
... for c in yroots:
... if points.count([c,a]) < 1:
... points.append([c,a])
... return points
The new version is quite fast, comparatively.
sage: f
x^2 - 1
sage: %time
sage: c=lazy_rational_points(f,200)
sage: len(c)
802
CPU time: *0.59 s*, Wall time: 0.62 s
sage: %time
sage: bound=200
sage: points=Y.rational_points(ZZ,bound)
sage: len(points)
802
CPU time: *42.85 s*, Wall time: 51.11 s
Even up to a thousand, quite quickly. I didn't feel like seeing about
the old version.
sage: %time
sage: c=lazy_rational_points(f,1000)
sage: len(c)
4002
CPU time: 5.78 s, Wall time: 7.26 s
Now, for some random tests.
sage: A,B,C,D,E,F=[randint(-1000,1000) for i in range(6)]
sage: R.<x,y>=PolynomialRing(ZZ,2)
sage: f=A*x^2+B*x*y+C*y^2+D*x+E*y+F # C:f=0
sage: X=AffineSpace(ZZ,2)
sage: Y=X.subscheme(f)
sage: bound=100
sage: %time
sage: points=Y.rational_points(ZZ,bound)
sage: print f
sage: print len(points)
190*x^2 - 561*x*y - 507*y^2 - 502*x + 133*y + 21
0
CPU time: *21.26 s*, Wall time: 27.55 s
sage: %time
sage: points1=lazy_rational_points(f,bound)
sage: print f
sage: len(points)
190*x^2 - 561*x*y - 507*y^2 - 502*x + 133*y + 21
0
CPU time: *0.68 s*, Wall time: 0.72 s
Now, a hundred times.
sage: %time
sage: bound=10
sage: for i in [1..100]:
... A,B,C,D,E,F=[randint(-1000,1000) for j in range(6)]
... R.<x,y>=PolynomialRing(ZZ,2)
... f=A*x^2+B*x*y+C*y^2+D*x+E*y+F
... points=Y.rational_points(ZZ,bound)
CPU time: 23.41 s, Wall time: 30.17 s
sage: %time
sage: bound=10
sage: for i in [1..100]:
... A,B,C,D,E,F=[randint(-1000,1000) for j in range(6)]
... R.<x,y>=PolynomialRing(ZZ,2)
... f=A*x^2+B*x*y+C*y^2+D*x+E*y+F
... points=lazy_rational_points(f,bound)
CPU time: 7.23 s, Wall time: 8.86 s
Finally, here is a version that is not lazy: it checks and only returns
points with the correct bound.
sage: def new_rational_points(f,bound):
... r'''
... Given a polynomial in two variables over ZZ, returns all points
... of bound less <= bound, and the possibly some more points.
... '''
... points=[]
... for a in [(-bound)..(bound)]:
...
xroots=R(f(a,y)).univariate_polynomial().roots(multiplicities=False)
... for b in xroots:
... if abs(b) <= bound:
... if points.count([a,b]) < 1:
... points.append([a,b])
...
yroots=R(f(x,a)).univariate_polynomial().roots(multiplicities=False)
... for c in yroots:
... if abs(c) <= bound:
... if points.count([c,a]) < 1:
... points.append([c,a])
... return points
More random tests, now between the two new versions. The performance is
about the same. Thus, if you want to find points, it might be best to use
lazy. However, if you want to study the growth behavior of the counting
function, use new_rational_points.
sage: %time
sage: bound=200
sage: for i in [1..10]:
... A,B,C,D,E,F=[randint(-1000,1000) for j in range(6)]
... R.<x,y>=PolynomialRing(ZZ,2)
... f=A*x^2+B*x*y+C*y^2+D*x+E*y+F
... points=lazy_rational_points(f,bound)
CPU time: 13.60 s, Wall time: 22.57 s
sage: %time
sage: bound=200
sage: for i in [1..10]:
... A,B,C,D,E,F=[randint(-1000,1000) for j in range(6)]
... R.<x,y>=PolynomialRing(ZZ,2)
... f=A*x^2+B*x*y+C*y^2+D*x+E*y+F
... points=new_rational_points(f,bound)
CPU time: 13.50 s, Wall time: 17.14 s
Finally, I tried something with a bigger bound. This took a touch more than
a minute on my 1.5ghz Pentium M, 512meg of ram thinkpad. So, I think that if
you had some real computing power, you could do quite well with this.
sage: A,B,C,D,E,F=[randint(-1000,1000) for j in range(6)]
sage: R.<x,y>=PolynomialRing(ZZ,2)
sage: f=A*x^2+B*x*y+C*y^2+D*x+E*y+F
sage: show(f)
<html><div class="math">652 x^{2} - 639 xy - 569 y^{2} + 899 x - 976 y
+ 545</div></html>
sage: %time
sage: bound=*10000*
sage: points=lazy_rational_points(f,bound)
sage: len(points)
0
CPU time: *68.67 s*, Wall time: 89.74 s
On Jan 15, 2008 12:19 PM, John Cremona <[EMAIL PROTECTED]> wrote:
>
> Finding integral points on an affine curve is not the same as finding
> rational points on the projective model and then scaling!
>
> Quick answer to William's question is "no", since my code always finds
> rational points (and their parametrization). The same sort of thing
> that Simon's gp program does except using a different algorithm.
>
> Example: If Enrique gave us X^2+Y^2=1 then the projective curve
> X^2+Y^2-Z^2=0 has parametric solution (X,Y,Z)=(u^2-v^2,2*u*v,u^2+v^2)
> but going from there to the list of integral points (+-1,+-1) really
> involves number theory and not just algebra. For example, I seem to
> remember that there's a theorem that says that the integral points are
> given by a finte set of parametrizations (and not just one as you need
> for the rational points). That only makes sense when there are
> infitely many integral points of course...Enrique did not actually
> tell us whether his conic was an ellipse (with a finite set of
> integral points) or not, so I'm not sure what kind of answer he
> wanted. Enrique?
>
> John
>
>
> On 15/01/2008, Nick Alexander <[EMAIL PROTECTED]> wrote:
> >
> >
> > On 15-Jan-08, at 8:28 AM, William Stein wrote:
> >
> > >
> > > On Jan 15, 2008 7:39 AM, Enrique Gonzalez Jimenez
> > > <[EMAIL PROTECTED]> wrote:
> > >>
> > >> Hi,
> > >>
> > >> Let C be a plane conic given by an equation of the form
> > >> C:Ax^2+Bxy+Cy^2+Dx+Ey+F=0 where A,B,C,D,E,F in ZZ.
> > >>
> > >> Is there a package or function in SAGE that compute C(ZZ)?
> > >
> > > John Cremona -- is there code in your mwrank package that could do
> > > this??
> >
> > I have recently integrated code to do this for a projective model
> > over QQ, using routines of Denis Simon (qfsolve.gp) and Paul van
> > Wamelen. I believe this helps answer the problem over ZZ -- is it
> > not just a matter of scaling projective points?
> >
> > This code is close to being ready for Sage, and I could cut a pre-
> > production patch if that would help. In fact, I would appreciate
> > someone using the code.
> >
> > Nick
> >
> > >
> >
>
>
> --
> John Cremona
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
