Opened 9 years ago

Closed 8 years ago

#13951 closed defect (fixed)

(non)archimedian_local_height broken for rational points on elliptic curves over Q

Reported by: pbruin Owned by: cremona
Priority: major Milestone: sage-5.13
Component: elliptic curves Keywords: local heights
Cc: Merged in: sage-5.13.beta4
Authors: Peter Bruin, John Cremona Reviewers: John Cremona, Peter Bruin
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12509, #13953, #14609 Stopgaps:

Status badges

Description (last modified by cremona)

Computing local heights uses functions that are only available when the base field is a NumberField?, and not over the RationalField?:

sage: E = EllipticCurve([0, 0, 0, -36, 0])
sage: P = E(-3, 9)
sage: P.archimedian_local_height()
...
AttributeError: 'RationalField_with_category' object has no attribute 'places'
sage: P.nonarchimedian_local_height()
...
AttributeError: 'RationalField_with_category' object has no attribute 'factor'

Note: at the moment this bug only shows up for non-torsion points because of bug #13953 (asking for local heights of torsion points always returns 0, which is in general incorrect).

Apply: trac13951-local_heights.patch, trac13951-local_heights_2.patch, trac_13951_extra.patch

Attachments (5)

trac13951-local_heights_QQ.patch (4.8 KB) - added by pbruin 8 years ago.
based on 5.9 + #12509 + #13953
trac13951-local_heights.patch (16.0 KB) - added by cremona 8 years ago.
rebased on 5.10.rc0 and extended: replaces previous patch
trac13951-local_heights_2.patch (15.1 KB) - added by pbruin 8 years ago.
apply after trac13591-local_heights.patch
trac13951-docstring_raw.patch (676 bytes) - added by pbruin 8 years ago.
Label docstring as "raw" due to UTF-8 character
trac_13951_extra.patch (1.9 KB) - added by cremona 8 years ago.
Small additional fix

Download all attachments as: .zip

Change History (43)

comment:1 Changed 9 years ago by pbruin

  • Description modified (diff)

comment:2 Changed 9 years ago by pbruin

  • Authors set to Peter Bruin

comment:3 Changed 9 years ago by pbruin

  • Authors Peter Bruin deleted

comment:4 follow-up: Changed 9 years ago by cremona

For global heights over QQ we just call pari, but here I suggest that we call the local height functions implemented over number fields, which should be straightforward (but not completely trivial). Must be based on #12509. I should have time to do this next week if no-one else does it first.

comment:5 in reply to: ↑ 4 Changed 9 years ago by pbruin

Replying to cremona:

For global heights over QQ we just call pari, but here I suggest that we call the local height functions implemented over number fields, which should be straightforward (but not completely trivial).

Yes, that was what I was thinking too.

Changed 8 years ago by pbruin

based on 5.9 + #12509 + #13953

comment:6 Changed 8 years ago by pbruin

  • Authors set to pbruin
  • Status changed from new to needs_review

comment:7 Changed 8 years ago by pbruin

  • Authors changed from pbruin to Peter Bruin
  • Dependencies set to #12509, #13953

comment:8 follow-up: Changed 8 years ago by cremona

I am looking at this now. I note that the two prerequisites are already merged in 5.10.beta3/4 and plan to test on 5.10.rc0.

One preliminary comment: the little function to compute the local degree at an archimedean place by testing if the image of the generator under the embedding has 0 imaginary part looks very ugly to me (and it is possible that I wrote it). Surely there is a better way? I looked to see what I did for the period functions in period_lattice.py to test whether an embedding was real or not: there, the given embedding is first refined to an embedding into AA if real or QQbar if not, using sage.rings.number_fields.refine_embedding, which in turn tests whether the codomain of the embedding passes sage.rings.real_mpfr.is_RealField(). Would that be better?

comment:9 follow-up: Changed 8 years ago by cremona

A second comment, of a different kind: how can it have happened and never been noticied that these related functions are all spelled wrong! It is "archimedean" and not "archimedian" (think "Archimedes").

