Extend IsogenyClass_EC to work over number fields

[JohnCremona]

If E is an elliptic curve over QQ then E.isogeny_class() is an object of type (class) IsogenyClass_EC which which one can work in a nice way. This should be extended to number fields. Two reasons why this is notn-trivial (and hence was not done at the same time as over QQ): (1) bounding the possible primes degrees of isogenies; (2) handling curves with CM. For (1), the module gal_reps_number_field does what is required. For (2) new code has been written.

Depends on #11327 Depends on #16764 Depends on #16806

Component: elliptic curves

Keywords: isogeny class

Author: John Cremona

Branch/Commit: 79fee2d

Reviewer: Jeroen Demeyer, Chris Wuthrich

Issue created by migration from https://trac.sagemath.org/ticket/16743

[JohnCremona]

Dependencies: #11327, #16764

[JohnCremona]

Last 10 new commits:

8dff296	#16764: CM detection over number fields
caf41e6	#16764 revert changes to isogeny_class.py which belong in #16743
93ef887	Merge branch 'develop' into isogs-ecnf
e043ae8	#11327,#16779: improvements to isogeny class internals and docstrings
7763359	Merge branch 'isogs' into isogs-ecnf
c89a6a6	#16743 in progress
8e203af	Merge branch 'develop' into cm
3cacdb2	#16764: adjustments after review
8a74959	Merge remote-tracking branch 'trac/u/cremona/ticket/16764' into isogs-ecnf
3c96a71	#16743: elliptic curve isogeny classes over number fields

[JohnCremona]

Commit: 3c96a71

[JohnCremona]

Branch: u/cremona/ticket/16743

[JohnCremona]

comment:4

To potential reviewers: don't be put off by the large number of commits listed, that is just because of the dependencies. Once the dependencies are accepted there is just one commit which is relevant (3c96a71 #16743: elliptic curve isogeny classes over number fields).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c96a71 to e543565

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

ea410d4	Revert "Updated Sage version to 6.3"
4b1a2d4	Revert "Revert "Updated Sage version to 6.3""
12c6f01	comitting because git wants me to?
dc0185c	sorted out now?
8771832	forgot to import Set
d7c3326	Merge remote-tracking branch 'trac/u/elarson3/isogeny_bounds_for_elliptic_curves_over_number_fields' into isogs-ecnf
cadd58f	Merge remote-tracking branch 'trac/u/elarson3/isogeny_bounds_for_elliptic_curves_over_number_fields' into larson
828ed6f	#16806: reviewer's patch
77ac994	Merge branch 'larson' into isogs-ecnf
e543565	#16743: now use reducible_primes from #16806

[JohnCremona]

comment:6

I added #16806 as a dependency: that ticket concerns Gal Reps over number fields and provides an isogeny_bound() function (method) for those, to which I have added a function reducible_primes() for compatibility with the class for Gal Reps over QQ, which takes the primes in isogeny_bounds() and actually checks if there are isogenies of those degrees. At the same time I simplified the reducible_primes() method for the Gap Reps class over Q so that it does not compute the whole isogeny class but is slightly more clever, since apart from 2,3,5,7,13 one can tell by looking at a list of special j-invariants.

