Opened 7 years ago

Closed 6 years ago

Last modified 4 weeks ago

#11068 closed enhancement (fixed)

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

Reported by: SimonKing Owned by: AlexGhitza
Priority: major Milestone: sage-5.0
Component: algebra Keywords: onesided twosided ideal noncommutative ring sd32
Cc: nthiery, jhpalmieri Merged in: sage-5.0.beta1
Authors: Simon King Reviewers: John Perry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #9138, #11900, #11115 Stopgaps:

Description (last modified by jdemeyer)

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:

Attachments (3)

trac11068_lifting_map.patch (3.2 KB) - added by SimonKing 6 years ago.
Lifting map for quotients of rings not inheriting from sage.rings.ring.Ring
trac11068_quotient_ring_without_names.patch (3.8 KB) - added by SimonKing 6 years ago.
Add support for quotient rings without named generators
trac11068_nc_ideals_and_quotients.patch (66.1 KB) - added by jdemeyer 6 years ago.
Non-commutative ideals and quotient rings

Download all attachments as: .zip

Change History (81)

comment:1 Changed 7 years ago by SimonKing

  • Cc nthiery added
  • Description modified (diff)
  • Summary changed from Basic implementation of one- and twosided ideals of non-commutative rings to Basic implementation of one- and twosided ideals of non-commutative rings, and quotients by twosided ideals
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 7 years ago by SimonKing

  • Description modified (diff)
  • Status changed from new to needs_work
  • Work issues set to Add examples; move code from ring.py to rings.py

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.

comment:3 follow-up: Changed 7 years ago by SimonKing

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.

comment:4 Changed 7 years ago by nthiery

Nice! That sounds like a perfect example indeed.

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

comment:5 in reply to: ↑ 3 ; follow-up: Changed 6 years ago by SimonKing

Replying to SimonKing:

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

comment:6 in reply to: ↑ 5 Changed 6 years ago by SimonKing

Replying to SimonKing:

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.

comment:7 follow-up: Changed 6 years ago by SimonKing

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.

comment:8 Changed 6 years ago by SimonKing

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.

comment:9 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by nthiery

Replying to SimonKing:

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

comment:10 in reply to: ↑ 9 Changed 6 years ago by SimonKing

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.

comment:11 Changed 6 years ago by SimonKing

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

comment:12 Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues changed from Add examples; move code from ring.py to rings.py to Shall one move code from ring.pyx to rings.py?

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

comment:13 Changed 6 years ago by SimonKing

  • Description modified (diff)

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

comment:14 Changed 6 years ago by SimonKing

  • Authors set to Simon King
  • Dependencies set to #10961, #9138, #11115

comment:15 Changed 6 years ago by SimonKing

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.

comment:16 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work

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

comment:17 Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review

Done!

With the new patch, we have

sage: R = Integers(8)
sage: I = R.ideal(2)
sage: R.quotient(I)
Ring of integers modulo 2

comment:18 Changed 6 years ago by SimonKing

I had to rebase my patch against sage-4.7.1.rc1

Review is still welcome...

comment:19 Changed 6 years ago by SimonKing

I had to rebase my patch.

That only concerns trivial changes in the doc tests, due to the fact that Steenrod algebras are now (by sage-4.7.1.rc2, at least) naming their basis ("mod 2 Steenrod algebra" became "mod 2 Steenrod algebra, milnor basis"), and that Sq(0) now prints as "1".

I still think that having one and twosided ideals of non-commutative rings in Sage is a good think, and thus I'd appreciate a review. That said, reviews of #9138 and #11115 are more urgent...

comment:20 Changed 6 years ago by jhpalmieri

  • Cc jhpalmieri added

comment:21 Changed 6 years ago by john_perry

I'm working on testing this (have to recompile nearly everything!) but here are two comments:

  1. As far as I can tell, _ideal_class() does not distinguish between left, right, & two-sided ideals. The TO_DO (old lines 503-504 of sage/rings/ring.pyx) aims for this. This would be desirable; have I missed where it happens?
  2. typos: "synonym" is misspelled as "synonyme" in a few places, "seves" should be "serves".

comment:22 follow-up: Changed 6 years ago by john_perry

