@comment -*-texinfo-*-
@comment $Id: letterplace.doc,v 1.11 2009-04-08 17:02:52 Singular Exp $
@comment this file contains the mathematical background of Singular:Letterplace

@c The following directives are necessary for proper compilation
@c with emacs (C-c C-e C-r).  Please keep it as it is.  Since it
@c is wrapped in `@ignore' and `@end ignore' it does not harm `tex' or
@c `makeinfo' but is a great help in editing this file (emacs
@c ignores the `@ignore').
@ignore
%**start
@end ignore

@node LETTERPLACE,Non-commutative libraries,Super-commutative algebras,Non-commutative subsystem
@section LETTERPLACE
@cindex LETTERPLACE
@cindex Letterplace

This section describes mathematical notions and definitions used in
the experimental @sc{Letterplace} extension of @sc{Singular}.

For further details, please, refer to the forthcoming paper 
[LL]:  Roberto La Scala and Viktor Levandovskyy, "Letterplace ideals and non-commutative Groebner bases", 
submitted to the Journal of Symbolic Computation.

All algebras are assumed to be associative @math{K}-algebras for some field @math{K}.

@menu
* Free associative algebras::
* Groebner bases for two-sided ideals in free associative algebras::
* Letterplace correspondence::
* Example of use of Letterplace::
* Release notes::
@end menu


@c ---------------------------------------------------------------------------
@node Free associative algebras, Groebner bases for two-sided ideals in free associative algebras, , LETTERPLACE
@subsection Free associative algebras
@cindex free associative algebra, tensor algebra

Let @math{V} be a @math{K}-vector space, spanned by the symbols @math{x_1},@dots{},@math{x_n}.
A free associative algebra in @math{x_1},@dots{},@math{x_n} over @math{K}, denoted by @math{K}< @math{x_1},@dots{},@math{x_n} >
is also known as a tensor algebra @math{T(V)} of @math{V}. It is an infinite dimensional @math{K}-vector space, where one can take
as a basis the elements of the free monoid < @math{x_1},@dots{},@math{x_n} >. In other
words, the monomials of @math{K} < @math{x_1},@dots{},@math{x_n} > are the words
of finite length in the finite alphabet @{ @math{x_1},@dots{},@math{x_n} @}. The algebra @math{K}< @math{x_1},@dots{},@math{x_n} > is an
integral domain, which is not Noetherian for @math{n>1} (hence, a Groebner basis of a finitely generated ideal might
be infinite). The free associative algebra can be regarded as a graded algebra in a natural way.

Any finitely presented associative algebra is isomorphic to a
quotient of @math{K}< @math{x_1},@dots{},@math{x_n} > modulo a two-sided ideal.

@c ---------------------------------------------------------------------------
@node Groebner bases for two-sided ideals in free associative algebras, Letterplace correspondence, Free associative algebras, LETTERPLACE
@subsection Groebner bases for two-sided ideals in free associative algebras
@cindex Groebner bases in free associative algebras

@tex
We call a total ordering $<$ on the free monoid $X := \langle x_1,\dots,x_n \rangle$ a
\textbf{monomial ordering} if the following conditions hold:
@end tex
@ifinfo
We call a total ordering @math{<} on @math{X} := @math{< x_1},@dots{},@math{x_n >} a
@strong{monomial ordering} if the following conditions hold:
@end ifinfo

@itemize
@item
@ifinfo
< is a well-ordering on X, that is 1 < x forall x in X,
@end ifinfo
@tex
$<$ is a well-ordering on $X$, that is $ 1 < x$ $\forall x \in X$,
@end tex
@item
@ifinfo
forall p,q,s,t in X,  if s<t, then p . s . q < p . t . q,
@end ifinfo
@tex
$\forall p,q,s,t \in X$, if $s<t$, then $p\cdot s \cdot q< p\cdot t \cdot q$,
@end tex
@item
@ifinfo
forall p,q,s,t in X, if s=p . t . q and s<>t, then t<s.
@end ifinfo
@tex
$\forall p,q,s,t \in X$, if $s=p\cdot t \cdot q$ and $s\not=t$, then $t<s$.
@end tex
@end itemize

Hence the notions of a leading monomial and coefficients transfer to this situation.
@c as they usually do

We say that a monomial @math{v} divides monomial @math{w}, if there exist monomials
@tex
$p,s \in X$, such that $w = p \cdot w \cdot s$.
@end tex

@ifinfo
@math{p,s} in @math{X}, such that @math{w = p} .  @math{w} .  @math{s} .
@end ifinfo

@tex
For a subset $G \subset T := K\langle x_1,\dots,x_n \rangle$,
define a \textbf{leading ideal} of $G$ to be the two-sided ideal
$L(G) \; = \; {}_{T} \langle$ $\; \{lm(g) \;|\; g \in G\setminus\{0\} \}$ $\; \rangle_{T} \subseteq T$.

Let $<$ be a fixed monomial ordering on $T$.
We say that a subset $G \subset I$ is a \textbf{(two-sided) Groebner basis} for the ideal $I$ with respect to $<$, if $L(G) = L(I)$. That is $\forall f\in I$ there exists $g\in G$, such that
$lm(g)$ divides $lm(f)$.
@end tex


@ifinfo
For a subset @math{G} in @math{T} := @math{K< x_1},@dots{},@math{x_n >},
define a @strong{leading ideal} of @math{G} to be the two-sided ideal
@math{L(G)  =}  @{ @math{lm(g) | g} in @math{G}\@{0@} @} in @math{T}.

Let @math{<} be a fixed monomial ordering on @math{T}.
We say that a subset @math{G} of @math{I} is a (two-sided) Groebner basis for the ideal @math{I} with respect to @math{<}, if @math{L(G) = L(I)}. That is for all @math{f} from @math{I} there exists @math{g} in @math{G}, such that @math{lm(g)} divides @math{lm(f)}.
@end ifinfo

@c ---------------------------------------------------------------------------
@node Letterplace correspondence, Example of use of Letterplace, Groebner bases for two-sided ideals in free associative algebras,LETTERPLACE
@subsection Letterplace correspondence
@cindex letterplace correspondence

@tex
We utilize the ideas of Feynmann and Rota and encode
the monomials (words) of the free algebra
$x_{i_1} x_{i_2} \dots x_{i_m} \in K\langle x_1,\ldots,x_n \rangle$
via the double-indexed letterplace
(that is encoding the letter (= variable) and its place in the word) monomials
$x(i_1 | 1) x(i_2 | 2) \dots x(i_m | m) \in K[X\times N]$, where $X=\{x_1,\ldots,x_n\}$
and $N$ is the monoid of natural numbers, starting with 0 which cannot be used as a place.
@end tex
@ifinfo
We utilize the ideas of Feynmann and Rota and encode
the monomials (words) of the free algebra
@math{x_(i_1) x_(i_2)} @dots{} @math{x_(i_m)} in @math{K< x_1},@dots{},@math{x_n >}
via the double-indexed letterplace
(that is encoding the letter (= variable) and its place in the word) monomials
@math{x(i_1 | 1) x(i_2 | 2)} @dots{} @math{x(i_m | m)} in @math{K[X x N]}, where @math{X=} @{ @math{x_1},@dots{},@math{x_n} @}
and @math{N} is the monoid of natural numbers, starting with 0 which cannot be used as a place.
@end ifinfo

Note, that the latter letterplace algebra @math{K[X \times N]} is an infinitely generated commutative polynomial algebra.
Since @math{K<} @math{x_1},@dots{},@math{x_n} @math{>} is not Noetherian, it is common to perform the computations up to a given degree.
In that case the truncated letterplace algebra is (a) finitely generated (commutative ring).

Indeed, there is 1-to-1 correspondence between graded two-sided ideals
of a free algebra and so-called letterplace ideals in the letterplace algebra, see [LL].
All the computations take place in the latter algebra. A letterplace ideal
is a subset of a special vector space @math{V}, which is spanned by all letterplace
monomials. A letterplace monomial of length m is a monomial of
a letterplace algebra, such that its m places are exactly 1,2,@dots{},@math{m}.
That is a multilinearity with respect to places occur.

@c ---------------------------------------------------------------------------
@node Example of use of Letterplace, Release notes, Letterplace correspondence,LETTERPLACE
@subsection Example of use of @sc{Letterplace}

The input monomials must be given in a letterplace notation. We recommend
first to define a commutative ring @math{K[X]} in @sc{Singular} and equip it with
a degree well-ordering. Then, decide what should be the degree bound d and
run the procedure @code{makeLetterplaceRing(d)}
@c @code{freegbRing(d)} 
from the library @code{freegb.lib}.
This procedure creates a letterplace algebra with an induced ordering.
In this algebra, define an ideal @code{I} in the letterplace encoding and run the procedure
@code{system("freegb",I,d,n)}, where @math{n} is the number of variables of
the original commutative ring. The output is given in the letterplace encoding.

Note that one can also use @code{freeGBasis} from @code{freegb.lib} in order to simplify technicalities.

We illustrate this approach with the following example:

@smallexample
@c example
LIB "freegb.lib";
ring r = 0,(x,y,z),dp;
int d =4; // degree bound
def R = makeLetterplaceRing(d);
setring R;
ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
option(redSB); option(redTail);
ideal J = system("freegb",I,d,nvars(r));
J;
// ----------------------------------
  lp2lstr(J,r); // export an object called @code{@LN} to the ring r
  setring r;  // change to the ring r
  lst2str(@LN,1); // output the string presentation
@c example
@end smallexample

It is possible to convert the letterplace presentation of an ideal
to a list of strings with the help of procedures @code{lp2lstr}
and @code{lst2str} from the library @code{freegb.lib}. This is shown in the 
second part of the example above.

There are various conversion routines in the library @code{freegb.lib}.
We work further on implementing more algorithms for
non-commutative ideals and modules over free associative algebra.

@c ---------------------------------------------------------------------------
@node Release notes,  , Example of use of Letterplace,LETTERPLACE
@subsection Release notes of @sc{Letterplace}

With this functionality it is possible to compute two-sided Groebner basis
of a graded two-sided ideal (that is, generated by homogeneous polynomials)
in a free associative algebra up to a given degree.

Restrictions of the @sc{Letterplace} package:
@itemize
@item At the moment we provide stable implementation for the homogeneous input only,
computations with inhomogeneous ideals are under development. (There are no automatic checks.)
@item Since free algebra is not Noetherian, one has to define an explicit degree bound,
up to which a partial Groebner basis will be computed.
@item the options @code{option(redSB);option(redTail);} must be always activated
@item we advise to run the computations with the options  @code{option(prot);option(mem);}
in order to see the activity journal as well as the memory usage
@end itemize