TODO (but not on this ticket): unify the two GaloisRepresentation classes! Perhaps there should be a base class which is rather abstract but defines the interface, with child classes for Galois Reps attached to (1) elliptic curves over number fields, (1') same over QQ, (2) modular forms, etc etc.

[JohnCremona]

Changed dependencies from #11327, #16764 to #11327, #16764, #16806

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e543565 to 06d9eb2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3fe066e	Merge remote-tracking branch 'trac/u/jdemeyer/ticket/15767' into isogs-ecnf
0f4e30b	Merge branch 'develop' into larson
be81f80	#16806: minor changes after review
7c93be1	Merge branch 'larson' into isogs-ecnf
06d9eb2	#16743: tweak to ideal comparison function

[JohnCremona]

comment:8

The last push only does one small thing really, the rest being to merge in other branches which have positive review or are merged. The actual change ("tweak") is to the comparison of ideals in number fields using the HNF: we were comparing the values of I.pari_hnf() which is a wrapped Pari GEN, and did not agree with what was intended, which comes from comparing I.pari_hnf().sage().

This is actually important for the purpose of ordering the primes in a number field, first by norm and then by their HNF. The observant reviewer may notice one doctest change in the prime_ideals() function, but this is a red herring caused by merging in the pari upgrade to 2.7.1 which gives a different generator for one ideal. For an actual change which the tweak causes you can look at the two primes of norm 17 in Q(i).

[jdemeyer]

comment:9

Sorry to bother, but it really would be much better to add the functions which have nothing to do with elliptic curves to the relevant places. For example, prime_ideals() should really be a method prime_ideals_of_bounded_norm() of NumberField. We don't want another #11905.

[JohnCremona]

comment:10

Good point, will do. It's clear for prime_ideals() and hnf_cmp() BUT in the latter case there is already a cmp function for ideals which is very similar but not good for my purposes: it does not first compare norms, and it uses the pari_hnf directly. So The simplest thing to do (replace the existing ideal cmp with mine) may cause a lot of annoying doctest changes. I'll try and see.

curve_cmp() can be a method of the class for elliptic curves over number fields, or even (almost) for generic elliptic curves as it uses no special number field stuff, just compares the list of a-invariants. Not quite since I replace each ai with its list of coefficients and flatten to get a list of 5*d rational numbers where d is the degree of the field.

curve_cmp_cm() is a bit of an experiment: for curves with (rational) CM only.

I really need these comparison functions for ordering of the elliptic curves in a single isogeny class in a deterministic way. For CM isogeny classes it is nicer to group together the curves whose Endomorphism ring is the same (they are all orders in the same imaginary quadratic field, but can have different indices in the maximal order). So curve_cmp_cm() is only really relevant in the context of isogeny classes. Comments?

Lastly there are a couple of utility functions concerning binary quadratic forms, which I will put elsewhere.

[JohnCremona]

comment:11

OK, so I would like some feedback on the change in ideal comparison. Quite a lot of doctests will need changing in sage/rings/number_field (I have not yet gone further), which looks bad BUT thee seem to be all due not to the addition of using a norm comparison first, but in the change from comparing pari_hfn() and pari_hnf().sage(), which in particular causes the primes in factorizations to be ordered differently. This looks like a big negative -- but see my earlier remark: I don't think we can trust the comparison of two Pari-GEN objects to mean what we think, so that although the old comparison appears to be comaring the HNFs of the ideals, it is not really doing that as far as I can see.

[jdemeyer]

comment:12

Replying to @JohnCremona:

Good point, will do. It's clear for prime_ideals() and hnf_cmp() BUT in the latter case there is already a cmp function for ideals which is very similar but not good for my purposes: it does not first compare norms, and it uses the pari_hnf directly. So The simplest thing to do (replace the existing ideal cmp with mine) may cause a lot of annoying doctest changes. I'll try and see.

I don't think this should be the default cmp() for ideals (it's more expensive to compute), but it should be function defined in rings/number_field/number_field_ideal.py. And why do you need

cmp(I.pari_hnf().sage(), J.pari_hnf().sage())

as opposed to

cmp(I.pari_hnf(), J.pari_hnf())

That's not clear to me...

Finally, a Python tip: you can shorten

t = int(I.norm() - J.norm())
if t:
    return cmp(t,0)

return cmp(I.pari_hnf().sage(), J.pari_hnf().sage())

to

return cmp(I.norm(), J.norm()) or cmp(I.pari_hnf().sage(), J.pari_hnf().sage())

[jdemeyer]

comment:13

Replying to @JohnCremona:

I don't think we can trust the comparison of two Pari-GEN objects to mean what we think

What do you think that comparing HNFs should mean? I don't see a meaningful comparison, we just need it to be consistent.

[jdemeyer]

comment:14

Concerning comparisons, there is also #16127 and #17026.

[JohnCremona]

comment:15

OK, so here is an example:

sage: K.<i> = QuadraticField(-1)
sage: I = K.ideal(4+i)
sage: J = K.ideal(4-i)
sage: HI = I.pari_hnf()
sage: HJ = J.pari_hnf()
sage: HIS = HI.sage()
sage: HJS = HJ.sage()
sage: cmp(HI,HJ)
1
sage: cmp(HIS,HJS)
-1

so they diagree. We have

