John,
Do you have a reference for p-adic Elkies? I would be interested in looking
at that, and possibly implementing it in as much generality as possible in
sage.
Ben
On Jan 16, 2008 3:15 AM, John Cremona <[EMAIL PROTECTED]> wrote:
>
> 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/
-~----------~----~----~----~------~----~------~--~---
