I assumed that Enrique wanted *all* integral points (in some sense
when there are infinitely many).
For listing rational (or integral) points up to some height bound
there are methods which are vastly more efficient than the one being
proposed here, which does not even use a quadratic sieve. Optimal
(for any kind of variety, not just curves, not just plane curves, not
just conics) are the p-adic lattice reduction methods (sometimes known
as "p-adic Elkies" by analogy with the real -- as opposed to p-adic--
version first proposed by Elkies around 2000.
Implementing this in Sage should be put onto our
useful-projects-for-students list.
John
On 16/01/2008, D. Benjamin Antieau <[EMAIL PROTECTED]> wrote:
> 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
> >
> >
> >
> > > >
> >
>
--
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/
-~----------~----~----~----~------~----~------~--~---
