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

[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

[xcaruso]

comment:8

Replying to @johanrosenkilde:

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?

Maybe I misunderstand your proposal but I really think that a ring extension should be a parent because we really want to take advantage of the coercion stuff.
Nonetheless, the question "should it derive from CommutativeAlgebra?" is arguable and I can imagine arguments in both directions.

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.

It is definitely.

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.

I agree. But all of this has to be implemented in subclasses. For now, I just wrote a very general class which is supposed to deal with all algebras (possibly not free, not finite...) so it is of course difficult to implement concrete methods.

But these methods clearly exist. Here is a far-from-exhaustive list: scalar_restriction (which is already implemented), __mul__ (usual product of algebras), tensor_product, scalar_extension, cayley_differentials, krull_relative_dimension, is_free, is_finite, is_flat, is_etale, is_smooth, is_open_immersion, is_closed_immersion, is_galois, galois_group. And for elements: trace, norm.

If you insist, I can put these methods in the general class and let them raise NotImplementedError... but it would be difficult to write the doctest :-)

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).

The generator of an algebra is a well-defined mathematical notion: the algebra L/K is generated by x if $K \cup {x}$ generates L as a ring. So it clearly makes sense to have a gen method.

But it should definitely have a basis method.

Well there does exist algebras which are not free. So the basis method is clearly something we want. However it should not be inserted in such a general class but in the subclass FreeAlgebraFromMorphism or FiniteFreeAlgebraFromMorphism (which is coming soon).

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?

Suppose that we create an algebra L/K with a defining morphism phi : K -> L which is not a coercion map. If K coerces to L/K through phi and L/K coerces to L, then we would derive that K coerces to L through phi.

Such a situation really occurs in every day life (at least for people working in algebraic geometry). For instance, if K has characteristic p, these people often consider K as an algebra over itself through the Frobenius morphism (which is definitely not a coercion map).

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.

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

Ok for both. I'll try to fix this.

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.

It is not my fault :-). This method is needed by the coercion model.

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

Ok. I'll do it.

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.?

Sure, it is something we normally do... just as composing ring homomorphisms.

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

Ok for changing. I'm also not completed satisfied with these names. Do you have some propositions?

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 definitely agree that it is not perfect, but I have not found something better :-).
The point is that I really want to have algebras_from_morphisms_which_are_not_coercion_maps and I think that implementing the action of scalars (through the defining morphism) is the least we can do.

I'm also very concerned that this might break several things in Sage since you're inheriting from CommutativeAlgebra.

It is one reason why I'm sure that we should inherit from CommutativeAlgebra

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

Ok.

Xavier

[johanrosenkilde]

comment:9

Thanks for your careful explanations. I'm learning a lot here.

Replying to @xcaruso:

Maybe I misunderstand your proposal but I really think that a ring extension should be a parent because we really want to take advantage of the coercion stuff.

Nonetheless, the question "should it derive from CommutativeAlgebra?" is arguable and I can imagine arguments in both directions.

OK, so "coercion stuff" is an argument in favour of a Parent. I guess you mean that many objects will magically coerce to the Do-What-I-Mean behaviour on methods. But if a weird/surprising behaviour follows from forcing it into the category framework, perhaps that's an argument against it.

At least having a RingExtension being a class with lots of service methods, sort of like David's RelativeFiniteFieldExtension, there will be no arithmetic problems. You could also put norm and trace there.

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.

I agree. But all of this has to be implemented in subclasses. For now, I just wrote a very general class which is supposed to deal with all algebras (possibly not free, not finite...) so it is of course difficult to implement concrete methods.

OK, that makes sense. I can see why the general class would have very weak functionality then.

But these methods clearly exist. Here is a far-from-exhaustive list: ....
If you insist, I can put these methods in the general class and let them raise NotImplementedError... but it would be difficult to write the doctest :-)

