%Date: Thu, 24 Feb 94 10:51:56 PST
%From: jwavrik@math.UCSD.EDU (John Wavrik)

 
\subsection{Comments on Gr\"obner Bases}

{\bf DELETE ?? - Most of this is used elsewhare??}
 
   The need for Gr\"obner Bases arises because a given set of relations 
(or replacement rules) may not be adequate for simplifying all 
expressions involving the variables. We have seen in Example 
\ref{example:1pt7} that 
a basic set of rules involving $x$, $x^{-1}$ and $(1-x)^{-1}$ could not detect 
that the simple expression (\ref{eq:1pt9}) should simplify to zero. This example 
is typical.
 
   The Gr\"obner Basis Algorithm provides a systematic way to add new 
relations to obtain a ``complete" set. The new relations are obtained 
as combinations of existing relations, and so provide valid 
simplification rules. A criterion is provided to verify that a set of 
relations satisfies the Gr\"obner Basis property given in Definition 
1.
 
-------------------------------


MOVED

   In the commutative setting, there is a standard algorithm
(Buchberger) which always terminates and provides
a Gr\"obner Basis.
%the Gr\"obner Basis Algorithm always 
%terminates and provides a Gr\"obner Basis. 
We have used an adaptation 
of the algorithm to polynomials in non-commuting variables due to F. 
Mora. The details of this algorithm, which we refer to as Mora's 
Algorithm,  are found in 
{\bf [FMora]} or {\bf [HW]}. In contrast to the 
commutative case, the Mora Algorithm does not always terminate.
If Mora`s algorithm terminates, the output is a finite basis
which automatically is a Gr\"obner Basis. If the algorithm
does not terminate, additional criteria must be applied
to determine if the output is a Gr\"obner Basis or not.
%%In this case, Mora's algorithm does not guarantee a
%%Gr\"obner basis, so additional tests are needed.
% it may 
%produce an infinite set of relations. If an infinite set is produced, 
%it is not automatically guaranteed to satisfy the Gr\"obner criterion. 
 
   The output of the Mora Algorithm is a list of polynomials. In each 
of the two examples (preNF and NF) mentioned above, the list is 
infinite. Analysis of the list shows that it consists of a collection 
of ``special" relations followed by several sequences of parametrized 
``general" rules. Ad hoc techniques were used to identify the general 
rules and verify the Gr\"obner criterion for these examples.
 
--------------------------------

   It should be noted that the simplification process is practical 
even in cases in which the Gr\"obner Basis is infinite. We have used an 
ordering which depends, first of all, on the number of factors in a 
term. If we wish to simplify an expression, $f$, 
no rules in which $LHS$
has a higher order than the terms of $f$ will apply. Thus a finite 
subset of the rules in an infinite basis will be enough to reduce all 
expressions up to a certain order of complexity. The (infinite) set of 
NF rules has been implemented by having instances of the general rules 
generated when needed. 
 
%    The production of a Gr\"obner Basis from a set of starting relations 
%can be quite intensive -- and would usually be done, once for all, for 
%various classes of expressions. Once produced, however, the process of 
%using it to simplify an expression is fairly quick.            

%The production of a Gr\"obner Basis from a set of 
%starting relations can
%be quite demanding of computer resources. The task can be done, once
%and for all, for
%various classes of expressions. Once a Gr\"obner Basis is at hand,
%the use of it to simplify expressions is usually quite efficient.
%Several examples of simplification using the GBs discussed
%in part I are found in the applications given in 
%part II of the paper.


%{\BF
%We finish this subsection by giving an example
%to show that the converse of the last observation 
%of Section 1 is false and give a related discussion. 
%
%Recall that in Section 1 we defined
%two polynomials to be equivalent if, upon 
%substituting the polynomial variables for given
%matrix values, the polynomials produce the same matrix. 
%
%\begin{remark}
%Let $\cal S$ be a Gr\"obner Basis. Let $p_1$ and
%$p_2$ be equivalent polynomials. 
%It may be the case that the normal form
%of $p_1$ is {\it not} equal to the normal form of $p_2$.
%\label{remark:one}
%\end{remark}
%
%\noindent
%Proof. \ \ \ 
%Let ${\cal S} = \{a\}$, $p_1 = b$, $p_2 = c$ and
%$A = B = C = 0$. If one considers the substitution
%of 
%$A$ for $a$,
%$B$ for $b$ and
%$C$ for $c$, then $p_1$ and $p_2$ are equivalent, but
%there normal forms are not the same.  \hfill \endproof
%
%In view of the proof, the converse 
%of the last observation
%of Section 1
%is obviously naive.
%The following remark shows that a natural strengthening
%of the hypothesis to Remark \ref{remark:one} does not
%yield equal normal forms. Remark \ref{remark:two}
%is a natural observation from the point of view 
%of representation theory.
%
%Let $\cal P$ be the collection of all polynomials
%in noncommuting variables $x_1,x_2,\ldots,x_n$.
%Let $S\subset \cal P$ and $I$ be the ideal of
%$\cal P$ generated by $S$. Let $\cal S$ be a Gr\"obner Basis
%for $I$ and $\cal R$ be the associated set of replacement
%rules.
%
%We say that a tuple of $m \times m$ matrices
%$(A_1,\ldots,A_n)$ is a root of a polynomial $p \in \cal P$
%if p is zero upon substuting $A_j$ for $x_j$ for $j=1,\ldots,n$.
%
%\begin{remark}
%Let $\cal S$ be a Gr\"obner Basis. 
%Suppose that for all tuples  of $m \times m$ matrices
%$(A_1,\ldots,A_n)$ which are roots of every polynomial 
%in $\cal S$, $p_1$ and
%$p_2$ be equivalent polynomials under the substitution
%of $A_j$ for $x_j$ for each $j=1,\ldots,n$. 
%It may be the case that the normal form
%of $p_1$ is {\it not} equal to the normal form of $p_2$.
%\label{remark:two}
%\end{remark}
%
%\noindent
%Proof. \ \ \ 
%Let $m=2$, $n=4$, $p_1$ be the zero polynomial and
%$p_2$ be the polynomial
%$$
%p_2(x_1,x_2,x_3,x_4) = \Sigma_{\sigma\in S_4} sgn(\sigma)
%x_{\sigma(1)} x_{\sigma(2)} x_{\sigma(3)} x_{\sigma(4)} \, 
%$$
%where $S_4$ is the symmetric group on $\{1,2,3,4\}$.
%It can be shown that $p_2(A,B,C,D) = 0$ for 
%$2\times2$ matrices $A$, $B$, $C$ and $D$. Therefore,
%$p_1$ and $p_2$ are equivalent under {\it any}
%substitution of $2\times 2$ matrices $A_j$ for $x_j$ for $j=1,2,3,4$. 
%Now let $I$ be any ideal of the polynomial ring
%in the variables $x_1$, $x_2$, $x_3$ and $x_4$ which
%does not contain $p_2$ and let $\cal S$ be a Gr\"obner
%Basis of $I$. 
%The normal forms of $p_1$ with respect to $\cal S$ is $0$, but
%the normal forms of $p_2$ with respect to $\cal S$ is not $0$.
%\hfill\endproof
%}
