Here the references which I know:
1. Elkies ANTS paper:
\bibitem{Elkies}
N. D. Elkies.
\newblock Rational points near curves and small nonzero $|x^3 - y^2|$
via lattice reduction.
\newblock In ANTS IV proceedings (W.~Bosma, ed.), LNCS
{\bf1838}. Springer-Verlag,
2000, pages 33--63.
2. Notes by Mark Watkins for a talk given by Michael Stoll at a
meeting in Bremen summer 2005:
http://www.maths.bris.ac.uk/~mamjw/papers/padic.ps
3. PhD thesis of Rachel Long, 2006 (not available online) (only treats
quadric intersections in P^3):
\bibitem{Long}
R. Long.
\newblock The algorithmic solution of simultaneous Diophantine equations.
\newblock PhD thesis, Oxford Brookes University, 2006.
4. PhD thesis of David Roberts (Nottingham 2007), mainly about the
function field analogue, not yet online as it is being revised after a
successful viva; but the relevant part is in:
5. J E Cremona and D A Roberts, "Applications of polynomial lattices
to point-finding over rational function fields", progress report &
draft preprint.
I'll send you the latter off-list as it is not ready for distribution;
it is my attempts to understand and make rigorous most of the
preceding, and is only for curves and only has full details when the
ambient space is of dimensions 2 or 3.
It is also worth looking at the magma source
/home/src/magma/package/Geometry/Arith/locsol.m which is much more
general, and written by Nils Bruin who reads sage-devel, so probably
makes all the preceding redundant. Nils, do you have a version of
that which you could legally donate to Sage?
John
On 16/01/2008, D. Benjamin Antieau <[EMAIL PROTECTED]> wrote:
> 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
> >
> >
>
>
> >
>
--
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/
-~----------~----~----~----~------~----~------~--~---
