nc algebra?
Kyle Schalm
what's the status of noncommutative algebra in sage?
suppose i want to play with expressions in the free algebra Z<a,b> modulo
the relation ab=ba+a. i'd also like to factor and gcd, ideally. er... no
pun intended.
how do i do this -- or if sage can't do this (yet), what are my
options?
thanks
kyle
Mike Hansen
This is one area in which Sage (and GAP4 for that matter) could use
some work -- there hasn't really been anyone been working on it.
Right now, there is a FreeAlgebraQuotient (
http://www.sagemath.org/doc/html/ref/module-sage.algebras.free-algebra-quotient.html
) in Sage which allows you to work with these objects assuming you
have a faithful representation for the algebra. The vector
enumeration algorithms allow one to go from a description of the
underlying two sided ideal like you have with a*b-b*a-a to a
representation that could be plugged into FreeAlgebraQuotient. There
is a free software implementation in C by Steve Linton, and we should
definitely think about including it in Sage. It comes with the GAP3
package "ve".
The other way to go about doing things is with noncommutative Grobner
bases which I would be pretty interested in. But, Sage does not have
any support for these at the moment. The only real algorithm that I
know of is due to Mora, but this is probably due to my relative
unfamiliarity with the area. I do know that Bergman (
http://servus.math.su.se/bergman/ ) and the GAP4 package GBNP (
http://www.mathdox.org/products/gbnp/ ) can carry out these
computations. I have no idea on their relative efficiency though.
It may come as no surprise, but Magma is probably the best software
now in this area. Reading Magma's docs on this stuff is a good place
to start http://www.math.uiuc.edu/Software/magma/text433.html .
--Mike
P.S. I'm not sure what you (specifically) want when you say factoring
or gcd in these algebras.
mabshoff
On Dec 26, 9:57 am, "Mike Hansen" <mhan...@gmail.com> wrote:
> Hi Kyle,
>
> This is one area in which Sage (and GAP4 for that matter) could use
> some work -- there hasn't really been anyone been working on it.
> have a faithful representation for the algebra. The vector
> enumeration algorithms allow one to go from a description of the
> underlying two sided ideal like you have with a*b-b*a-a to a
> representation that could be plugged into FreeAlgebraQuotient. There
> is a free software implementation in C by Steve Linton, and we should
> definitely think about including it in Sage. It comes with the GAP3
> package "ve".
>
> The other way to go about doing things is with noncommutative Grobner
> bases which I would be pretty interested in. But, Sage does not have
> any support for these at the moment. The only real algorithm that I
> know of is due to Mora, but this is probably due to my relative
> unfamiliarity with the area. I do know that Bergman (http://servus.math.su.se/bergman/)
clisp newer than the 2.32 release. I have complained about that, but
nothing happened. You can use other lisp implementations to get it to
run, though. As fas as I can remember Bergman is also limited to
homogeneous ideals when computing those nc-GBases, but I wouldn't
swear on it.
A much more plausible candidate to do nc operations and GBasis
computations would be Singular. It should also be possible to use
libSingular for that, but I guess malb has to fill in the details.
Cheers,
Michael
> and the GAP4 package GBNP (http://www.mathdox.org/products/gbnp/) can carry out these
>
> It may come as no surprise, but Magma is probably the best software
> now in this area. Reading Magma's docs on this stuff is a good place
> to starthttp://www.math.uiuc.edu/Software/magma/text433.html.
>
> --Mike
>
> P.S. I'm not sure what you (specifically) want when you say factoring
> or gcd in these algebras.
>
Mike Hansen
nice, but the interface is a little clunky. I think it could easily
provide a lot of functionality to Sage so I am going to spend some of
my time at the AMS meeting working on this.
I made a very basic spkg at
http://sage.math.washington.edu/home/mhansen/gbnp-0.9.5.spkg . Here
is an example in the quotient algebra you mentioned:
sage: gap.eval('LoadPackage("GBNP")')
'true'
sage: gen = [ [[1,2],[2,1],[1]], [1,-1,-1] ]
sage: relations = gap( [ gen ] )
sage: print gap.eval('PrintNPList(%s)'%relations.name())
ab - ba - a
sage: GB = gap.SGrobner(relations)
sage: print gap.eval('PrintNPList(%s)'%GB.name())
ba - ab + a
sage: p = gap.StrongNormalFormNP( [[[1,2]],[1]], GB ); print
gap.eval('PrintNP(%s)'%p.name())
ab
sage: p = gap.StrongNormalFormNP( [[[2,1]],[1]], GB ); print
gap.eval('PrintNP(%s)'%p.name())
ab - a
sage: p = gap.StrongNormalFormNP( [[[2,1,1,2,1,2]],[1]], GB ); print
gap.eval('PrintNP(%s)'%p.name())
a^3b^3 - 4a^3b^2 + 3a^3b
Your quotient algebra is infinite dimensional whose dimension grows like n^2.
sage: gap.FinCheck(gap.LTermsNP(GB), 2)
false
You can get a basis for the components of degree 0 through 4:
sage: B = gap.BaseQA(GB, 2, 10)
sage: print gap.eval('PrintNPList(%s)'%B.name())
1
a
b
a^2
ab
b^2
a^3
a^2b
ab^2
b^3
a^4
a^3b
a^2b^2
ab^3
b^4
Check out the examples for some more ideas of what you can do with
this: http://www.mathdox.org/products/gbnp/chapA.html
--Mike
Kyle Schalm
Mike,
sorry, i've been away from the internet, and also distracted,
or would have replied sooner. see below.
On Wed, 26 Dec 2007, Mike Hansen wrote:
>
> Hi Kyle,
>
> This is one area in which Sage (and GAP4 for that matter) could use
> some work -- there hasn't really been anyone been working on it.
> Right now, there is a FreeAlgebraQuotient (
> http://www.sagemath.org/doc/html/ref/module-sage.algebras.free-algebra-quotient.html
> ) in Sage which allows you to work with these objects assuming you
> have a faithful representation for the algebra. The vector
> enumeration algorithms allow one to go from a description of the
> underlying two sided ideal like you have with a*b-b*a-a to a
> representation that could be plugged into FreeAlgebraQuotient. There
> is a free software implementation in C by Steve Linton, and we should
> definitely think about including it in Sage. It comes with the GAP3
> package "ve".
this isn't my area at all, so i didn't really understand that, but doesn't
FreeAlgebraQuotient create only finite dimensional algebras, which mine is
not?
>
> The other way to go about doing things is with noncommutative Grobner
> bases which I would be pretty interested in. But, Sage does not have
> any support for these at the moment. The only real algorithm that I
> know of is due to Mora, but this is probably due to my relative
> unfamiliarity with the area. I do know that Bergman (
> http://servus.math.su.se/bergman/ ) and the GAP4 package GBNP (
> http://www.mathdox.org/products/gbnp/ ) can carry out these
> computations. I have no idea on their relative efficiency though.
i finally figured out how to construct the algebra in
singular/plural, and i can get the "gcd" by asking for a standard basis
for the ideal generated by a given set of elements. but it seems like
that's about all i can do in singular. not only that, but i want the
output grouped by powers of a, say like (b^2 + 1)*a^2 + (b+1)*a + 1, and i
can't see how to even do that.
>
> It may come as no surprise, but Magma is probably the best software
> now in this area. Reading Magma's docs on this stuff is a good place
> to start http://www.math.uiuc.edu/Software/magma/text433.html .
too bad it costs money. i do have access to it through the school, but i
want something i can use on my laptop.
>
> --Mike
>
> P.S. I'm not sure what you (specifically) want when you say factoring
> or gcd in these algebras.
yes, yes... good question... mainly i want a
factorization into factors with lower degree in a, if one exists. in
my example, a and b have infinite order, so i think this makes sense.
i will now peruse your next message about GAP and try to digest it.
thanks
-kyle