sage: HI, HJ
([17, 4; 0, 1], [17, 13; 0, 1])
sage: HIS, HJS
(
[17  4]  [17 13]
[ 0  1], [ 0  1]
)

and I think that I should come before J but using the pari_hnf as is gives the reverse.

Background: I am making databases of things like elliptic curves over number fields, and am having to be very explicit indeed about how various objects are ordered. This is a special case: two conjugate primes above a rational prime p which plsits in a quadratic field. I need to order these, and want to do so using the HNFs which only differ in one entry. Using pari_hnf is not consistent! (Try the ideals (2+i) and (2-i) and the pari_hnf's compare "correctly".)

I'll have to look at those two other tickets, certainly. Yet another quagmire!

[jdemeyer]

comment:16

Replying to @jdemeyer:

Finally, a Python tip: you can shorten

t = int(I.norm() - J.norm())
if t:
    return cmp(t,0)

return cmp(I.pari_hnf().sage(), J.pari_hnf().sage())

to

return cmp(I.norm(), J.norm()) or cmp(I.pari_hnf().sage(), J.pari_hnf().sage())

Better yet: define a sorting key instead of a comparison function, this is the only(!) way in Python 3 and already works now. Your key would then be the tuple (norm,hnf). See http://python3porting.com/preparing.html#when-sorting-use-key-instead-of-cmp

[jdemeyer]

comment:17

Replying to @JohnCremona:

I'll have to look at those two other tickets, certainly.

I think that those will solve your problem, since matrices would be compared entry-wise, starting with the first column (top-left entry first, then the one below that).

[JohnCremona]

comment:18

Replying to @jdemeyer:

Replying to @JohnCremona:

I'll have to look at those two other tickets, certainly.

I think that those will solve your problem, since matrices would be compared entry-wise, starting with the first column (top-left entry first, then the one below that).

Right, so I have some work to do, and this ticket will acqure another dependency or two -- I hope those two tickets are not going to get held up!

[JohnCremona]

comment:19

Thanks a lot for your help and suggestions. I did not need that ideal comparison for this ticket anyway, so I have left alone the ideal comparison function except to tidy the code as you suggested. the two elliptic curve comparison functions have gone, replaced by little key comparison functions in the code where they are used -- much better and shorter and faster!

I am doing some final testing and then will upload a new branch in which you will find no utility functions in the wrong place.

In the other tickets where you are dealing with comparing pari objects, good luck: if you have not already discovered this, you will find that hunderds of number field factorizations have their orders changed....

[jdemeyer]

comment:20

Replying to @JohnCremona:

Background: I am making databases of things like elliptic curves over number fields, and am having to be very explicit indeed about how various objects are ordered.

Before worrying about ideals, first consider the ring O_K. Since the HNF is essentially coordinates w.r.t. to a basis, the chosen Z-basis of O_K also matters a lot. For quadratic fields, one can easily define a canonical basis, but in higher degree that gets a lot more tricky.

[JohnCremona]

comment:21

Replying to @jdemeyer:

Replying to @JohnCremona:

Background: I am making databases of things like elliptic curves over number fields, and am having to be very explicit indeed about how various objects are ordered.

Before worrying about ideals, first consider the ring O_K. Since the HNF is essentially coordinates w.r.t. to a basis, the chosen Z-basis of O_K also matters a lot. For quadratic fields, one can easily define a canonical basis, but in higher degree that gets a lot more tricky.

Absolutely right! We have had alot of such discussions with the LMFDB project. Personally, I will stick to quadratic fields at least as far as making databases of elliptic curves is concerned (though the LMFDB does have some over the cubic field of discriminant -23).....

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 06d9eb2 to c9bd242

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c9bd242

#16743: moved or deleted various utility functions and simplified come sorting

[JohnCremona]

comment:23

I hope I have done what was wanted. On testing the whole library I find some doctest failures which I think were caused by merging the pari 2.7.1 upgrade branch, and I hope they will go away by themselves. I see that ticket #15767 is merged, but I am not sure whether all of the relevant branch is already merged here.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cfd3f54

#16743: corrected sorting in primes_of_bounded_norm

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c9bd242 to cfd3f54

[JohnCremona]

comment:26

Oops, forgot to sort the primes using a dual key (norm,ideal). Note that the order will change after the comparison of pari gen objects changes.

[jdemeyer]

comment:27

Shaks -> Shanks

[jdemeyer]

comment:28

Hurwitx -> Hurwitz

[jdemeyer]

comment:29

In the implementation of quadclassunit(), using 0 for prec is wrong. Usually, prec arguments are set to prec_bits_to_words(precision) where long precision=0 is the last argument of the Sage method. The flag is obsolete and tech should best be left alone, so I don't mind that you don't allow to set those.

[jdemeyer]

comment:30

The EXAMPLES:: blocks in BinaryQF.solve() and in small_prime_value() are badly indented.

[jdemeyer]

comment:31

In this solve() method, I would prefer it made more clear that you're solving for integers (as opposed to, say, rationals). For example, replace the first line by

Solve `Q(x,y) = n` in integers `x` and `y` where `Q` is this quadratic form.

In the light of a future solve() for rationals, it might even be good to rename this method solve_integer()

[jdemeyer]

comment:32

Obvious failure:

sage -t src/sage/rings/number_field/number_field.py
**********************************************************************
File "src/sage/rings/number_field/number_field.py", line 3073, in sage.rings.number_field.number_field.NumberField_generic.primes_of_bounded_norm
Failed example:
    K.primes_of_bounded_norm(10)
Expected:
    [Fractional ideal (i + 1), Fractional ideal (3), Fractional ideal (-i - 2), Fractional ideal (2*i + 1)]
Got:
    [Fractional ideal (i + 1), Fractional ideal (-i - 2), Fractional ideal (2*i + 1), Fractional ideal (3)]
**********************************************************************

[jdemeyer]

comment:33

You can simplify

from sage.misc.all import flatten
P = flatten([pp for pp in [self.primes_above(p) for p in primes(B+1)]])

by

P = [pp for p in primes(B+1) for pp in self.primes_above(p)]

(note the order of the for statements!)

[jdemeyer]

comment:34

In primes_of_bounded_norm(), why B.ceil()? This would disallow Python ints for no good reason. I think you can remove the whole block

try:
    B = ZZ(B.ceil())
except (TypeError, AttributeError):
    raise TypeError("%s is not valid bound on prime ideals" % B)

[jdemeyer]

comment:35

I'll make a reviewer patch with these changes...

[jdemeyer]

Changed branch from u/cremona/ticket/16743 to u/jdemeyer/ticket/16743

[jdemeyer]

comment:37

These are some reviewer fixes, however I do not intend to fully review this ticket.

---

New commits:

29d2784

Various reviewer fixes

[jdemeyer]

Reviewer: Jeroen Demeyer

[jdemeyer]

Changed commit from cfd3f54 to 29d2784

[JohnCremona]

comment:38

Thanks a lot for tidying various things up ( at least some of which were not introduced by me, I think!).

We do need someone with a good knowledge of isogenies to check this. In writing the code I had to work out quite a lot of mathematics for which I do not know a good source (in the CM and potential CM cases). I am actually using the code a lot all the time now, on many thousands of curves, which is a good test, but the field degrees are small.

I have merged your changes into my branch so if I make any further changes the branch name will go back to what it was (not that it really matters). I did this using

git remote update
git merge trac/u/jdemeyer/ticket/16743
make

(in my own local branch), for the record.

[jdemeyer]

comment:39

I usually use ./sage -dev and then you can simply do ./sage -dev pull.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2d89c05

Add # long time is 2 places where it was needed

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 29d2784 to 2d89c05

[JohnCremona]

comment:41

Replying to @sagetrac-git:

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

2d89c05

Add # long time is 2 places where it was needed

It's pretty shocking that to take a list of 4 elliptic curves and compute their j-invariants and count the distinct ones takes a long time! Even if it is over a number field of degree 6. But so be it.

[jdemeyer]

comment:42

Replying to @JohnCremona:

It's pretty shocking that to take a list of 4 elliptic curves and compute their j-invariants and count the distinct ones takes a long time! Even if it is over a number field of degree 6. But so be it.

No no, it is because those 2 tests depend on an earlier # long time test. The following doesn't work:

sage: x = answer_to_the_ultimate_question()  # long time (7.5 million years)
sage: x
42

If you run this without --long the first line will be skipped and the second line will therefore fail.