|
7.7.1 Examples of use of LETTERPLACE
First, define a commutative ring
in SINGULAR, equipped with a monomial well-ordering
and call it, say, r .
Then, decide what should be the degree (length) bound
,
that is how long may the words (monomials in the free algebra) become
and run the procedure freeAlgebra(r, d) .
In the case you wish to work with subbimodules of the free bimodule of rank
,
use freeAlgebra(r, d, k) instead of the previous.
The freeAlgebra . procedure creates free algebra
resp. the free bimodule
of rank
over
subject to a monomial (module) ordering, corresponding to
the one in the original commutative ring
, see Monomial orderings on free algebras.
Polynomial (vector) arithmetics in this
-algebra is the usual one: +,-,*,^ while
of course, x*y and y*x are different monomials while x*7=7*x .
Let us define an ideal I as a list of polynomials in the
free algebra and run, for example, twostd (see twostd (letterplace)).
The answer is a two-sided Groebner basis J of the two-sided ideal
up to the length bound d .
Then, we want to compute the following:
1. The two-sided normal form of xyzy with respect to J
using the function reduce (see reduce (letterplace)).
2. By introducing a factor algebra
of type qring ,
and demonstrate the functions reduce and rightstd (for right
Groebner bases) over the factor algebra.
3. By creating the free R -bimodule of rank 8, we demonstrate how
embeddins works with imap and also, how to express a subbimodule
(or a single element) in terms of bimodule generators with lift .
In other words, we compute and compare presentations of a polynomials with respect to
the original generating set of ideal and with respect to a Groebner basis.
4. In the same free R -bimodule we will compute the module of
bisyzygies of J and do some syzygy tests.
5. We demonstrate the bimodule membership problem: a boolean answer via NF
and the certified version (with a Groebner presentation) via lift .
6. We show how elimination of module components works for bimodules.
We illustrate the approach with the following example:
| //******* Part 1 *******//
LIB "freegb.lib";
ring r = 0,(x,y,z),dp; // the ordering on the free algebra will be degree right lex
ring R = freeAlgebra(r, 5); // 5 the is degree (length) bound;
ideal I = x*y + y*z, x*x + x*y - z; // define an ideal via the set of polynomials
ideal J = twostd(I);
J; // as we see, with respect to the current ordering this Groebner basis
==> J[1]=x*y+y*z
==> J[2]=x*x-y*z-z
==> J[3]=y*z*y-y*z*z+z*y
==> J[4]=y*z*x+y*z*z+z*x-x*z
==> J[5]=y*z*z*y-y*z*z*z-x*z*y
==> J[6]=y*z*z*x+y*z*z*z-x*z*x+y*z*z+z*z
==> J[7]=y*z*z*z*y-y*z*z*z*z+y*z*z*z+x*z*y+z*z*y
==> J[8]=y*z*z*z*x+y*z*z*z*z+x*z*x+z*z*x-x*z*z-y*z*z-z*z
// tends to be infinite. Increasing the bound and recomputing helps to check it.
poly p = reduce(x*y*z*y,J);
p; // since p!=0, x*y*z*y is not contained in J up to length 5
==> -y*z*z*z-x*z*y
// however this does not imply a definite answer on whether p is in J
poly q = x*(y+1)*z*y-x*y*z^2;
reduce(q, J); // 0, thus q is in J
==> 0
//******* Part 2 *******//
qring Q = J; // J is a Groebner basis, computed above
poly p = reduce(x*x, twostd(0)); // the canonical representative of x*x in Q
p;
==> y*z+z
rightstd(ideal(p)); // right Groebner basis of the right ideal, generated by p in Q
==> _[1]=z*z
==> _[2]=y*z+z
==> _[3]=x*z
//******* Part 3 *******//
setring r;
ring R8 = freeAlgebra(r, 5, 8); // 5 the is length bound; 8 is the rank of the free bimodule
ideal J = imap(R, J); // we map J identically from R (of rank 1)
J = twostd(J);
poly q = imap(R, q);
NF(q, J); // NF is an alias to reduce, we have rechecked that q is in J
==> 0
matrix L = lift(J, q); // creates the presentation for q in terms of J
// since J is a Groebner basis, this is a Groebner presentation of q
print(transpose(matrix(L))); // J has 8 generators and these are the needed coefficients
==> ncgen(1)*z*y-ncgen(1)*z*z,0,0,0,-ncgen(5),0,0,0
// here, the generators of the free bimodule are ncgen(1)*gen(1), ... , ncgen(8)*gen(8)
// the output means, that substituting ncgen(i) by the i-th generator of J, we get q
J[1]*z*y - J[1]*z*z - J[5] - q; // 0, so this is the seeked expression of q
==> 0
testLift(J,L); // recovers q from the lift matrix
==> _[1]=x*y*z*y-x*y*z*z+x*z*y
// Let us compare now this nice Groebner presentation with the one
// obtained from the original set of generators
ideal I = imap(R,I); // note: I is not a Groebner basis of itself
matrix M = lift(I, q); // creates the presentation for q in terms of I
M; // presentation is longer and more complicated than the one in L
==> M[1,1]=-ncgen(1)*x*y+x*ncgen(1)*y-ncgen(1)*y*z-x*ncgen(1)*z+y*z*ncgen(1)+\
z*ncgen(1)
==> M[2,1]=ncgen(2)*x*y-x*ncgen(2)*y+ncgen(2)*y*z
testLift(I,M); // a routine test to ensure that indeed we recover q
==> _[1]=x*y*z*y-x*y*z*z+x*z*y
//******* Part 4 *******//
// Let us compute the module of bisyzygies of J and analyze it
module S = syz(J); size(S); // 18
==> 18
S[6]; // consider, for example, this element
==> ncgen(1)*z*y*gen(1)-ncgen(1)*z*z*gen(1)+y*z*ncgen(1)*gen(1)-ncgen(4)*y*ge\
n(4)-ncgen(3)*z*gen(3)+z*ncgen(1)*gen(1)-x*ncgen(3)*gen(3)
// plugging the i-th generator of J instead of ncgen(i), we obtain a bisyzygy:
J[1]*z*y - J[1]*z*z - x*J[3] - J[5]; //0
==> 0
module S2 = S[6..8]; // pick just three generators
testSyz(J,S2); // tests the bisyzygy property for the generators
==> _[1]=0
==> _[2]=0
==> _[3]=0
//******* Part 5 *******//
option(redSB); option(redTail); // to compute minimal and tail-reduced bases
module GS = twostd(S); size(GS); // 30
==> 30
// let us construct a vector, belonging to GS:
vector v = GS[11]*y - x*GS[7] + z*GS[3]*z;
print(v);
==> [-x*ncgen(1)*x*y-x*ncgen(1)*y*z+x*x*y*ncgen(1)-x*z*ncgen(1),y*z*z*ncgen(2\
)*y+z*y*z*ncgen(2)*z-x*z*ncgen(2)*y+z*z*ncgen(2)*z,z*ncgen(3)*z*z+x*ncgen\
(3)*z,-z*ncgen(4)*x*z+x*ncgen(4)*y,ncgen(5)*z*y-x*ncgen(5),-ncgen(6)*x*y+\
z*ncgen(6)*z+ncgen(6)*y,0,ncgen(8)*y]
NF(v, GS); // 0, by the construction
==> 0
// now we wish to compute the expression of v via GS
ring r3 = 0,(x,y,z),(c,dp);
ring R30 = freeAlgebra(r3,5,30);
module GS = imap(R8,GS);
vector v = imap(R8,v);
matrix L = lift(GS,v); // via printing we see only three components involved:
L[3,1]; // =z*ncgen(3)*z, as well as
==> z*ncgen(3)*z
L[7,1]; // =-x*ncgen(7) and
==> -x*ncgen(7)
L[11,1]; // =ncgen(11)*y
==> ncgen(11)*y
//******* Part 6 *******//
// Notice, that the module ordering is (c,dp): it is a position-over-term ordering
// which eliminates module components in an descending way.
GS = GS[1..5]; // consider just first five syzygies, for a smaller example
GS = twostd(GS); // a nice finite Groebner basis
print(matrix(GS)); // shows the structure
==> 0, 0, 0, 0, 0, _[1,6], _[1,7], _[1,8],
==> 0, _[2,2], _[2,3],_[2,4],_[2,5],_[2,6], _[2,7], 0,
==> _[3,1], _[3,2], _[3,3],_[3,4],_[3,5],-ncgen(3),0, _[3,8],
==> 0, _[4,2], _[4,3],_[4,4],_[4,5],-ncgen(4),-ncgen(4),_[4,8],
==> ncgen(5),0, 0, _[5,4],_[5,5],0, 0, ncgen(5),
==> 0, ncgen(6),0, _[6,4],_[6,5],0, 0, 0,
==> ncgen(7),0, 0, 0, _[7,5],0, 0, 0
// As we can see, intersections of the subbimodule GS with the free bimodules
// generated by all but first resp. all but first two bimodule generators
// are not empty and given by vectors having zero in the first resp.
// in the first two components.
|
See Functions (letterplace) for the list of all available kernel functions.
There are various conversion routines in the library freegb_lib (see freegb_lib).
Many algebras are predefined in the library fpalgebras_lib (see fpalgebras_lib).
Important ring-theoretic properties can be established with the help of the library fpaprops_lib (see fpaprops_lib),
while K-dimension and monomial bases and Hilbert data - with the help of the library fpadim_lib (see fpadim_lib).
We work further on implementing more algorithms for non-commutative ideals and modules over free associative algebra.
|