Perhaps that's not a bad idea: it's nicer that any algebra will have the methods you expect and then throw NotImplementedError rather than not advertising the method at all.

The doc-test can be on a more concrete class that does implement the method. If none exist for this ticket, the doc-test will just be one demonstrating the NotImplentedError for now, with the sole purpose of doc-test coverage ;-)

The generator of an algebra is a well-defined mathematical notion: the algebra L/K is generated by x if $K \cup {x}$ generates L as a ring. So it clearly makes sense to have a gen method.

Hmm, but couldn't there be multiple generators? E.g. F[x,y]/F?

Well there does exist algebras which are not free. So the basis method is clearly something we want. However it should not be inserted in such a general class but in the subclass FreeAlgebraFromMorphism or FiniteFreeAlgebraFromMorphism (which is coming soon).

OK, argument accepted. But I think this kind of stuff reinforces that we should try to design the first concrete RingExtension, e.g. FiniteFieldExtension simultaneously with this ticket. Then we'll better be able to judge what goes where and how it should look to be useful on both sides.

Suppose that we create an algebra L/K with a defining morphism phi : K -> L which is not a coercion map. If K coerces to L/K through phi and L/K coerces to L, then we would derive that K coerces to L through phi.

Such a situation really occurs in every day life (at least for people working in algebraic geometry). For instance, if K has characteristic p, these people often consider K as an algebra over itself through the Frobenius morphism (which is definitely not a coercion map).

Yikes! So we must disallow coercion from K -> L/K. But we should allow A(k)
and k*a, a*k, k + a, etc. for k in K and a in A. And A(a * l) is
different from a * A(l). Oh man...

It seems to me that this is really dangerous territory - but perhaps
unavoidable. Someone implementing algorithms for CommutativeAlgebra is going
to assume that there is coercion from base to self. And that multiplication
of base and self elements commute!

Perhaps CommutativeAlgebra should be called something different, and
AlgebraFromMorphism should have a different base class. I've cc'ed Nicolas
Thiery and Simon King in this discussion to chip in.

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.

It is not my fault :-). This method is needed by the coercion model.

Eew, yet another symptom that we're perhaps abusing the current hierarchy.

Why doesn't GF(9) have from_base_ring? What kind of Parent requires it?

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.?

Sure, it is something we normally do... just as composing ring homomorphisms.

So it is something where established mathematical notation supports this
directly? It's much more explicit to just write
A.scalar_restriction(Aother.ring()), so I'd prefer not supporting
A.scalar_restriction(Aother), except if a properly educated mathematician
would be very surprised if this didn't exist.

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

Ok for changing. I'm also not completed satisfied with these names. Do you have some propositions?

We should probably first figure out what to do hierarchy-wise. But perhaps
keep ring -> ring_of_element and base -> ring_of_scalars. Alternative element_ring resp. scalar_ring.

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 definitely agree that it is not perfect, but I have not found something better :-).
The point is that I really want to have algebras_from_morphisms_which_are_not_coercion_maps and I think that implementing the action of scalars (through the defining morphism) is the least we can do.

What do you mean "is the least we can do"?

Why is this an argument to make left and right actions different? Couldn't you implement the same left/right action, namely mapping K -> A by phi, followed by multiplication in A.

Best,
Johan

[xcaruso]

comment:10

Replying to @johanrosenkilde:

Perhaps that's not a bad idea: it's nicer that any algebra will have the methods you expect and then throw NotImplementedError rather than not advertising the method at all.

OK. But, on the other hand, the list of possible methods is possibly quite long. Having a parent with 90% not implemented methods is also not that nice.

The generator of an algebra is a well-defined mathematical notion: the algebra L/K is generated by x if $K \cup {x}$ generates L as a ring. So it clearly makes sense to have a gen method.

Hmm, but couldn't there be multiple generators? E.g. F[x,y]/F?

Yes, of course.

