Computing non-commutative Groebner bases and Groebner bases for modules - Maple Help

Online Help

All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Algebra : Polynomials : Groebner : Groebner/Basis_details

Computing non-commutative Groebner bases and Groebner bases for modules

Calling Sequence

Basis(F, T, opts)

MonomialOrder(A, tord, U)




list or set of polynomials






optional arguments of the form keyword=value



commutative algebra of polynomials, Weyl algebra, or Ore algebra






(optional) module placeholder variables



The Groebner[Basis] command computes Groebner bases for ideals and modules over both commutative and skew polynomial rings.  This help page describes how to compute Groebner bases for modules and non-commutative Groebner bases. For the ordinary polynomial case, please refer to the Basis help page.


Most commands in the Groebner package support computations with modules and in non-commutative algebras. In both cases there are two steps to perform before Groebner bases can be computed:


1) construct an appropriate polynomial algebra A using the Ore_algebra package


2) construct a term order on A using Groebner[MonomialOrder]

Groebner Bases for Commutative Modules


To represent modules over the polynomial ring K[x1,...,xn] Maple uses placeholder (or dummy) variables U = {u1,...,um}. Multiplication by the Ui are not allowed, so different monomials in U = {u1,...,um} indicate different module components. Terms can be ordered by any total order on {x1,...,xn,u1,...,um}, but typically a built-in monomial order is used.


F := [x+y+z, x*y+y*z+z*x, x*y*z-1];



We will use Groebner bases for modules to express a Groebner basis for F in terms of the original polynomials. To keep track of what multiples of each F[i] were used, we will construct the Q[x,y,z]-module of rank 4 shown below.

M := [seq(Vector(subsop(i+1=1, [F[i], 0, 0, 0])), i=1..3)];



To put this module in a form suitable for the Groebner package, we use polynomials for each module element. The module components are distinguished by powers of a single dummy variable s, where higher powers of s indicate more significant components.

M := [seq( s^3*F[i] + s^(3-i), i=1..3)];



Next we must construct an algebra on s,x,y,z and choose a monomial order. The elements of Q[x,y,z,s] are commutative polynomials, so we use the poly_algebra command. To order the module elements we use lexdeg([s], [x,y,z]) which compares first by module component and then by tdeg(x,y,z). This is a "position-over-term" or "POT" order in the terminology of Adams and Loustaunau. To construct a "term-over-position" or "TOP" order we could use lexdeg([x,y,z],[s]) or, more generally, a product order. The module placeholder variables are declared as the third argument to Groebner[MonomialOrder].




A := poly_algebra(x,y,z,s);



T := MonomialOrder(A, lexdeg([s], [x,y,z]), {s});



G := Groebner[Basis](M, T);



We have computed a Groebner basis for the module of syzygies of F. The polynomials with maximal degree in s contain a Groebner basis for F and their lower-degree components describe how to express that basis in terms of the elements of F.

G1 := select(proc(a) evalb(degree(a,s)=3) end proc, G);



[seq(Vector([seq(coeff(j,s,3-i), i=0..3)]), j=G1)];



The transformation matrix (whose dot product with F gives the Groebner basis) is the transpose of the bottom three rows.

C := Matrix([seq([seq(coeff(j,s,3-i), i=1..3)], j=G1)]);



GB := map(expand, convert(C.Vector(F), list));



Groebner[Basis](F, tdeg(x,y,z));



Non-Commutative Groebner Bases


To compute non-commutative Groebner bases in Maple we again define an algebra using the Ore_algebra package. For example, a Weyl algebra (Ore_algebra[diff_algebra]) is an algebra consisting of linear differential operators. There are also shift and q-shift algebras (Ore_algebra[shift_algebra]), and general skew algebras (Ore_algebra[skew_algebra]).  See the Ore_algebra help pages for more information.


Here is an example of a non-commutative Weyl algebra where D[i]*x[i] = x[i]*D[i] + 1 for i=1..N.


N := 3:

A := diff_algebra(seq([D[i], x[i]], i=1..N), polynom={seq(x[i], i=1..N)});



Next we define a monomial order on A using the MonomialOrder command. There are no module placeholder variables, A is a skew polynomial ring.

tord := tdeg(seq(D[i],i=1..N), seq(x[i],i=1..N));



T := MonomialOrder(A, tord);



Finally we construct a set of generators F and compute a Groebner basis with respect to T.

S := `+`(seq(x[i]*D[i], i=1..N)):

P := skew_product(S+1, S+1, A):

F := [seq(skew_product(D[i], x[i]*D[i], A) - P, i=1..N)]:

G := Basis(F, T):


In the next example we prove that k=0nbinomialn,k=2n.

A := shift_algebra([Sn,n], [Sk,k], polynom={n,k});



T := MonomialOrder(A, lexdeg([k], [n,Sn,Sk]));



G := Basis([(n+1-k)*Sn-(n+1),(k+1)*Sk-(n-k)], T);






See Also

Basis, MonomialOrder, Ore_algebra

Download Help Document

Was this information helpful?

Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam