quotient of a Weyl algebra by a left ideal

[DanGrayson]

Reported by: anton (on trac)

Forming a QuotientRing as in the example below should produce an error (for noncommutative algebras)... as this makes little sense.

i1 : W = QQ[x,dx,WeylAlgebra=>{x=>dx}]

o1 = W

o1 : PolynomialRing

i2 : A := W/ideal dx

  W
o2 = --                                                                         
 dx

o2 : QuotientRing

i3 : dx_A*x_A == (dx*x)_A

o3 = false

An alternative behaviour would be to return the module W^1/I.

[DanGrayson]

Perhaps a better alternative behavior would be to declare that ideals of class Ideal should be 2-sided. And then to leave them unimplemented until someone comes up with an algorithm for them. Example: given generators of an ideal, find generators for it as a left ideal.

We don't need the concept of left ideal or of right ideal because we have the concept of submodule of R^1.

Comments?

[antonleykin]

In the case of the Weyl algebra two-sided ideals are trivial... Given that M2 does not implement many more noncommutative algebras and that for "GB-friendly algebras", in general, one-sidedness is natural there is no necessity in redefining Ideal to be two-sided at this point.

[DanGrayson]

We have to do something, though, because R/I will still try to make a ring.

On Tue, Oct 29, 2013 at 4:15 PM, antonleykin notifications@github.comwrote:

In the case of the Weyl algebra two-sided ideals are trivial... Given that M2 does not implement many more noncommutative algebras and that for "GB-friendly algebras", in general, one-sidedness is natural there is no necessity in redefining Ideal to be two-sided at this point.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27339140 .

[DanGrayson]

The thing to do is to have "ideal(...)" check the ring, and if it's noncommutative, to give an error message: ideals in noncommutative rings are not implemented. And to fix the documentation under the class Ideal to say that ideals are two-sided, so quotient rings make sense.

[antonleykin]

... that will invalidate a lot of code in the packages. There is also no mechanism implemented to do computations in noncommutative quotient rings.

On the other hand, making a remark in documentation for Ideal that "left" is implied in the noncommutative case and giving error in Ring/Ideal does not break anything.

[DanGrayson]

Maybe your point is that we actually need left ideals for something. What do you use them for?

If that's the case, then we have to distinguish between left ideals and two-sided ideals somehow. And it would be good to design that now.

On Wed, Oct 30, 2013 at 8:04 AM, antonleykin notifications@github.comwrote:

... that will invalidate a lot of code in the packages. There is also no mechanism implemented to do computations in noncommutative quotient rings.

On the other hand, making a remark in documentation for Ideal that "left" is implied in the noncommutative case and giving error in Ring/Ideal does not break anything.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27383394 .

[antonleykin]

Left ideals (which are implemented in M2) have been already used in packages, two-sided ideals do not exist as a concept implemented in M2.

One of my points is that there is no pressing need to introduce two-sided ideals.

[DanGrayson]

What are left ideals currently used for in packages? Do they offer any advantages over submodules of R^1?

If we're going to introduce 2-sided ideals eventually, now is as good a time as any to plan the organizational aspects that will make that possible.

On Wed, Oct 30, 2013 at 8:46 AM, antonleykin notifications@github.comwrote:

Left ideals (which are implemented in M2) have been already used in packages, two-sided ideals do not exist as a concept implemented in M2.

One of my points is that there is no pressing need to introduce two-sided ideals.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27385694 .

[antonleykin]

Left ideals and left submodules of the ring are, of course, the same thing. By the same token two-sides ideals are the sub-bimodules of the ring considered as a bimodule.

I think, people who would use two-sided ideals and algebras of non-polynomial type should contribute to this discussion... but suppose we do want to introduce two-sided ideals now. I see two ways:

• make a new type "TwoSidedIdeal"
• let the meaning of "Ideal" depend on the ring: e.g., for the Weyl algebra it will remain left (since two-sided ideals are useless), but for some matrix algebra of the future it would be two-sided.

[DanGrayson]

