Basic implementation of one- and twosided ideals of non-commutative rings, and quotients by twosided ideals

[simon-king-jena]

It was suggested that my patch for #7797 be split into several parts.

The first part shall be about ideals in non-commutative rings. Aim, for example:

sage: A = SteenrodAlgebra(2)
sage: A*[A.0,A.1^2]
Left Ideal (Sq(1), Sq(1,1)) of mod 2 Steenrod algebra
sage: [A.0,A.1^2]*A
Right Ideal (Sq(1), Sq(1,1)) of mod 2 Steenrod algebra
sage: A*[A.0,A.1^2]*A
Twosided Ideal (Sq(1), Sq(1,1)) of mod 2 Steenrod algebra

It was suggested to also add quotients by twosided ideals, although it will be difficult to provide examples before having letterplace ideals.

Apply:

• attachment: trac11068_nc_ideals_and_quotients.patch
• attachment: trac11068_quotient_ring_without_names.patch
• attachment: trac11068_lifting_map.patch

Depends on #9138
Depends on #11900
Depends on #11115

CC: @nthiery @jhpalmieri

Component: algebra

Keywords: onesided twosided ideal noncommutative ring sd32

Author: Simon King

Reviewer: John Perry

Merged: sage-5.0.beta1

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

[simon-king-jena]

Work Issues: Add examples; move code from ring.py to rings.py

[simon-king-jena]

comment:2

Depends on #10961

The patch is incomplete, since proper examples are missing. Proper examples will be provided by #7797, but Nicolas promised to try and find some "small" example.

Really, all what we need is a non-commutative ring and something that inherits from Ideal_nc and provides a reduce() method yielding normal forms.

Also, that patch is preliminary, since it copies some code from sage/rings/ring.pyx to sage/categories/rings.py, rather than moving it.

[simon-king-jena]

comment:3

Concerning examples.

I suggest to make a standard example out of the following emulation of a certain very simple ideals of a free algebra, without letterplace:

sage: from sage.rings.noncommutative_ideals import Ideal_nc
# mainly we need a 'reduce()' method. So, provide one!
sage: class PowerIdeal(Ideal_nc):
....:     def __init__(self, R, n):
....:         self._power = n
....:         Ideal_nc.__init__(self,R,[x^n for x in R.gens()])
....:     def reduce(self,x):
....:         R = self.ring()
....:         return add([c*R(m) for c,m in x if len(m)<self._power],R(0))
....:
sage: F.<x,y,z> = FreeAlgebra(QQ, 3)
sage: I3 = PowerIdeal(F,3); I3
Twosided Ideal (x^3, y^3, z^3) of Free Algebra on 3 generators (x, y, z) over Rational Field
# We need to use super in order to access the generic quotient:
sage: Q3.<a,b,c> = super(F.__class__,F).quotient(I3)
sage: Q3
Quotient of Free Algebra on 3 generators (x, y, z) over Rational Field by the ideal (x^3, y^3, z^3)
sage: (a+b+2)^4
16 + 32*x + 32*y + 24*x^2 + 24*x*y + 24*y*x + 24*y^2
sage: Q3.is_commutative()
False
sage: I2 = PowerIdeal(F,2); I2
Twosided Ideal (x^2, y^2, z^2) of Free Algebra on 3 generators (x, y, z) over Rational Field
sage: Q2.<a,b,c> = super(F.__class__,F).quotient(I2)
sage: Q2.is_commutative()
True
sage: (a+b+2)^4
16 + 32*x + 32*y

I think I would be able to add this example as doc test tomorrow, also removing the whole ideal and quotient stuff from sage.rings.ring.Ring to sage.categories.rings.Rings.ParentMethods.

[nthiery]

comment:4

Nice! That sounds like a perfect example indeed.

Thanks for removing this item from my TODO list :-)

[simon-king-jena]

comment:5

Replying to @simon-king-jena:

