Basis (details) - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


Computing non-commutative Groebner bases and Groebner bases for modules

 

Calling Sequence

Parameters

Description

Groebner Bases for Commutative Modules

Non-Commutative Groebner Bases

Calling Sequence

Basis(F, T, opts)

MonomialOrder(A, tord, U)

Parameters

F

-

list or set of polynomials

T

-

MonomialOrder

opts

-

optional arguments of the form keyword=value

A

-

commutative algebra of polynomials, Weyl algebra, or Ore algebra

tord

-

ShortMonomialOrder

U

-

(optional) module placeholder variables

Description

• 

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  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.

with(Groebner):

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

(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)];

(2)
• 

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)];

(3)
• 

Next we must construct an algebra on  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].

with(Ore_algebra);

(4)

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

(5)

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

(6)

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

(7)
• 

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);

(8)

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

(9)
• 

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)]);

(10)

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

(11)

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

(12)

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.

with(Ore_algebra):

N := 3:

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

(13)
• 

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));

(14)

T := MonomialOrder(A, tord);

(15)
• 

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 .

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

(16)

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

(17)

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

(18)

map(factor,subs(Sk=1,remove(has,G,k)));

(19)

See Also

Basis

MonomialOrder

Ore_algebra

 


Download Help Document