I don't think I will be able to resist correcting all these: about 24 occurrences including doctests. Interestingly, in almost all places the word is spelled correctly in comments. But should we just deprecate the old spelling? I will consult sage-devel.

  1. In line 2858 of the patched file I removed the division by K.degree() since that is 1. This appeared to cut the time to doctest this file (with --long) by a few seconds, but that might have been a freak!
  1. The global height function would now work without calling pari, hence with no special case needed for K==QQ. Alternatively, we could easily add an "algorithm" parameter which could be either "sage" or "pari", with "pari" the default. I think that over QQ pari uses Mestre's AGM method for the real place, which is likely to be faster. Having the choice of algorithm would make it easy to add a doctest to compare the two; there should already be a doctest showing that the global height is the sum of the arch. and non-arch. heights which would actually be a test since we are computing them entirely indepependently!
  1. The non-arch. height has a parameter "weighted" which is not documented and should be, with doctests shoing its use. Similarly with the is_minimal parameter. And for consistency, surely the arch. height should also have a weighted parameter?

Sorry to be awkward; mathematically the patch is certainly ok!

I have a second patch which deals only with (1) spelling corrrections, but no deprecation warning, (2) not dividing by K.degree() when it is 1. I can add to that after this discussion, so will not upload it yet.

comment:10 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by pbruin

Replying to cremona:

I am looking at this now. I note that the two prerequisites are already merged in 5.10.beta3/4 and plan to test on 5.10.rc0.

One preliminary comment: the little function to compute the local degree at an archimedean place by testing if the image of the generator under the embedding has 0 imaginary part looks very ugly to me (and it is possible that I wrote it). Surely there is a better way? I looked to see what I did for the period functions in period_lattice.py to test whether an embedding was real or not: there, the given embedding is first refined to an embedding into AA if real or QQbar if not, using sage.rings.number_fields.refine_embedding, which in turn tests whether the codomain of the embedding passes sage.rings.real_mpfr.is_RealField(). Would that be better?

One easy solution would be to rely on the fact that K.places() returns the r_1 real embeddings followed by the r_2 complex embeddings:

r1, r2 = K.signature()
pl = K.places()
return (sum(self.archimedian_local_height(pl[i], prec) for i in range(r1))
        + 2 * sum(self.archimedian_local_height(pl[i], prec) for i in range(r1, r1 + r2))) / K.degree()

This leaves the job of distinguishing real and complex places to the NumberField? code. I just tested this and it appears to work

comment:11 in reply to: ↑ 10 Changed 8 years ago by cremona

Replying to pbruin:

Replying to cremona:

I am looking at this now. I note that the two prerequisites are already merged in 5.10.beta3/4 and plan to test on 5.10.rc0.

One preliminary comment: the little function to compute the local degree at an archimedean place by testing if the image of the generator under the embedding has 0 imaginary part looks very ugly to me (and it is possible that I wrote it). Surely there is a better way? I looked to see what I did for the period functions in period_lattice.py to test whether an embedding was real or not: there, the given embedding is first refined to an embedding into AA if real or QQbar if not, using sage.rings.number_fields.refine_embedding, which in turn tests whether the codomain of the embedding passes sage.rings.real_mpfr.is_RealField(). Would that be better?

One easy solution would be to rely on the fact that K.places() returns the r_1 real embeddings followed by the r_2 complex embeddings:

r1, r2 = K.signature()
pl = K.places()
return (sum(self.archimedian_local_height(pl[i], prec) for i in range(r1))
        + 2 * sum(self.archimedian_local_height(pl[i], prec) for i in range(r1, r1 + r2))) / K.degree()

This leaves the job of distinguishing real and complex places to the NumberField? code. I just tested this and it appears to work

I like that a lot. Since I am already working on a second patch, I will put that in. Thanks.

comment:12 in reply to: ↑ 9 Changed 8 years ago by pbruin

Replying to cremona:

A second comment, of a different kind: how can it have happened and never been noticied that these related functions are all spelled wrong! It is "archimedean" and not "archimedian" (think "Archimedes").

I agree with the spelling "archimedean". (It is "archimedisch" in German and Dutch, and "archimédien" in French, but in these cases the "i" is part of the suffix. Similarly, "Euclidean geometry" vs. "géométrie euclidienne" etc.)

If we are changing the spelling anyway, should we also write "non_archimedean_local_height" instead of "nonarchimedean_local_height" for readability?

I also noticed that "independent" is spelled "independant" in three places in the documentation.

I don't think I will be able to resist correcting all these: about 24 occurrences including doctests. Interestingly, in almost all places the word is spelled correctly in comments. But should we just deprecate the old spelling? I will consult sage-devel.

  1. In line 2858 of the patched file I removed the division by K.degree() since that is 1. This appeared to cut the time to doctest this file (with --long) by a few seconds, but that might have been a freak!

