reduce-historical/r38/doc/manual2/ncpoly.tex

\chapter[NCPOLY: Ideals in non--comm case]%
{NCPOLY: Non--commutative polynomial ideals}
\label{NCPOLY}
\typeout{{NCPOLY: Non--commutative polynomial ideals}}

{\footnotesize
\begin{center}
Herbert Melenk\\
Konrad--Zuse--Zentrum f\"ur Informationstechnik Berlin \\
Takustra\"se 7 \\
D--14195 Berlin--Dahlem, Germany \\[0.05in]
e--mail:  melenk@zib.de \\[0.1in]
Joachim Apel\\
Institut f\"ur Informatik, Universit\"at Leipzig \\
Augustusplatz 10--11\\
D--04109 Leipzig, Germany \\[0.05in]
e--mail:  apel@informatik.uni--leipzig.de
\end{center}
}
\ttindex{NCPOLY}\index{Groebner Bases}

\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 the user 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 \REDUCE\
{\bf noncom} mechanism for elementary polynomial arithmetic; the
commutator rules are automatically computed from the Lie brackets.
Polynomial arithmetic may be performed directly, including {\bf
division} and {\bf factorisation}.  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 {\tt nc\_setup}:\ttindex{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$.

{\tt 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 {\tt nc\_setup} may be
omitted if the operator is called for the second time,
{\em 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 ({\em 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}

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\ttindex{nc\_cleanup}
\begin{verbatim}
    nc_cleanup;
\end{verbatim}
without parameters. It removes all internal rules and definitions
which {\tt nc\_setup} had introduced. To reactive non--commutative
call {\tt 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 {\tt nc\_setup}, a basis for a left or right polynomial ideal
can be transformed into a Gr\"obner basis by the operator
{\tt nc\_groebner}\ttindex{nc\_groebner}
\begin{verbatim}
   nc_groebner(<plist>);
\end{verbatim}
Note that the variable set and variable sequence must be
defined before in the {\tt nc\_setup} call. The term order
for the Gr\"obner calculation can be set by using the
{\tt torder} declaration.

For details about {\tt torder}
see the {\bf \REDUCE\ GROEBNER} manual, or chapter~\ref{GROEBNER}.
\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 {\tt nc\_divide}\ttindex{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
{\tt nc\_preduce} may be used:\ttindex{nc\_preduce}
\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{Factorisation}

Polynomials in a non--commutative ring cannot be factored
using the ordinary {\tt factorize} command of \REDUCE.
Instead one of the operators of this section must be
used:\ttindex{nc\_factorize}
\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 factorisation is not unique, there is
an additional operator which computes all possible
factorisations\ttindex{nc\_factorize\_all}
\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.

\section{Output of expressions}

It is often desirable to have the commutative parts (coefficients)
in a non--commutative operation condensed by factorisation. The
operator\ttindex{nc\_compact}
\begin{verbatim}
   nc_compact(<polynomial>)
\end{verbatim}
collects the coefficients to the powers of the lowest possible
non-commutative variable.
\begin{verbatim}
load_package 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}