@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.
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] > <javascript:>> 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] <javascript:>. > > To post to this group, send email to [email protected] > <javascript:>. > > 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.