You could have a family of Weyl algebras over a polynomial ring. That would be an algebra with additional central variables, and then it would make sense to form a quotient ring by an ideal generated by central elements.

It would too confusing to have the meaning of Ideal depend on the context. If submodules of R^1 can be used instead of left ideals, why have left ideals at all? What are left ideals currently used for in your packages? Could you easily transition to submodules of R^1?

I'm still leaning toward making Ideal mean 2-sided ideal, since there seems to be no concrete use for left ideals.

On Fri, Nov 1, 2013 at 8:54 AM, antonleykin notifications@github.comwrote:

Left ideals and left submodules of the ring are, of course, the same thing. By the same token two-sides ideals are the sub-bimodules of the ring considered as a bimodule.

I think, people who would use two-sided ideals and algebras of non-polynomial type should contribute to this discussion... but suppose we do want to introduce two-sided ideals now. I see two ways:

• make a new type "TwoSidedIdeal"
• let the meaning of "Ideal" depend on the ring: e.g., for the Weyl algebra it will remain left (since two-sided ideals are useless), but for some matrix algebra of the future it would be two-sided.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27563463 .

[mikestillman]

I think that Anton is correct though, in that people use Ideal currently to mean left ideal, and that to change it would break significant amount of code. (At least, I suspect that it is significant). I would like to hear from Frank Moore about what he thinks, as he is programming non-commutative algebras.

[moorewf]

In my NCAlgebra package, I have been distinguishing between left, right and two-sided ideals (though the package would not handle the Weyl algebra very well (if at all), as it is not graded). Left and right ideal types are not as fully featured as the two-sided ideal types at this time.

I think allowing 'Ideal' to be dependent on the ring is indeed dangerous, since left/right ideals and two-sided ideals are so fundamentally different. I think Dan's example of a family of Weyl algebras also shows the utility of this approach. It does seem that to make this change would break a lot of code, but a new type called LeftIdeal can be made, with all the relevant utility functions that Ideal has, so that the current code would not need any 'substantial' changes.

It seems that if one implemented functions with sided modules (or bi-modules), then one would by extension also have operations on sided ideals (or ideals) as well. The NCAlgebra package does not yet have functionality for modules, but will soon I think.

Hope this helps.

[DanGrayson]

Frank, do you see any use for left ideals or right ideals that wouldn't be served adequately by submodules of R^1? And do you really need both left and right, or will one suffice? If not, do you need also left and right free modules, etc?

On Fri, Nov 1, 2013 at 3:43 PM, Frank Moore notifications@github.comwrote:

In my NCAlgebra package, I have been distinguishing between left, right and two-sided ideals (though the package would not handle the Weyl algebra very well (if at all), as it is not graded). Left and right ideal types are not as fully featured as the two-sided ideal types at this time.

I think allowing 'Ideal' to be dependent on the ring is indeed dangerous, since left/right ideals and two-sided ideals are so fundamentally different. I think Dan's example of a family of Weyl algebras also shows the utility of this approach. It does seem that to make this change would break a lot of code, but a new type called LeftIdeal can be made, with all the relevant utility functions that Ideal has, so that the current code would not need any 'substantial' changes.

It seems that if one implemented functions with sided modules (or bi-modules), then one would by extension also have operations on sided ideals (or ideals) as well. The NCAlgebra package does not yet have functionality for modules, but will soon I think.

Hope this helps.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27595210 .

[moorewf]

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

[DanGrayson]

So maybe Ideal should be augmented with a new class called LeftIdeal. (We provide only left modules, so providing right ideals but not right modules would be overkill.) And then "ideal", the function, could be augmented with a function "leftIdeal". Fixing any broken code would then be trivial, and I could do it at the same moment, by running all of the packages' tests.

I see that in your package you have created three classes for the three types of ideals, bypassing the issue with Ideal that we're discussing. In particular, your code would probably not break if the functionality of "ideal" changes slightly.

Does anyone get confused that scalars and matrices both act on the left? That's why matrix multiplication is implemented with the opposite multiplication, so it will give a homomorphism of left R-modules.

