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.
