A class for ring extensions

[xcaruso]

Sage provides a rich framework for dealing with all classical algebraic structures: rings, fields, algebras, etc.
Nevertheless, given (for instance) two fields K and L with K \subset L, it is not possible to build the extension L/K as a Sage object. However one can easily imagine methods related to this extension (e.g. degree, discriminant, normal_basis, decompose_on_basis, etc.)

With Bruno Grenet, Johan Rosenkilde and Luca De Feo, we raised this issue at Sage Days 75. A summary of our discussion is available
here.

This ticket implements a generic class for ring extensions, and more specific classes for finite free ring extensions (as finite degree field extensions).

Below is a small tutorial extracted from the documentation:

Extension of rings.

Sage offers the possibility to work with ring extensions `L/K` as
actual parents and perform meaningful operations on them and their
elements.

The simplest way to build an extension is to use the method
:meth:`sage.rings.ring.CommutativeRing.over` on the top ring,
that is `L`.
For example, the following line constructs the extension of
finite fields `\mathbf{F}_{5^4}/\mathbf{F}_{5^2}`::

    sage: GF(5^4).over(GF(5^2))
    Field in z4 with defining polynomial x^2 + (4*z2 + 3)*x + z2 over its base

By default, Sage reuses the canonical generator of the top ring
(here `z_4 \in \mathbf{F}_{5^4}`), together with its name. However,
the user can customize them by passing in appropriate arguments::

    sage: F = GF(5^2)
    sage: k = GF(5^4)
    sage: z4 = k.gen()
    sage: K.<a> = k.over(F, gen = 1-z4)
    sage: K
    Field in a with defining polynomial x^2 + z2*x + 4 over its base

The base of the extension is available via the method :meth:`base` (or
equivalently :meth:`base_ring`)::

    sage: K.base()
    Finite Field in z2 of size 5^2

It also possible to building an extension on top of another extension,
obtaining this way a tower of extensions::

    sage: L.<b> = GF(5^8).over(K)
    sage: L
    Field in b with defining polynomial x^2 + (4*z2 + 3*a)*x + 1 - a over its base
    sage: L.base()
    Field in a with defining polynomial x^2 + z2*x + 4 over its base
    sage: L.base().base()
    Finite Field in z2 of size 5^2

The method :meth:`bases` gives access to the complete list of rings in
a tower::

    sage: L.bases()
    [Field in b with defining polynomial x^2 + (4*z2 + 3*a)*x + 1 - a over its base,
     Field in a with defining polynomial x^2 + z2*x + 4 over its base,
     Finite Field in z2 of size 5^2]

Once we have constructed an extension (or a tower of extensions), we
have interesting methods attached to it. As a basic example, one can
compute a basis of the top ring over any base in the tower::

    sage: L.basis_over(K)
    [1, b]
    sage: L.basis_over(F)
    [1, a, b, a*b]

When the base is omitted, the default is the natural base of the extension::

    sage: L.basis_over()
    [1, b]

The method :meth:`sage.rings.ring_extension_element.RingExtensionWithBasis.vector`
computes the coordinates of an element according to the above basis::

    sage: u = a + 2*b + 3*a*b
    sage: u.vector()   # over K
    (a, 2 + 3*a)
    sage: u.vector(F)
    (0, 1, 2, 3)

One can also compute traces and norms with respect to any base of the tower::

    sage: u.trace()           # over K
    (2*z2 + 1) + (2*z2 + 1)*a
    sage: u.trace(F)
    z2 + 1
    sage: u.trace().trace()   # over K, then over F
    z2 + 1

    sage: u.norm()            # over K
    (z2 + 1) + (4*z2 + 2)*a
    sage: u.norm(F)
    2*z2 + 2

And minimal polynomials::

    sage: u.minpoly()
    x^2 + ((3*z2 + 4) + (3*z2 + 4)*a)*x + (z2 + 1) + (4*z2 + 2)*a
    sage: u.minpoly(F)
    x^4 + (4*z2 + 4)*x^3 + x^2 + (z2 + 1)*x + 2*z2 + 2

Depends on #26105

CC: @johanrosenkilde @defeo @bgrenet @nthiery @simon-king-jena @saraedum

Component: algebra

Keywords: sd75, padicBordeaux

Author: Xavier Caruso

Branch: c43507c

Reviewer: David Roe, Frédéric Chapoton

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

[xcaruso]

Branch: u/caruso/21413/class_ring_extension

[sagetrac-git]

Commit: 556da4d

[sagetrac-git]

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

556da4d

Coercion system improved

[sagetrac-git]

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

b5e3eed	Coercion in scalar restriction and scalar extension
c82968f	Small tutorial