On Fri, Nov 1, 2013 at 4:18 PM, Frank Moore notifications@github.comwrote:

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27597620 .

[DanGrayson]

Forming a non-commutative quotient ring reveals a bug:

i1 : R = ZZ[x,d,WeylAlgebra => x => d]

o1 = R

o1 : PolynomialRing

i2 : d*x

o2 = x*d + 1

o2 : R

i3 : d*x-x*d

o3 = 1

o3 : R

i4 : S = R/x

o4 = S

o4 : QuotientRing

i5 : 1_S

o5 = 1

o5 : S

On Sat, Nov 2, 2013 at 9:55 AM, Daniel R. Grayson dan@math.uiuc.edu wrote:

This issue, number 58, seems to have mysteriously vanished from github.

On Sat, Nov 2, 2013 at 9:51 AM, Daniel R. Grayson dan@math.uiuc.eduwrote:

So maybe Ideal should be augmented with a new class called LeftIdeal. (We provide only left modules, so providing right ideals but not right modules would be overkill.) And then "ideal", the function, could be augmented with a function "leftIdeal". Fixing any broken code would then be trivial, and I could do it at the same moment, by running all of the packages' tests.

I see that in your package you have created three classes for the three types of ideals, bypassing the issue with Ideal that we're discussing. In particular, your code would probably not break if the functionality of "ideal" changes slightly.

Does anyone get confused that scalars and matrices both act on the left? That's why matrix multiplication is implemented with the opposite multiplication, so it will give a homomorphism of left R-modules.

On Fri, Nov 1, 2013 at 4:18 PM, Frank Moore notifications@github.comwrote:

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27597620 .

[DanGrayson]

Maybe this reveals the bug more clearly:

i1 : R = ZZ[x,d,WeylAlgebra => x => d]

o1 = R

o1 : PolynomialRing

i2 : d_x == x_d + 1

o2 = true

i3 : S = R/x

o3 = S

o3 : QuotientRing

i4 : d_x == x_d + 1

o4 = false

On Sat, Nov 2, 2013 at 10:06 AM, Daniel R. Grayson dan@math.uiuc.eduwrote:

Forming a non-commutative quotient ring reveals a bug:

i1 : R = ZZ[x,d,WeylAlgebra => x => d]

o1 = R

o1 : PolynomialRing

i2 : d*x

o2 = x*d + 1

o2 : R

i3 : d*x-x*d

o3 = 1

o3 : R

i4 : S = R/x

o4 = S

o4 : QuotientRing

i5 : 1_S

o5 = 1

o5 : S

On Sat, Nov 2, 2013 at 9:55 AM, Daniel R. Grayson dan@math.uiuc.eduwrote:

This issue, number 58, seems to have mysteriously vanished from github.

On Sat, Nov 2, 2013 at 9:51 AM, Daniel R. Grayson dan@math.uiuc.eduwrote:

So maybe Ideal should be augmented with a new class called LeftIdeal. (We provide only left modules, so providing right ideals but not right modules would be overkill.) And then "ideal", the function, could be augmented with a function "leftIdeal". Fixing any broken code would then be trivial, and I could do it at the same moment, by running all of the packages' tests.

I see that in your package you have created three classes for the three types of ideals, bypassing the issue with Ideal that we're discussing. In particular, your code would probably not break if the functionality of "ideal" changes slightly.

Does anyone get confused that scalars and matrices both act on the left? That's why matrix multiplication is implemented with the opposite multiplication, so it will give a homomorphism of left R-modules.

On Fri, Nov 1, 2013 at 4:18 PM, Frank Moore notifications@github.comwrote:

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27597620 .

[antonleykin]

Having LeftIdeal, RightIdeal, TwoSidedIdeal could be OK.

What would break a lot of code is changing the behavior of ideal(...) Replacing all entries of ideal(...) with leftIdeal(...) will do the trick, but is still a bit ugly... especially given that the change has to be applied in users code, which we don't see. (E.g., in Dmodules an "Ideal" is more or less synonymous with a "D-module"... and has been used as is for 10 years)

Moreover, I still think this is not only the legacy code and backward compatibility issue. As implemented, Ring implies having operations beyond * and +. One crucial operation is gb(Ideal). The way things are set up "Ring" means a "polynomial ring of solvable type", (a.k.a. Grobner friendly) and, say, an operation of taking a quotient ring should not take us out of this class.

Dan's example (central variables) is special: every two-sided ideal in such an algebra would be an extension of an ideal in k[central variables] and, yes, one should be able to take a quotient w.r.t. this. But this is possible at the moment -- the only bug that (started that thread and) needs to be fixed is in taking R/I when the left ideal I happens to be not two-sided... That can be fixed by checking if I is two-sided.

Perhaps, a clean solution would be to have a new type, Algebra, which has no operation "gb". Then -- ideal {RingElements} will remain intact returning an Ideal (or LeftIdeal if renamed), which is a natural thing to do for a Grobner friendly ring -- ideal {AlgebraElements} would return a TwoSidedIdeal

On Sat, Nov 2, 2013 at 9:52 AM, Daniel R. Grayson notifications@github.comwrote:

So maybe Ideal should be augmented with a new class called LeftIdeal. (We provide only left modules, so providing right ideals but not right modules would be overkill.) And then "ideal", the function, could be augmented with a function "leftIdeal". Fixing any broken code would then be trivial, and I could do it at the same moment, by running all of the packages' tests.

I see that in your package you have created three classes for the three types of ideals, bypassing the issue with Ideal that we're discussing. In particular, your code would probably not break if the functionality of "ideal" changes slightly.

Does anyone get confused that scalars and matrices both act on the left? That's why matrix multiplication is implemented with the opposite multiplication, so it will give a homomorphism of left R-modules.

On Fri, Nov 1, 2013 at 4:18 PM, Frank Moore notifications@github.comwrote:

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

— Reply to this email directly or view it on GitHub< https://github.com/Macaulay2/M2/issues/58#issuecomment-27597620> .

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27622354 .

[DanGrayson]

Okay, what about this amalgamation of the suggestions?

• objects of class Ideal are left ideals
• whether an object of class Ideal is a two-sided ideal is a property
• "ideal" continues to make left ideals, but an optional argument TwoSided=>true will tell it to add enough generators to make it two sided
• no new classes are introduced
• a predicate function "isTwoSided" is provided, caching the answer inside the ideal
• Ring/Ideal checks whether the ideal is two-sided, giving an error if not
• Ring/RingElement, Ring/Sequence, etc., call "ideal" with TwoSided=>true
• Module/RingElement is audited for correctness, etc.
• users who want right ideals have to use left ideals in the opposite ring, since we don't have the facility in the engine for doing it any other way
• gb(Ideal) continues to deal with generators of left ideals, as before

[antonleykin]

Sounds good! Other functions to audit are Ideal : Ideal and Ideal : RingElement.

On Sat, Nov 2, 2013 at 2:04 PM, Daniel R. Grayson notifications@github.comwrote:

Okay, what about this amalgamation of the suggestions?

• objects of class Ideal are left ideals
• whether an object of class Ideal is a two-sided ideal is a property
• "ideal" continues to make left ideals, but an optional argument TwoSided=>true will tell it to add enough generators to make it two sided
• no new classes are introduced
• a predicate function "isTwoSided" is provided, caching the answer inside the ideal
• Ring/Ideal checks whether the ideal is two-sided, giving an error if not
• Ring/RingElement, Ring/Sequence, etc., call "ideal" with TwoSided=>true
• Module/RingElement is audited for correctness, etc.
• users who want right ideals have to use left ideals in the opposite ring, since we don't have the facility in the engine for doing it any other way
• gb(Ideal) continues to deal with generators of left ideals, as before

On Sat, Nov 2, 2013 at 10:47 AM, antonleykin notifications@github.comwrote:

Having LeftIdeal, RightIdeal, TwoSidedIdeal could be OK.

What would break a lot of code is changing the behavior of ideal(...) Replacing all entries of ideal(...) with leftIdeal(...) will do the trick, but is still a bit ugly... especially given that the change has to be applied in users code, which we don't see. (E.g., in Dmodules an "Ideal" is more or less synonymous with a "D-module"... and has been used as is for 10 years)

Moreover, I still think this is not only the legacy code and backward compatibility issue. As implemented, Ring implies having operations beyond * and +. One crucial operation is gb(Ideal). The way things are set up "Ring" means a "polynomial ring of solvable type", (a.k.a. Grobner friendly) and, say, an operation of taking a quotient ring should not take us out of this class.

Dan's example (central variables) is special: every two-sided ideal in such an algebra would be an extension of an ideal in k[central variables] and, yes, one should be able to take a quotient w.r.t. this. But this is possible at the moment -- the only bug that (started that thread and) needs to be fixed is in taking R/I when the left ideal I happens to be not two-sided... That can be fixed by checking if I is two-sided.

Perhaps, a clean solution would be to have a new type, Algebra, which has no operation "gb". Then -- ideal {RingElements} will remain intact returning an Ideal (or LeftIdeal if renamed), which is a natural thing to do for a Grobner friendly ring -- ideal {AlgebraElements} would return a TwoSidedIdeal

On Sat, Nov 2, 2013 at 9:52 AM, Daniel R. Grayson notifications@github.comwrote:

So maybe Ideal should be augmented with a new class called LeftIdeal. (We provide only left modules, so providing right ideals but not right modules would be overkill.) And then "ideal", the function, could be augmented with a function "leftIdeal". Fixing any broken code would then be trivial, and I could do it at the same moment, by running all of the packages' tests.

I see that in your package you have created three classes for the three types of ideals, bypassing the issue with Ideal that we're discussing. In particular, your code would probably not break if the functionality of "ideal" changes slightly.

Does anyone get confused that scalars and matrices both act on the left? That's why matrix multiplication is implemented with the opposite multiplication, so it will give a homomorphism of left R-modules.

On Fri, Nov 1, 2013 at 4:18 PM, Frank Moore notifications@github.comwrote:

We haven't decided whether we need both left and right, since of course left modules over R are right modules over R^op, and that transition from R to R^op is aided by some functionality already.

If you want to take a look at what we have done thus far, you can find the package under "workshops/WFU-2012/NCAlgebra" on subversion. (I know, shame on me for not moving to git. Is there a 'friendly' introduction that you could point me to?)

While I don't necessarily see any theoretical benefit of having left ideals vs. left submodules of the left free module R^1, I do think it is beneficial to the user, much in the same way that M2 has facility for both Ideals as well as submodules of free modules, has them typed differently, etc.

— Reply to this email directly or view it on GitHub< https://github.com/Macaulay2/M2/issues/58#issuecomment-27597620> .

— Reply to this email directly or view it on GitHub< https://github.com/Macaulay2/M2/issues/58#issuecomment-27622354> .

— Reply to this email directly or view it on GitHub< https://github.com/Macaulay2/M2/issues/58#issuecomment-27623363> .

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27627458 .

[DanGrayson]

PS: It occurs to me that there isn't an algorithm for adding enough generators to make a left ideal two-sided, so we'll omit that part.

If no one objects, I'll assign this task to myself and eventually do it.

[antonleykin]

In the GB-friendly setting there is a naive algorithm: append (right) multiples of the generators of the left ideal by the generators of the ring until nothing new appears.

On Mon, Nov 4, 2013 at 10:56 AM, Daniel R. Grayson <notifications@github.com

wrote:

PS: It occurs to me that there isn't an algorithm for adding enough generators to make a left ideal two-sided, so we'll omit that part.

If no objects, I'll assign this task to myself and eventually do it.

— Reply to this email directly or view it on GitHubhttps://github.com/Macaulay2/M2/issues/58#issuecomment-27695882 .