Closed simon-king-jena closed 12 years ago
simon-king-jena
commented
13 years ago Description changed:
---
+++
@@ -11,3 +11,5 @@
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.
Work Issues: Add examples; move code from ring.py to rings.py
simon-king-jena
commented
13 years ago Description changed:
---
+++
@@ -13,3 +13,5 @@It was suggested to also add quotients by twosided ideals, although it will be difficult to provide examples before having letterplace ideals. + +Depends on #10961
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
commented
13 years ago 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*yI 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
commented
13 years ago Nice! That sounds like a perfect example indeed.
Thanks for removing this item from my TODO list :-)
simon-king-jena
commented
13 years ago 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.Ringtosage.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
commented
13 years ago 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
commented
13 years ago 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
commented
13 years ago I think it should be part of this ticket to properly use categories and the new coercion model for
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
commented
13 years ago 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
lifthave 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
commented
13 years ago 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
commented
13 years ago 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
commented
13 years ago 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
commented
13 years ago 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
commented
13 years ago Description changed:
---
+++
@@ -14,4 +14,4 @@
It was suggested to also add quotients by twosided ideals, although it will be difficult to provide examples before having letterplace ideals.
-Depends on #10961
+Depends on #10961 #9138 #11115I noticed that the ticket description stated an incomplete list of dependencies
simon-king-jena
commented
13 years ago Author: Simon King
simon-king-jena
commented
13 years ago Dependencies: #10961, #9138, #11115
simon-king-jena
commented
13 years ago 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
commented
13 years ago 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
commented
13 years ago Done!
With the new patch, we have
sage: R = Integers(8)
sage: I = R.ideal(2)
sage: R.quotient(I)
Ring of integers modulo 2I had to rebase my patch against sage-4.7.1.rc1
Review is still welcome...
simon-king-jena
commented
13 years ago 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...
johnperry-math
commented
13 years ago I'm working on testing this (have to recompile nearly everything!) but here are two comments:
johnperry-math
commented
13 years ago Update:
_ideal_class()? This is a method for a ring, not an ideal.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(...)Hi John,
Replying to @johnperry-math:
- 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]
)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(...)Changed work issues from Shall one move code from ring.pyx to rings.py? to Print quotient ring elements if the cover has no variable names
simon-king-jena
commented
13 years ago 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!
simon-king-jena
commented
13 years ago 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
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...
simon-king-jena
commented
13 years ago Changed work issues from Print quotient ring elements if the cover has no variable names to none
simon-king-jena
commented
13 years ago Changed dependencies from #10961, #9138, #11115 to #10961, #9138, #11115, #11342
simon-king-jena
commented
13 years ago 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."
johnperry-math
commented
13 years ago Changed keywords from onesided twosided ideal noncommutative ring to onesided twosided ideal noncommutative ring sd32
johnperry-math
commented
13 years ago 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?
simon-king-jena
commented
13 years ago Replying to @johnperry-math:
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.
johnperry-math
commented
13 years ago 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.RingThe thing is, we get
sage: x in Q
True
sage: y in Q
Truewhere Q is as above.
MatrixSpace() notice when it is generating a ring?x and y be elements of Q? Is this due to coercion?simon-king-jena
commented
13 years ago Replying to @johnperry-math:
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?
- Should
MatrixSpace()notice when it is generating a ring?
It obviously does. We have
sage: MS in Rings()
Trueeven without my patch.
johnperry-math
commented
13 years ago 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.
johnperry-math
commented
13 years ago Replying to @johnperry-math:
Apparently this was not a problem with
x=MS.1; I seem to have mistypedx==MS.1when I was testing that.
Sorry, I meant x=MS.0 there.
simon-king-jena
commented
13 years ago Work Issues: multiplication in quotient rings of matrix spaces
simon-king-jena
commented
13 years ago 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!
simon-king-jena
commented
13 years ago 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.
simon-king-jena
commented
13 years ago 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.
simon-king-jena
commented
13 years ago Lifting map for quotients of rings not inheriting from sage.rings.ring.Ring
simon-king-jena
commented
13 years ago Attachment: trac11068_lifting_map.patch.gz
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 mapThe tests in sage/rings/ pass (didn't run the other tests yet). Ready for review again!
simon-king-jena
commented
13 years ago Description changed:
---
+++
@@ -15,3 +15,5 @@
It was suggested to also add quotients by twosided ideals, although it will be difficult to provide examples before having letterplace ideals.
Depends on #10961 #9138 #11115
+
+Apply all three patches.PS: Multiplying Q.0*Q.1 now works as well.
johnperry-math
commented
13 years ago 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.
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:
It was suggested to also add quotients by twosided ideals, although it will be difficult to provide examples before having letterplace ideals.
Apply:
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