Clean up S-class group, S-unit and Selmer group code

[pjbruin]

The code for S-class groups, S-units and Selmer groups of number fields, and more generally étale algebras, is not entirely satisfactory in the following respects:

1. The code for computing Selmer groups is somewhat convoluted. Conceptually, the computation of the generators for principal ideals of the form gen^order belongs in selmer_group, not _S_class_group_and_units. It would be more correct to return, as S-class group generators, pairs (gen, order) instead of triples (gen, order, pr), and leave the computation of the principal ideal generators to selmer_group.

2. The docstrings are not very clear. The sentences are very long and contain awkward constructions ("a fractional ideal representative of the S-class group generator whose order (in the S-class group) is order"; "principal generator").

3. The docstring of NumberField._S_class_group_and_units suggests that to obtain a principal ideal, gen^order can be multiplied by any fractional ideal J whose class is in the subgroup of the class group generated by ideals in S. However, the condition is more strict: J must be in the subgroup of the ideal group generated by ideals in S.

The attached patch does the following things:

1. Move computation of generators of principal ideals from NumberField._S_class_group_and_units to NumberField.selmer_group.

2. Add a method _S_decomposition to PolynomialQuotientRing_generic, which computes the decomposition of an étale algebra as a product of number fields. Use this function in S_class_group, S_units and selmer_group.

3. Delete PolynomialQuotientRing_generic._S_class_group_and_units, and move its code and doctests to S_class_group, class_group, S_units and units.

4. Reimplement PolynomialQuotientRing_generic.selmer_group to compute the Selmer group as the product of the Selmer groups of the distinct components, instead of imitating the algorithm of NumberField.selmer_group.

5. Make the documentation more precise.

Apply: attachment: trac_14746_doctests_32_64_bit_undo.patch, attachment: trac_14746_selmer_group_cleanup.patch, attachment: trac_14746_docstring_fixes.patch

Depends on #14489

CC: @sagetrac-ArgaezG @sagetrac-akoutsianas

Component: number fields

Keywords: S-class group, S-units, Selmer group, sd51

Author: Peter Bruin

Reviewer: John Cremona, Alejandro Argaez, Angelos Koutsianas

Merged: sage-5.12.beta2

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

[pjbruin]

based on 5.10.rc1 + #14489

[pjbruin]

comment:1

Attachment: trac_14746_selmer_group_cleanup.patch.gz

[pjbruin]

Attachment: trac_14746_doctests_32_64_bit_undo.patch.gz

undo the effect of trac_14489_doctests_32_64_bit.patch

[pjbruin]

comment:4

For patchbot:

Apply trac_14746_doctests_32_64_bit_undo.patch, trac_14746_selmer_group_cleanup.patch

[vbraun]

comment:6

The source file needs to specify UTF-8 encoding if you want to use non-ascii characters, but rings/polynomial/polynomial_quotient_ring.py does not. See http://www.python.org/dev/peps/pep-0263/

[pjbruin]

comment:7

Replying to @vbraun:

The source file needs to specify UTF-8 encoding if you want to use non-ascii characters, but rings/polynomial/polynomial_quotient_ring.py does not. See http://www.python.org/dev/peps/pep-0263/

My patch fixes that as well, by adding a line # -*- coding: utf-8 -*- at the beginning (I forgot to mention this in the patch description). Does this conform to the expected syntax?

[pjbruin]

comment:8

After checking the documentation, I doubt that the 'raw' declaration (changing """ to r""") is the right fix. Should u""" be used instead, or is """ OK as long as the file is declared to be UTF-8?

[vbraun]

comment:9

OK, I didn't see the last patch in context. The raw only concerns backlashes but handy to not have to escape \TeX commands. No need for unicode strings.

[pjbruin]

comment:10

I removed the second part of the patch, which changed """ to r""".

[JohnCremona]

comment:11

I hope I can look at this and get it finished next week. Does it provide a class for S-units like the class for units?

[vbraun]

comment:12

Test failure in my 32-bit VM:

File "sage/rings/polynomial/polynomial_quotient_ring.py", line 926, in sage.rings.polynomial.polynomial_quotient_ring.PolynomialQuotientRing_generic._S_decomposition
Failed example:
    S._S_decomposition(tuple(K.primes_above(3)))
Expected:
    ([Number Field in x0 with defining polynomial x^2 + 23 over its base field,
      Number Field in x1 with defining polynomial x^2 + 31 over its base field],
     [(Ring endomorphism of Number Field in y0 with defining polynomial x^4 + 56*x^2 + 324
      Defn: y0 |--> y0,
       0),
      (Ring endomorphism of Number Field in y1 with defining polynomial x^4 + 72*x^2 + 676
      Defn: y1 |--> y1,
       1)],
     [(Number Field in y0 with defining polynomial x^4 + 56*x^2 + 324,
       [Fractional ideal (3, 1/4*y0^2 + 1/2*y0 + 11/2),
        Fractional ideal (3, 1/72*y0^3 + 1/4*y0^2 + 19/36*y0 + 8),
        Fractional ideal (3, 1/36*y0^3 + 1/4*y0^2 + 5/9*y0 + 13/2),
        Fractional ideal (3, 1/72*y0^3 + 1/4*y0^2 + 19/36*y0 + 6)]),
      (Number Field in y1 with defining polynomial x^4 + 72*x^2 + 676,
       [Fractional ideal (3, -1/52*y1^3 - 23/26*y1 - 1),
        Fractional ideal (3, -1/52*y1^3 - 23/26*y1 + 1)])])
Got:
    ([Number Field in x0 with defining polynomial x^2 + 23 over its base field, Number Field in x1 with defining polynomial x^2 + 31 over its base field], [(Ring endomorphism of Number Field in y0 with defining polynomial x^4 + 56*x^2 + 324
      Defn: y0 |--> y0, 0), (Ring endomorphism of Number Field in y1 with defining polynomial x^4 + 72*x^2 + 676
      Defn: y1 |--> y1, 1)], [(Number Field in y0 with defining polynomial x^4 + 56*x^2 + 324, [Fractional ideal (3, -1/4*y0^2 - 1/2*y0 - 11/2), Fractional ideal (3, 1/72*y0^3 + 1/4*y0^2 + 19/36*y0 + 8), Fractional ideal (3, 1/36*y0^3 - 1/4*y0^2 + 14/9*y0 - 17/2), Fractional ideal (3, 1/72*y0^3 + 1/4*y0^2 + 19/36*y0 + 6)]), (Number Field in y1 with defining polynomial x^4 + 72*x^2 + 676, [Fractional ideal (3, -1/52*y1^3 - 23/26*y1 - 1), Fractional ideal (3, -1/52*y1^3 - 23/26*y1 + 1)])])

Edit: sorry had the wrong ticket number, this is the failure I'm getting.

[pjbruin]

comment:13

Replying to @JohnCremona:

I hope I can look at this and get it finished next week. Does it provide a class for S-units like the class for units?

It doesn't add new (user-level) functionality, but the clean-up might make it easier to add this in the future.

[pjbruin]

comment:14

Replying to @vbraun:

Test failure in my 32-bit VM:

With hindsight I could have guessed that the new doctest would create another 32/64-bit difference... I am preparing a patch that

• adds a bit more explanation to the docstring;
• instead of checking the generators of the primes lying above 3, just checks whether the number of such primes is correct;
• makes a trivial simplification in the code;
• changes back """ to r""" in two docstrings, since they contain backslashes.

[pjbruin]

Attachment: trac_14746_docstring_fixes.patch.gz

add doctest, utf-8 declaration, r""" for backslashes, trivial edit in code

[loefflerd]

Changed keywords from S-class group, S-units, Selmer group to S-class group, S-units, Selmer group, sd51

[JohnCremona]

comment:16

All three patches apply fine to (5.11.beta3 + the two patches from #14489).
Most of the changes here are cosmetic, moving code around and improving the documentation, and they look fine to me. Testing now...

[JohnCremona]

Reviewer: John Cremona, Alejandro Argaez, Angelos Koutsianas

[JohnCremona]

comment:18

All tests (including long) pass in sage/rings, so I'll give this a positive review.

[jdemeyer]

Merged: sage-5.12.beta2

[JohnCremona]

comment:22

See #16496.