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]

To represent modules over the polynomial ring K[x1,...,xn] Maple uses placeholder (or dummy) variables U = {u1,...,um}. Multiplication by the $U_i$ 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≔\left[x+y+z\,xy+zx+yz\,xyz-1\right]$

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≔\left[\left[\begin{array}{c}x+y+z\\ 1\\ 0\\ 0\end{array}\right]\,\left[\begin{array}{c}xy+zx+yz\\ 0\\ 1\\ 0\end{array}\right]\,\left[\begin{array}{c}xyz-1\\ 0\\ 0\\ 1\end{array}\right]\right]$

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≔\left[s^3\left(x+y+z\right)+s^2\,s^3\left(xy+zx+yz\right)+s\,s^3\left(xyz-1\right)+1\right]$

Next we must construct an algebra on $\left\{s\,x\,y\,z\right\}$ 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);

$\left[\mathrm{Ore\_to\_DESol}\,\mathrm{Ore\_to\_RESol}\,\mathrm{Ore\_to\_diff}\,\mathrm{Ore\_to\_shift}\,\mathrm{annihilators}\,\mathrm{applyopr}\,\mathrm{diff\_algebra}\,\mathrm{dual\_algebra}\,\mathrm{dual\_polynomial}\,\mathrm{poly\_algebra}\,\mathrm{qshift\_algebra}\,\mathrm{rand\_skew\_poly}\,\mathrm{reverse\_algebra}\,\mathrm{reverse\_polynomial}\,\mathrm{shift\_algebra}\,\mathrm{skew\_algebra}\,\mathrm{skew\_elim}\,\mathrm{skew\_gcdex}\,\mathrm{skew\_pdiv}\,\mathrm{skew\_power}\,\mathrm{skew\_prem}\,\mathrm{skew\_product}\right]$

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

$A≔\mathrm{Ore\_algebra}$

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

$T≔\mathrm{monomial\_order}$

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

$G≔\left[sxyz-xy-zx-yz-s\,s^{2}xy+s^{2}xz+s^{2}yz-sx-sy-sz\,s^{2}x{z}^2+s^{2}y{z}^2-sxz-syz-s{z}^2+s^2+x+y+z\,s^2{y}^2{z}^2-s{y}^{2}z-sy{z}^2+s^{2}y+s^{2}z+y^2+yz+z^2-s\,s^{3}x+s^{3}y+s^{3}z+s^2\,s^3{y}^2+s^{3}yz+s^3{z}^2+s^{2}y+s^{2}z-s\,s^3{z}^3+s^2{z}^2-s^3-sz+1\right]$

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

$\mathrm{G1}≔\left[s^{3}x+s^{3}y+s^{3}z+s^2\,s^3{y}^2+s^{3}yz+s^3{z}^2+s^{2}y+s^{2}z-s\,s^3{z}^3+s^2{z}^2-s^3-sz+1\right]$

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

$\left[\left[\begin{array}{c}x+y+z\\ 1\\ 0\\ 0\end{array}\right]\,\left[\begin{array}{c}{y}^2+yz+z^2\\ y+z\\ \mathrm{-1}\\ 0\end{array}\right]\,\left[\begin{array}{c}{z}^3-1\\ z^2\\ -z\\ 1\end{array}\right]\right]$

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≔\left[\begin{array}{ccc}1& 0& 0\\ y+z& \mathrm{-1}& 0\\ z^2& -z& 1\end{array}\right]$

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

$\mathrm{GB}≔\left[x+y+z\,y^2+yz+z^2\,z^3-1\right]$

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

$\left[x+y+z\,y^2+yz+z^2\,z^3-1\right]$

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≔\mathrm{Ore\_algebra}$

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

$\mathrm{tord}≔\mathrm{tdeg}\left({\mathrm{D}}_1\,{\mathrm{D}}_2\,{\mathrm{D}}_3\,x_1\,x_2\,x_3\right)$

T := MonomialOrder(A, tord);

$T≔\mathrm{monomial\_order}$

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 $\sum _{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$.

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

$A≔\mathrm{Ore\_algebra}$

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

$T≔\mathrm{monomial\_order}$

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

$G≔\left[\mathrm{Sk}\mathrm{Sn}n+\mathrm{Sk}\mathrm{Sn}-\mathrm{Sk}n-\mathrm{Sk}-n-1\,\mathrm{Sk}k+\mathrm{Sk}+k-n\,\mathrm{Sn}k-\mathrm{Sn}n-\mathrm{Sn}+n+1\right]$

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

$\left[\left(n+1\right)\left(\mathrm{Sn}-2\right)\right]$