...
I think I would be able to add this example as doc test tomorrow, also removing the whole ideal and quotient stuff from sage.rings.ring.Ring to sage.categories.rings.Rings.ParentMethods.

Apparently it took a lot longer. The problem is "moving the whole ideal and quotient stuff from sage.rings.ring.Ring to sage.categories.rings.Rings.ParentMethods. Namely, that involves a couple of methods with cached output (the cache being hand-written). One could use the @cached_method decorator in the parent methods -- but the problem is that the cache breaks when one has a ring that does not allow attribute assignment.

That problem is solved at #11115. Moreover, @cached_method is now faster than a hand-written cache in Python. However, it is slower than a hand-written cache in Cython.

So, the question is: Can we accept the slow-down that would result from moving code from the ring class to the ring category? Or is it easier to accept some duplication of code?

[simon-king-jena]

comment:6

Replying to @simon-king-jena:

So, the question is: Can we accept the slow-down that would result from moving code from the ring class to the ring category? Or is it easier to accept some duplication of code?

Any answer? Probably one would first need to see how much of a slow-down we will really find.

[simon-king-jena]

comment:7

Currently I work on the following technical problem:

The category of a quotient ring is not properly initialised. Thus, a proper TestSuite is not available. I guess, a quotient ring of a ring R should belong to the category R.category().Quotients(). Doing, so, there are further problems, since some crucial methods such as lift have a completely different meaning in sage.rings.quotient_rings and sage.categories.quotients.

So, that mess needs to be cleaned up.

[simon-king-jena]

comment:8

I think it should be part of this ticket to properly use categories and the new coercion model for

• quotient rings
• (free) monoids
• free algebras

That has not been done in #9138, but I think it fits here as well, since "quotients" is mentioned in the ticket title, and free algebras could provide nice examples, if they would use the category framework.

[nthiery]

comment:9

Replying to @simon-king-jena:

I guess, a quotient ring of a ring R should belong to the category R.category().Quotients().

+1

Doing, so, there are further problems, since some crucial methods
such as lift have a completely different meaning in
sage.rings.quotient_rings and sage.categories.quotients.

That's precisely the issue that stopped me starting the refactoring of
quotient, because there was a design discussion to be run first on
sage-devel to see which syntax should be prefered:

• that currently used in the category framework for sub quotients:

  P.lift either a plain Python method, or better the lift
  function as a morphism
  P.lift(x) lifts x to the ambient space of P

• or that used in sage.rings.quotient_rings:

  P.lift()(x) lifts x to the ambient space of P
  P.lift() the lifting morphism

I personally prefer the former, first from a syntactical point of
view, and because it make it easy in practice to implement lift.

Note: at first sight, it seems easy to make the change in this
direction while retaining backward compatibility by just patching
sage.ring.quotient_rings so that P.lift(x) delegates the work to
P.lift()(x).

Do you mind running this dicussion on sage-devel?

Cheers,
Nicolas

[simon-king-jena]

comment:10

Replying to @nthiery:

• that currently used in the category framework for sub quotients:

  P.lift either a plain Python method, or better the lift
  function as a morphism
  P.lift(x) lifts x to the ambient space of P