Update:

  1. Now that I think of it, does the request to distinguish left, right, & two-sided ideals makes sense in _ideal_class()? This is a method for a ring, not an ideal.
  2. You write,

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

I took the example given above of a two-sided ideal with the Steenrod algebra, and it would not compute the quotient ring; see below. Is this supposed to work?

sage: A = SteenrodAlgebra(2)
sage: A*[A.0,A.1^2]*A
Twosided Ideal (Sq(1), Sq(1,1)) of mod 2 Steenrod algebra, milnor basis
sage: I = A*[A.0,A.1^2]*A
sage: A.quo(I)
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: variable names have not yet been set using self._assign_names(...)

comment:23 in reply to: ↑ 22 Changed 6 years ago by SimonKing

Hi John,

Replying to john_perry:

  1. Now that I think of it, does the request to distinguish left, right, & two-sided ideals makes sense in _ideal_class()? This is a method for a ring, not an ideal.

Yes, _ideal_class is a method of the ring, not of the ideal. However, the returned class already depends (in some cases) on the number of generators (principal ideals versus general ideals). Theoretically, it could allso be made dependent on the sidedness of the ideal-to-be-constructed.

However, I think it is better to have a common class for ideals in non-commutative rings. Instances of that class can be left, right or twosided. But (I think) it is not necessary to have one separate class for onesided and another separate class for twosided ideals.

I took the example given above of a two-sided ideal with the Steenrod algebra, and it would not compute the quotient ring; see below. Is this supposed to work?

... sage: A.quo(I) ... ValueError?: variable names have not yet been set using self._assign_names(...)

It is not so easy, because the Steenrod algebra has infinitely many generators (the number of generators is given by ngens). The Steenrod algebra can not provide a list of generator names either: The method variable_names() will not work, of course.

But when you want to construct a general ring quotient, the init method of the quotient ring expects that the ring you started with knows its variable names.

It may be possible to change the init method of quotient rings such that it will no longer be expected. But I think that should be on a different ticket.

Hint: You could start with a matrix algebra (say, 2x2 matrices over some field). Here, we have a finite list of generators (namely four matrices). And then, you could assign names to them when constructing the quotient, such as here

sage: MS = MatrixSpace(GF(5),2,2)
sage: I = MS*[MS.0*MS.1,MS.2+MS.3]*MS
sage: MS.ngens()
4
sage: I
Twosided Ideal
(
  [0 1]
  [0 0],

  [0 0]
  [1 1]
)
 of Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5
sage: Q.<a,b,c,d> = MS.quo(I)
sage: Q
Quotient of Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5 by the ideal
(
  [0 1]
  [0 0],

  [0 0]
  [1 1]
)

comment:24 Changed 6 years ago by john_perry

That worked. But should Q.an_element() produce something printable? I'm getting

sage: x = Q.an_element()
sage: x
ERROR: An unexpected error occurred while tokenizing input
...
ValueError: variable names have not yet been set using self._assign_names(...)

comment:25 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues changed from Shall one move code from ring.pyx to rings.py? to Print quotient ring elements if the cover has no variable names

It turns out that, although the variable names are available, Q does not know its generators. And that's clearly strange: MS knows its generators, and hence the quotient Q could simply be generated by the equivalence classes of the generators of MS:

sage: MS.gens()
(
[1 0]  [0 1]  [0 0]  [0 0]
[0 0], [0 0], [1 0], [0 1]
)
sage: Q.variable_names()
('a', 'b', 'c', 'd')
sage: Q.ngens()
4
sage: Q.gens()
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (359, 0))

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: variable names have not yet been set using self._assign_names(...)

Actually, it seems that the problem simply is printing the elements:

sage: L = Q.gens()
sage: L[0]
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (359, 0))

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
...
ValueError: variable names have not yet been set using self._assign_names(...)

Indeed, it seems that the printing method of quotient ring elements expects that the cover ring uses variable names in order to print its elemennts; the variable names of the quotient rings are used to replace the variable names of the cover ring.

However, the elements of MS are not printed using any variable names.

I think that's a bug that could be fixed here (I wouldn't open a new ticket for it).

Thank you for spotting it!

comment:26 Changed 6 years ago by SimonKing

  • Dependencies changed from #10961, #9138, #11115 to #10961, #9138, #11115, #11342
  • Status changed from needs_work to needs_review
  • Work issues Print quotient ring elements if the cover has no variable names deleted

Please apply the new patch from #11342 before installing the new patch from here'''

I resolved the problem with printing quotient ring elements of matrix spaces, and while I was at it, I also enabled the creation of quotients of the Steenrod algebras.

How's that?

String representation

The string representation of a quotient ring element is obtained from its representation in the cover ring. However, the variable names in the cover ring and the quotient ring may be different. That is taken care of by a local environment that temporarily changes the variable names in the cover ring.

However, that won't work if the cover ring has no variable names: If there are no names, they can't be changed. And similarly, if the quotient ring has no names then one wouldn't know how to change the names from the cover ring.

With the new patch, one can do:

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.an_element()
[1 0]
[0 0]

Cover rings with infinitely many generators

With the patch, we don't require the list of generators of the cover ring at initialisation time of the quotient ring. Hence, we can form quotient rings of Steenrod algebras. Here is a case where one has no variable names. Thus, the string representation of a quotient ring element must coincide with the string representation of a corresponding element in the cover ring.

That's to say:

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

Note, however, that in order to be able to do real computations in the quotient ring, someone needs to implement a method reduce() for the involved ideal class!

Coping with #11342 in conjunction with #9138

#11342 is a dependency for #11115, which is a dependency for this ticket.

Since today, there is a new patch at #11342, that fixes a problem with the Pari interface: On some machines, that problem would result in a segfault.

The new patches at #11342 add a doctest, that needs to be modified if #11342 is combined with #9138 (reason: Some element class introduce at #11342 gets a different name when #9138 adds the category framework).

Since both are dependencies for the ticket here, the new patch fixes the test.

Needs review, again...

comment:27 Changed 6 years ago by SimonKing

PS concerning string representation: I wrote "If there are no names, they can't be changed. And similarly, if the quotient ring has no names then one wouldn't know how to change the names from the cover ring."

I forgot to add: "Hence, with the new patch, the local environment simply ignores the error that would result from changing names that don't exist."

comment:28 Changed 6 years ago by john_perry

  • Keywords sd32 added

comment:29 follow-up: Changed 6 years ago by john_perry

I'm not sure this is an error, but here goes:

sage: QA.<i,j,k> = QuaternionAlgebra(2,3)
sage: QI = QA*[i]*QA
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
...
AttributeError: 'QuaternionFractionalIdeal_rational' object has no attribute '_scale'

This seems odd, since

sage: QI = QA.ideal([i])

works fine, but the discussion in #11342 makes me wonder if this is because, in the second case, QI is a "fractional ideal":

sage: QI
Fractional ideal (i,)

This is beyond my expertise, so I have to ask: is this appropriate behavior?

comment:30 in reply to: ↑ 29 Changed 6 years ago by SimonKing

Replying to john_perry:

works fine, but the discussion in #11342 makes me wonder if this is because, in the second case, QI is a "fractional ideal":

sage: QI
Fractional ideal (i,)

This is beyond my expertise, so I have to ask: is this appropriate behavior?

Hm. I think it would be nice to make fractional ideals constructible in the same way as usual ideals are constructible. But they belong to a different Python class; hence, the functionality can not so easily be provided.

Since QI = QA.ideal([i]) works, I'd prefer to keep it as is, and would consider QA*i*QA as syntactical sugar that might be added on a different ticket.

comment:31 follow-up: Changed 6 years ago by john_perry

Here's another one. Given the ring as defined so far:

sage: x = MS.0; y = MS.1
sage: x + y
[1 1]
[0 0]
sage: x * y
ERROR: An unexpected error occurred while tokenizing input
The following traceback may be corrupted or invalid
The error message is: ('EOF in multi-line statement', (64, 0))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
...
TypeError: Cannot convert MatrixSpace_generic_with_category to sage.rings.ring.Ring

The thing is, we get

sage: x in Q
True
sage: y in Q
True

where Q is as above.

  1. Should MatrixSpace() notice when it is generating a ring?
  2. Should x and y be elements of Q? Is this due to coercion?
  3. Are these completely separate issues?

comment:32 in reply to: ↑ 31 Changed 6 years ago by SimonKing

Replying to john_perry:

Here's another one. Given the ring as defined so far:


TypeError? Traceback (most recent call last) ... TypeError?: Cannot convert MatrixSpace_generic_with_category to sage.rings.ring.Ring

Could you please state precisely what you did?

When I start sage with the patches applied, I get

sage: MS = MatrixSpace(GF(5),2)
sage: MS.0+MS.1
[1 1]
[0 0]
sage: MS.0*MS.1
[0 1]
[0 0]

The thing is, we get

sage: x in Q

What is Q?

  1. Should MatrixSpace() notice when it is generating a ring?

It obviously does. We have

sage: MS in Rings()
True

even without my patch.

comment:33 follow-up: Changed 6 years ago by john_perry

Could you please state precisely what you did?

Sure.

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: x = Q.an_element()
sage: y = MS.1
sage: x in Q, y in Q
(True, True)
sage: x*y

...and we get the error generated above.

Apparently this was not a problem with x=MS.1; I seem to have mistyped x==MS.1 when I was testing that.

comment:34 in reply to: ↑ 33 Changed 6 years ago by john_perry

Replying to john_perry:

Apparently this was not a problem with x=MS.1; I seem to have mistyped x==MS.1 when I was testing that.

Sorry, I meant x=MS.0 there.

comment:35 Changed 6 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to multiplication in quotient rings of matrix spaces

Now I understand the problem.

Addition in Q works, but multiplication in Q doesn't. That is because the current multiplication of quotient ring elements relies on a generic implementation. Multiplication of Q.0 with Q.1 is essentially the same as

sage: Q(Q.lift(Q.0)*Q.lift(Q.1))

The problem is: Q.lift(Q.0) tries to call Q.lifting_map(), which should return the lift map - but fails. I guess the failure comes from a cdef attribute that can only take an instance of type Ring; so, one couldn't assign MS to it.

However, multiplication of Q.0 with Q.1 could also be done as follows:

sage: Q(Q.0.lift()*Q.1.lift())
[0 1]
[0 0]

The difference is that Q.lift(Q.0) is a generic method of quotient rings, whereas Q.0.lift() is a generic method of quotient ring elements.

Obvious solution: If Q.lifting_map() can not construct the lifting map via sage.rings.morphism.RingMap_lift, then it should try sage.categories.morphism.SetMorphism.

Thanks for spotting it! I hope I can soon provide a new patch!

comment:36 Changed 6 years ago by SimonKing

It is not as easy as I had hoped. I was able to make Q.lift(Q.0) work. But when multiplying Q.0*Q.1, it is also attempted to construct a cover map (from MS to Q). The cover map comes with a section -- and the section is expected to be of type sage.rings.morphism.RingMap_lift.

Bad luck.

comment:37 Changed 6 years ago by SimonKing

Another approach: It turns out that sage.rings.morphism.RingMap_lift does have a cdef attribute S of type Ring. However, it is not needed that it is of type ring. I am thus replacing it by type CategoryObject, which should be perfectly alright.

Changed 6 years ago by SimonKing

Lifting map for quotients of rings not inheriting from sage.rings.ring.Ring

comment:38 Changed 6 years ago by SimonKing

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I submitted a third patch, and I think it works now!

We have the new doctest

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.lift()
Set-theoretic ring morphism:
  From: Quotient of Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5 by the ideal
(
  [0 1]
  [0 0],

  [0 0]
  [1 1]
)
  To:   Full MatrixSpace of 2 by 2 dense matrices over Finite Field of size 5
  Defn: Choice of lifting map

