Home Online Manual
Top
Back: LETTERPLACE
Forward: Examples of use of Letterplace over Z
FastBack:
FastForward:
Up: Singular Manual
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

7.7.1 Examples of use of LETTERPLACE

First, define a commutative ring $K[X]$ in SINGULAR, equipped with a monomial well-ordering and call it, say, r.

Then, decide what should be the degree (length) bound $d$, 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 $k$, use freeAlgebra(r, d, k) instead of the previous.

The freeAlgebra. procedure creates free algebra $K<X>$ resp. the free bimodule of rank $k$ over $K<X>$ subject to a monomial (module) ordering, corresponding to the one in the original commutative ring $K[X]$, see Monomial orderings on free algebras.

Polynomial (vector) arithmetics in this $K$-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 $I$

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 $K<x,y,z>/J$ 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
==> // ** possible OVERFLOW in subst, max exponent is 3
==> // ** possible OVERFLOW in subst, max exponent is 3
==> // ** possible OVERFLOW in subst, max exponent is 3
==> _[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.