Improve Selmer Group method for number fields

[JohnCremona]

If K is a number field and S a finite set of primes of K, then for any m > 1 there is a finite multiplicative abelian group of exponent at most m called the m-Selmer group, denoted K(S, m), a subgroup of K<sup>*/(K</sup>*)^m.

The existing method K.selmer_group(m) returns a list of elements of K^* which generate K(S, m), with no access to the group structure. There is also a utility method K.selmer_group_iterator(m) which I wrote ages ago to make it easy to iterate through all the elements of the group. There is no method to determine whether a given element of K^* represents an element of K(S, m) and if so express it in terms of the generators.

For many applications of mine I have needed something better, and for m = p prime I have code for a function pSelmerGroup(K, S, p) which returns a quadruple (KSp, KSp_gens, from_KSp, to_KS_p) where KSp is an abstract vector space over GF(p), KSp_gens is a set of elements of K^* which generate K(S, p) (similar to K.selmer_group(S, p)), from_KSp is a map from the abstract KSp to K^* (the easy one) and to_KSp is the harder map from a subset of K^* to the vector space.

Together with some utilities this is about 560 lines of code, with docstrings but no doctest yet. I intend to add this to Sage.

There are two issues: (1) it would make sense to have K.selmer_group(S, p) return the quadruple as above, but this would not be backwards compatible; (2) the new functionality is only for prime p, not general m. I have no plans for a general version, giving a finite abelian group rather than a vector space, though for elliptic curve applications the cases m = 4, m = 6, m = 12 are all useful. There's a version of the Chinese Remainder Theorem at play here so m = 6 is easy using m = 2 and m = 3, and m = 12 is easy given m = 3 and m = 4, while m = 4 requires real work. I implemented these cases some time ago in Magma, where I also implemented the prime case, so it is possible.

I am not sure how to solve the backwards compatibility issue. Places in Sage itself will be easy to handle (there are not many), but to avoid breaking user code will be harder unless I use a new name for the new method, perhaps K.selmer_space(S, p), though "Selmer space" is not standard terminology. I'll think of something by the time I have a patch ready for review.

Component: number fields

Author: John Cremona

Branch/Commit: 257a47d

Reviewer: David Roe

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

[slel]

Description changed:

--- 
+++ 
@@ -1,11 +1,11 @@
-Ik K is a number field and S a finite set of primes of K, then for any m>1 there is a finite multiplcative abelian group of exponent at most m called the m-Selmer group, denoted K(S,m), a subgroup of `K<sup>*/(K</sup>*)^m`.
+If `K` is a number field and `S` a finite set of primes of `K`, then for any `m > 1` there is a finite multiplicative abelian group of exponent at most `m` called the `m`-Selmer group, denoted `K(S, m)`, a subgroup of `K<sup>*/(K</sup>*)^m`.

-The existing method K.selmer_group(m) returns a list of elements of `K^*` which generate K(S,m), with no access to the group structure.  There is also a utility method K.selmer_group_iterator(m) which I wrote ages ago to make it easy to iterate through all the elements of the group.  There is no method to determine whether a given element of `K^*` represents an element of K(S,m) and if so express it i terms of the generators.
+The existing method `K.selmer_group(m)` returns a list of elements of `K^*` which generate `K(S, m)`, with no access to the group structure.  There is also a utility method `K.selmer_group_iterator(m)` which I wrote ages ago to make it easy to iterate through all the elements of the group.  There is no method to determine whether a given element of `K^*` represents an element of `K(S, m)` and if so express it in terms of the generators.

-For many applications of mine I have needed something better, and m=p prime I have code for a function pSelmerGroup(K, S, p) which returns a quadruple (KSp, KSp_gens, from_KSp, to_KS_p) where KSp is an abstract vector space over GF(p), KSp_gens is a set of elements of `K^*` which generate K(S,p) (similar to K.selmer_group(S,p)), from_KSp is a map from the abstract KSp to `K^*` (the easy one) and to_KSp is the harder map from a subset of `K^*` to the vector space.
+For many applications of mine I have needed something better, and for `m = p` prime I have code for a function `pSelmerGroup(K, S, p)` which returns a quadruple `(KSp, KSp_gens, from_KSp, to_KS_p)` where `KSp` is an abstract vector space over `GF(p)`, `KSp_gens` is a set of elements of `K^*` which generate `K(S, p)` (similar to `K.selmer_group(S, p)`), `from_KSp` is a map from the abstract `KSp` to `K^*` (the easy one) and `to_KSp` is the harder map from a subset of `K^*` to the vector space.

 Together with some utilities this is about 560 lines of code, with docstrings but no doctest yet.  I intend to add this to Sage.