[sagetrac-git]

Changed commit from 556da4d to c82968f

[sagetrac-git]

Changed commit from c82968f to 036fb2a

[sagetrac-git]

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

f0a7ce4	Doctest from the class AlgebraFromMorphism and some methods of this class
b6c9a33	Doctest fixed
67c82c7	Merge branch 'develop' into 21413/class_ring_extension
8d70dbe	Code split in several files. More doctests.
efa3689	Doctest for BaseActionOnRing
7f8ce2d	Doctest for the class AlgebraToRing_coercion
991cc70	Doctest for the class AlgebraFMElement
036fb2a	Adding licence & author

[xcaruso]

Description changed:

--- 
+++ 
@@ -3,3 +3,5 @@
 
 With Bruno Grenet, Johan Rosenkilde and Luca De Feo, we raised this issue at Sage Days 75. A summary of our discussion is available 
 [here](https://gist.github.com/defeo/cabab27ea93aeb9e0deb0ba8c5bc745b).
+
+This ticket implements very generic classes for ring extensions. Other more specific classes (e.g. for field extensions or even finite field extensions) are coming soon...

[johanrosenkilde]

comment:6

Wow, this is great Xavier! Sorry for not being more active before - I promise to look more at it tomorrow.

I'm wondering whether it's a good idea to merge the "framework" before the first concrete instantiation? I.e. whether we should try to get the field-extension-algebra finished before considering this as mature? (I know you have bad experience with too large patches, but if we don't put too much stuff in the field extension as a first approximation, perhaps it's ok).

Best,
Johan

[johanrosenkilde]

comment:7

In the following, the extension is A = L/K with L and K rings. L.base() is B.
Sometimes B is a subring of K.

Right now this AlgebraFromMorphism is mainly a thin wrapper around the
L, so e.g. A elements are represented internally as elements of L, and this is
also how you print them. Can you try to convince me of the value from a user's
POV that he can do arithmetic on his elements inside this algebra, rather than
dropping the whole Algebra idea and just letting RingExtension be some
non-parent object with fancy methods on it like decompose_on_basis?

What I had in mind after SD75 is that RingExtension is an Algebra as in "a
vector space equipped with a bilinear product"; in other words, when I want to
see L as a vector space over K, I use RingExtension. In this world, it makes
sense to have arithmetic on elements of A and they should print (and possibly
be internally represented by) vectors over K; because that's the whole point of
why I'm wrapping L.

In that world, AlgebraFromMorphism shouldn't have a gen method because it
isn't really focused on its personality as a ring (it might have a
multiplicative_generator if you like). But it should definitely have a basis
method.

Other remarks that I got by looking at the code. Let's see where the above
discussion takes us before doing much about the stuff below:

1. Why are you not giving self._base as argument to CommutativeAlgebra.__init__? You write in a comment that we don't want a coercion map base -> self -- I don't see why not? I guess this is related to the left/right action dichotomy you have?

2. The module doc for algebra_from_morphism is too short. It should explain what this module is and what is offered.
   Redundancy is not bad.

3. A method "def something(self)" should never have the doc-string "Return the something of self". That's utterly unhelpful :-)

4. from_base_ring has an extremely bad name considering that it doesn't embed an element of the base. I think we need to establish some proper nomenclature and do some commutation diagrams in the doc of this module.

5. The doc for scalar_restriction is very hard to read. Attempt to write before INPUT what this means. Could we write something like

    ```
    If ``newbase`` is a sub-ring of `self.base()`, then the scalar restriction of `self` to `newbase` is the ring extension `self.ring()/newbase`. The defining morphism will be the composition of `f` and ``self.defining_morphism()`` where `f` is the coercion map from `newbase` to `self.base()`.
   
    ``newbase`` can be given as an extension, ... 
   
    ``newbase`` can be given as a morphism, ...
    ```
   

   What is the argument for allowing extensions and morphisms as arguments to scalar_restriction? Is it really something you would normally do? Couldn't the user just do A.scalar_restriction(mymorphism.codomain()), etc.?

6. I don't like ring and base. They are too short and it's not clear which is which.

7. Speaking in parents, you let K * A = A but you let A * K = L. Won't this be a major source of confusion for users? I think your nasty example with non-commutativity at the end of RingExtension doc makes this even worse! I'm also very concerned that this might break several things in Sage since you're inheriting from CommutativeAlgebra.

8. Doc of RingExtension: can we make a commuting diagram to describe the coercion between L1/K1 and L2/K2? Something like

   K1 -----> L1
   ^         |
   |         | 
   |         v
   K2 -----> L2
   

Best,
Johan