The tests in sage/rings/ pass (didn't run the other tests yet). Ready for review again!

comment:39 Changed 6 years ago by SimonKing

PS: Multiplying Q.0*Q.1 now works as well.

comment:40 Changed 6 years ago by john_perry

  • Status changed from needs_review to needs_work

Bad news. On OSX 10.6.8, the development version of sage (alpha2) fails three tests with these patches:

...
The following tests failed:

	sage -t -long devel/sage-main/sage/matrix/matrix2.pyx # 1 doctests failed
	sage -t -long devel/sage-main/sage/matrix/matrix_double_dense.pyx # 3 doctests failed
	sage -t -long devel/sage-main/sage/rings/polynomial/pbori.pyx # 2 doctests failed
----------------------------------------------------------------------

This makes some sense.

comment:41 Changed 6 years ago by SimonKing

And how do they fail?

comment:42 follow-up: Changed 6 years ago by john_perry

That wasn't smart of me. I looked at them, and they turned out to be numerical issues; I've seen the first reported elsewhere (0.0 v. -0.0). So this doesn't strike me as being caused by a change to categories & rings. If you want details, I'll copy them.

I'm not done with the other architectures; I started one last night before leaving the office, & have another to do here at home. I hope to wrap this up tonight.

comment:43 in reply to: ↑ 42 ; follow-up: Changed 6 years ago by SimonKing

  • Status changed from needs_work to needs_review

Replying to john_perry:

That wasn't smart of me. I looked at them, and they turned out to be numerical issues; I've seen the first reported elsewhere (0.0 v. -0.0). So this doesn't strike me as being caused by a change to categories & rings.

I remember that I had the same problem with one of the alpha versions.

By the way: Four days ago, I had updated the patch at #9138. Do you use the new version? With the old version, one would get an error on sage.math.

Can you test at what point in the patch chain the test starts to fail, and report appropriately? That's to say, if it fails with unpatched sage-4.7.2.alpha2 then report to sage-release; if it fails with #11115 or #11342 only, then report there.

comment:44 in reply to: ↑ 43 Changed 6 years ago by john_perry

Replying to SimonKing:

Can you test at what point in the patch chain the test starts to fail, and report appropriately?

If I have problems, I'll do that. Unfortunately, as I relayed to you in email, my OSX installation of sage no longer works after popping all the patches. Next time I'll pop only one at a time. I'm trying to rebuild it by reinstalling those patches, & hope something works.

Some good news: these three doctests work fine on Fedora-13. I'm now running all doctests there. More news as it comes.

comment:45 Changed 6 years ago by john_perry

All doctests pass on the Phenom X4 running Fedora 13.

comment:46 Changed 6 years ago by john_perry

All doctests pass on Intel Core 2 running Ubuntu 10.04.

comment:47 Changed 6 years ago by john_perry

  • Status changed from needs_review to positive_review

Two of the doctests I reported earlier fail on an unpatched 4.7.2alpha on an Intel Core 2 MacBook? Pro running OSX 10.6.8. That they still fail after this patch, which is wholly unrelated, is not a cause for concern. I tried looking for where these patches are discussed, but I didn't find them.

The regression I reported with pbori.pyx no longer appears with the more recent patch for #9138.

Thanks for the help fixing my installation. :-)

comment:48 Changed 6 years ago by SimonKing

There has been a short discussion on sage-devel. The aim was to make quotient rings unique parents, which also means that a better framework should be provided for testing equality of ideals.

First, I thought it would be best to do it on top of #9138 and add it as a new dependency for this ticket.

On the other hand, #11342 already has a positive review, and I hope that #9138 will soon be off my plate as well. Hence, the only dependency left for this ticket is #11115. Probably it will be better to do the new stuff on top of this ticket.

comment:49 Changed 6 years ago by SimonKing

  • Status changed from positive_review to needs_work
  • Work issues changed from multiplication in quotient rings of matrix spaces to rebase wrt new version of #9138

I am afraid that the ticket needs to be rebased. There has been a change in #9138, that must now be coped with here.

Changed 6 years ago by SimonKing

Add support for quotient rings without named generators

comment:50 Changed 6 years ago by SimonKing

  • Description modified (diff)
  • Status changed from needs_work to needs_review

I have rebased the patches. I guess it needs a new review. Note that the patches from #9138 have changed as well.

comment:51 Changed 6 years ago by SimonKing

PS: After rebasing, the tests still pass for me. But I think I am not entitled to reinstate the positive review.

comment:52 Changed 6 years ago by john_perry

  • Status changed from needs_review to positive_review

The tests pass for me as well.

comment:53 Changed 6 years ago by john_perry

By the way, I took a look at #11115, and while it looked good to me & the doctests pass, I don't feel I know enough about the workings of the cache to say for sure.

comment:54 Changed 6 years ago by leif

  • Dependencies changed from #10961, #9138, #11115, #11342 to #10961 #9138 #11115 #11342
  • Reviewers set to John Perry
  • Work issues rebase wrt new version of #9138 deleted

comment:55 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-4.7.2 to sage-4.7.3

