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.