-There are two issues: (1) it would make sense to have K.selmer_group(S, p) return the quadruple as above, but this would not be backwards compatible; (2) the new functionality is only for prime p, not general m.  I have no plans for a general version, giving a finite abelian group rather than a vector space, though for elliptic curve applications the cases m=4, m=6, m=12 are all useful.  There's a version of the Chinese Remainder Theorem at play here so m=6 is easyusing m=2,3, and m=12 is easy given m=3,4, while m=4 requires real work.  I implemented these cases some time ago in Magma, where I also implemented the prime case, so it is possible.
+There are two issues: (1) it would make sense to have `K.selmer_group(S, p)` return the quadruple as above, but this would not be backwards compatible; (2) the new functionality is only for prime `p`, not general `m`.  I have no plans for a general version, giving a finite abelian group rather than a vector space, though for elliptic curve applications the cases `m = 4`, `m = 6`, `m = 12` are all useful.  There's a version of the Chinese Remainder Theorem at play here so `m = 6` is easy using `m = 2` and `m = 3`, and `m = 12` is easy given `m = 3` and `m = 4`, while `m = 4` requires real work.  I implemented these cases some time ago in Magma, where I also implemented the prime case, so it is possible.

-I am not sure how to solve the backwards compatibility issue.  Places in Sage itself will be easy to handle (there are not many), but to avoid breaking user code will be harder unless I use a new name for the new method, perhaps K.selmer_space(S, p), though "Selmer space" is not standard terminology.  I'll think of something by the time I have a patch ready for review.
+I am not sure how to solve the backwards compatibility issue.  Places in Sage itself will be easy to handle (there are not many), but to avoid breaking user code will be harder unless I use a new name for the new method, perhaps `K.selmer_space(S, p)`, though "Selmer space" is not standard terminology.  I'll think of something by the time I have a patch ready for review.

[JohnCremona]

comment:2

Thanks for tidying up the description.

What do you think about the name of the new method? Preferable -- at least in the end -- would be to rename the current method called selmer_group to selmer_generators (which is a more accurate description) and have the new one called selmer_group. But that obviously breaks backwards compatibility. I do not see how to manage this using the Deprecation mechanism, so please tell me how to do that if it can be done.

Meanwhile what I will do is this: I'll change the method selmer_group to generators, at the same time adding the line selmer_group = selmer_generators in the number field class and changing all uses to this method within Sage source code to use the new name; I will call my new method selmer_space. Then at some future point we can possibly make selmer_group the same as selmer_space instead of selmer_generators.

[JohnCremona]

comment:3

The main new code is in a new file selmer_group.py, with interface via new methods selmer_space for both number fields and the rational field.

Towards the backwards compatibility, here is what I did: I changed the name of the existing method selmer_group (in those two places and in polynomial_quotient_ring) to selmer_generators, but also for compatibility added an alias in all three places so that the method selmer_group still works. In a small number of places where the old selmer_group method was used I changed it to selmer_generators.

I think there will be a couple of follow-up tickets to sort out things I spotted but which I did not want to complicate this ticket with. (1) Where the selmer_generators method is used in (elliptic curve) gal_rep_number_field, it is possible that the loop should be through all nontrivial elements of the selmer group, not just the generators. (2) In the etale algebra code in polynomial_quotient_ring, written (I think) ages ago by Robert Miller, there should be a non-hidden method to compute the decomposition as a sum of number fields, which does not refer to any set S of primes; and the hidden function which does this now looks rather inefficiently coded as well as probably being incorrect (at one point it computes an isomorphism from a field D_abs to itself but I think it means to compute one from D to D_abs or vice versa). Those two issues are best dealt with after this is merged.