Yes, the division by K.degree() should clearly be omitted.

  1. The global height function would now work without calling pari, hence with no special case needed for K==QQ. Alternatively, we could easily add an "algorithm" parameter which could be either "sage" or "pari", with "pari" the default. I think that over QQ pari uses Mestre's AGM method for the real place, which is likely to be faster. Having the choice of algorithm would make it easy to add a doctest to compare the two; there should already be a doctest showing that the global height is the sum of the arch. and non-arch. heights which would actually be a test since we are computing them entirely indepependently!

As far as I can see the doctest verifying that the height equals the sum of the archimedean and non-archimedean local heights is not there yet, but there should certainly be one!

  1. The non-arch. height has a parameter "weighted" which is not documented and should be, with doctests shoing its use. Similarly with the is_minimal parameter. And for consistency, surely the arch. height should also have a weighted parameter?

Yes, that sounds reasonable.

comment:13 follow-up: Changed 8 years ago by pbruin

And maybe the global height function should also have a parameter "weighted", where True means no division by the degree of the number field. Instead of "weighted" the parameter could be called something like "absolute" or "normalised", where True means that we do divide by the degree.

comment:14 in reply to: ↑ 13 ; follow-up: Changed 8 years ago by cremona

Replying to pbruin:

And maybe the global height function should also have a parameter "weighted", where True means no division by the degree of the number field. Instead of "weighted" the parameter could be called something like "absolute" or "normalised", where True means that we do divide by the degree.

OK, I am working on it. For non-arch. places the default, only relevant for a single place, is weighted=False but when it adds up all the non-arch contributions it puts in the weightings as that is needed for the global height. When weighting is False the local height is divided by the local degree. Now for arch. places there is currently no weighting for individual places but we multiply by the local degree when adding up all the arch. contributions. So I think that the consistent thing to do would be have weighting=True mean that at complex places the local height would be multiplied by 2, then again the total arch. contribution would be obtained by adding up the individual ones, weighted, but the default for a single place would be to have weighting=False and return the same as now.

The only thing about all that which puzzles me is that in the non-arch. case we divide by the local degree when weighting=False, while for arch. places we multiply by it when weighting=True. This suggests to me that our conventions for the non-weighted local heights are inconsistent. What do you think?

comment:15 in reply to: ↑ 14 Changed 8 years ago by pbruin

Replying to cremona:

Replying to pbruin:

And maybe the global height function should also have a parameter "weighted", where True means no division by the degree of the number field. Instead of "weighted" the parameter could be called something like "absolute" or "normalised", where True means that we do divide by the degree.

OK, I am working on it. For non-arch. places the default, only relevant for a single place, is weighted=False but when it adds up all the non-arch contributions it puts in the weightings as that is needed for the global height. When weighting is False the local height is divided by the local degree. Now for arch. places there is currently no weighting for individual places but we multiply by the local degree when adding up all the arch. contributions. So I think that the consistent thing to do would be have weighting=True mean that at complex places the local height would be multiplied by 2, then again the total arch. contribution would be obtained by adding up the individual ones, weighted, but the default for a single place would be to have weighting=False and return the same as now.

It seems to me that the parameter "weighted" still makes sense if v = None: we should take the weighted sum of the local heights at all (non-)Archimedean places, and if weighted = False, we divide this sum by the degree of K.

Although it would certainly be good to have a parameter "weighted" for archimedean_local_height, the drawback is that we would again need to distinguish between real and complex places. With the above way of eliminating the local_degree function, this is only avoided because we know which one it is because of our position in the list of all places.

The only thing about all that which puzzles me is that in the non-arch. case we divide by the local degree when weighting=False, while for arch. places we multiply by it when weighting=True. This suggests to me that our conventions for the non-weighted local heights are inconsistent. What do you think?

The current conventions for the return values of (non)archimedian_local_height are consistent. The difference is that the calculation is done differently: for v Archimedean we compute with the smaller of the two all the time and multiply by the local degree at the end if necessary, while for v non-Archimedean we compute with the larger of the two and divide by the local degree at the end if necessary.

comment:16 Changed 8 years ago by cremona

I am right now rebasing this on top of #14609 which I wil add to the prerequisites. This was rather messy, and the result will be a single new patch instead of the second additional reviewer's patch. Not quite ready yet...

