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

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

with(Groebner):

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

F:=x+y+z,xy+xz+yz,xyz1

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

M:=x+y+z100,xy+xz+yz010,xyz1001

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

M:=s3x+y+z+s2,s3xy+xz+yz+s,s3xyz1+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].

with(Ore_algebra);

Ore_to_DESol,Ore_to_RESol,Ore_to_diff,Ore_to_shift,annihilators,applyopr,diff_algebra,dual_algebra,dual_polynomial,poly_algebra,qshift_algebra,rand_skew_poly,reverse_algebra,reverse_polynomial,shift_algebra,skew_algebra,skew_elim,skew_gcdex,skew_pdiv,skew_power,skew_prem,skew_product

(4)

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

A:=Ore_algebra

(5)

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

T:=monomial_order

(6)

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

G:=sxyzxyxzyzs,s2xy+s2xz+s2yzsxsysz,s2xz2+s2yz2sxzsyzsz2+s2+x+y+z,s2y2z2sy2zsyz2+s2y+s2z+y2+yz+z2s,s3x+s3y+s3z+s2,s3y2+s3yz+s3z2+s2y+s2zs,s3z3+s2z2s3sz+1

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

G1:=s3x+s3y+s3z+s2,s3y2+s3yz+s3z2+s2y+s2zs,s3z3+s2z2s3sz+1

(8)

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

x+y+z100,y2+yz+z2y+z10,z31z2z1

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

C:=100y+z10z2z1

(10)

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

GB:=x+y+z,y2+yz+z2,z31

(11)

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

x+y+z,y2+yz+z2,z31

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

A:=Ore_algebra

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

tord:=tdegD1,D2,D3,x1,x2,x3

(14)

T := MonomialOrder(A, tord);

T:=monomial_order

(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 k=0nbinomialn,k=2n.

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

A:=Ore_algebra

(16)

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

T:=monomial_order

(17)

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

G:=SkSnn+SkSnSknSkn1,Skk+Sk+kn,SnkSnnSn+n+1

(18)

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

n+1Sn2

(19)

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