I do have some application of my own waiting in the wings which will use this new improved Selmer group.

---

New commits:

557591c	#31345: implementation of Selmer groups of number fields
99dce60	fix docstring issues
ddadaac	Merge remote-tracking branch 'trac/develop' into 31345-KSp
d7c7378	#31345: check in new file, previously forgotten

[JohnCremona]

Commit: d7c7378

[JohnCremona]

Branch: u/cremona/31345

[mkoeppe]

comment:4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[roed314]

Reviewer: David Roe

[roed314]

comment:5

Overall it looks good. As a followup ticket, it shouldn't be too hard to make things work for m=4 using #31548, which makes left_kernel function for matrices mod 4.

• I would suggest having selmer_group print a deprecation warning (from sage.misc.superseded), so that we can switch it from selmer_generators to selmer_space eventually.
• The Sage docstring convention seems to be to start on the line after the triple quotes
• Your version of the copyright notice is different than what I'm used to in Sage; I would probably copy the copyright notice from another file (e.g. number_field.py)
• Does ideal_generator ever return a negative integer, and if so would it be better to return the absolute value in this case?
• coords_in_C_p will return an incorrect result if passed an ideal that has coordinate in a p-index location that's not divisible by n//p (since you're just doing floor division). You should probably add a test like all(coords[i] % n == 0 for (i, n) in p_indices).
• Similarly, root_ideal doesn't check that the input is a p-th power.
• Typos in the docstring for pSelmerGroup: th p'th powers and al ist
• There's an indentation problem in selmer_space over Q (In general there is one generator...), which also needs another newline afterward
• There are some grammar problems in the error message for at all prime in

[JohnCremona]

comment:6

Thanks a lot for the review (at last!). I will deal with the issues you raise.

[JohnCremona]

comment:7

Replying to @roed314:

Overall it looks good. As a followup ticket, it shouldn't be too hard to make things work for m=4 using #31548, which makes left_kernel function for matrices mod 4.

• I would suggest having selmer_group print a deprecation warning (from sage.misc.superseded), so that we can switch it from selmer_generators to selmer_space eventually.

Not yet fixed. Currently I just use assignment selmer_group = selmer_group_generators and to implement this suggestion I think it would have to be a genuine separate method with full docstring, which I have not yet done.

• The Sage docstring convention seems to be to start on the line after the triple quotes

Unfortunately emacs python-mode disagrees so I always have to fix these manually and often miss some. I think I have fixed them now.

• Your version of the copyright notice is different than what I'm used to in Sage; I would probably copy the copyright notice from another file (e.g. number_field.py)

Oops, I left in what I had from when it was a separate piece of my own code. I copied from number_field.py (changing name).

• Does ideal_generator ever return a negative integer, and if so would it be better to return the absolute value in this case?

It's an internal function, so no -- but I put in I.abs() for the case where I is an integer rather than an ideal. But this is an internal function so does not do checking of its input. I have also added an underscore prefix to the function name, and also for the two coords_in functions.

• coords_in_C_p will return an incorrect result if passed an ideal that has coordinate in a p-index location that's not divisible by n//p (since you're just doing floor division). You should probably add a test like all(coords[i] % n == 0 for (i, n) in p_indices).

Thanks for catching that, I have put in tthe second part of the test for being p-torsion, which also ensures that the division is exact. This should not matter in practice since the function will only be called with ideals whose p'th power is principal, but it is still good to check properly.

• Similarly, root_ideal doesn't check that the input is a p-th power.

Check added.

• Typos in the docstring for pSelmerGroup: th p'th powers and al ist

Fixed

• There's an indentation problem in selmer_space over Q (In general there is one generator...), which also needs another newline afterward

Fixed

• There are some grammar problems in the error message for at all prime in

Fixed.

OK, I have fixed all but the deprecation, which I will come back to after building the documentation to check on all the docstrings.

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

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

f5fef1d	Merge branch 'develop' into 31345-KSp
1658dda	#31345 revisions after review

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

Changed commit from d7c7378 to 1658dda

[JohnCremona]

comment:9

I have still not addressed teh deprecation question, but all else should be fixed.

[fchapoton]

comment:10

one trivial failing doctest in src/sage/rings/rational_field.py

[JohnCremona]

comment:11

Replying to @fchapoton:

one trivial failing doctest in src/sage/rings/rational_field.py

Sorry to be dim, but I see that error but don't know why it is occurring: it complains that there is an extra before the ValueError message.

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

Changed commit from 1658dda to cfbe590

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

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

cfbe590

#31345 fix typo in error message

[JohnCremona]

comment:13

OK, fixed. (The BLANKLINE distracted me from the actual error, which was just that I had corrected the grammar in the error message.)

[roed314]

comment:14

For the deprecation, I'd suggest just using deprecated_function_alias from sage.misc.superseded. I understand about emacs being a bit misconfigured for Sage's docstring conventions: I always have to add 4 spaces manually in EXAMPLE blocks. I think you just missed one more: class_number in number_field.py.

Otherwise, it looks good!

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

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

9aa52e2

#31345: added deprecation aliases

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

Changed commit from cfbe590 to 9aa52e2

[JohnCremona]

comment:16

I added deprecation aliases in both places, and also fixed the docstring formatting issue raised (and one other I found).

The deprecation aliases seem to work as expected, in tha if you call QQ.selmer_group() or K.selmer_group() for a number field K, then it outputs a message asking the user to use selmer_generators() instead, before calling selmer_generators(). It is not perfect, since it does not also recommend that the user might want to use selmer_space() instead for extra functionality -- I don't think that the deprecation alias machinery can handle that -- and also, I noticed that the deprecation warning appears every time you call the deprecated method, not just the first time. But neither of these should hold up this enhancement.

[JohnCremona]

comment:17

Perhaps I could also add a separate deprecation warning to the selmer_generators() method too, when it is called with a prime, alerting the user to the selmer_space() method which gives more functionality?

[roed314]

comment:18

I don't think we need to use a deprecation warning on selmer_generators. If you want to make selmer_space more findable, you could add a SEEALSO block to selmer_generators. You could also use the more general deprecation function in selmer_group and point to selmer_space in the message, but that would require writing out the function instead of just using selmer_group = deprecated_function_alias....

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

Changed commit from 9aa52e2 to df80c65

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

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

df80c65

#31345: removed the additions Deprecation Warnings introduced in the previous commit, and added two SEEALSO blocks

[JohnCremona]

comment:20

Replying to @roed314:

I don't think we need to use a deprecation warning on selmer_generators. If you want to make selmer_space more findable, you could add a SEEALSO block to selmer_generators. You could also use the more general deprecation function in selmer_group and point to selmer_space in the message, but that would require writing out the function instead of just using selmer_group = deprecated_function_alias....

OK, I removed the additional deprecation warnings introduced, converted the NOTE block cross-referencing to selmer_space into a SEEALSO block, and added a similar SEEALSO block for the RationalField case.

I hope this can finally be given a green light now!

[fchapoton]

comment:21

doc does not build, because the seealso block is not correctly indented.

[JohnCremona]

comment:22

Replying to @fchapoton:

doc does not build, because the seealso block is not correctly indented.

Dammit I already spent time fixing that exact issue and thought I had. I'll get back onto it.

[JohnCremona]

comment:23

Please tell me why the SEEALSO block in rational_field.py is OK but the one in number_field.py is not, since they are indented the same way as far as I can see.

[fchapoton]

comment:24

both are wrong, I think

[JohnCremona]

comment:25

Replying to @fchapoton:

both are wrong, I think

Fixed. I think. I'm sure this is the indentation I put in originally, then I saw an error message and changed it.

This sort of error is extremely tedious to fix since the error message is insufficient and it takes 5-10 minutes for each "make" even if you only touch one file.

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

Changed commit from df80c65 to 257a47d

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

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

257a47d

#31345: fix indentation in 2 docstrings

[fchapoton]

comment:27

looks good now

I agree that the error message is sometimes not so clear

Note that sage -docbuild can be launched on a single file, or on just one component like combinat or schemes.

[fchapoton]

comment:28

green bot. I will let David give the final word.

[roed314]

comment:29

Looks good to me!

[vbraun]

Changed branch from u/cremona/31345 to 257a47d