comment:17 Changed 8 years ago by cremona

  • Authors changed from Peter Bruin to Peter Bruin, John Cremona
  • Dependencies changed from #12509, #13953 to #12509, #13953, #14609
  • Description modified (diff)
  • Reviewers set to John Cremona, Peter Bruin

comment:18 follow-up: Changed 8 years ago by cremona

Peter, this is ready for review again. It would be useful if you could review the changes I made before we ask a 3rd party; I am sorry that because of the rebasing, by patch is not separate.

I did not add a weighted parameter to the archimedean height, for the reasons discussed.

I was about to add a normalised parameter to the global height, defaulting to True, but changed my mind since that would require having two different cached values, one normalised and one not, and I was lazy.

By the way, I did verify using independent code in eclib that the examples you added (local heights over QQ) give the correct values.

comment:19 follow-up: Changed 8 years ago by pbruin

OK, I will install 5.10.rc1 and review the patch. One quick comment: the parameter "prec" in non_archimedean_local_height is documented twice (lines 2801-2806).

Changed 8 years ago by cremona

rebased on 5.10.rc0 and extended: replaces previous patch

comment:20 in reply to: ↑ 19 Changed 8 years ago by cremona

Replying to pbruin:

OK, I will install 5.10.rc1 and review the patch. One quick comment: the parameter "prec" in non_archimedean_local_height is documented twice (lines 2801-2806).

Let me fix that one right away to save you trouble. Done!

comment:21 Changed 8 years ago by pbruin

  • Description modified (diff)

Thanks! The only problem was a warning while building the documentation. The new patch fixes this and polishes the documentation of [[non_]archimedean_local_]height.

I now added a "weighted" flag to the global height function (only the normalised height is cached) and to archimedean_local_height. For the latter I reintroduced the ugly way of checking whether an Archimedean place is real (v.im_gens()[0] in rings.RR). However, this is only needed when the user directly calls archimedean_local_height(v, weighted=True), not when v = None.

comment:22 in reply to: ↑ 18 ; follow-up: Changed 8 years ago by pbruin

Replying to cremona:

I was about to add a normalised parameter to the global height, defaulting to True, but changed my mind since that would require having two different cached values, one normalised and one not, and I was lazy.

Probably "normalised" (default True) is more intuitive than "weighted" (default False); I changed this in the latest patch, together with some minimal extra polishing of the documentation.

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

Replying to pbruin:

Replying to cremona:

I was about to add a normalised parameter to the global height, defaulting to True, but changed my mind since that would require having two different cached values, one normalised and one not, and I was lazy.

Probably "normalised" (default True) is more intuitive than "weighted" (default False); I changed this in the latest patch, together with some minimal extra polishing of the documentation.

Thanks for doing the extra work on this, whic certainly makes it better. I'll look at it today.

comment:24 Changed 8 years ago by cremona

One small point: on line 2618 you set w=1, which will be a python int, and then you multiply the final returned height by w (in 3 places, 2 with the cached value and one when it is computed). Maybe I am old-fashioned, but I don't like multiplying by 1: can we reply on python doing nothing when that value of 1 is a plain python int? If it were not for this scaling needing to be done in three places I would suggest not defining w at all and ending the function with

if normalised:
    return height
else:
    return height * K.degree()

but it is not very nice to add that three times.

Perhaps multiplying by one in the usual (and default) case is not serious.

The only other thing to point out is that there is no new doctest to show the effect of the normalisation parameter. How about:

sage: E = EllipticCurve('37a1')
sage: P = E([0,0])
sage: P.height()
0.0511114082399688
sage: P.height(normalised=False)
0.0511114082399688
sage: K.<z> = CyclotomicField(5) # or perhaps something simpler
sage: EK = E.change_ring(K)
sage: PK = EK([0,0])
sage: PK.height()
0.0511114082399688
sage: PK.height(normalised=False)
0.204445632959875

comment:25 Changed 8 years ago by pbruin

I updated trac13951-local_heights_2.patch; height() now only has one return statement, and multiplication by the degree, if necessary, is done at the very end. You are right that I should have made a doctest; I added the one you suggested.

Changed 8 years ago by pbruin

apply after trac13591-local_heights.patch

comment:26 follow-up: Changed 8 years ago by cremona

Excellent, now I am happy with everything.

At this point we need a reviewer for our combined work, unless some independent third party is happy that we have each reviewed the other's work and can give the pair of patches a combined positive review.

John

comment:27 Changed 8 years ago by wuthrich

  • Status changed from needs_review to needs_work

I was willing to review this, but unfortunately it does not apply to 5.10. It needs to be rebased.

...
patching file sage/schemes/elliptic_curves/ell_point.py
Hunk #1 FAILED at 138
Hunk #3 succeeded at 2390 with fuzz 2 (offset -17 lines).
...

comment:28 Changed 8 years ago by pbruin

That is strange, I just checked that both patches apply without any problems to a fresh copy of 5.11.rc3:

sage: hg_sage.qimport('trac13951-local_heights.patch')
cd "/home/staff/pbruin/src/sage-5.11.beta3/devel/sage" && sage --hg qimport  /home/staff/pbruin/src/sage-5.11.beta3/trac13951-local_heights.patch
adding trac13951-local_heights.patch to series file
sage: hg_sage.qpush()
cd "/home/staff/pbruin/src/sage-5.11.beta3/devel/sage" && sage --hg qpush  
applying trac13951-local_heights.patch
now at: trac13951-local_heights.patch
sage: hg_sage.qimport('trac13951-local_heights_2.patch')
cd "/home/staff/pbruin/src/sage-5.11.beta3/devel/sage" && sage --hg qimport  /home/staff/pbruin/src/sage-5.11.beta3/trac13951-local_heights_2.patch
adding trac13951-local_heights_2.patch to series file
sage: hg_sage.qpush()
cd "/home/staff/pbruin/src/sage-5.11.beta3/devel/sage" && sage --hg qpush  
applying trac13951-local_heights_2.patch
now at: trac13951-local_heights_2.patch
sage: hg_sage.qapplied()
cd "/home/staff/pbruin/src/sage-5.11.beta3/devel/sage" && sage --hg qapplied  
trac13951-local_heights.patch
trac13951-local_heights_2.patch

comment:29 Changed 8 years ago by wuthrich

  • Status changed from needs_work to needs_review

Hmmmm, I still cannot do it. I was not able to figure out what is wrong with my new 5.10 installation. Well, I am sorry, but I won't be able to get a new copy and do it again before leaving on holidays. So the ticket has to wait review for a few weeks unless someone else picks it up first.

Sorry.

comment:30 Changed 8 years ago by pbruin

For patchbot:

Apply trac13951-local_heights.patch, trac13951-local_heights_2.patch

Last edited 8 years ago by pbruin (previous) (diff)

comment:31 Changed 8 years ago by pbruin

  • Description modified (diff)

Patchbot complains about the non-ASCII character in "Néron". I assume this isn't a problem, cf. the discussion about Ш in a docstring in #14561. The relevant file is already UTF-8-encoded; I'll just make the docstring start with r""".

Changed 8 years ago by pbruin

Label docstring as "raw" due to UTF-8 character

comment:32 Changed 8 years ago by pbruin

  • Description modified (diff)

The last patch wasn't necessary, see the comments at #14746.

Patchbot: apply trac13951-local_heights.patch, trac13951-local_heights_2.patch

comment:33 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 8 years ago by cremona

Small additional fix

comment:34 Changed 8 years ago by cremona

  • Description modified (diff)

comment:35 follow-up: Changed 8 years ago by cremona

I added an additional bugfix and doctest in the patch trac_13951_extra.patch.

Peter, there's a patch by you not listed in the description. Is that intended to be applied too?

comment:36 in reply to: ↑ 35 Changed 8 years ago by pbruin

Replying to cremona:

I added an additional bugfix and doctest in the patch trac_13951_extra.patch.

Good!

Peter, there's a patch by you not listed in the description. Is that intended to be applied too?

No, the idea of that patch was to mark some docstring because of an accented character, but it did the wrong thing (using r""", which just prevents backslashes from being interpreted). In fact, nothing had to be done since the file was already UTF-8-encoded.

comment:37 in reply to: ↑ 26 Changed 8 years ago by pbruin

  • Status changed from needs_review to positive_review

Replying to cremona:

Excellent, now I am happy with everything.

At this point we need a reviewer for our combined work, unless some independent third party is happy that we have each reviewed the other's work and can give the pair of patches a combined positive review.

I assume Jeroen Demeyer's comment on sage-support when you mentioned this ticket (https://groups.google.com/forum/#!topic/sage-support/xe69MXW0aSE) qualifies as such!

comment:38 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.13.beta4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.