Derivation and twisted derivations over rings

[gh-Diarmund33]

This ticket implements derivation and theta-derivations over rings. (It would be useful for implementing general Ore polynomials.)

[git]

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

​b927acd

add method to create derivation in polynomial ring

[caruso]

New commits:

​a3de074

Initial code written by Amaury Durand

[git]

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

​823594a	Merge branch 'develop' into t/25134/derivation
​a222da8	Implement left Euclidean division

[git]

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

​532604b

Add a parent for the module of derivations

[git]

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

​44f0ca2	Implement twisted derivations
​cf978b3	Some documentation

[git]

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

​51f8b53

More doctests

[git]

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

​da46772

Add author

[caruso]

New commits:

​da46772

Add author

[git]

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

​ec909af

Add a hash function

[git]

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

​5b9bab9

Add doctest for is_zero

[caruso]

Hi Johan,

With a master student of mine (Amaury Durand), we generalized the notion of Gabidulin codes to any Ore algebra (possibly with derivation) and managed to allow more evaluation points. We are preparing a paper now and we trying to implement our generalized Gabidulin codes in Sage.

This ticket implements derivations and theta-derivations over arbitrary commutative rings. It is a first step towards implementing our generalized Gabidulin.

[jsrn]

Replying to caruso:

Hi Johan,

With a master student of mine (Amaury Durand), we generalized the notion of Gabidulin codes to any Ore algebra (possibly with derivation) and managed to allow more evaluation points. We are preparing a paper now and we trying to implement our generalized Gabidulin codes in Sage.

This ticket implements derivations and theta-derivations over arbitrary commutative rings. It is a first step towards implementing our generalized Gabidulin.

Hi Xavier and Amaury,

This looks very promising. I have no experience with theta-derivations over arbitrary commutative rings, but you code seems to explain the definition nicely. I should be able to review the code in the not-too-far-future. I'd like to see a preprint of your paper (if you prefer, in private email), if some of it is ready for consumption, and if you believe it would help my reading of the code.

Best, Johan

[git]

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

​f4fed16

Fix doctest

[tscrim]

This is a good advancement and looks in good shape. I have a few comments and suggestions.

The set of all derivations forms a Lie algebra with [X, Y] = X*Y - Y*X, which Sage has support for. So for untwisted derivations, it should be in the category of LieAlgebras. Let me know if you have any questions about adding this. (The twisted derivations forms what is known as a hom-Lie algebra, where the Jacobi relation also needs to be twisted.)

Additionally, when the ring is a finite-dimensional algebra with an explicit basis, we can compute a basis for the derivation module in terms of matrices:

sage: E.<x,y> = ExteriorAlgebra(QQ)
sage: E.derivations_basis()
(
[0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]
[0 1 0 0]  [0 0 1 0]  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]  [0 0 0 0]
[0 0 0 0]  [0 0 0 0]  [0 1 0 0]  [0 0 1 0]  [0 0 0 0]  [0 0 0 0]
[0 0 0 1], [0 0 0 0], [0 0 0 0], [0 0 0 1], [0 1 0 0], [0 0 1 0]
)

Although incorporating that is something that could easily be on a followup ticket as it will likely require a bit of extending your current implementation.

A few quick comments from reading the browsing the code:

• You should not set self.element_class attribute, but instead set self.Element (the Parent.__init__ ends up creating the new subclass element_class using stuff from the category).
• Python convention is error messages do not start with a capital letter.
• Remove the first :: here:

  ::
  
  Twisted derivations and handled similarly::
  

• Returns -> Return.
• ``n``th -> ``n``-th as otherwise it does not get parsed correctly.
• ``n`` - an integer (default: ``0``) -> -``n`` -- integer (default: ``0``)
• It might actually be good to have RingDerivation still inherit from (Ring)Map as the composition just becomes a formal composition of maps in the homspace (IIRC the default behavior). Plus it allows for natural functionality.
• I think it would be better to remove derivation_twisted and just have an extra input to derivation. It will have better localization of code and documentation and match the semantic of derivation_module.

[caruso]

Replying to jsrn:

This looks very promising. I have no experience with theta-derivations over arbitrary commutative rings, but you code seems to explain the definition nicely. I should be able to review the code in the not-too-far-future.

Great!

I'd like to see a preprint of your paper (if you prefer, in private email), if some of it is ready for consumption, and if you believe it would help my reading of the code.

OK, we'll send it to you... as soon as it is ready.

[caruso]

Thanks Travis for your comments.

Replying to tscrim:

The set of all derivations forms a Lie algebra with [X, Y] = X*Y - Y*X, which Sage has support for. So for untwisted derivations, it should be in the category of LieAlgebras. Let me know if you have any questions about adding this. (The twisted derivations forms what is known as a hom-Lie algebra, where the Jacobi relation also needs to be twisted.)

Good point. I'll add it. (I think I can do it by myself but I'll ask you if I have questions.)

Are the support in Sage for hom-Lie algebras?

• You should not set self.element_class attribute, but instead set self.Element (the Parent.__init__ ends up creating the new subclass element_class using stuff from the category).

Ah, OK.

• Python convention is error messages do not start with a capital letter.

Really? Is it the Sage convention as well? I ask the question because I remember that, one time, somebody told me that I should capitalize my error messages.

• It might actually be good to have RingDerivation still inherit from (Ring)Map as the composition just becomes a formal composition of maps in the homspace (IIRC the default behavior). Plus it allows for natural functionality.

Actually, I already tried to inherit from RingMap but had some troubles. But I can try harder :-)

• I think it would be better to remove derivation_twisted and just have an extra input to derivation. It will have better localization of code and documentation and match the semantic of derivation_module.

The semantic of derivation is a bit different from that of derivation_twisted. It's the reason why I've implemented two distinct methods.

By the way, I just realized that my current code works almost only for polynomial algebras. In particular, it does not work for quotients of polynomial algebras: d/dx does not define a derivation over A[x]/P(x) but it does define a derivation from A[x]/P(x) to A[x]/(P(x),P'(x)). I don't know what is the best way to fix this: I can certainly move the method derivation to the classes PolynomialRing_general, MPolynomialRing_base and FractionField_generic) but this implies code duplication. Otherwise, I can leave it in the class Ring but check if self is an instance of those classes. I don't know if it's a good practice.

[caruso]

Replying to caruso:

By the way, I just realized that my current code works almost only for polynomial algebras. In particular, it does not work for quotients of polynomial algebras: d/dx does not define a derivation over A[x]/P(x) but it does define a derivation from A[x]/P(x) to A[x]/(P(x),P'(x)). I don't know what is the best way to fix this: I can certainly move the method derivation to the classes PolynomialRing_general, MPolynomialRing_base and FractionField_generic) but this implies code duplication. Otherwise, I can leave it in the class Ring but check if self is an instance of those classes. I don't know if it's a good practice.

In fact, I think I can test it in the __init function of RingDerivation. So everything's fine.

[tscrim]

Replying to caruso:

Thanks Travis for your comments.

Replying to tscrim:

The set of all derivations forms a Lie algebra with [X, Y] = X*Y - Y*X, which Sage has support for. So for untwisted derivations, it should be in the category of LieAlgebras. Let me know if you have any questions about adding this. (The twisted derivations forms what is known as a hom-Lie algebra, where the Jacobi relation also needs to be twisted.)

Good point. I'll add it. (I think I can do it by myself but I'll ask you if I have questions.)

Thank you.

Are there support in Sage for hom-Lie algebras?

Currently no. It is not hard to add generic support in the form of having a category and lifting the bracket methods. However, I am not sure how much of the general theory (and hence code) could be lifted from Lie algebras to hom-Lie algebras.

• Python convention is error messages do not start with a capital letter.

Really? Is it the Sage convention as well? I ask the question because I remember that, one time, somebody told me that I should capitalize my error messages.

Yes. Whomever said otherwise was mistaken (granted there are exceptions when the message needs to be really long, but these are quite rare). At least, that is the consensus I have understood.

• It might actually be good to have RingDerivation still inherit from (Ring)Map as the composition just becomes a formal composition of maps in the homspace (IIRC the default behavior). Plus it allows for natural functionality.

Actually, I already tried to inherit from RingMap but had some troubles. But I can try harder :-)

If it was giving you difficulties, then feel free to drop it. It is not a big issue. I am happy to help try and debug things here as well.

• I think it would be better to remove derivation_twisted and just have an extra input to derivation. It will have better localization of code and documentation and match the semantic of derivation_module.

The semantic of derivation is a bit different from that of derivation_twisted. It's the reason why I've implemented two distinct methods.