For traditional rings, the current behaviour of gen is rather stange (to me):

    sage: R.<x,y> = QQ[]
    sage: R.gen()
    x

Is that normal?

OK, argument accepted. But I think this kind of stuff reinforces that we should try to design the first concrete RingExtension, e.g. FiniteFieldExtension simultaneously with this ticket. Then we'll better be able to judge what goes where and how it should look to be useful on both sides.

I just do not want this ticket to become too big.
But I agree for implementing FiniteFieldExtension here.

Yikes! So we must disallow coercion from K -> L/K. But we should allow A(k)
and k*a, a*k, k + a, etc. for k in K and a in A. And A(a * l) is
different from a * A(l). Oh man...

(First, let me emphasize that this issue only occurs when the defining morphism is not a coercion map.)

Currently A(k), a*k, k + a uses coercion maps (and not defining morphism): for instance, if K coerces to L then k+a is the addition in L while if K does not coerce to L, k+a produces an error. Only k*a (implemented by a left action of K on L/K) uses the defining morphism.

I agree that it is really confusing but the same confusion appears exactly in the same way in the "theory". So I assume that people who really wants to work with algebras whose defining morphisms are not coercion maps are very aware of this source of confusion!

Why left action and not right action? Because usually scalars act on the left (for instance, we write 2x and not x2 when x lies in some vector space). I nevertheless agree that this convention is not very strong. Another option would be to implement both actions (at some point I actually did this) but it then becomes impossible to multiply an element of K by an element of L without writing explicitly the conversion.

Probably the best solution would be to have a completely different operator for the action of the base through the defining morphism. But which one? Is it a good idea to override the dot operator?

Why doesn't GF(9) have from_base_ring? What kind of Parent requires it?

