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//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//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//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//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//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//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//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//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//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//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//issues/58#issuecomment-27695882
.