@comment -*-texinfo-*-
@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,Graded commutative algebras (SCA),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 papers 

[LL09]:  Roberto La Scala and Viktor Levandovskyy, "Letterplace ideals and non-commutative Groebner bases", Journal of Symbolic Computation, Volume 44, Issue 10, October 2009, Pages 1374-1393. 

[LL10]: Roberto La Scala and Viktor Levandovskyy, "Skew polynomial rings, Groebner bases and the letterplace embedding of the free associative algebra", @url{http://arxiv.org/abs/1009.4152}.

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} >, identifying the identity element (the empty word) with the @math{1} in @math{K}. 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 two-sided 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$ (where $1$ is identified with the identity element) 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, x != 1, 
@end ifinfo
@tex
$<$ is a well-ordering on $X$, that is $ 1 < x$ $\forall x \in X \setminus \{1\}$,
@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 like a leading monomial and a leading coefficient 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 v \cdot s$.
@end tex

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

In other words @math{v} is a proper subword of @math{w}.

@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\setminus\{0\}$ 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}\@{0@} 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

Our work as well as the name letteplace has been inspired by the work of Rota.

@tex
Already Feynman and Rota encoded 
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
Already Feynman and Rota encoded
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 letterplace algebra @math{K[X \times N]} is an infinitely generated commutative polynomial @math{K}-algebra.
Since @math{K<} @math{x_1},@dots{},@math{x_n} @math{>} is not Noetherian, it is common to perform the computations with modules up to a given degree.
In that case the truncated letterplace algebra is finitely generated commutative ring.

In [LL09] a natural shifting on letterplace polynomials was introduced and used. 
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 [LL09] for details.
All the computations take place in the letterplace algebra. 

A letterplace monomial of length @math{m} is a monomial of a letterplace algebra, such that its @math{m} places are exactly 1,2,@dots{},@math{m}. In particular, such monomials are multilinear with respect to places. A letterplace polynomial is an element of the @math{K}-vector space, spanned by letterplace monomials. A letterplace ideal is generated by letterplace polynomials subject to two kind of operations: 

the 
@tex
$K$-algebra operations of the letterplace algebra and simultaneous shifting of places by any natural number $n$.
@end tex
@ifinfo
@math{K}-algebra operations of the letterplace algebra and simultaneous shifting of places by any natural number @math{n}.
@end ifinfo

@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 (though we recommend to 
get used to the letterplace notation, the procedure @code{freeGBasis } from the @ref{freegb_lib}
provides an alternative). 

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 @ref{freegb_lib}.
This procedure creates a letterplace algebra with an ordering, induced from the given commutative ring @math{K[X]}.
In this algebra, define an ideal @code{I} as a list of polynomials in the letterplace encoding 
and run the procedure @code{letplaceGBasis}. The output is given in the letterplace encoding as well.

Alternatively, one can run the procedure @code{system("freegb",I,d,n)}, where @math{n} is the number of variables of the original commutative ring which does the same computations as @code{letplaceGBasis}. 

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 @ref{freegb_lib}. This is shown in the second part of the example below.

Yet another anternative is to use the procedure @code{freeGBasis} from @ref{freegb_lib} in order to use a different encoding for polynomials in free algebra. No conversion tools are needed in that case.

We illustrate the 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 = letplaceGBasis(I);
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

There are various conversion routines in the library @code{freegb_lib} (see @ref{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, an ideal, generated by homogeneous polynomials)
in a free associative algebra up to a given degree. It is assumed, that each variable
has degree $1$.

Restrictions of the @sc{Letterplace} package:
@itemize
@item At the moment we provide stable implementation for the homogeneous input only,
computations with quasi-homogeneous and general 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. Note, that @code{makeLetterplaceRing} procedure
stores the bound in the structure of the ring it creates. Thus running @code{letplaceGBasis} in such a 
ring does not require the degree bound in its argument.
@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

Further functionality is provided in the libraries for the @sc{Letterpace} subsystem.

In the @ref{freegb_lib} one finds e.g. letterplace arithmetics procedures, conversion tools,
procedures for creating some common ideals of relations as well as the normal form 
procedure, providing effective ideal memnership test.


The @ref{fpadim_lib} contains procedures for computations with vector space basis 
of a factor algebra including finiteness check and dimension computation.