I think (but I'm not quite sure) that it is used when no coercing map is set from self._base to self.

So it is something where established mathematical notation supports this
directly? It's much more explicit to just write
A.scalar_restriction(Aother.ring()), so I'd prefer not supporting
A.scalar_restriction(Aother), except if a properly educated mathematician
would be very surprised if this didn't exist.

I think that sometimes mathematicians may want to invoke A.scalar_restriction(Aother). For instance assume that we have an algebra A defined over C[X]. The fibre of A at the point x is by definition the scalar extension of A with respect to the morphism C[X] -> C mapping X to x. (It is actually also A/(X-x), but sometimes we really want to think of it as a scalar extension.)

Actually we probably prefer to use the "base_change" in that case. So maybe we can implement two methods: first scalar_extension which always uses coercion maps and second base_change which accepts all constructions.

I think that implementing the action of scalars (through the defining morphism) is the least we can do.

What do you mean "is the least we can do"?

When we want to regard L as a K-algebra, a basic thing we want to have is the action of K on L defining the algebra.

[kwankyu]

comment:11

I just found this ticket and I only have a vague idea about what this ticket does. I am curious if the present ticket would solve or at least help one solve each of the following problems (of mine)? I believe that these cases are not supported by Sage yet.

1. Suppose F is a non-prime finite field, say GF(3^2). I want to construct an extension field E over F. So E,phi=F.extension(4,map=True) gives the extension field GF(3^8)and the embedding phi. This currently only works for prime fields.

2. Suppose K is a field and R is a subring of K. Suppose K is the fraction field of R. Let e be an element of K. Then d=e.denominator(R) gives a denominator of e in R such that d*e.numerator(R) is in R.

3. Let E,F be rings. Suppose phi is a homomorphism from E to F. I want to extend phi to a homomorphism psi from the polynomial ring R=E[x] to F mapping x to c in F. Thus psi(a2*x<sup>2+a1*x+a0)==phi(a2)*c</sup>2+phi(a1)*c+phi(a0). Perhaps I want R.hom([c],F, base=phi) or like to work.

[johanrosenkilde]

comment:12

Replying to @kwankyu:

1. Suppose F is a non-prime finite field, say GF(3^2). I want to construct an extension field E over F. So E,phi=F.extension(4,map=True) gives the extension field GF(3^8)and the embedding phi. This currently only works for prime fields.

That currently works fine, just try it.

If you want to go from F back to E for any of the elements phi(E), use phi.section().

If you want to express F as a vector space over E, things are more limited. We implemented basic support for it in sage.coding.relative_finite_field_extension. This ticket is about making that functionality much more general and thought out, and getting it into the core algebra of Sage.

2. Suppose K is a field and R is a subring of K. Suppose K is the fraction field of R. Let e be an element of K. Then d=e.denominator(R) gives a denominator of e in R such that d*e.numerator(R) is in R.

That also currently works fine. I just tested with R = GF(3^2)['x']:

sage: R = GF(3^2)['x']
sage: K = R.fraction_field()
sage: e = K.random_element()
sage: e.denominator()
(z2 + 2)*x^2 + (z2 + 1)*x
sage: e.denominator().parent()
Univariate Polynomial Ring in x over Finite Field in z2 of size 3^2
sage: e.denominator() in R
True
sage: R( e.denominator() * e )
(2*z2 + 2)*x^2 + (z2 + 2)*x + z2

3. Let E,F be rings. Suppose phi is a homomorphism from E to F. I want to extend phi to a homomorphism psi from the polynomial ring R=E[x] to F mapping x to c in F. Thus psi(a2*x<sup>2+a1*x+a0)==phi(a2)*c</sup>2+phi(a1)*c+phi(a0). Perhaps I want R.hom([c],F, base=phi) or like to work.

That seems more tricky to do. Note that it can easily be split into the composition of two homomorphisms:

mapCoef:  E[x]  --> F[x]
          a*x^i |-> phi(a)*x^i

eval:     F[x] --> F
             x |-> c

The eval homomorphism can be created in the current Sage, but I don't know how to conveniently create mapCoef (as a Morphism object).

Best,
Johan

[kwankyu]

comment:13

Replying to @johanrosenkilde:

Replying to @kwankyu:

1. Suppose F is a non-prime finite field, say GF(3^2). I want to construct an extension field E over F. So E,phi=F.extension(4,map=True) gives the extension field GF(3^8)and the embedding phi. This currently only works for prime fields.

That currently works fine, just try it.

If you want to go from F back to E for any of the elements phi(E), use phi.section().

If you want to express F as a vector space over E, things are more limited. We implemented basic support for it in sage.coding.relative_finite_field_extension. This ticket is about making that functionality much more general and thought out, and getting it into the core algebra of Sage.

Nice. Good luck!

[kwankyu]

comment:14

The following reference might be useful for the design of the class:

Lattices of Compatibly Embedded Finite Fields - WIEB BOSMA, JOHN CANNON AND ALLAN STEEL 1997

as various extensions should be compatible to each other...

[defeo]

Changed branch from u/caruso/21413/class_ring_extension to u/defeo/21413/class_ring_extension

[defeo]

comment:16

Doctest failures:

sage -t src/sage/rings/algebra_from_morphism.py
**********************************************************************
File "src/sage/rings/algebra_from_morphism.py", line 260, in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
Failed example:
    E2._pushout_(E1) is E2
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/rings/algebra_from_morphism.py", line 262, in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
Failed example:
    E1._pushout_(E2) is E2
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/rings/algebra_from_morphism.py", line 265, in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
Failed example:
    E1._pushout_(L2) is L2
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/rings/algebra_from_morphism.py", line 272, in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
Failed example:
    E1p._pushout_(E2) is L2
Expected:
    True
Got:
    False
**********************************************************************
File "src/sage/rings/algebra_from_morphism.py", line 276, in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
Failed example:
    E1p._pushout_(E2p) is L2
Expected:
    True
Got:
    False
**********************************************************************
1 item had failures:
   5 of  11 in sage.rings.algebra_from_morphism.AlgebraFromMorphism._pushout_
    [119 tests, 5 failures, 0.86 s]
----------------------------------------------------------------------
sage -t src/sage/rings/algebra_from_morphism.py  # 5 doctests failed
----------------------------------------------------------------------
Total time for all tests: 0.9 seconds
    cpu time: 0.9 seconds
    cumulative wall time: 0.9 seconds

---

New commits:

5c1c5b6

Merge 7.6.beta2

[defeo]

Changed commit from 036fb2a to 5c1c5b6

[defeo]

comment:17

Had you guys notice that there is this interface in Sage, which returns a mostly empty shell:

sage: K = GF(5^2)
sage: L = GF(5^4)
sage: E = L.algebra(K, category=Semigroups())
sage: E
Free module generated by Finite Field in z4 of size 5^4 over Finite Field in z2 of size 5^2
sage: E.an_element()
2*B[0] + 2*B[z4] + 3*B[z4^2]
sage: E.categories()

[Category of finite dimensional semigroup algebras over Finite Field in z2 of size 5^2,
 Category of semigroup algebras over Finite Field in z2 of size 5^2,
 Category of associative algebras over Finite Field in z2 of size 5^2,
 Category of rngs,
 Category of associative additive commutative additive associative additive unital distributive magmas and additive magmas,
 Category of magma algebras over Finite Field in z2 of size 5^2,
 Category of magmatic algebras with basis over Finite Field in z2 of size 5^2,
 Category of magmatic algebras over Finite Field in z2 of size 5^2,
 Category of additive commutative additive associative additive unital distributive magmas and additive magmas,
 Category of additive commutative additive associative distributive magmas and additive magmas,
 Category of additive associative distributive magmas and additive magmas,
 Category of distributive magmas and additive magmas,
 Category of magmas and additive magmas,
 Category of finite semigroups,
 Category of semigroups,
 Category of magmas,
 Category of finite dimensional modules with basis over Finite Field in z2 of size 5^2,
 Category of set algebras over Finite Field in z2 of size 5^2,
 Category of vector spaces with basis over Finite Field in z2 of size 5^2,
 Category of modules with basis over Finite Field in z2 of size 5^2,
 Category of finite dimensional modules over Finite Field in z2 of size 5^2,
 Category of vector spaces over Finite Field in z2 of size 5^2,
 Category of modules over Finite Field in z2 of size 5^2,
 Category of bimodules over Finite Field in z2 of size 5^2 on the left and Finite Field in z2 of size 5^2 on the right,
 Category of right modules over Finite Field in z2 of size 5^2,
 Category of left modules over Finite Field in z2 of size 5^2,
 Category of commutative additive groups,
 Category of additive groups,
 Category of additive inverse additive unital additive magmas,
 Category of commutative additive monoids,
 Category of additive monoids,
 Category of additive unital additive magmas,
 Category of commutative additive semigroups,
 Category of additive commutative additive magmas,
 Category of additive semigroups,
 Category of additive magmas,
 Category of finite sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

[simon-king-jena]

comment:18

Replying to @defeo:

Had you guys notice that there is this interface in Sage, which returns a mostly empty shell:

In what sense would it be relevant for this ticket?

[defeo]

comment:19

Hello, as you might have guessed, I'm trying to resurrect this ticket.

My biggest concern is the same as Johan's: I find k*a != a*k very confusing for two reasons:

• It is silently not commutative;
• The parent of a*k is neither A nor K.

However I think the fix is simple: explicit is better than implicit, get rid of the coercion A -> L. I find the following idiom completely reasonable:

sage: K = GF(5^2); z2 = K.gen()
sage: L = GF(5^4); z4 = L.gen()
sage: A = RingExtension(L, K, K.frobenius_endomorphism())
sage: z2 * E(z4)
4*z4^3 + 3*z4^2 + 2*z4 + 2
sage: E(z4) * z2
TypeError: ...
sage: L(E(z4)) * z2
z4^3 + 2*z4^2 + 4*z4 + 3

It could be useful if the left action was represented by an operator other than *, however there is no acceptable operator in Python (. cannot be overridden and @ (matmul) was only introduced in Python 3.5).

Or maybe just have the right action be the same as the left action, which apparently you already did.

[sagetrac-git]

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

a7a6fa8

Merge branch 'develop' into ring_extension

[fchapoton]

Changed reviewer from David Roe to David Roe, Frédéric Chapoton

[fchapoton]

comment:108

ok, let it be

[xcaruso]

comment:109

Thanks.

BTW, do you know why some patchbots report building errors?

[vbraun]

comment:110

I'm getting a lot of failures like this on 32-bit

**********************************************************************
File "src/sage/categories/commutative_rings.py", line 156, in sage.categories.commutative_rings.CommutativeRings.ParentMethods.over
Failed example:
    L = GF(5^12).over(K)
Exception raised:
    Traceback (most recent call last):
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 681, in _run
        self.compile_and_execute(example, compiler, test.globs)
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/doctest/forker.py", line 1123, in compile_and_execute
        exec(compiled, globs)
      File "<doctest sage.categories.commutative_rings.CommutativeRings.ParentMethods.over[17]>", line 1, in <module>
        L = GF(Integer(5)**Integer(12)).over(K)
      File "/var/lib/buildbot/slave/sage_git/build/local/lib/python3.7/site-packages/sage/categories/commutative_rings.py", line 212, in over
        return RingExtension(self, base, gens, names)
      File "sage/structure/factory.pyx", line 369, in sage.structure.factory.UniqueFactory.__call__ (build/cythonized/sage/structure/factory.c:2240)
        return self.get_object(version, key, kwds)
      File "sage/structure/factory.pyx", line 406, in sage.structure.factory.UniqueFactory.get_object (build/cythonized/sage/structure/factory.c:2444)
        return self._cache[version, cache_key]
      File "sage/misc/weak_dict.pyx", line 703, in sage.misc.weak_dict.WeakValueDictionary.__getitem__ (build/cythonized/sage/misc/weak_dict.c:3650)
        cdef PyObject* wr = PyDict_GetItemWithError(self, k)
      File "sage/categories/morphism.pyx", line 323, in sage.categories.morphism.Morphism.__hash__ (build/cythonized/sage/categories/morphism.c:4888)
        return hash((domain, codomain, definition))
      File "sage/rings/ring_extension.pyx", line 696, in sage.rings.ring_extension.RingExtension_generic.__hash__ (build/cythonized/sage/rings/ring_extension.c:10685)
        return id(self)
    OverflowError: Python int too large to convert to C ssize_t
**********************************************************************

[fchapoton]

comment:111

using id(self) for the hash may be a bad idea

[roed314]

comment:112

We can certainly fix that problem, but neither Xavier nor I have access to a 32-bit machine, so I'm not sure what other problems might arise.

[dimpase]

comment:113

Replying to @roed314:

We can certainly fix that problem, but neither Xavier nor I have access to a 32-bit machine, so I'm not sure what other problems might arise.

just to mention that the access is now available :-)

[sagetrac-git]

Changed commit from a7a6fa8 to c43507c

[sagetrac-git]

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

98dc411	Merge branch 'develop' into ring_extension
c43507c	use fonction hash_by_id

[xcaruso]

comment:115

I'm trying with the function hash_by_id...

[fchapoton]

comment:117

did you check on a 32-bit machine ? If yes, you can set to positive on my name

[roed314]

comment:118

I just ran make ptestlong on a 32-bit machine and they all passed. Setting back to positive review.

[vbraun]

Changed branch from u/caruso/21413/class_ring_extension to c43507c

[xcaruso]

comment:120

Champagne!

[xcaruso]

Changed commit from c43507c to none