Opened 11 years ago

Closed 6 years ago

Last modified 6 years ago

#8828 closed enhancement (fixed)

Lower height bound for elliptic curves

Reported by: robertwb Owned by: cremona
Priority: major Milestone: sage-6.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) 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)

8828-min-height-working.patch (48.5 KB) - added by robertwb 11 years ago.

Download all attachments as: .zip

Change History (56)

Changed 11 years ago by robertwb

comment:1 Changed 11 years ago by robertwb

  • Status changed from new to needs_work

It works fine, but is still missing documentation and doctests.

comment:2 Changed 11 years ago by robertwb

Depends on #8535 and #8818 at least.

comment:3 Changed 11 years ago by cremona

  • Cc cremona added

comment:4 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 7 years ago by cremona

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 7 years ago by cremona

  • Authors set to Robert Bradshaw, John Cremona
  • Cc cremona removed

comment:7 Changed 7 years ago by cremona

  • Branch set to u/cremona/ticket/8828
  • Commit set to 7b637e34b9ed6d26880b4732cec51bdf19290a72

New commits:

7b637e3trac 8828: initial commit

comment:8 Changed 7 years ago by cremona

Here is a commit which make essentially the same changes as the patch. I omitted some low-level 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.

Last edited 7 years ago by cremona (previous) (diff)

comment:9 Changed 7 years ago by git

  • Commit changed from 7b637e34b9ed6d26880b4732cec51bdf19290a72 to 307891bccd485a4c72ca0868ddee799ab78e4025

Branch pushed to git repo; I updated commit sha1. New commits:

307891btrac 8828: small rebasing edit to make tests pass

comment:10 Changed 7 years ago by cremona

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 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:12 Changed 7 years ago by pbruin

  • Cc pbruin added

comment:13 Changed 7 years ago by robertwb

  • 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 7 years ago by robertwb

  • Commit changed from 307891bccd485a4c72ca0868ddee799ab78e4025 to 46ab74b2c8055b851c467fc3789e1f8914a10358

I started adding doctests.


New commits:

127c66f8828 - Lower bound on canonical height for elliptic curves.
2a453d1Merge branch 'ticket/8828' into heights
46ab74bDocument and test most of period lattice region.

comment:15 Changed 7 years ago by cremona

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 follow-up: Changed 7 years ago by robertwb

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 7 years ago by cremona

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 follow-up: Changed 7 years ago by robertwb

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 7 years ago by cremona

Replying to robertwb:

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.

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 7 years ago by cremona

  • Branch changed from u/robertwb/ticket/8828 to u/cremona/ticket/8828
  • Commit changed from 46ab74b2c8055b851c467fc3789e1f8914a10358 to 756d0eee273bb77bb96dd314e89af19076d8a10b

New commits:

b2bc066trac 8828: work in progress
756d0eeMerge branch 'u/robertwb/ticket/8828' of git://trac.sagemath.org/sage into trac8828

comment:21 Changed 7 years ago by cremona

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 follow-up: Changed 7 years ago by 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?

comment:23 in reply to: ↑ 22 Changed 7 years ago by cremona

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 follow-up: Changed 7 years ago by 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 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 7 years ago by cremona

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 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.

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 7 years ago by git

  • Commit changed from 756d0eee273bb77bb96dd314e89af19076d8a10b to f7647c482174079db2ac38eb20d3688b2e92033d

Branch pushed to git repo; I updated commit sha1. New commits:

f7647c4Merge branch 'develop' into trac8828

comment:27 Changed 7 years ago by cremona

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 7 years ago by git

  • Commit changed from f7647c482174079db2ac38eb20d3688b2e92033d to ccd138c3e9aeab0c35ccc6e5a5d3011fe21b47b4

Branch pushed to git repo; I updated commit sha1. New commits:

f5ea499Merge branch 'develop' into trac8828
ccd138cTrac#8828: finished adding docs and tests to elliptic_curves/height.py

comment:29 Changed 7 years ago by cremona

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 7 years ago by git

  • Commit changed from ccd138c3e9aeab0c35ccc6e5a5d3011fe21b47b4 to 361590b875996d1a5eadd350e110052341603ca8

