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.
