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