I think the object oriented mantra implies that the correct syntax for lifting an element x of P to the ambient space of P is x.lift() (which is implemented). And I am not a fan of providing stuff by attributes (so, I wouldn't like P.lift being a morphism).

On the other hand, P.lift(x) could be understood as "P, please lift x!".

Moreover:

• or that used in sage.rings.quotient_rings:

  P.lift()(x) lifts x to the ambient space of P
  P.lift() the lifting morphism

As you state, it is the "lifting morphism", not the "lift". The term "lifting morphism" is used in the documentation as well. So, explicit being better than implicit, "P.lift()" as it is used in sage.rings.quotient_rings, should be renamed as "P.lifting_morphism()".

So, I tend towards using the notions from the subquotient framework.

Do you mind running this dicussion on sage-devel?

Not at all. I just hope that people will answer.

[simon-king-jena]

comment:11

It was suggested on sage-devel to have both: By making x an optional argument, Q.lift() could return the lifting map (following the old rules of sage.rings.quotient_ring), and Q.lift(x) could return a lift of x (following the old rules of the category framework).

I think I will go for that solution.

Unfortunately, I was not told yet whether I shall duplicate the code, or move it...

[simon-king-jena]

comment:12

I updated my patch, now as the background work in #9138 seems settled from my point of view.

In that patch, I went for the "duplicate code for speed's sake" approach. I don't mind beig asked to change it, though (i.e., it seems possible to delete the ideal stuff from sage.rings.ring and move it over to sage.categories.rings).

Depends on #10961 #9138 #11115

[simon-king-jena]

Changed work issues from Add examples; move code from ring.py to rings.py to Shall one move code from ring.pyx to rings.py?

[simon-king-jena]

comment:13

I noticed that the ticket description stated an incomplete list of dependencies

[simon-king-jena]

Author: Simon King

[simon-king-jena]

Dependencies: #10961, #9138, #11115

[simon-king-jena]

comment:15

I had to rebase my patch, because of #11139 (I don't add it as a dependency for this ticket, since it is already, by #9138).

I am now running doctests. It is still "needs review", but I think #11342, #9138 and #11115 need review more urgently.

[simon-king-jena]

comment:16

I just found one problem that should be fixed.

In unpatched Sage, we have

sage: R = Integers(8)
sage: R.quotient(R.ideal(2),['bla'])
Quotient of Integer Ring by the ideal (2)

Shouldn't the result rather be the same as Integers(2)?

With my patch as it currently is, the example fails with a type error. But I think I can make it work, so that the result will be "Ring of integers modulo 2".

[simon-king-jena]

comment:61

The trouble with #11339 has been resolved: #11339 can in fact only be used in conjunction with #10903. The patches here can remain as they are now. #10903 should be added as a new dependency (#11339 is a dependency of #10903).

All doc tests succeeded with sage-4.7.2.alpha3 plus #11339, #10903, #11856, #11115 and #11068. So, I hope that it is alright that I now reinstate the positive review.

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

[johnperry-math]

comment:62

Replying to @simon-king-jena:

All doc tests succeeded with sage-4.7.2.alpha3 plus #11339, #10903, #11856, #11115 and #11068. So, I hope that it is alright that I now reinstate the positive review.

I gave the positive review, and I am fine with that. I can run the doctests on my own machine if someone likes, but since I'm working on something else, I'm unable to do it at the moment.

Out of curiosity, why was the milestone changed to 4.7.3?

[jdemeyer]

comment:63

Replying to @johnperry-math:

Out of curiosity, why was the milestone changed to 4.7.3?

Mainly because I would like to finish the sage-4.7.2 release. I do not see a compelling reason for this to be merged quickly, so it will be in sage-4.7.3.

[jdemeyer]

Changed dependencies from #10961 #9138 #11115 #11342 #10903 to #9138, #11900, #11115

[jdemeyer]

comment:65

This will eventually need to be rebased to #11900.

[simon-king-jena]

comment:66

Replying to @jdemeyer:

This will eventually need to be rebased to #11900.

I just did so. Only the first patch has changed.

For me, all tests pass, and thus I keep the positive review. But I would appreciate if someone could test it.

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

[johnperry-math]

comment:67

Replying to @simon-king-jena:

For me, all tests pass, and thus I keep the positive review. But I would appreciate if someone could test it.

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

I will try this at some point. Do I need to download the latest alpha, or mere #11900?

[simon-king-jena]

comment:68

Replying to @johnperry-math:

Replying to @simon-king-jena:

For me, all tests pass, and thus I keep the positive review. But I would appreciate if someone could test it.

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

I will try this at some point. Do I need to download the latest alpha, or mere #11900?

There is an "inofficial" sage-4.7.3.alpha1, which actually contains #11068. So, you may test with this, if you like. If all tests pass with sage-4.7.3.alpha1, then (I think) it is justified to keep your original positive review.

[jdemeyer]

comment:69

On sage.math, all short and long tests pass. If all Simon did was an obvious rebase (I did not check this), then it is certainly okay to keep the positive_review.

[jdemeyer]

comment:70

Replying to @simon-king-jena:

There is an "inofficial" sage-4.7.3.alpha1, which actually contains #11068. So, you may test with this, if you like. If all tests pass with sage-4.7.3.alpha1, then (I think) it is justified to keep your original positive review.

Yes, but keep in mind that this 4.7.3.alpha1 contains much more than just this ticket. If all tests pass, that's great but if not, you wouldn't know that it's because of this ticket. So for actually testing this ticket, it would be better to use sage-4.7.2 (which is now official) and apply the dependencies of this ticket: #9138, #11900, #11115.

[simon-king-jena]

comment:71

Since apparently sage-4.7.3.alpha1 is not relevant, I took into account sage-4.8.alpha0 instead. I worked on top of #11935, but I hope I did the rebase (yes, really not more than a trivial rebase) such that it should not matter whether one has #11935 applied or not. I will test this in two hours...

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

[simon-king-jena]

comment:72

Meanwhile I have updated my patches both here and at #11943. I just verified that the new patches do commute, so that it does not matter whether this ticket is merged before or after #11943 and #11935.

Again, the change was trivial (actually involving a blank space that I had accidentally introduced at #11943).

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

[jdemeyer]

Attachment: trac11068_nc_ideals_and_quotients.patch.gz

Non-commutative ideals and quotient rings

[jdemeyer]

comment:75

Patch rebased to latest version of #11900.

[jdemeyer]

Merged: sage-5.0.beta1

[koffie]

comment:77

The reduce function of the two doctests

All failures will probably be fixed if these three tests pass

sage: MS = MatrixSpace(GF(5),2,2)
sage: I = MS*[MS.0*MS.1,MS.2+MS.3]*MS
sage: Q = MS.quo(I)
sage: Q.0*Q.1   # indirect doctest
[0 1]
[0 0]

and

sage: S = SteenrodAlgebra(2)
sage: I = S*[S.0+S.1]*S
sage: Q = S.quo(I)
sage: Q.0
Sq(1)

Added by this ticket both do not satisfy the condition on reduce as documented in this ticket

In :trac:`11068`, non-commutative quotient rings `R/I` were
implemented.  The only requirement is that the two-sided ideal `I`
provides a ``reduce`` method so that ``I.reduce(x)`` is the normal
form of an element `x` with respect to `I` (i.e., we have
``I.reduce(x) == I.reduce(y)`` if `x-y \in I`, and
``x - I.reduce(x) in I``).

This issue is now tracked at #23621

[simon-king-jena]

comment:78

Wrong ticket? This one was closed six years ago...

Replying to @koffie:

The reduce function of the two doctests

All failures will probably be fixed if these three tests pass

sage: MS = MatrixSpace(GF(5),2,2)
sage: I = MS*[MS.0*MS.1,MS.2+MS.3]*MS
sage: Q = MS.quo(I)
sage: Q.0*Q.1   # indirect doctest
[0 1]
[0 0]

and

sage: S = SteenrodAlgebra(2)
sage: I = S*[S.0+S.1]*S
sage: Q = S.quo(I)
sage: Q.0
Sq(1)

Added by this ticket both do not satisfy the condition on reduce as documented in this ticket

In :trac:`11068`, non-commutative quotient rings `R/I` were
implemented.  The only requirement is that the two-sided ideal `I`
provides a ``reduce`` method so that ``I.reduce(x)`` is the normal
form of an element `x` with respect to `I` (i.e., we have
``I.reduce(x) == I.reduce(y)`` if `x-y \in I`, and
``x - I.reduce(x) in I``).

This issue is now tracked at #23621