\documentstyle[11pt,reduce]{article}
\title{NCPOLY: Computation in non--commutative polynomial ideals}
\date{}
\author{
Herbert Melenk\\[0.05in]
Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\
Takustrasse 7 \\
D--14195 Berlin -- Dahlem \\
Germany \\[0.05in]
E--mail: melenk@zib.de \\[0.1in]
Joachim Apel\\[0.05in]
Institut f\"ur Informatik \\[0.05in]
Universit\"at Leipzig \\[0.05in]
Augustusplatz 10--11\\[0.05in]
D--04109 Leipzig \\[0.05in]
Germany \\[0.05in]
E--mail: apel@informatik.uni--leipzig.de \\[0.05in]
}
\begin{document}
\maketitle
\index{Groebner Bases}
\section{Introduction}
{\small REDUCE} supports a very general mechanism for computing
with objects under a non--commutative multiplication, where
commutator relations must be introduced explicitly by rule
sets when needed. The package {\bf NCPOLY} allows you to
set up automatically a consistent environment for computing in an algebra
where the non--commutativity is defined by Lie-bracket commutators.
The package uses the {\small REDUCE} {\bf noncom}
mechanism for elementary polynomial arithmetic; the commutator
rules are automatically computed from the Lie brackets.
You can perform polynomial arithmetic directly, including
{\bf division} and {\bf factorization}.
Additionally {\bf NCPOLY} supports computations in a one sided ideal (left or right),
especially one sided {\bf Gr\"obner} bases and {\bf polynomial reduction}.
\section{Setup, Cleanup}
Before the computations can start the environment for a
non--commutative computation must be defined by a
call to {\bf nc\_setup}:
\begin{verbatim}
nc_setup(<vars>[,<comms>][,<dir>]);
\end{verbatim}
where
$<vars>$ is a list of variables; these must include the
non--commutative quantities.
$<comms>$ is a list of equations \verb&<u>*<v> - <v>*<u>=<rh>&
where $<u>$ and $<v>$ are members of $<vars>$, and $<rh>$ is
a polynomial.
$<dir>$ is either $left$ or $right$ selecting a left or a
right one sided ideal. The initial direction is $left$.
{\bf nc\_setup} generates from $<comms>$ the necessary
rules to support an algebra where all monomials are
ordered corresponding to the given variable sequence.
All pairs of variables which are not explicitly covered in
the commutator set are considered as commutative and the
corresponding rules are also activated.
The second parameter in {\bf nc\_setup} may be
omitted if the operator is called for the second time,
e.g. with a reordered variable sequence. In such a case
the last commutator set is used again.
Remarks: \begin{itemize}
\item The variables need not be declared {\bf noncom} -
{\bf nc\_setup} performs all necessary declarations.
\item The variables need not be formal operator expressions;
{\bf nc\_setup} encapsulates a variable $x$ internally
as \verb+nc!*(!_x)+ expressions anyway where the operator $nc!*$
keeps the noncom property.
\item The commands {\bf order} and {\bf korder} should be avoided
because {\bf nc\_setup} sets these such that the computation
results are printed in the correct term order.
\end{itemize}
Example:
\begin {verbatim}
nc_setup({KK,NN,k,n},
{NN*n-n*NN= NN, KK*k-k*KK= KK});
NN*n; -> NN*n
n*NN; -> NN*n - NN
nc_setup({k,n,KK,NN});
NN*n - NN -> n*NN;
\end{verbatim}
Here $KK,NN,k,n$ are non--commutative variables where
the commutators are described as $[NN,n]=NN$, $[KK,k]=KK$.
The current term order must be compatible with the commutators:
the product $<u>*<v>$ must precede all terms on the right hand
side $<rh>$ under the current term order. Consequently
\begin{itemize}
\item the maximal degree of $<u>$ or $<v>$ in $<rh>$ is 1,
\item in a total degree ordering the total degree of $<rh>$ may be
not higher than 1,
\item in an elimination degree order (e.g. $lex$) all variables in
$<rh>$ must be below the minimum of $<u>$ and $<v>$.
\item If $<rh>$ does not contain any variables or has at most $<u>$ or
$<v>$, any term order can be selected.
\end{itemize}
If you want to use the non--commutative variables or results from
non--commutative computations later in commutative operations
it might be necessary to switch off the non--commutative
evaluation mode because not
all operators in REDUCE are prepared for that environment. In
such a case use the command
\begin{verbatim}
nc_cleanup;
\end{verbatim}
without parameters. It removes all internal rules and definitions
which {\bf nc\_setup} had introduced. To reactive non--commutative
call {\bf nc\_setup} again.
\section{Left and right ideals}
A (polynomial) left ideal $L$ is defined by the axioms
$u \in L, v \in L \Longrightarrow u+v \in L$
$u \in L \Longrightarrow k*u \in L$ for an arbitrary polynomial $k$
where ``*'' is the non--commutative multiplication. Correspondingly,
a right ideal $R$ is defined by
$u \in R, v \in R \Longrightarrow u+v \in R$
$u \in R \Longrightarrow u*k \in R$ for an arbitrary polynomial $k$
\section{Gr\"obner bases}
When a non--commutative environment has been set up
by {\bf nc\_setup}, a basis for a left or right polynomial ideal
can be transformed into a Gr\"obner basis by the operator
{\bf nc\_groebner}:
\begin{verbatim}
nc_groebner(<plist>);
\end{verbatim}
Note that the variable set and variable sequence must be
defined before in the {\bf nc\_setup} call. The term order
for the Gr\"obner calculation can be set by using the
{\bf torder} declaration. The internal steps of the
Gr\"obner calculation can be watched by setting the
switches {\bf trgroeb} (=list all internal basis polynomials)
or {\bf trgroebs} (=list additionally the $S$-polynomials)
\footnote{The command \verb+lisp(!*trgroebfull:=t);+ causes additionally
all elementary polynomial operations to be printed.}.
For details about {\bf torder}, {\bf trgroeb} and {\bf trgroebs}
see the {\bf {\small REDUCE} GROEBNER} manual.
\begin{verbatim}
2: nc_setup({k,n,NN,KK},{NN*n-n*NN=NN,KK*k-k*KK=KK},left);
3: p1 := (n-k+1)*NN - (n+1);
p1 := - k*nn + n*nn - n + nn - 1
4: p2 := (k+1)*KK -(n-k);
p2 := k*kk + k - n + kk
5: nc_groebner ({p1,p2});
{k*nn - n*nn + n - nn + 1,
k*kk + k - n + kk,
n*nn*kk - n*kk - n + nn*kk - kk - 1}
\end{verbatim}
Important: Do not use the operators of the GROEBNER
package directly as they would not consider the non--commutative
multiplication.
\section{Left or right polynomial division}
The operator {\bf nc\_divide} computes the one sided quotient and remainder of
two polynomials:
\begin{verbatim}
nc_divide(<p1>,<p2>);
\end{verbatim}
The result is a list with quotient and remainder.
The division is performed as a pseudo--division, multiplying
$<p1>$ by coefficients if necessary. The result $\{<q>,<r>\}$
is defined by the relation
$<c>*<p1>=<q>*<p2> + <r>$ for direction $left$ and
$<c>*<p1>=<p2>*<q> + <r>$ for direction $right$,
where $<c>$ is an expression that does not contain any of the
ideal variables, and the leading term of $<r>$ is lower than
the leading term of $<p2>$ according to the actual term order.
\section{Left or right polynomial reduction}
For the computation of the one sided remainder of a polynomial
modulo a given set of other polynomials the operator
{\bf nc\_preduce} may be used:
\begin{verbatim}
nc_preduce(<polynomial>,<plist>);
\end{verbatim}
The result of the reduction is unique (canonical) if
and only if $<plist>$ is a one sided Gr\"obner basis.
Then the computation is at the same time an ideal
membership test: if the result is zero, the
polynomial is member of the ideal, otherwise not.
\section{Factorization}
\subsection{Technique}
Polynomials in a non--commutative ring cannot be factored
using the ordinary {\bf factorize} command of {\small REDUCE}.
Instead one of the operators of this section must be used:
\begin{verbatim}
nc_factorize(<polynomial>);
\end{verbatim}
The result is a list of factors of $<polynomial>$. A list
with the input expression is returned if it is irreducible.
As non--commutative factorization is not unique, there is
an additional operator which computes all possible factorizations
\begin{verbatim}
nc_factorize_all(<polynomial>);
\end{verbatim}
The result is a list of factor decompositions of $<polynomial>$.
If there are no factors at all the result list has only one
member which is a list containing the input polynomial.
\subsection{Control of the factorization}
In contrast to factoring in commutative polynomial rings, the non--commutative
factorization is rather time consuming. Therefore two additional
operators allow you to reduce the amount of computing time when
you look only for isolated factors in special context, e.g. factors
with a limited degree or factors which contain only explicitly
specified variables:
\begin{verbatim}
left_factor(<polynomial>[,<deg>[,<vars>]])
right_factor(<polynomial>[,<deg>[,<vars>]])
left_factors(<polynomial>[,<deg>[,<vars>]])
right_factors(<polynomial>[,<deg>[,<vars>]])
\end{verbatim}
where $<polynomial>$ is the form under investigation,
$<vars>$ is an optional list of variables which must appear in the
factor, and $<deg>$
is an optional integer degree bound for the total degree of the
factor, a zero for an unbounded search, or a monomial
(product of powers of the variables) where each exponent
is an individual degree bound for its base variable; unmentioned
variables are allowed in arbitrary degree. The operators
$*\_factor$ stop when they have found one factor, while
the operators $*\_factors$ select all one--sided factors
within the given range. If there is no factor of the
desired type, an empty list is returned by $*\_factors$
while the routines $*\_factor$ return the input polynomial.
\subsection{Time of the factorization}
The share variable $nc\_factor\_time$ sets an upper limit
for the time to be spent for a call to the non--commutative
factorizer. If the value is a positive integer, a
factorization is terminated with an error message as soon
as the time limit is reached. The time units are milliseconds.
\subsection{Usage of SOLVE}
The factorizer internally uses $solve$, which is controlled
by the \REDUCE \ switch $varopt$. This switch (which per default
is set $on$) allows, to reorder the variable sequence, which is
favourable for the normal system. It should be avoided to set $varopt$
$off$, when using the non--commutative factorizer, unless very small
polynomials are used.
\section{Output of expressions}
It is often desirable to have the commutative parts (coefficients)
in a non--commutative operation condensed by factorization. The operator
\begin{verbatim}
nc_compact(<polynomial>)
\end{verbatim}
collects the coefficients to the powers of the lowest possible
non-commutative variable.
\begin{verbatim}
load ncpoly;
nc_setup({n,NN},{NN*n-n*NN=NN})$
p1 := n**4 + n**2*nn + 4*n**2 + 4*n*nn + 4*nn + 4;
4 2 2
p1 := n + n *nn + 4*n + 4*n*nn + 4*nn + 4
nc_compact p1;
2 2 2
(n + 2) + (n + 2) *nn
\end{verbatim}
\end{document}