Branch pushed to git repo; I updated commit sha1. New commits:

361590bTrac#8828: finished adding docs and tests to elliptic_curves/period_lattice_region

comment:31 Changed 7 years ago by cremona

  • Status changed from needs_work to needs_review

Done! Please review...

comment:32 Changed 7 years ago by pbruin

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() and unframe_data() in period_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 7 years ago by pbruin

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 follow-up: Changed 7 years ago by cremona

Maybe in future, but it would delay this (and the dependent tickets such as #8289), and the code here is tested. I would say we should put in a reference to a new ticket to consider doing that in future. But this is partly laziness, and not being familiar with the code at #13125.

comment:35 in reply to: ↑ 34 Changed 7 years ago by pbruin

Replying to cremona:

Maybe in future, but it would delay this (and the dependent tickets such as #8289), and the code here is tested. I would say we should put in a reference to a new ticket to consider doing that in future.

OK, this is now #16063.

comment:36 Changed 7 years ago by pbruin

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 7 years ago by cremona

No reason. If you are making some reviewer changes, please could you make this consistent? Thanks.

comment:38 Changed 7 years ago by pbruin

  • Branch changed from u/cremona/ticket/8828 to u/pbruin/8828-lower_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 into RIF or CIF, it just uses these to determine the required precision if prec=None. I have not changed the documentation; it could be done in an additional commit here or in a new ticket. For the new method RationalField.places(), I just added the prec=Infinity option.
  • For consistency, RDF is now used instead for all bounds (there were two places where RR was used).
  • The two coefficients of the Laurent series of the Weierstrass p-function that are needed can be obtained more easily as suitable multiples of the usual modular forms c4 and c6.
  • 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 7 years ago by cremona

Thanks -- I will look at your patches carefully when I am back next week.

comment:40 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:41 follow-up: Changed 6 years ago by cremona

  • 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 ; follow-up: Changed 6 years ago by 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.

comment:43 in reply to: ↑ 42 Changed 6 years ago by cremona

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 follow-up: Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work

PDF docs don't build

comment:45 in reply to: ↑ 44 Changed 6 years ago by cremona

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 follow-up: Changed 6 years ago by vbraun

grep -A 3 "Emergency stop" logs/docpdf.log

comment:47 in reply to: ↑ 46 Changed 6 years ago by cremona

Replying to vbraun:

grep -A 3 "Emergency stop" logs/docpdf.log

This shows nothing, even after several rounds of make doc-clean and make doc-pdf 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 6 years ago by vbraun

Does sage -sync-build fix it? If not: make distclean && make.

comment:49 Changed 6 years ago by git

  • Commit changed from 5a9b58a34ad4b8e24c17828031417af15e862759 to 36dd3883da7f25876330d22b060f59f91630f102

Branch pushed to git repo; I updated commit sha1. New commits:

36dd388Trac 8828: \eps should be \epsilon

comment:50 follow-up: Changed 6 years ago by pbruin

  • Status changed from needs_work to positive_review

I tried make doc-pdf 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 6 years ago by pbruin

  • Status changed from positive_review to needs_work

Replying to pbruin:

I tried make doc-pdf 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 6 years ago by git

  • Commit changed from 36dd3883da7f25876330d22b060f59f91630f102 to d5e37d3dc083081323b9ad523f346a5bd20d3803

Branch pushed to git repo; I updated commit sha1. New commits:

d5e37d3Trac 8828: fix two other LaTeX errors

comment:53 Changed 6 years ago by pbruin

  • Status changed from needs_work to positive_review

comment:54 Changed 6 years ago by vbraun

  • Branch changed from u/pbruin/8828-lower_height_bound to d5e37d3dc083081323b9ad523f346a5bd20d3803
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:55 Changed 6 years ago by jdemeyer

  • Commit d5e37d3dc083081323b9ad523f346a5bd20d3803 deleted

Please see #17088 for a follow-up.

Note: See TracTickets for help on using tickets.