A patch is up for review now at https://trac.sagemath.org/ticket/22063
On 15 December 2016 at 17:02, John Cremona <[email protected]> wrote: > Without going so far as to use interval arithmetic (which leads to at > least one annoying problem: the RealIntervalField in Sage has no > is_square() methods which is enough to make it hard to work with as > far as creating points on elliptic curves is concerned) I came up with > a better solution. > > I will create a trac ticket for this. Briefly, I replaced the small > function which took a real point and decided whether or not it was > integral. It used to test whether the x and y coordinates were > withing some (arbitrary) epsilon of the nearest integer. Now it just > rounds them and tests if they resulting integers satisfy the curve's > defining equation. This is a lot more robust, and now all the test > cases from Zagier's paper succeed *without increasing precision from > 100 bits*. > > John > > On 15 December 2016 at 16:06, John Cremona <[email protected]> wrote: >> On 15 December 2016 at 14:52, <[email protected]> wrote: >>> @John : Good point. The change in precision, at least seems to fix the >>> previous problems (at least in the specific examples). >>> I suppose, this is the precision that is used to bound the coefficients of >>> the linear form of elliptic logarithms (?) >>> If this is the case, and I remember right, this precision varies and there >>> are some relations to get the "right" precision. >>> I checked the book of Tzanakis : Elliptic Diophantine Equations, and >>> provides some relations on how to choose the precision on the computation of >>> elliptic logarithms ( relations (10.7) and (9.10)) >>> Maybe computing each time the right precision is not very efficient. >>> >> >> No, it is simpler and more stupid than that. In the serious part of >> the computation where we deal with elliptic logs, precision is dealt >> with in (I hope) a more intelligent way. Here it is just computing >> all linear combinations sum(n_i*P_i) for all r-tuples (n_1,...,n_r) >> with all |n_i| up to some bound and testing for integrality; and -- as >> William notes -- it is doing that over R rather than Q as it is much >> faster. And the "decision" to do that with 100 bits of precision was >> an arbitrary choice I made about 8 years ago based on no analysis at >> all -- my bad. >> >> Interval arithmetic would certainly be good; I will have a quick >> attempt at that but don't have time to put much work into it. >> >> John >> >>> I don't know if that helps. >>> >>> Costas >>> >>> >>> On Thursday, December 15, 2016 at 4:37:59 PM UTC+2, William wrote: >>>> >>>> On Thu, Dec 15, 2016 at 4:51 AM, Dima Pasechnik <[email protected]> wrote: >>>> > >>>> > >>>> > On Thursday, December 15, 2016 at 12:23:15 PM UTC, John Cremona wrote: >>>> >> >>>> >> I just confirmed that if I change RealField(100) to RealField(200) in >>>> >> one place (line 6975 of ell_rational_field.py) then both the points >>>> >> Costas missed are found, so I was right that this is a stupid problem >>>> >> of precision rather than something more complicated. >>>> >> >>>> >> I can easily make a patch to make this change, but if I do there will >>>> >> be two objections (at least): first, that I have done no analysis to >>>> >> see whether 200 bits will always work (clearly not) so this is just >>>> >> kicking a problem down the road; and secondly that I will nopt have >>>> >> fixed other known problems, as I explained earlier. >>>> >> >>>> >> I tried all the examples in Zagier's paper (Tables 1-3 except the >>>> >> non-standard examples in Table 3) using 1000 bits (which is not >>>> >> noticeably slower than 100 -- note that first the algorithm finds a >>>> >> Mordell-Weil basis which often dominates). All work fine and very >>>> >> quickly. >>>> > >>>> > >>>> > I am just wondering whether some kind of interval or ball arithmetic >>>> > ought to be used there (we do have Arb package in Sage nowadays), >>>> > instead of blindly increasing precision? >>>> >>>> Without looking, the computation is "Otherwise it is very very much >>>> faster to first compute the linear combinations over RR, and only >>>> compute them as >>>> rational points if they are approximately integral." This does seem >>>> like a perfect situation in which to apply standard interval >>>> arithmetic over RR. >>>> We're just applying algebraic operations to points purely to speed up >>>> an algorithm, then checking at the end if the resulting coordinates >>>> could possibly be integers... >>>> >>>> - William >>>> >>>> >>>> > >>>> > >>>> >> >>>> >> >>>> >> John >>>> >> >>>> >> On 15 December 2016 at 09:17, John Cremona <[email protected]> wrote: >>>> >> > On 14 December 2016 at 21:34, <[email protected]> wrote: >>>> >> >> Thank you both for the answers, >>>> >> >> >>>> >> >> I found another problematic example >>>> >> >> >>>> >> >> sage:E1=EllipticCurve([0,0,0,37,18]);E1;S=E1.integral_points();S; >>>> >> >> Elliptic Curve defined by y^2 = x^3 + 37*x + 18 >>>> >> >> over Rational Field >>>> >> >> [(2 : 10 : 1), (126 : 1416 : 1)] >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> and >>>> >> >> >>>> >> >> R = E1(64039202,512470496030);M=E1(2,10 );3*M==R >>>> >> >> True >>>> >> >> >>>> >> >> Both examples are from the paper >>>> >> >> of Don Zagier: Large integral points on Elliptic curves >>>> >> >> >>>> >> >> Also, I tried the previous examples in the online calculator of >>>> >> >> magma >>>> >> >> and >>>> >> >> seems that magma works fine. >>>> >> >> >>>> >> >> magma: E := EllipticCurve([0,0,0,37,18]); >>>> >> >> IntegralPoints(E); >>>> >> >> [ (2 : 10 : 1), (126 : 1416 : 1), (64039202 : 512470496030 : 1) ] >>>> >> >> [ <(2 : 10 : 1), 1>, <(126 : 1416 : 1), 1>, >>>> >> >> <(64039202 : 512470496030 : 1), 1> ] >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> I use this function a lot and >>>> >> >> I think many people (heavily) use this function >>>> >> >> for their research. I was not aware of the problems of this function >>>> >> >> :( >>>> >> >> >>>> >> >> I am wondering if this bug affects other functions concerning >>>> >> >> elliptic curves? >>>> >> > >>>> >> > The only other functions I can think of are >>>> >> > EllipticCurves_with_good_reduction_outside_S() which uses the more >>>> >> > general S-integral points code, which potentially suffers from >>>> >> > similar >>>> >> > problems and more (it uses p-adic elliptic logs for example, and >>>> >> > p-adic precision matters). But that does not use the function I >>>> >> > mentioned for which real precision seems to be a problem. >>>> >> > >>>> >> > Nils: of course I know you were not jibing at me! >>>> >> > >>>> >> > Costas: thanks for pointing this out, and the extra exmaples. I know >>>> >> > Zagier's paper well, and we should certainly include the examples >>>> >> > from >>>> >> > that paper as doctests where possible. >>>> >> > >>>> >> > Regarding Magma comparison: the Sage code was written in 2008 by two >>>> >> > masters' students under my supervision, though it has had some >>>> >> > attention since then. At that time I was systematically testing >>>> >> > against Magma, and in the process we found many cases where our >>>> >> > developing code missed points and many more where Magma missed >>>> >> > points. >>>> >> > All of these were duly reported to Steve Donelly (of Magma). As a >>>> >> > result, Sage ended up with a not-too-bad implementation, and Magma's >>>> >> > was vastly improved: Steve essentially completely rewrote Magma's >>>> >> > original code using many new ideas, which he has sadly not written up >>>> >> > and so are not available to the rest of the world. >>>> >> > >>>> >> > To give a small idea of the problems I have been trying to address >>>> >> > (see https://trac.sagemath.org/ticket/10973). The Sage >>>> >> > implementation >>>> >> > for integral points over Q (but not S-integral points) follwed >>>> >> > closely >>>> >> > the account in Henri COhen's book, which in turn follwed Smart's >>>> >> > book. >>>> >> > But there are errors in those, arising from Smart's incorrect use of >>>> >> > formulas from a paper of Sinnou David (literally he and David have >>>> >> > opposite conventions for the periods of an elliptic curve, one has >>>> >> > w1/w2 in the fundmental region and the other has w2/w1). I noticed >>>> >> > that 2 years ago, or possibly 3, but it has been so caught up in >>>> >> > other >>>> >> > issues on that ticket (including some more glaring gaps in Smart's >>>> >> > account of integral points over number fields) that it has not yet >>>> >> > been finished. >>>> >> > >>>> >> >> >>>> >> >> Thanks again for the answers >>>> >> > >>>> >> > You are welcome, >>>> >> > >>>> >> > John >>>> >> > >>>> >> >> Costas. >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> >>>> >> >> On Wednesday, December 14, 2016 at 10:25:25 PM UTC+2, Nils Bruin >>>> >> >> wrote: >>>> >> >>> >>>> >> >>> On Wednesday, December 14, 2016 at 12:09:36 PM UTC-8, John Cremona >>>> >> >>> wrote: >>>> >> >>>> >>>> >> >>>> >>>> >> >>>> Thanks for the bug report. As Nils pointed out there are known >>>> >> >>>> bugs >>>> >> >>>> in the integral point code which cause solutions to be missed. >>>> >> >>> >>>> >> >>> >>>> >> >>> Just to make clear: I wasn't taking a jibe at sage/or John on this, >>>> >> >>> and I >>>> >> >>> wasn't previously aware there are bugs in the integral points code >>>> >> >>> in >>>> >> >>> Sage. >>>> >> >>> I was just observing that in the past 20 years, any computer >>>> >> >>> algebra >>>> >> >>> package >>>> >> >>> that implements integral point finding on elliptic curves has had >>>> >> >>> significant errors (of the type reported here). Apparently it's >>>> >> >>> something >>>> >> >>> that is particularly hard to get reliably correct. >>>> >> >> >>>> >> >> -- >>>> >> >> You received this message because you are subscribed to the Google >>>> >> >> Groups >>>> >> >> "sage-support" group. >>>> >> >> To unsubscribe from this group and stop receiving emails from it, >>>> >> >> send >>>> >> >> an >>>> >> >> email to [email protected]. >>>> >> >> To post to this group, send email to [email protected]. >>>> >> >> Visit this group at https://groups.google.com/group/sage-support. >>>> >> >> For more options, visit https://groups.google.com/d/optout. >>>> > >>>> > -- >>>> > You received this message because you are subscribed to the Google >>>> > Groups >>>> > "sage-support" group. >>>> > To unsubscribe from this group and stop receiving emails from it, send >>>> > an >>>> > email to [email protected]. >>>> > To post to this group, send email to [email protected]. >>>> > Visit this group at https://groups.google.com/group/sage-support. >>>> > For more options, visit https://groups.google.com/d/optout. >>>> >>>> >>>> >>>> -- >>>> William (http://wstein.org) >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "sage-support" group. >>> To unsubscribe from this group and stop receiving emails from it, send an >>> email to [email protected]. >>> To post to this group, send email to [email protected]. >>> Visit this group at https://groups.google.com/group/sage-support. >>> For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
