New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement integral point finding for elliptic curves over Q #3674
Comments
Not a patch (yet) |
comment:1
Attachment: ell_rational_field.py.gz In 3.0.5 I replaced sage/schemes/elliptic_curves/ell_rational_field.py with the file emailed to me Comments:
If the curve has trivial MW group then this is what you would expect, so why not just return the empty list? That's all I'll write for now. You have done some great work here, but what I think I will do is rewrite it a bit myself and post a new patch based on that.
should be if self.j_invariant()==0 ? j is undefined here. Also, since height_of_curve() might be useful in other places I would make this a separate function for the class. |
comment:2
Dear John, thanks to your answer and your advise.
your right that was a bit imprecise of us
we didn't thought of the problem that a set might make across platforms
yes, there is a mistake. We thought this would be impossible so we raised an Error
The code with trash is more or less the same, because the function .point() raises an Error
We also thought that there must be better ways of checking the type but because we
Thanks. So we shouldn't fix what you commented on here ?
At runtime j is defined so it seems no problem to us
If you're going do this you need self.j_invariant() that's right. I would also suggest to make complex_elliptic_logarithm() a seperate function in the class Now in the following weeks, Michael and I will go on with the problem of S-integral point Best wishes |
comment:3
Dear Tobias (and Michael) For trac: write to Michael Abshoff (see sage-devel emails) and ask I have started editing your code, and I think it would be most Other comments about your internal functions:
That's enough for now. I will paste this into the trac ticket too. It might be a good idea to wait until this function is finished and John |
Attachment: sage-trac3674a.patch.gz Based on 3.0.4 |
comment:4
The patch sage-trac3674a.patch is a first version after some working by me. It needs more work still (e.g. |
comment:5
Replying to @JohnCremona:
Dear John, it is very informative to look at the changes you made. We hadn't such a deep knowledge how to work with sage (e.g. computing the roots).
Greetings |
Replaces earlier patch -- applies to 3.0.4 |
comment:6
Attachment: sage-trac3674.patch.gz The patch sage-trac3674.patch supercedes the earlier one and should be applied to 3.0.4 (or, I hope 3.0.5, 3.0.6). From the code supplied by Tobias and Michael I moved elliptic_logarithm() and on_identity_component() to ell_points.py since they are more generally useful, and included doctests for these. I edited the code for integral_points quite a lot without changing the algorithm, mainly better handling of floating point numbers and use of some Sage functions rather than reinvent wheels in a few places. One change to functionality is that by default only one of each pair P, -P is output; this can be changed using both_signs=True. The elliptic logarithm doctests have been checked against pari's ellpointtoz() function, and the integral points on 5077a1 with Magma (which revealed a Magma bug, duly reported). |
comment:7
The second patch sage-trac3674b.patch adds a function antilogarithm() for elliptic curves over Q, which is an inverse to elliptic_logarithm(). A Note 1: elliptic_logarithm() is a method of the class Note 2: antilogarithm() just calls ellztopoint() from the pari library. But the way that function is wrapped does not allow the passing of a precision parameter, which it should. |
comment:8
Attachment: sage-trac3674b.patch.gz For CC read QQ in the above. |
Attachment: sage-trac3674c.patch.gz fix so e.integral_points() works when e.rank() >= 1. |
comment:9
REFEREE REPORT: This is a wonderful contribution to Sage! Since we're writing professional quality code here, there are several quality and consistency issues that need to be addressed. Please see below.
should be
Notice the period at the end of the sentence and not starting right after """ (a Sage convention).
One should NEVER have a naked except: unless there is a very good reason for it.
Why not just
In fact, you should probably do:
Make sure you know the difference between is and == (and 'is not' and !=).
it would be vastly more consistent with sage to replace the
There is an extra newline that shouldn't be there. Also, one never explicitly lists self in the INPUT's in Sage docstrings.
The three curves for which this new code "hangs forever" are: 79a1, 117a2, and 205a1.
Also, even worse, when I control-c'd out of running 205a1 from Sage I got a SIGBUS exception:
|
comment:10
Many thanks for the very detailed, helpful and constructive comments, William! Almost all the points you raise are about things introduced by me and not by the people who did the real work, so I'll take the blame for all that. The one exception to that remark, I think, is the hanging on test cases, which I'll blame on the real implementors -- but help debug if I can. I'll try to do some work on this soon. There's something about being in a Marriott Residence Inn of an evening which makes Sage development seem just the right thing to do... |
Attachment: sage-trac3674c.2.patch.gz replaces earlier sage-trac3674c.patch |
comment:11
The new patch sage-trac3674c.2.patch replaces sage-trac3674c.patch. I have dealt with all (I hope) of the stylistic points raised in the review (if not, I will of course do more in that direction). Of the curves which had been reported as hanging, only the third hung for me, but I tracked the problem down to an over-strict test for ending an AGM loop in elliptic_logarithm() -- I had made a necessary change in one branch of a split on the sign of the discriminant but not in the other. However, there is more debugging to do which I want to hand back to the original implementers! I ran all curves in the database in order like this:
and all went well until a runtime error in '289a3'. The low_bound variable becomes 0 which leads to H_q_new being Infinity. Secondly, I found lots of curves where fewer integral points were listed than by magma.
So there is something wrong here too. Over to you, Tobias and Michael! |
Attachment: sage-trac3674d.patch.gz |
comment:12
sage-trac3674d.patch fixes a problem with rank 0 curves (it was returning the 0 point and both signs even when both_signs=False). |
comment:13
We will start debugging and hopefully fix the problem soon. |
comment:17
There are still issues. The doctests do not pass for me: Mac OS X 10.4, Core 2 duo. I get:
Also, as jcremona points out:
The problem is that a singular matrix is being sent into gram_schmidt -- namely [[0, 0], [1, 1]]. I don't think that will ever work. |
Attachment: 3674-jcremona-integral-points.patch.gz |
comment:18
I have attached the patch I used, |
comment:19
I must have messed up in my attempt to simplify a series of patches into one, and sent something incomplete. I'll sort that out, but I'll be off line all day today so it will not be immediate. We know about the singular matrix problem with 5478j1; Michael and Tobias are looking to fix that. |
Attachment: sage-trac3674new-extra3.patch.gz |
Attachment: sage-trac3674new-extra4.patch.gz Attachment: sage-trac3674new-extra5.patch.gz |
comment:20
Debugging after initial review has finished, and three new (small) patches are the result. Apply the following to 3.1.alpha1 in order:
Apologies for having 6 patches but last time I tried to merge them and messed up. You should find that all doctests in sage.schemes.elliptic_curves.ell_rational_field.py pass. We have also checked that (1) for all database curves up to conductor 1000 the results agree with Magma; (2) the code runs fine for all the 64687 curves of conductor up to 10000 (which takes under 32m on my laptop). If you want to rerun those tests, first install the optional database since otherwise it will be much slower as the MW groups will need to be computed too. Hoping for a review in time for 3.1! John, Michael and Tobias |
comment:21
REFEREE REPORT:
I applied all the patches under OS X and had the following errors when doctesting the elliptic_curves directory. Maybe you could fix things so they pass? E.g., maybe they are the result of randomness, etc.
|
comment:22
I think that is all explainable by either decimal randomness, or the kind of thing I was fixing in #3793. I'll see what I can do. |
comment:23
Replying to @JohnCremona:
I don't understand your comment about 3.0.6 vs. 3.1.alpha1. Before I posted the latest patches I did apply all 6 in order to a fresh clone of a 3.1.alpha 1 build, and all applied with no issues at all. There's some mystery here, and inconsistency which is making it very hard to iron out these last doctests. |
Attachment: sage-trac3674new-extra6.patch.gz |
comment:24
Two things: (1) for the doctests to work you need to have already applied the patch to #3793. (2) I replaced some least significant decimal digits by ... to avoid decimal fuzz. Please can you check this again? |
comment:25
OK, everything works now and I'm happy with this code. POSITIVE REVIEW. |
comment:26
Hi John, with the "new" patches applied up to number 6 I see the following doctest failures on sage.math:
They all seem to be of the form
|
comment:27
Hi, I am an idiot and forgot to apply one patch in the series. Sorry - I should sleep more ;) Cheers, Michael |
comment:28
Hi, the doctests now pass, but there is the following issue: Due to using the symbolic sqrt, ceil and floor the time to doctest sha.py double from 22 to 45 seconds (not long) and the time to doctest it long goes from 4 minutes to 10.5. The extra time seems to be mostly spend in clisp. A number of other doctests also show similar increase in time. I have made this isssue a blocker for 3.1 at #3837, but the patches will be merged shortly. Cheers, Michael |
comment:29
Merged
in Sage 3.1.alpha2 |
comment:30
I know what this is -- on Williams's suggestion (insistence!) in his review I made a change entirely independent of the integral points stuff, namely that in the torsion_subgroup function the algorithm parameter should change from being an integer to a string. And so there are problems all over the place with other functions which call that one. I can fix all that, but it might not be tonight since I've just got home after an evening out. First thing tomorrow, I promise! |
comment:31
Replying to @sagetrac-mabshoff:
Michael, Could you confirm that there are no problems after all with those "sage -t -long" tests? They work for me. John |
comment:32
Replying to @JohnCremona:
Hi John, yes, after applying all patches "sage -t -long" passes. Otherwise I would not have closed this ticket as fixed :) Cheers, Michael |
The problem of enumerating integral and S-integral points on elliptic curves over Q and over number fields is one which it would be wonderful to have implemented in Sage. Magma has this over Q (for general S), but no package has the general case (except possibly in code for Simath written by E.Hermann).
I suggested this as a good problem for a Masters student to work on after the Sage Days in Bristol in November 2007. After that, Tobias Nagel & Michael Mardaus (students at Mainz) started to work on it. At my suggestion they started with the easiest case: integral points over Q (i.e. S=\emptyset). They have just sent me this, and I am about to start testing it:
Dear John,
we just finished our work (or at least part one of it).
As you explained to us we put our code into ell_rational_field.py. So a new function 'integral_points(self, mw_base='auto', tors_points='auto')' is provided after a rebuild of sage.
Our testcases are also attached to the mail. If you load self_test.sage you have a funtion called 'test_integral_points'. Call it by test_integral_points('all') to test 12 testcases, which mean several curves and changes in the generators of the Mordell-Weil base. (As an overview we made an excel-sheet with the computation time, but it is only one run and not statistically correct evaluated ;) )
We are not sure if all the functionality should be written in ell_rational_field.py as we did or if it should be swaped out to somewhere.
We hope you are satisfied with our work.
Greetings
Tobias and Michael
I will attach a patch file created from the attachments they sent me shortly.
John Cremona
CC: mardaus@students.uni-mainz.de
Component: number theory
Issue created by migration from https://trac.sagemath.org/ticket/3674
The text was updated successfully, but these errors were encountered: