#8828 closed enhancement (fixed)
Lower height bound for elliptic curves
Reported by:  robertwb  Owned by:  cremona 

Priority:  major  Milestone:  sage6.3 
Component:  elliptic curves  Keywords:  
Cc:  pbruin  Merged in:  
Authors:  Robert Bradshaw, John Cremona  Reviewers:  Peter Bruin 
Report Upstream:  N/A  Work issues:  
Branch:  d5e37d3 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description
Implements Cremona and and Samir Siksek's algorithm for computing lower bounds on canonical heights, with Nook's extensions to number fields.
Attachments (1)
Change History (56)
Changed 12 years ago by
comment:1 Changed 12 years ago by
 Status changed from new to needs_work
comment:2 Changed 12 years ago by
comment:3 Changed 12 years ago by
 Cc cremona added
comment:4 Changed 9 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:5 Changed 8 years ago by
I am about to convert this patch to a new git branch based on the 6.1 develop branch, in an attempt to revive the code and get it finished. Note that this is a prerequisite for the related #8829.
comment:6 Changed 8 years ago by
 Cc cremona removed
comment:7 Changed 8 years ago by
 Branch set to u/cremona/ticket/8828
 Commit set to 7b637e34b9ed6d26880b4732cec51bdf19290a72
New commits:
7b637e3  trac 8828: initial commit

comment:8 Changed 8 years ago by
Here is a commit which make essentially the same changes as the patch. I omitted some lowlevel stuff which seems to have been included anyway in the intervening 4 years. I changed the QQ.residue_field() function to be even more like the number field version.
comment:9 Changed 8 years ago by
 Commit changed from 7b637e34b9ed6d26880b4732cec51bdf19290a72 to 307891bccd485a4c72ca0868ddee799ab78e4025
Branch pushed to git repo; I updated commit sha1. New commits:
307891b  trac 8828: small rebasing edit to make tests pass

comment:10 Changed 8 years ago by
The two commits up to 307891b implement the original patch with one small additional rebasing edit. This now passes all tests, but that is not saying a lot since there are very few doctests in the new code.
My next job: add docstrings and doctests.
comment:11 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:12 Changed 8 years ago by
 Cc pbruin added
comment:13 Changed 8 years ago by
 Branch changed from u/cremona/ticket/8828 to u/robertwb/ticket/8828
 Modified changed from 02/28/14 14:50:27 to 02/28/14 14:50:27
comment:14 Changed 8 years ago by
 Commit changed from 307891bccd485a4c72ca0868ddee799ab78e4025 to 46ab74b2c8055b851c467fc3789e1f8914a10358
comment:15 Changed 8 years ago by
Robert, I spent some time on this a mnth or two ago (how do you find out when a branch was last modified?) and I'm sure some of what I did will be useful  certain, in fact, since at least one doctest revealed a bug.
What is the best way of sharing my branch with you? There are 2 or 3 commits on top of 6.1.beta2.
comment:16 followup: ↓ 17 Changed 8 years ago by
I merged your branch into mine, so you should be able to merge that in easily with whatever future work you do.
comment:17 in reply to: ↑ 16 Changed 8 years ago by
Replying to robertwb:
I merged your branch into mine, so you should be able to merge that in easily with whatever future work you do.
Git is not clever enough for you to lift by last commit off my own computer though. I had one more commit with a lot of stuff. I made a patch from it and put it in boxen:/home/cremona/8828.patch, and it might be worth looking at.
comment:18 followup: ↓ 19 Changed 8 years ago by
Fair point :). You should be able to do
./sage dev pull ticket 8828 ./sage dev push ticket 8828
to pull these changes in and then push your changes out. This might involve a merge, but it shouldn't conflict. Alternatively, you could publish your repo somewhere (e.g. on github or even boxen) and I could merge it in.
comment:19 in reply to: ↑ 18 Changed 8 years ago by
Replying to robertwb:
Fair point :). You should be able to do
./sage dev pull ticket 8828 ./sage dev push ticket 8828to pull these changes in and then push your changes out. This might involve a merge, but it shouldn't conflict. Alternatively, you could publish your repo somewhere (e.g. on github or even boxen) and I could merge it in.
OK, but I don't have time to do that right now as I'm leaving for a conference tomorrow and have a lot to do before that...
comment:20 Changed 8 years ago by
 Branch changed from u/robertwb/ticket/8828 to u/cremona/ticket/8828
 Commit changed from 46ab74b2c8055b851c467fc3789e1f8914a10358 to 756d0eee273bb77bb96dd314e89af19076d8a10b
comment:21 Changed 8 years ago by
The automatic merge worked fine: the two new commits are my work + the merge commit. This gives us a new basis for further work (adding doctests etc): I will not touch this again for 10 days or so at least!
comment:22 followup: ↓ 23 Changed 8 years ago by
This branch looks suspicious: according to the "diffstat" that appears when clicking on the branch name, it deletes three entire files (rings/number_field/morphism.pyx
, rings/rational_field.py
, schemes/elliptic_curves/ell_local_data.py
). Is this a Git (merge) accident?
comment:23 in reply to: ↑ 22 Changed 8 years ago by
Replying to pbruin:
This branch looks suspicious: according to the "diffstat" that appears when clicking on the branch name, it deletes three entire files (
rings/number_field/morphism.pyx
,rings/rational_field.py
,schemes/elliptic_curves/ell_local_data.py
). Is this a Git (merge) accident?
That is not what I see when I click on the brnaches, either the merge I did (756d0ee) or the "work in progress" commit b2bc066.
comment:24 followup: ↓ 25 Changed 8 years ago by
It only occurs when you look at the whole branch, i.e. when you click on u/cremona/ticket/8828
in the "Branch:" field. I now tried to fetch the branch with git fetch trac u/cremona/ticket/8828
and the output of git diff develop...FETCH_HEAD
does not show anything like this, just normal changes. Also merging with develop
seems to work fine. So it actually looks like a glitch in Trac's git plugin.
comment:25 in reply to: ↑ 24 Changed 8 years ago by
Replying to pbruin:
It only occurs when you look at the whole branch, i.e. when you click on
u/cremona/ticket/8828
in the "Branch:" field. I now tried to fetch the branch withgit fetch trac u/cremona/ticket/8828
and the output ofgit diff develop...FETCH_HEAD
does not show anything like this, just normal changes. Also merging withdevelop
seems to work fine. So it actually looks like a glitch in Trac's git plugin.
That is a relief  though I still have that branch on my own computer and presumably if and when I check it out again I will see a file with the changes I made.
comment:26 Changed 8 years ago by
 Commit changed from 756d0eee273bb77bb96dd314e89af19076d8a10b to f7647c482174079db2ac38eb20d3688b2e92033d
Branch pushed to git repo; I updated commit sha1. New commits:
f7647c4  Merge branch 'develop' into trac8828

comment:27 Changed 8 years ago by
The previous commit is simply merging the current develop branch (at commit 9db8c5c, tag 6.2.beta5) into my branch, which I now intend to resume work on.
comment:28 Changed 8 years ago by
 Commit changed from f7647c482174079db2ac38eb20d3688b2e92033d to ccd138c3e9aeab0c35ccc6e5a5d3011fe21b47b4
comment:29 Changed 8 years ago by
I have finished workin on height.py, adding a large amount of documentation and examples. There were some bugs revealed by this, which have been fixed. One was in the function non_neg_region
and was a simple slip, I forget the details. The second was due to wrong normalisation of period lattice basis (for real embeddings): L.basis() gives w1, w2 with w1 real, while L.normalised_basis() gives w1,w2 with w2 minimal and tau=w1/w2 in the fundamental region. To avoid this catching people out in future I added a method tau() to the period lattice class. The effect here is that in some of the tests the error is now better than it was; but also the test results (for fk and wp) are different since they work with respect to the normalised lattice [1,tau] and so are different when the correct value of tau is used!
I added more examples from the papers cited, and also give more specific references to those papers throughout, especially the paper [TT] by Nook (Thotsaphon Thonjungthug); the theory here was developed by himself with me and Samir Siksek while Nook was our PhD student.
It seems to be four years since Robert Bradshaw implemented this (Nook himself implemented it too, in Magma) so it seem rather unreasonable to ask him to look at it again. Peter Bruin would be a good person, since his own recent paper improves Nook's results (and makes some of this redundant perhaps?)
I will set this to "needs review" as soon as I have added a couple of missing doctests in the file period_lattice_region.pyx
to bring the two files up to 100%.
comment:30 Changed 8 years ago by
 Commit changed from ccd138c3e9aeab0c35ccc6e5a5d3011fe21b47b4 to 361590b875996d1a5eadd350e110052341603ca8
Branch pushed to git repo; I updated commit sha1. New commits:
361590b  Trac#8828: finished adding docs and tests to elliptic_curves/period_lattice_region

comment:31 Changed 8 years ago by
 Status changed from needs_work to needs_review
Done! Please review...
comment:32 Changed 8 years ago by
I'm now reading the code and documentation. Apart from a number of small spelling/typographical things (for which I'll just make a reviewer patch), there are a few functions of which the documentation is missing:
EllipticCurve_number_field.height_function()
 the functions
frame_data()
andunframe_data()
inperiod_lattice_region.pyx
By the way, I don't think my paper of last year makes any of this redundant. My method is almost certainly slower (I don't know by how much; it is only implemented as a PARI script and I did not make a lot of effort to make it fast, but I doubt it can beat the algorithms in this patch). Which method is most suitable probably depends a lot on the curve.
comment:33 Changed 8 years ago by
I just found out about #13125, which implements a RealSet
class representing finite unions of real intervals and points. Would it make sense to use this (and extend it where necessary) instead of the UnionOfIntervals
introduced in this ticket?
comment:34 followup: ↓ 35 Changed 8 years ago by
comment:35 in reply to: ↑ 34 Changed 8 years ago by
comment:36 Changed 8 years ago by
A question about the new method RationalField.places()
: is there a reason why the prec
argument is handled differently than in NumberField_absolute.places()
? Here is a table of which fields are used for the embedding depending on prec
:
prec RationalField NumberField  None RR/CC RIF/CIF Infinity not accepted AA/QQbar 53 RDF/CDF RDF/CDF other RealField(prec) RealField(prec)
comment:37 Changed 8 years ago by
No reason. If you are making some reviewer changes, please could you make this consistent? Thanks.
comment:38 Changed 8 years ago by
 Branch changed from u/cremona/ticket/8828 to u/pbruin/8828lower_height_bound
 Commit changed from 361590b875996d1a5eadd350e110052341603ca8 to 5a9b58a34ad4b8e24c17828031417af15e862759
 Reviewers set to Peter Bruin
Could you please check if you agree with the changes in the new branch (which is based on yours)? Here is a summary of the changes:
 The first commit ("reviewer patch") consists mostly of formatting changes, spelling fixes and Python style issues. It also adds the new files to the reference manual. Because of this I had to change one of the references [TT] to [T]. I also changed [Cremona2010] to [CT] to be more consistent.
 The documentation of the existing method
NumberField_absolute.places()
is wrong; in fact it never returns an embedding intoRIF
orCIF
, it just uses these to determine the required precision ifprec=None
. I have not changed the documentation; it could be done in an additional commit here or in a new ticket. For the new methodRationalField.places()
, I just added theprec=Infinity
option.
 For consistency,
RDF
is now used instead for all bounds (there were two places whereRR
was used).
 The two coefficients of the Laurent series of the Weierstrass pfunction that are needed can be obtained more easily as suitable multiples of the usual modular forms c_{4} and c_{6}.
 Added documentation for the functions mentioned in comment:32.
All tests pass, so if you are happy with the changes you can set this to positive review.
comment:39 Changed 8 years ago by
Thanks  I will look at your patches carefully when I am back next week.
comment:40 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:41 followup: ↓ 42 Changed 8 years ago by
 Status changed from needs_review to positive_review
Peter, I am very sorry it took me so long to look at your reviewer's patches. You should have reminded me! I have looked at them and approve. I do not know why the coloured blob at the top is not green (it looks red to me but I am not good on colours).
comment:42 in reply to: ↑ 41 ; followup: ↓ 43 Changed 8 years ago by
Replying to cremona:
Peter, I am very sorry it took me so long to look at your reviewer's patches. You should have reminded me! I have looked at them and approve.
Thank you!
I do not know why the coloured blob at the top is not green (it looks red to me but I am not good on colours).
It is indeed red; this is because the blob shows the patchbot result for the latest stable release (6.2) instead of the latest development version, and the patchbot failed to build with 6.2, for reasons unrelated to this ticket. Clicking on the blob will give you the result of all patchbot runs; the latest patchbot build (with 6.3.beta2) succeeded and passed tests.
comment:43 in reply to: ↑ 42 Changed 8 years ago by
Replying to pbruin:
Replying to cremona:
Peter, I am very sorry it took me so long to look at your reviewer's patches. You should have reminded me! I have looked at them and approve.
Thank you!
I do not know why the coloured blob at the top is not green (it looks red to me but I am not good on colours).
It is indeed red; this is because the blob shows the patchbot result for the latest stable release (6.2) instead of the latest development version, and the patchbot failed to build with 6.2, for reasons unrelated to this ticket. Clicking on the blob will give you the result of all patchbot runs; the latest patchbot build (with 6.3.beta2) succeeded and passed tests.
Yes, I saw that green one. It makes the blob on the ticket itself rather misleading!
comment:44 followup: ↓ 45 Changed 8 years ago by
 Status changed from positive_review to needs_work
PDF docs don't build
comment:45 in reply to: ↑ 44 Changed 8 years ago by
Replying to vbraun:
PDF docs don't build
Please be more specific. I don't know how to build the pdf docs for just the files created here, and a complete build (which I did do) produced such vast output that I cannot look for anything relevant in it.
comment:46 followup: ↓ 47 Changed 8 years ago by
grep A 3 "Emergency stop" logs/docpdf.log
comment:47 in reply to: ↑ 46 Changed 8 years ago by
Replying to vbraun:
grep A 3 "Emergency stop" logs/docpdf.log
This shows nothing, even after several rounds of make docclean and make docpdf etc. The log shows that the build quits after
OSError: [combinat ] /home/jec/sage/src/doc/en/reference/combinat/algebra.rst:4: WARNING: toctree contains reference to nonexisting document u'sage/combinat/free_module'
which has nothing to do with this ticket!
comment:48 Changed 8 years ago by
Does sage syncbuild
fix it? If not: make distclean && make
.
comment:49 Changed 8 years ago by
 Commit changed from 5a9b58a34ad4b8e24c17828031417af15e862759 to 36dd3883da7f25876330d22b060f59f91630f102
Branch pushed to git repo; I updated commit sha1. New commits:
36dd388  Trac 8828: \eps should be \epsilon

comment:50 followup: ↓ 51 Changed 8 years ago by
 Status changed from needs_work to positive_review
I tried make docpdf
and it TeX complained about being \eps
being an undefined control sequence. I changed it to \epsilon
; hopefully that was the only problem.
comment:51 in reply to: ↑ 50 Changed 8 years ago by
 Status changed from positive_review to needs_work
Replying to pbruin:
I tried
make docpdf
and it TeX complained about being\eps
being an undefined control sequence. I changed it to\epsilon
; hopefully that was the only problem.
Actually it wasn't, there is also a \time
that should be a \times
, patch coming soon.
comment:52 Changed 8 years ago by
 Commit changed from 36dd3883da7f25876330d22b060f59f91630f102 to d5e37d3dc083081323b9ad523f346a5bd20d3803
Branch pushed to git repo; I updated commit sha1. New commits:
d5e37d3  Trac 8828: fix two other LaTeX errors

comment:53 Changed 8 years ago by
 Status changed from needs_work to positive_review
comment:54 Changed 8 years ago by
 Branch changed from u/pbruin/8828lower_height_bound to d5e37d3dc083081323b9ad523f346a5bd20d3803
 Resolution set to fixed
 Status changed from positive_review to closed
comment:55 Changed 8 years ago by
 Commit d5e37d3dc083081323b9ad523f346a5bd20d3803 deleted
Please see #17088 for a followup.
It works fine, but is still missing documentation and doctests.