comment:56 Changed 6 years ago by SimonKing

  • Dependencies changed from #10961 #9138 #11115 #11342 to #10961 #9138 #11115 #11342 #11339
  • Description modified (diff)

There was a conflict of the first patch with some cosmetical change that was done at #11339. Since #11339 has a positive review as well, I was changing the first patch. Since the code did not change (only the line breaks changed), I keep the positive review, but to be on the safe side I'll run doc tests now.

Apply trac11068_nc_ideals_and_quotients.patch trac11068_quotient_ring_without_names.patch trac11068_lifting_map.patch

comment:57 follow-up: Changed 6 years ago by SimonKing

Today is really not a good day for work. I had rebased my patch against #11339, but it turns out that #11339 needs work -- it creates some doctest errors with sage-4.7.2.alpha3-prerelease. So, I guess it would be better to return to the original patch version, which unfortunately is now lost.

comment:58 in reply to: ↑ 57 Changed 6 years ago by leif

Replying to SimonKing:

Today is really not a good day for work. I had rebased my patch against #11339, but it turns out that #11339 needs work -- it creates some doctest errors with sage-4.7.2.alpha3-prerelease. So, I guess it would be better to return to the original patch version, which unfortunately is now lost.

In case they are of any help, I have some old versions here:

-rw-r--r-- 1 leif leif  3236 2011-09-09 04:33 trac11068_lifting_map.patch
-rw-r--r-- 1 leif leif 65984 2011-09-09 04:33 trac11068_nc_ideals_and_quotients.patch
-rw-r--r-- 1 leif leif  3861 2011-09-09 04:33 trac11068_quotient_ring_without_names.patch

(The date refers to the time of download, CEST.)

comment:59 Changed 6 years ago by leif

I've now copied them into sage:/home/leif/tmp/ (http://boxen.math.washington.edu/home/leif/tmp/).

comment:60 Changed 6 years ago by SimonKing

  • Status changed from positive_review to needs_work

Thank you, Leif!

I think it make sense to take the time and use the occasion to start on top of sage-4.7.2.alpha3, not alpha3-prerelease. After all, the milestone has already been shifted by Jeroen to 4.7.3. So, I refuse being in a hurry now - that wouldn't be healthy.

comment:61 follow-up: Changed 6 years ago by SimonKing

  • Dependencies changed from #10961 #9138 #11115 #11342 #11339 to #10961 #9138 #11115 #11342 #10903
  • Status changed from needs_work to positive_review

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

comment:62 in reply to: ↑ 61 ; follow-up: Changed 6 years ago by john_perry

Replying to SimonKing:

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?

comment:63 in reply to: ↑ 62 Changed 6 years ago by jdemeyer

Replying to john_perry:

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.

comment:64 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-4.7.3 to sage-pending

comment:65 follow-up: Changed 6 years ago by jdemeyer

  • Dependencies changed from #10961 #9138 #11115 #11342 #10903 to #9138, #11900, #11115

This will eventually need to be rebased to #11900.

comment:66 in reply to: ↑ 65 ; follow-up: Changed 6 years ago by SimonKing

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

comment:67 in reply to: ↑ 66 ; follow-up: Changed 6 years ago by john_perry

Replying to SimonKing:

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?

comment:68 in reply to: ↑ 67 ; follow-up: Changed 6 years ago by SimonKing

Replying to john_perry:

Replying to SimonKing:

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.

comment:69 Changed 6 years ago by jdemeyer

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.

comment:70 in reply to: ↑ 68 Changed 6 years ago by jdemeyer

Replying to SimonKing:

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.

comment:71 Changed 6 years ago by SimonKing

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

comment:72 Changed 6 years ago by SimonKing

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

comment:73 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-pending to sage-5.0

comment:74 Changed 6 years ago by jdemeyer

  • Description modified (diff)

Changed 6 years ago by jdemeyer

Non-commutative ideals and quotient rings

comment:75 Changed 6 years ago by jdemeyer

Patch rebased to latest version of #11900.

comment:76 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.0.beta1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:77 follow-up: Changed 4 weeks ago by mderickx

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

comment:78 in reply to: ↑ 77 Changed 4 weeks ago by SimonKing

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

Replying to mderickx:

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

Note: See TracTickets for help on using tickets.