Basis (details) - Maple Help

Computing non-commutative Groebner bases and Groebner bases for modules

 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 ${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}{,}{x}{}{y}{+}{z}{}{x}{+}{y}{}{z}{,}{x}{}{y}{}{z}{-}{1}\right]$ (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}{≔}\left[\left[\begin{array}{c}{x}{+}{y}{+}{z}\\ {1}\\ {0}\\ {0}\end{array}\right]{,}\left[\begin{array}{c}{x}{}{y}{+}{z}{}{x}{+}{y}{}{z}\\ {0}\\ {1}\\ {0}\end{array}\right]{,}\left[\begin{array}{c}{x}{}{y}{}{z}{-}{1}\\ {0}\\ {0}\\ {1}\end{array}\right]\right]$ (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}{≔}\left[{{s}}^{{3}}{}\left({x}{+}{y}{+}{z}\right){+}{{s}}^{{2}}{,}{{s}}^{{3}}{}\left({x}{}{y}{+}{z}{}{x}{+}{y}{}{z}\right){+}{s}{,}{{s}}^{{3}}{}\left({x}{}{y}{}{z}{-}{1}\right){+}{1}\right]$ (3)
 • 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]$ (4)
 > A := poly_algebra(x,y,z,s);
 ${A}{≔}{\mathrm{Ore_algebra}}$ (5)
 > T := MonomialOrder(A, lexdeg([s], [x,y,z]), {s});
 ${T}{≔}{\mathrm{monomial_order}}$ (6)
 > G := Groebner[Basis](M, T);
 ${G}{≔}\left[{s}{}{x}{}{y}{}{z}{-}{x}{}{y}{-}{z}{}{x}{-}{y}{}{z}{-}{s}{,}{{s}}^{{2}}{}{x}{}{y}{+}{{s}}^{{2}}{}{x}{}{z}{+}{{s}}^{{2}}{}{y}{}{z}{-}{s}{}{x}{-}{s}{}{y}{-}{s}{}{z}{,}{{s}}^{{2}}{}{x}{}{{z}}^{{2}}{+}{{s}}^{{2}}{}{y}{}{{z}}^{{2}}{-}{s}{}{x}{}{z}{-}{s}{}{y}{}{z}{-}{s}{}{{z}}^{{2}}{+}{{s}}^{{2}}{+}{x}{+}{y}{+}{z}{,}{{s}}^{{2}}{}{{y}}^{{2}}{}{{z}}^{{2}}{-}{s}{}{{y}}^{{2}}{}{z}{-}{s}{}{y}{}{{z}}^{{2}}{+}{{s}}^{{2}}{}{y}{+}{{s}}^{{2}}{}{z}{+}{{y}}^{{2}}{+}{y}{}{z}{+}{{z}}^{{2}}{-}{s}{,}{{s}}^{{3}}{}{x}{+}{{s}}^{{3}}{}{y}{+}{{s}}^{{3}}{}{z}{+}{{s}}^{{2}}{,}{{s}}^{{3}}{}{{y}}^{{2}}{+}{{s}}^{{3}}{}{y}{}{z}{+}{{s}}^{{3}}{}{{z}}^{{2}}{+}{{s}}^{{2}}{}{y}{+}{{s}}^{{2}}{}{z}{-}{s}{,}{{s}}^{{3}}{}{{z}}^{{3}}{+}{{s}}^{{2}}{}{{z}}^{{2}}{-}{{s}}^{{3}}{-}{s}{}{z}{+}{1}\right]$ (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);
 ${\mathrm{G1}}{≔}\left[{{s}}^{{3}}{}{x}{+}{{s}}^{{3}}{}{y}{+}{{s}}^{{3}}{}{z}{+}{{s}}^{{2}}{,}{{s}}^{{3}}{}{{y}}^{{2}}{+}{{s}}^{{3}}{}{y}{}{z}{+}{{s}}^{{3}}{}{{z}}^{{2}}{+}{{s}}^{{2}}{}{y}{+}{{s}}^{{2}}{}{z}{-}{s}{,}{{s}}^{{3}}{}{{z}}^{{3}}{+}{{s}}^{{2}}{}{{z}}^{{2}}{-}{{s}}^{{3}}{-}{s}{}{z}{+}{1}\right]$ (8)
 > [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}}{+}{y}{}{z}{+}{{z}}^{{2}}\\ {y}{+}{z}\\ {-1}\\ {0}\end{array}\right]{,}\left[\begin{array}{c}{{z}}^{{3}}{-}{1}\\ {{z}}^{{2}}\\ {-}{z}\\ {1}\end{array}\right]\right]$ (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}{≔}\left[\begin{array}{ccc}{1}& {0}& {0}\\ {y}{+}{z}& {-1}& {0}\\ {{z}}^{{2}}& {-}{z}& {1}\end{array}\right]$ (10)
 > GB := map(expand, convert(C.Vector(F), list));
 ${\mathrm{GB}}{≔}\left[{x}{+}{y}{+}{z}{,}{{y}}^{{2}}{+}{y}{}{z}{+}{{z}}^{{2}}{,}{{z}}^{{3}}{-}{1}\right]$ (11)
 > Groebner[Basis](F, tdeg(x,y,z));
 $\left[{x}{+}{y}{+}{z}{,}{{y}}^{{2}}{+}{y}{}{z}{+}{{z}}^{{2}}{,}{{z}}^{{3}}{-}{1}\right]$ (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}{≔}{\mathrm{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));
 ${\mathrm{tord}}{≔}{\mathrm{tdeg}}{}\left({{\mathrm{D}}}_{{1}}{,}{{\mathrm{D}}}_{{2}}{,}{{\mathrm{D}}}_{{3}}{,}{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}\right)$ (14)
 > T := MonomialOrder(A, tord);
 ${T}{≔}{\mathrm{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 ${\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)={2}^{n}$.
 > A := shift_algebra([Sn,n], [Sk,k], polynom={n,k});
 ${A}{≔}{\mathrm{Ore_algebra}}$ (16)
 > T := MonomialOrder(A, lexdeg([k], [n,Sn,Sk]));
 ${T}{≔}{\mathrm{monomial_order}}$ (17)
 > 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]$ (18)
 > map(factor,subs(Sk=1,remove(has,G,k)));
 $\left[\left({n}{+}{1}\right){}\left({\mathrm{Sn}}{-}{2}\right)\right]$ (19)