Somewhat, but it feels a little artificial. You could just have a keyword only argument of twist, which I feel is quite natural to have. However, I don't feel that strongly about it, so if you would rather keep the current constructs, then it is fine by me.

By the way, I just realized that my current code works almost only for polynomial algebras. In particular, it does not work for quotients of polynomial algebras: d/dx does not define a derivation over A[x]/P(x) but it does define a derivation from A[x]/P(x) to A[x]/(P(x),P'(x)). I don't know what is the best way to fix this: I can certainly move the method derivation to the classes PolynomialRing_general, MPolynomialRing_base and FractionField_generic) but this implies code duplication. Otherwise, I can leave it in the class Ring but check if self is an instance of those classes. I don't know if it's a good practice.

I feel like it should work with quotients: If a map is a derivation in the ambient space, so when taking the quotient (which is functorial), you are preserving the equality. Perhaps I am over-simplifying things. I am guessing you have an explicit example in mind?

[git]

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

​2bb4bbd	Small fixes
​568ba75	Merge branch 'develop' into t/25134/derivation

[caruso]

Replying to tscrim:

By the way, I just realized that my current code works almost only for polynomial algebras. In particular, it does not work for quotients of polynomial algebras: d/dx does not define a derivation over A[x]/P(x) but it does define a derivation from A[x]/P(x) to A[x]/(P(x),P'(x)). I don't know what is the best way to fix this: I can certainly move the method derivation to the classes PolynomialRing_general, MPolynomialRing_base and FractionField_generic) but this implies code duplication. Otherwise, I can leave it in the class Ring but check if self is an instance of those classes. I don't know if it's a good practice.

I feel like it should work with quotients: If a map is a derivation in the ambient space, so when taking the quotient (which is functorial), you are preserving the equality. Perhaps I am over-simplifying things. I am guessing you have an explicit example in mind?

Well, if A = B (mod P), we can write A = B + PQ and taking the derivative, one gets A' = B' + P'Q + PQ' meaning that A' = B' (mod (P,P')) but in general A' != B' (mod P).

For a concrete example, take P = X^n and observe that the derivative of a polynomial defined modulo X^n is a polynomial defined modulo X^(n-1) (basically, we shift coefficients).

[tscrim]

Ah, I know where I was going wrong: taking a quotient by a fixed ideal is not functorial, you need the ideal to be in the kernel.

[git]

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

​d380337

New version with less bugs (e.g. derivations over iterated polynomial rings now works) and more functionalities (Lie bracket, pth power, etc.)

[caruso]

I've redesigned the way derivations are handled in order to fix the bug I pointed out above (and some others) and addressed some of your remarks.

I tried again to make RingDerivation inherit from RingMap but it's tricky because it implies that the parent RingDerivationModule must inherit from Homset, which now implies to define a method homset_category specifying in which category are the elements (i.e. the derivations). Since the derivations are not the morphims in any category (they are not stable under composition), I gave up.

Something we can implement is two methods precompose and postcompose that precompose/postcompose a derivation with a ring homomorphism (in which case, the result is again a derivation). The tricky point is that we get this way a derivation from a ring A to B where B is a A-algebra but the defining morphism might not be the coercion morphism (if it exists). So we should have support for this (which is good thing to have I think but needs some extra work).

[git]

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

​b588b09

Fix doctest

[git]

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

​e037783	Implement comparison between derivations
​5b1cb68	Add support for algebras defined by any ring homomorphism
​0017f96	Add precompose and postcompose
​77dce7b	Check that the morphisms passed to the methods precompose/postcompose are indeed ring homomorphisms

[caruso]

Replying to caruso:

Something we can implement is two methods precompose and postcompose that precompose/postcompose a derivation with a ring homomorphism (in which case, the result is again a derivation). The tricky point is that we get this way a derivation from a ring A to B where B is a A-algebra but the defining morphism might not be the coercion morphism (if it exists). So we should have support for this (which is good thing to have I think but needs some extra work).

OK. I've implemented this.

[tscrim]

Thank you for adding the Lie algebra support and your additional changes and experiments. It is a little sad the Morphism framework is not working here, but that is a limitation of the current implementation. This should be my last group of questions.

I think there is something we should be careful about in the module doc. If A is not a commutative ring, then B needs to be an A-bimodule (not necessarily an algebra) to be a derivation. However, there is a left and a right action of A on B used in the definition. (With the code itself, this is not a problem because you enforce A to be commutative.)

I feel like, at least for ease of maintenance, it would be better for basis to return self._basis even if it is _gens. It helps keep these as separate constructs and allows us later to take a larger generator set and then reduce it to a basis.

You need to add derivation.py to the documentation.

Replace _cmp_ with _richcmp_ as this will make it Python3 compatible.

It is better to use

-self.parent().codomain()(0)
+self.parent().codomain().zero()

since the latter is cached and avoids coercion/conversion.

I think your elements need to implement a monomial_coefficients() method, where the output is a dict whose keys are the basis indices and the values are the corresponding coefficients.

I think (dual_)basis should return a Family (or a Sequence, but this has a more limited feature set) to be consistent with other parts of Sage in ModulesWithBasis.

Every __init__ should have a TestSuite(foo).run() call. This is usually a good way to catch bugs and implementation requirements from the category.

I think a better __hash__ test would be

sage: hash(M) == hash((M.domain(), M.codomain(), M.twisting_morphism())
True

as it shows that the hash works and what it should be equal to.

-``n`` - an integer (default: ``0``)
+-``n`` -- an integer (default: ``0``)

Instead of self(x), why not do self.element_class(self, x)? Granted, it is not going to make a big difference in speed, but I think it is a little better because it is more direct.

In the same vein, for the arithmetic operations, it is faster to do, e.g.,

-return self.parent()(self._scalar - other._scalar)
+return type(self)(self.parent(), self._scalar - other._scalar)

Why all the same definition of __hash__? You are not doing a new __eq__/__richcmp__, so there should not be a need to do this. Why not have this be in the ABC and override when you need to?

General question, how much speed do you think you need with these elements? It might be worthwhile to consider Cythonizing the elements.

[git]

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

​c9deb7f

Address some of Travis' comments

[caruso]

Replying to tscrim:

I think there is something we should be careful about in the module doc. If A is not a commutative ring, then B needs to be an A-bimodule (not necessarily an algebra) to be a derivation. However, there is a left and a right action of A on B used in the definition. (With the code itself, this is not a problem because you enforce A to be commutative.)

What do you propose concretely? I can add a doctest demonstrating that derivations are not supported over noncommutative rings. How does it sound?

I feel like, at least for ease of maintenance, it would be better for basis to return self._basis even if it is _gens. It helps keep these as separate constructs and allows us later to take a larger generator set and then reduce it to a basis.

Sure!

You need to add derivation.py to the documentation.

I'm unsure what I'm supposed to do exactlt? It is fine now?

Replace _cmp_ with _richcmp_ as this will make it Python3 compatible.

OK. So far, I've just implemented == and !=. Should I implement the other rich comparison operators as well? (But I don't know how they should behave.)

It is better to use

-self.parent().codomain()(0)
+self.parent().codomain().zero()

since the latter is cached and avoids coercion/conversion.

OK.

I think your elements need to implement a monomial_coefficients() method, where the output is a dict whose keys are the basis indices and the values are the corresponding coefficients.

Done.

I think (dual_)basis should return a Family (or a Sequence, but this has a more limited feature set) to be consistent with other parts of Sage in ModulesWithBasis.

Well, ok for returning a Family...

Every __init__ should have a TestSuite(foo).run() call. This is usually a good way to catch bugs and implementation requirements from the category.

I'll do it.

I think a better __hash__ test would be

sage: hash(M) == hash((M.domain(), M.codomain(), M.twisting_morphism())
True

as it shows that the hash works and what it should be equal to.

OK.

-``n`` - an integer (default: ``0``)
+-``n`` -- an integer (default: ``0``)

Done.

Instead of self(x), why not do self.element_class(self, x)? Granted, it is not going to make a big difference in speed, but I think it is a little better because it is more direct.

I've changed this.

In the same vein, for the arithmetic operations, it is faster to do, e.g.,

-return self.parent()(self._scalar - other._scalar)
+return type(self)(self.parent(), self._scalar - other._scalar)

OK. I'll change this.

Why all the same definition of __hash__? You are not doing a new __eq__/__richcmp__, so there should not be a need to do this. Why not have this be in the ABC and override when you need to?

It seems that you must have to redefine __hash__ in each class even if the code does not change (otherwise I got an error). I don't know why.

General question, how much speed do you think you need with these elements? It might be worthwhile to consider Cythonizing the elements.

For now, I'm not that concerned with speed. But on the other hand, I'm aware that my code is rather slow (especially for iteration polynomial rings). I will probably (one day) consider Cythonizing derivations but, except if you strongly disagree, it will be for another ticket.

[tscrim]

Replying to caruso:

Replying to tscrim:

I think there is something we should be careful about in the module doc. If A is not a commutative ring, then B needs to be an A-bimodule (not necessarily an algebra) to be a derivation. However, there is a left and a right action of A on B used in the definition. (With the code itself, this is not a problem because you enforce A to be commutative.)

What do you propose concretely? I can add a doctest demonstrating that derivations are not supported over noncommutative rings. How does it sound?

I don't think it needs a doctest since for the actual implementation you say commutative ring. I think it is sufficient to just replace "algebra over A" with "A-bimodule" in the top-level docstring.

It might be worthwhile mentioning somewhere (maybe RingDerivationModule, but maybe elsewhere) that when B = A, then the set of (twisted) derivations has a (hom-)Lie algebra structure. However, I am bias because I like Lie algebras. :)

You need to add derivation.py to the documentation.

I'm unsure what I'm supposed to do exactlt? It is fine now?

Yes, that is what was missing.

Replace _cmp_ with _richcmp_ as this will make it Python3 compatible.

OK. So far, I've just implemented == and !=. Should I implement the other rich comparison operators as well? (But I don't know how they should behave.)

No, you shouldn't. In fact, that is once of the nice things about _richcmp_ is you do not need other comparisons. You can just return a NotImplemented. Although, you could just do

from sage.structure.richcmp import richcmp  # put this import at the top level
return richcmp(self.list(), other.list(), op)

I think (dual_)basis should return a Family (or a Sequence, but this has a more limited feature set) to be consistent with other parts of Sage in ModulesWithBasis.

Well, ok for returning a Family...

Thank you. This also makes it so self.basis().cardinality() and self.basis().keys() works and helps make things uniform.

Why all the same definition of __hash__? You are not doing a new __eq__/__richcmp__, so there should not be a need to do this. Why not have this be in the ABC and override when you need to?

It seems that you must have to redefine __hash__ in each class even if the code does not change (otherwise I got an error). I don't know why.

That is very strange. I would figure it would be sufficient for some ABC. I might have to look more closely into that.

General question, how much speed do you think you need with these elements? It might be worthwhile to consider Cythonizing the elements.

For now, I'm not that concerned with speed. But on the other hand, I'm aware that my code is rather slow (especially for iteration polynomial rings). I will probably (one day) consider Cythonizing derivations but, except if you strongly disagree, it will be for another ticket.

Another ticket is fine. It is slightly easier to split the element class into a Cython file here than on a separate ticket, but only slightly. I am fine with whatever you decide.

[git]

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

​369db6a

Address Travis' review

[caruso]

There is still a bug with pickling but it's not because of this ticket.

I've opened up a new ticket (#26354) reporting the bug.

[git]

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

​94f6985	Set immutable in unpickling ring morphisms
​c4fffe2	Merge branch 't/26354/pickling_morphisms_is_broken' into t/25134/derivation
​267f74d	Implement _richcmp_ for twisted derivations

[tscrim]

Thank you for all the changes. I made a few reviewer changes to fix the docbuild error, some broken doc links, bad formatting, and other small adjustments. I also did a bunch of PEP8 consistency changes.

If my changes are good with you, then positive review.

---

New commits:

​f0878eb

Fixing some docstrings and some PEP8.

[caruso]

I've fixed a few typos in the doctest.

I can give a positive review now but maybe it's better to wait for #26354. What's your opinion?

[git]

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

​dbe85c5

Typos

[tscrim]

It's a positive review, but it won't get merged until the dependency is merged.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:

​dee878e	Revert "Set immutable in unpickling ring morphisms"
​e2931b6	Fix pickling for PolynomialSequence_generic
​1ea91f7	Add a doctest
​c8fee99	Merge branch 't/26354/pickling_morphisms_is_broken' into t/25134/polynomial_derivations-25134

[caruso]

I just merged with #26354. Actually, I'm not sure it was needed but it's probably safer like this.