%PART II
\def\theitem{\hspace{0.3in}}


In this part we will give lists of simplification rules which
arise in settings of increasing complexity. We will provide examples
of complete bases which are finite and also some which are
infinite.  We conclude with a formulation which provides a 
powerful general summary of many of our simplification rules.


\section{Simplification Rules for some Common Settings}
\label{simplification:rules:for:some}

In this section we list Gr\"obner Bases for
reducing polynomials in
\begin{description}
\item{(RESOL)} \ \
$x$, $x^{-1}$ and  $(1-x)^{-1}$ 

\item{(EB)} \ \
$x$, $y$,  $x^{-1}$, $y^{-1}$, $(1-xy)^{-1}$ and $(1-yx)^{-1}$

\item{(preNF)} \ \
$x$, $y$, $x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$,
$(1-xy)^{-1}$ and $(1-yx)^{-1}$

\item{(NF)} \ \
$x$, $y$,  $x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$,
$(1-xy)^{-1}$, $(1-yx)^{-1}$, $(1-xy)^{1/2}$ and $(1-yx)^{1/2}$ \, .
\end{description}
The names (RESOL), (EB), (preNF) and (NF) 
are explained in the following sections even though
the names are 
irrelevant to what we are doing here.

Here, as in the rest of this paper, we have adopted the
convention that atomic expressions will be used
as the names of polynomial variables (sometimes called indeterminates). 
Thus,
for example, $x$ and $x^{-1}$ are not
matrices; they are variables for which
matrices can be substituted. If we substitute
a matrix for $x$, we must substitute the inverse
of that matrix for $x^{-1}$.

There are many 
ways to impose orders on the
monomials
in the expressions we have listed above.
As indicated in Part I, we 
choose a graded lexicographic order
which is induced by an order on 
atomic expressions.
We have selected
%\footnote{
%graded lexicographic ordering
%which is induced by an ordering on atomic
%expressions.  }
orderings which reflect our notion of
which expressions ``feel" less complicated than others.  
We describe the overall structure of these orders on
indeterminates as follows:
\medskip

\theitem
Square roots of complicated polynomials are considered most complicated.

\theitem
Square roots of simple polynomials are considered second most complicated.

\theitem
Inverses of complicated polynomials are considered third most complicated.

\theitem
Inverses of simple polynomials are considered fourth most complicated.

\theitem
Other complicated-looking indeterminates are considered fifth most complicated.

\theitem
Simple-looking indeterminates are considered sixth most complicated.

\theitem
Commuting elements are considered the least complicated.
\smallskip

For example, the ordering $x < x^{-1} < (1-xy)^{-1}$
of variables is consistent with the intuitive idea
of increasing complexity. 
Specifying an order on the three variables imposes
a unique graded lexicographic order on the monomials
in these variables.
When we use this graded lexicographic order, the following monomials
are ordered as indicated:
$$
xx < x x^{-1} < x (1-xy)^{-1} < x^{-1} x
< (1-xy)^{-1} x < (1-xy)^{-1} x (1-xy)^{-1} < (1-xy)^{-1} x^{-1}x
$$

\subsection{A Gr\"obner Basis for Resol}
\label{subsection:Resol}

The first list, called
RESOL Rules, is a generalization of the example 
presented in Part I which involves expressions in
$x$, $x^{-1}$ and
$(1-x)^{-1}$.
The following list of 
rules\footnote{We use graded lexicographic order consistent
with the order in which the symbols are listed.}
involves expression in
$x$, 
$(\lambda -x)^{-1}$ and
$(\mu -x)^{-1}$.

%The list of
%rules (a point we discuss shortly) involves the 
%resolvent of $x$ and $y$.
%$\lambda$ and $\mu$ are complex numbers.
\bigskip

\centerline{RESOL Rules}
$$
(\lambda - x)^{-1} x \rightarrow \lambda (\lambda - x)^{-1} - 1
\leqno{(RESOL_0)}
$$ 
$$
x (\lambda - x)^{-1} \rightarrow \lambda (\lambda - x)^{-1} - 1
\leqno{(RESOL_1)}
$$ 
$$
(\mu -x)^{-1}  x \rightarrow \mu (\mu-x)^{-1} - 1
\leqno{(RESOL_2)}
$$ 
$$
x (\mu -x)^{-1}  \rightarrow \mu (\mu-x)^{-1} - 1
\leqno{(RESOL_3)}
$$ 
$$
(\mu-x)^{-1} (\lambda - x)^{-1} \rightarrow 
{1 \over {\mu - \lambda}} (\lambda - x)^{-1} + 
{1 \over {\lambda - \mu}} (\mu - x)^{-1} 
\leqno{(RESOL_4)}
$$ 
$$
(\lambda - x)^{-1} (\mu-x)^{-1}  \rightarrow 
{1 \over {\mu - \lambda}} (\lambda - x)^{-1} + 
{1 \over {\lambda - \mu}} (\mu - x)^{-1} 
\leqno{(RESOL_5)}
$$ 
for all operators $x$ on a Hilbert space $\cal H$
and distinct complex numbers $\lambda$ and $\mu$. The following
theorem is an easy generalization of a corresponding result from
{\bf [HW]}. 

\proclaim{Theorem 2.1}
The list RESOL Rules is a Gr\"obner basis in the symbols
$x$, $(\lambda - x)^{-1}$ and $(\mu - x)^{-1}$ where $\lambda$
and $\mu$ are distinct complex numbers and the terms are
ordered using the graded lexicographical order with
$$x<(\lambda-x)^{-1}<(\mu-x)^{-1}.$$
\endproclaim

While one does not need to know the proof in order
to use RESOL, a few words on the proof
serves to illustrate the
theory of Part I. If one uses 
$(RESOL_0)$, $(RESOL_1)$, $(RESOL_2)$ and $(RESOL_3)$ 
together with the fact
that scalars $\lambda$ and $\mu$ 
commute with everything as starting
relations for Mora's algorithm, then one obtains
$(RESOL_0)$ through $(RESOL_5)$ as output.
Thus the theory of Section \ref{subsection:GroebnerBases}
tells us that this is a GB.

%Due to idiosyncracies of our program,
%this is not exactly what we did. 
%
%If $\lambda$ and $\mu$ are specific complex numbers
%(e.g., $\lambda = 1$ and $\mu = 2$), then one can prove
%that the RESOL Rules (for this specific choice of
%scalars $\lambda$ and $\mu$) is a Gr\"obner Basis
%by running Mora's algorithm 
%(Section \ref{subsection:GroebnerBases}) on 
%the rules $(RESOL_0)$ through $(RESOL_3)$ and one
%will obtain the rules $(RESOL_0)$ through $(RESOL_5)$
%(for this specific choice of scalars $\lambda$ and $\mu$).
%For fixed but unspecified values of $\lambda$ and $\mu$,
%we proved that RESOL Rules is a Gr\"obner Basis by hand.

The name RESOL reflects the fact that 
operator theorists call 
$(\lambda -x)^{-1}$
the resolvent of $x$.

%----------------------------------------------------------
%----------------------------------------------------------
%----------------------------------------------------------
%FILE  ch3 tex
%----------------------------------------------------------
%----------------------------------------------------------
%----------------------------------------------------------
%\subsection{More GB`s}
%\noindent {\bf \S 3. FURTHER COMMON SITUATIONS}

%In this section we list Gr\"obner Bases for
%reducing polynomials in
%\footnote{Here we use graded lexicographic order consistent
%with the order in which the symbols are listed.}
%\begin{description}
%\item{(EB)} \ \
%$x$, $y$,  $x^{-1}$, $y^{-1}$, $(1-xy)^{-1}$ and $(1-yx)^{-1}$
%
%\item{(preNF)} \ \ 
%$x$, $y$, $x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$,
%$(1-xy)^{-1}$ and $(1-yx)^{-1}$
%
%\item{(NF)} \ \
%$x$, $y$,  $x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$,
%$(1-xy)^{-1}$, $(1-yx)^{-1}$, $(1-xy)^{1/2}$ and $(1-yx)^{1/2}$ \, .
%\end{description}
%The names (EB) (preNF) (NF) arise from certain contexts which are
%irrelevant to this discussion.
%
%%\subsubsection{Ordering on monomials}
%% \noindent {\bf 3A. Ordering on monomials}
%

%   Move this to where preNF is discussed
%Using the above ordering criterion, the orders which we
%consider for the expressions of $preNF$ (expressions in $x$, $y$,
%$x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$, $(1 -xy)^{-1}$ and
%$(1-yx)^{-1})$ all have the
%form
%$$
%{x\atop y}<
%{x^{-1}\atop y^{-1}}<
%{(1-x)^{-1}\atop (1-y)^{-1}}<
%{(1-xy)^{-1}\atop(1-yx)^{-1}} \,\, .
%$$
%%$$ \matrix {x& & x^{-1} && (1-xy)^{-1}\cr
%%&< &&<&\cr
%%y&&y^{-1}&&(1-yx)^{-1}\cr}\quad .$$
%By specifying in addition that $x<y$ we have the order
%$$x < y < x^{-1} < y^{-1} < (1-xy)^{-1} < (1-yx)^{-1}.$$
%
%%Now, if one has a polynomial relation
%%$$a_n m_n + a_{n-1} m_{n-1} + \dots + a_0 = 0$$
%%where the $a_j$'s are scalars, the $m_j$'s are monomials,
%%$a_n\not= 0$ and $m_n > m_{n-1} > m_{n-2} > \dots > m_1 > 1$,
%%then the corresponding replacement rule is
%%$$m_n \rightarrow -{a_{n-1}\over a_n} m_{n-1} - {a_{n-2}\over
%%a_n} m_{n-2} - \dots - {a_0\over a_n}.$$
%
%For polynomial relations of the form $M_1 = M_2$ with degree$(M_1)$ $=$ 
%degree$(M_2)$, using the replacement rule can have the effect of
%moving complicated indeterminates to the right. 
%For example, the identity $(1-xy)^{-1}$$x = x (1-yx)^{-1}$ can be
%converted to 
%a replacement rule in two ways. The one consistent with the above order is:
%
%$$(1-xy)^{-1} x\longrightarrow x (1-yx)^{-1}$$
%in that the complicated  inverse 
%%$(\ )^{-1}$ 
%moves to the right. The wrong rule is 
%$$x (1-yx)^{-1}\longrightarrow (1-xy)^{-1} x\;.$$
%


%%For the set of relations which we call NF, we use the order 
%%\begin{eqnarray*}
%%x<y<x^{-1}<y^{-1}<(1-x)^{-1}<(1-y)^{-1}<(1-xy)^{-1}\\
%%\phantom{x}<(1-yx)^{-1}<(1-xy)^{1/2}<(1-yx)^{1/2}\;.
%%\end{eqnarray*}
%
%%Among the replacement rules of NF are
%%\begin{eqnarray*}
%%((1-yx)^{1/2})^2&\longrightarrow&  1-yx\\
%%((1-xy)^{1/2})^2&\longrightarrow& 1-xy \, .
%%\end{eqnarray*}
%%Therefore, any expression involving higher powers of $(\phantom{0})^{1/2}$ is
%%reduced.
%%All higher powers  will be replaced by lower order expressions.
\bigskip

\subsection{A Gr\"obner basis for EB}
%\noindent {\bf \S 3B. A Gr\"obner basis for EB}

%Theorem 2.1 above states that RESOL is a Gr\"obner basis. 
%Before moving onto the main result, we recall another
%useful Gr\"obner basis for the set of relations called
%EB. 
The indeterminates which are used in EB and the
ordering which we use is as follows:
$$x<y<x^{-1}<y^{-1}<(1-xy)^{-1}<(1-yx)^{-1}\;.$$
The set of relations of EB is the set of defining relations
of $x^{-1}$, $y^{-1}$, $(1-xy)^{-1}$ and $(1-yx)^{-1}$ ($EB_0$ 
through $EB_7$ below)
\footnote{That is, they come from the
definition of ``inverse".}.
This set of relations is not a Gr\"obner basis.
The following theorem shows that one can extend this list of
relations to obtain a Gr\"obner basis.

%\proclaim{Theorem 3.1({\bf [HW]})} 
\begin{theorem}
The following relations constitute a
finite Gr\"obner basis for \ro{EB}.
\begin{eqnarray*}
{\rm EB_0}&=&x^{-1}\; x-1\\
{\rm EB_1}&=&xx^{-1}-1\\
{\rm EB_2}&=&y^{-1}\; y-1\\
{\rm EB_3}&=&\; yy^{-1}-1\\
{\rm EB_4}&=&xy\; (1-xy)^{-1}-(1-xy)^{-1}+1\\
{\rm EB_5}&=&yx\; (1-yx)^{-1}-(1-yx)^{-1}+1\\
{\rm EB_6}&=&(1-xy)^{-1}xy-(1-xy)^{-1}+1\\
{\rm EB_7}&=&(1-yx)^{-1}yx-(1-yx)^{-1}+1\\
{\rm EB_8}&=&(1-yx)^{-1}\; x^{-1}-y(1-xy)^{-1}-x^{-1}\\  
{\rm EB_9}&=&(1-xy)^{-1}\; y^{-1}-x\; (1-yx)^{-1}-y^{-1}\\ 
{\rm EB_{10}}&=&x^{-1}\; (1-xy)^{-1}-y\;(1-xy)^{-1}-x^{-1}\\
{\rm EB_{11}}&=&y^{-1}\; (1-yx)^{-1}-x\;(1-yx)^{-1}-y^{-1}\\
{\rm EB_{12}}&=&(1-yx)^{-1}\; y-y\;(1-xy)^{-1}\\
{\rm EB_{13}}&=&(1-xy)^{-1}\; x-x\;(1-yx)^{-1}\, .
\end{eqnarray*}
\end{theorem}

We express this GB as a list of polynomials
rather than as a list of replacement rules.
%Here we follow the algebraist convention and suppress the $=0$
%or the rule (`$\rightarrow$') notation.
We will use the convention that polynomials are written 
with terms in descending order. Thus the first term 
of a polynomial will be the 
$LHS$ when it is converted to a replacement rule.
%Also, clearly one only needs to remember 7 rules and the fact 
%that one can derive the other 7 by swapping $x$ and $y$.
Note that $EB_6$ and $EB_7$ can be 
reduced to 0 using the other rules
and so $EB_0$ through $EB_6$ together with
$EB_9$ through $EB_{13}$ is a 
%we still have a 
GB. They have been included in this list because
they are in the starting set of relations, and we were worried that
an observant reader would be concerned if they were left out.

The relations which form the GB for $(EB)$ are of interest
because they underlie energy balance equations in $H^\infty$ control.


\begin{remark}
{\rm 
Once an ordering has been selected, every polynomial in the basis is
converted to a replacement rule in a very precise way.
The LHS is always the largest term in the ordering.
If (for example) we convert $EB_{13}$  to a replacement 
rule, we use the rule 
$(1-xy)^{-1} x \rightarrow x (1-yx)^{-1}$
because $(1-yx)^{-1} x$ is larger than
$x (1-xy)^{-1}$ in the given ordering.
Notice that simplification using 
lexicographic ordering has the effect of moving
more complicated atomic expressions to the right
in a term because the ``simpler" atomic
expressions (like $x$) occur earlier in the
alphabet than more complicated atomic expressions
(like $(1-xy)^{-1}$).
%Here is an informative practical illustration of the role 
%of  the lexicographic contribution of the order.
%The identity $(1-xy)^{-1}$$x = x (1-yx)^{-1}$ could be
%sensibly converted to 
%a replacement rule in two ways. The one consistent with the above order is:
%$$(1-xy)^{-1} x\longrightarrow x (1-yx)^{-1}$$
%in that the complicated  inverse 
%moves to the right. The wrong rule is 
%$$x (1-yx)^{-1}\longrightarrow (1-xy)^{-1} x\;.$$
%even though it appears as intuitive as the first one.
}
\end{remark}

\subsection{An infinite Gr\"obner basis for preNF}
%\noindent {\bf \S 3C. An (infinite) Gr\"obner basis for preNF}
\label{section:preNF}

The set of relations considered in this section is named
(preNF) 
%case is named 
because it is {\it pre}liminary to the
set of relations 
which will be considered in the 
following section
which is named NF for $N$agy-$F$oias.
%NF (for Nagy-Foias) case 
The indeterminates which are used in (preNF) and the
ordering which we use are as follows.
%Using the above ordering criterion, the orders which we
Using the guidelines
for ordering atomic expressions mentioned
at the beginning of 
\ref{simplification:rules:for:some},
the orders which we 
consider for the expressions of $(preNF)$ (expressions in $x$, $y$,
$x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$, $(1 -xy)^{-1}$ and
$(1-yx)^{-1})$ all have the
form
$$
{x\atop y}<
{x^{-1}\atop y^{-1}}<
{(1-x)^{-1}\atop (1-y)^{-1}}<
{(1-xy)^{-1}\atop(1-yx)^{-1}} \,\, .
$$
%$$ \matrix {x& & x^{-1} && (1-xy)^{-1}\cr
%&< &&<&\cr
%y&&y^{-1}&&(1-yx)^{-1}\cr}\quad .$$
By specifying in addition that $x<y$ we have the order
% MXS Apr 15,1996
%$$x < y < x^{-1} < y^{-1} < (1-xy)^{-1} < (1-yx)^{-1}.$$
%
%Now, if one has a polynomial relation
%$$a_n m_n + a_{n-1} m_{n-1} + \dots + a_0 = 0$$
%where the $a_j$'s are scalars, the $m_j$'s are monomials,
%$a_n\not= 0$ and $m_n > m_{n-1} > m_{n-2} > \dots > m_1 > 1$,
%then the corresponding replacement rule is
%$$m_n \rightarrow -{a_{n-1}\over a_n} m_{n-1} - {a_{n-2}\over
%a_n} m_{n-2} - \dots - {a_0\over a_n}.$$
%
%I understand what you are trying to say here -- but I don't
%think that what has been said is true in a strict sense -- and I
%am not sure it would be really illuminating to add the extra verbiage
%needed to make it true.
%
%\item{(preNF)}
$$ 
\ro{preNF}
\quad x<y<x^{-1}<y^{-1}<(1-x)^{-1}<(1-y)^{-1}<(1-xy)^{-1}<(1-yx)^{-1}\;.
$$


%Is there any reason for sometimes using preNF and sometimes (preNF)?

The set of relations of (preNF) is the set of 
defining relations
of $x^{-1}$, $y^{-1}$, $(1-x)^{-1}$, $(1-y)^{-1}$,
$(1-xy)^{-1}$ and $(1-yx)^{-1}$.
Notice that the variables and relations for (preNF) are those
for (EB) together with those for (RESOL) with $\lambda=0$
and $\mu=1$. 
The Gr\"obner basis obtained for (preNF) is infinite.
It consists of a small collection of special relations
followed by 
several sequences of parameterized relations. This is the content
of the next theorem. The proof of this theorem is in a 
manuscript which is in preparation.
%As an illustration, one parameterized relation of 
%this type is
%$$
%x\; (1-yx)^{-n}\; (1-x)^{-1}-(1-xy)^{-n} (1-x)^{-1} + (1-xy)^{-n} 
%$$
%for all integers $n\ge 0$.



\begin{THEOREM}
%{\bf Theorem 3.2} 
\label{thm:preNF}
\ The following relations form a Gr\"{o}bner Basis for
$(preNF)$.

\noindent
There are 22 special relations:
\begin{description}
\item{(A)} The relations for $(EB)$
\item{(B)} The $(RESOL)$ relations 
for both $x$ and $y$
with $\lambda =0,\mu =1$ 
\item{(C)} Two additional relations
\end{description}

\noindent$\
preNF_1=(1-y)^{-1}x(1-yx)^{-1}-(1-y)^{-1}(1-yx)^{-1}-x(1-yx)^{-1}+(1-y)^{-1}$

\noindent
$\
preNF_2=(1-x)^{-1}y(1-xy)^{-1}-(1-x)^{-1}(1-xy)^{-1}-y(1-xy)^{-1}+(1-x)^{-1}$

\noindent
There are 8 (infinite) classes of general relations 
each of which are parameterized by a positive integer n:

\begin{description}
\item{$I.\ \ \ $} $x{(1-yx)}^{-n}(1-x)^{-1}-{(1-xy)}^{-n}(1-x)^{-1}+{(1-xy)}^{-n}%
$
\item{$II.\ \ $} $x{(1-yx)}^{-n}(1-y)^{-1}-{(1-xy)}^{-n}(1-y)^{-1}-x{(1-yx)}%
^{-n}+\allowbreak {(1-xy)^{-(n-1)}}(1-y)^{-1}$
\item{$  III.\ $} $y{(1-xy)}^{-n}(1-x)^{-1}-{(1-yx)}^{-n}(1-x)^{-1}-y{%
(1-xy)^{-n}}+\allowbreak {(1-yx)}^{-(n-1)}(1-x)^{-1}$
\item{$IV.\ \ $} $y{(1-xy)}^{-n}(1-y)^{-1}-{(1-yx)}^{-n}(1-y)^{-1}+{(1-yx)}^{-n}$%
\item{$V.\ \ \ $} $(1-x)^{-1}{(1-yx)}^{-n}(1-x)^{-1}-(1-x)^{-1}{(1-xy)}^{-n}%
(1-x)^{-1}-\allowbreak {(1-yx)}^{-n}(1-x)^{-1}+(1-x)^{-1}{(1-xy)}^{-n}$
\item{$VI.\ \ $} $(1-x)^{-1}{(1-yx)}^{-n}(1-y)^{-1}-(1-x)^{-1}{(1-xy)}^{-n}%
(1-y)^{-1}-\allowbreak {(1-yx)}^{-n}(1-y)^{-1}-(1-x)^{-1}{(1-yx)}^{-n}%
+(1-x)^{-1}{(1-xy)^{-(n-1)}}(1-y)^{-1}+\allowbreak {(1-yx)}^{-n}$
\item{$VII.\ $} $(1-y)^{-1}{(1-yx)}^{-n}(1-x)^{-1}-(1-y)^{-1}{%
\{(1-xy)^{-n}+...+1\}}(1-x)^{-1}+\allowbreak $ $\{{(1-xy)}^{-n}%
+...+(1-xy)^{-1}\}(1-x)^{-1}+\allowbreak (1-y)^{-1}\{{(1-xy)}^{-n}%
+...+(1-xy)^{-1}\}-$\allowbreak $\{{(1-xy)}^{-n}+...+(1-xy)^{-1}\}$
\item{$VIII.$} $(1-y)^{-1}{(1-yx)^{-n}}(1-y)^{-1}-(1-y)^{-1}{(1-xy)}^{-n}%
(1-y)^{-1}+\allowbreak {(1-xy)}^{-n}(1-y)^{-1}-(1-y)^{-1}{(1-yx)}^{-n}$
\end{description}
\end{THEOREM}

\noindent
{\bf Observations:} \ \ \ 
Class $IV$ is obtained from class $I$ by interchanging $x$ and $y$.
Class $II$ and $III$ are similarly related. 
Class $VIII$ is obtained from class $V$
by interchanging $x$ and $y$ and reordering terms. 
Some of the other classes (classes $I$ and $V$)
are obtained from very general rules
( $(Gr2)$ respectively $(Gr4)$ )
in the forthcoming Section \ref{sec:gen}.
%We may obtain class $I$ from
%the functional calculus rule $(Gr2)$ by substituting  
%$h(s)=(1-s)^{-n}.$ We
%similarly obtain class $V$ from $(Gr4)$. Since 
%$(preNF)$ is a combination of
%$(RESOL)$ and $(EB)$, we expect it to contain the relations 
%obtained from them.
%What is unique to $(preNF)$ is the appearance of infinite 
%classes of relations
%which come from interaction between $(RESOL)$ relations 
%and $(EB)$ relations.
%

%\proclaim{Theorem 3.2}
%%Define a set of relations called GBpreNF by
%%%to be 
%%\begin{description}
%%%\item{\rm rel[Pre1]}$ =
%%%\item{I.}
%%%$(1-x)^{-1} y (1-xy)^{-1} - (1-x)^{-1} (1-xy)^{-1} - y (1-xy)^{-1} 
%%+ (1-x)^{-1}$
%%\medskip
%
%% SWAP
%%\item{\rm rel[Pre2]}$ =
%%(1-y)^{-1} x (1-yx)^{-1} - (1-y)^{-1} (1-yx)^{-1} - x (1-yx)^{-1} 
%%+ (1-y)^{-1}$
%%\medskip
%
%% IS A GENR
%%\item{$I^*$. }$x (1-yx)^{-n} (1-x)^{-1} - (1-xy)^{-n} 
%%\{(1-x)^{-1} - 1\}$
%%\medskip
%
%%\item{II. }
%%\item{I. }
%%$x (1-yx)^{-n} (1-y)^{-1} - (1-xy)^{-n} 
%%(1-y)^{-1} - x (1-yx)^{-n} + (1-xy)^{-(n-1)} (1-y)^{-1}$ 
%%\medskip
%%
%%%\item{$III^*$.}
%%$x (1-yx)^{-n} (1-yx)^{1/2} (1-x)^{-1} - 
%%(1-xy)^{-n} (1-xy)^{1/2} \{(1-x)^{-1}-1\}$ 
%%\medskip
%
%%\item{$IV^*$. }
%%$x (1-yx)^{-n} (1-yx)^{1/2} (1-y)^{-1} - 
%%\{(1-xy)^{-n} - (1-xy)^{-(n-1)}\} (1-xy)^{1/2} 
%%(1-y)^{-1} -
%%x (1-yx)^{-n} (1-yx)^{1/2}$
%%\medskip
%
%%SWAP
%%$y (1-xy)^{-n} (1-x)^{-1} - 
%%\{(1-yx)^{-n} - (1-yx)^{-(n-1)}\} (1-x)^{-1} - y (1-xy)^{-n}$
%%\medskip
%
%% IS A GENR
%%\item{$VI^*$. }
%%$y (1-xy)^{-n} (1-y)^{-1} - (1-yx)^{-n} 
%%\{(1-y)^{-1} - 1\}$
%%\medskip
%
%%\item{$VII^*$. }
%%$y (1-xy)^{-n} (1-xy)^{1/2} (1-x)^{-1} - 
%%\{(1-yx)^{-n} - (1-yx)^{-(n-1)}\} (1-yx)^{1/2} (1-x)^{-1} -
%%y (1-xy)^{-n} (1-xy)^{1/2}$
%%\medskip
%
%%\item{$VIII^*$. }
%%$y (1-xy)^{-n} (1-xy)^{1/2} (1-y)^{-1} 
%%- (1-yx)^{-n} (1-yx)^{1/2} \{(1-y)^{-1}-1\}$ 
%%\medskip
%
%% IS A GENR
%%\item{$IX^*$. }
%%$(1-x)^{-1} (1-yx)^{-n} (1-x)^{-1} - 
%%(1-x)^{-1} (1-xy)^{-n} (1-x)^{-1} -
%%(1-yx)^{-n} (1-x)^{-1} + (1-x)^{-1} (1-xy)^{-n}$ 
%%\medskip
%
%%\item{X. }
%%\item{III.}
%%\item{II.}
%%$(1-x)^{-1} (1-yx)^{-n} (1-y)^{-1} - 
%%(1-x)^{-1} \{(1-xy)^{-n} - (1-xy)^{-(n-1)}\} (1-y)^{-1} - (1-yx)^{-n} 
%%\{(1-y)^{-1}-1\} -
%%(1-x)^{-1} (1-yx)^{-n}$
%%\medskip
%
%%\item{XI. }
%%$(1-x)^{-1} (1-yx)^{-n} (1-yx)^{1/2} 
%%(1-x)^{-1} -
%%(1-x)^{-1} (1-xy)^{-n} (1-xy)^{1/2} \{(1-x)^{-1}-1\} - (1-yx)^{-n} 
%%(1-yx)^{1/2} (1-x)^{-1}$
%%\medskip
%
%%\item{XII. }
%%$(1-x)^{-1} (1-yx)^{-n} (1-yx)^{1/2} 
%%(1-y)^{-1} -
%%(1-x)^{-1} \{(1-xy)^{-n} - (1-xy)^{-(n-1)}\} \break(1-xy)^{1/2} (1-y)^{-1}
%%-
%%(1-yx)^{-n} (1-yx)^{1/2} \{(1-y)^{-1} - 1\} - (1-x)^{-1} (1-yx)^{-n} 
%%(1-yx)^{1/2}$
%%\medskip
%
%%\item{XIII. }
%%\item{IV.}
%%\item{III.}
%%$(1-y)^{-1} (1-yx)^{-n} (1-x)^{-1} - 
%%(1-y)^{-1} \{(1-xy)^{-n} +\ldots+1\} (1-x)^{-1} +
%%\break\{(1-xy)^{-n}+\ldots+(1-xy)^{-1}\}
%% (1-x)^{-1} + (1-y)^{-1} \{(1-xy)^{-n}+\ldots+(1-xy)^{-1}\} -\break
%%\{(1-xy)^{-n}+\ldots+(1-xy)^{-1}\}$
%%\medskip
%
%% IS A GENR
%%\item{$XIV^*$. }
%%$(1-y)^{-1} (1-yx)^{-n} (1-y)^{-1} - 
%%(1-y)^{-1} (1-xy)^{-n} (1-y)^{-1} +
%%(1-xy)^{-n} (1-y)^{-1} - (1-y)^{-1} (1-yx)^{-n}$ 
%%\medskip
%
%%\item{XV. }
%%$(1-y)^{-1} (1-yx)^{-n} (1-yx)^{1/2} 
%%(1-x)^{-1} -
%%(1-y)^{-1} \{(1-xy)^{-n}+\ldots+(1-xy)^{-1}\}\break (1-xy)^{1/2} (1-x)^{-1}
%%+
%%\{1-xy)^{-n}+\ldots+(1-xy)^{-1}\} 1-xy)^{1/2} (1-x)^{-1} 
%%+ (1-y)^{-1}\break\{1-xy)^{-n}+\ldots+(1-xy)^{-1}\} (1-xy)^{1/2} -
%%\{(1-xy)^{-n}+\ldots+(1-xy)^{-1}\} (1-xy)^{1/2} - \break(1-y)^{-1}
%%(1-yx)^{1/2}  (1-x)^{-1}$
%%\medskip
%
%%\item{$XVI^*$. }
%%$(1-y)^{-1} (1-yx)^{-n} (1-yx)^{1/2} 
%%(1-y)^{-1} -
%%%(1-y)^{-1} (1-xy)^{-n} (1-xy)^{1/2} (1-y)^{-1} + (1-xy)^{-n} (1-xy)^{1/2}
%% (1-y)^{-1} -
%%(1-y)^{-1} (1-yx)^{-n} (1-yx)^{1/2}$
%%\end{description}
%
%%\noindent
%%for any $n \ge 1$ 
%%together with 
%%\begin{description}
%%\item{(A)} (RESOL) and (EB)
%%\item{(B)} 
%%$(1-x)^{-1} y (1-xy)^{-1} - (1-x)^{-1} (1-xy)^{-1} - y (1-xy)^{-1} 
%%+ (1-x)^{-1}$
%%\item{(C)} (Gr2) and (Gr4) with $h(s) = (1-s)^{-n}$ for $n\ge1$ and
%%$\lambda = 1$
%%
%%\item{(D)} the general relation $I$ and item (A), (B), and (C)
%%with $x$ swapped with $y$.
%%\end{description}
%%GBpreNF is a Gr\"obner basis.
%%\endproclaim
%

\subsection{ An infinite Gr\"obner basis for NF }
%\noindent {\bf \S 3D. Another (infinite) Gr\"obner basis}
\label{section:NF} 

%There is another set of expressions for which we have determined a GB,
%however we shall not list it here. 
%See {\bf{[HW,HSW]}}.
%See {\bf{[HW]}}.
%We designate this as the NF case.
The indeterminates which are used in NF and their 
ordering which we use is as follows
%\item{(NF)}
$$
\ro{NF} \quad 
 \ \ indeterminates\ of\ preNF\ <(1-xy)^{1/2}<(1-yx)^{1/2}\;.
$$

These satisfy the set of defining relations for
$x^{-1}$, $y^{-1}$, $(1-x)^{-1}$ and $(1-y)^{-1}$,
$(1-xy)^{-1}$ and $(1-yx)^{-1}$ together with the four relations
corresponding to the rules
\begin{eqnarray*}
((1-xy)^{1 \over 2})^2 \rightarrow 1 - x y\\
((1-yx)^{1 \over 2})^2 \rightarrow 1 - y x\\
(1-xy)^{1/2} x \rightarrow x (1-yx)^{1/2}\\
(1-yx)^{1/2} y \rightarrow y (1-xy)^{1/2} \, .
\end{eqnarray*}
The first two of these relations are the defining relations for
$(1-xy)^{1 \over 2}$ and $(1-yx)^{1 \over 2}$.
% and they insure
%that all higher powers  will be replaced by lower order expressions. 
The third and fourth
relations are not an algebraic consequence of the other relations of 
$(NF)$. These third and fourth relations can be proven by
an analytic argument if $x$ is a contraction, 
$y$ as the adjoint of $x$ and 
$(\phantom{0})^{1 \over 2}$ means ``positive square root".
These relations are
extremely important to those working with 
$2\times2$ block unitary matrices or with the Nagy-Foias 
{\bf [NF]} model.


As in the preNF case, a Gr\"obner basis consists of a collection 
of special rules together with families of general rules.  In the
NF case there are 16 families of parametrized rules.  Further details
are found in  {\bf{[HW]}}.
\medskip
%-----------------------------------------------
%-----------------------------------------------
%-----------------------------------------------
% OLD FILE ch2_gen*
%-----------------------------------------------
%-----------------------------------------------
\section{General Rules}
\label{sec:gen}

\iffalse
%%%%%%%%%%%%%

%As noted, the section needs some work.  Reviewers objected to
%statements that, I notice, still are included.
%There seems to be some vagueness about this that is being
%communicated to readers.  Also vague is the connection
%with the previous work.  The truth of these rules, under the
%conditions stated, do not follow from the GB machinery alone.
%[e.g. it is already noted that Gr0 in the NF case requires an
%analytic proof.]

%This section contains a 
%set of rules of which 
Many rules which you have just seen are
special cases of rules from the set of rules
given in this section. 
These  rules together with the (RESOL) rules are simple
enough that they could actually be used in hand
computation.

\subsection{Statement of GENR Rules}
\label{subsection:Statement:GENR}

The following is a set of rules which hold for 
all operators $x$ and $y$ on a Hilbert space $\cal H$
with $x$, $y$, $\lambda-x$ and $\lambda- y$ invertible,
functions $h$ analytic on the spectrum of
$xy$ and $yx$ and all $\lambda \ne 0$. 
(Technically, the following are not necessarily
replacement rules for certain $h$ since the left hand side
may not be a monomial. We will discuss this shortly.)

\bigskip

\centerline{GENR Rules}
$$
h(xy) x\rightarrow x h(yx)
\leqno{(Gr0)}
$$
$$
h(yx) x^{-1}\rightarrow x^{-1}  h(xy)
\leqno{(Gr1)}
$$
%Corrected Gr2...MXS
$$
x h(yx) (\lambda-x)^{-1}\rightarrow \lambda h(xy) (\lambda-x)^{-1} - h(xy)
\leqno{(Gr2)}
$$
%Cosmetic change to Gr3...MXS
$$
x^{-1} h(xy) (\lambda-x)^{-1}\rightarrow \lambda^{-1} x^{-1} h(xy)
+\lambda^{-1} h(yx) (\lambda-x)^{-1}
\leqno{(Gr3)}
$$
%Corrected power of lambda in Gr4...MXS
$$
(\lambda-x)^{-1} h(y x) (\lambda-x)^{-1}-(\lambda-x)^{-1} h(x y) 
(\lambda-x)^{-1} \rightarrow 
\leqno{(Gr4)}
$$
$$
\lambda^{-1} (h(y x) (\lambda-x)^{-1}-(\lambda-x)^{-1} h(x y) )
$$
%$$
%\leqalignno{
%(\lambda-x)^{-1} h(y x) &(\lambda-x)^{-1}-(\lambda-x)^{-1} h(x y) 
%(\lambda-x)^{-1} \rightarrow & (Gr4) \cr
%&\lambda^{-1} (h(y x) (\lambda-x)^{-1}-(\lambda-x)^{-1} h(x y) )\cr
%}
%$$
$$
\mbox{\rm The\ rules\ (Gr0)\ through\ (Gr4)\ with\ $x$ and $y$ swapped.}\leqno{(Gr5-9)}
$$

Operators of the form $h(xy)$ arise, of course, in what is called the {\it
functional calculus} of the operator $xy$. Examples are
$h(xy)=(1-xy)^{-1}$, $h(xy)=(1-xy)^{1/2}$ and
$h(xy)=e^{xy}$ provided the eigenvalues of $xy$ are in the right location.
%A person might well find
%%these rules useful in a hand computation. 

%For future reference, let (Gr0$\,^\prime$) through (Gr4$\,^\prime$) denote the 
%replacement rules
%(Gr0) through (Gr4) with $x$ and $y$ swapped. For example,
%$$
%y^{-1} h(yx) (\lambda-y)^{-1}\rightarrow \lambda^{-1} y^{-1} h(yx)
%+\lambda^{-1} h(xy) (\lambda-y)^{-1} \, .
%\leqno{(Gr3\,^\prime)}
%$$
%Of course, mathematically (Gr0$^\prime$) through (Gr4$^\prime$) 
%are equivalent to (Gr0) through (Gr4).

In the above list of rules, the expression on the left hand side
of the rule may not be a monomial. For example, see (Gr4) or set
$h(z) = z+z^2$. 
It is easier to automate replacement rules if the $LHS$ of
a rule is a monomial. When these rules are used for machine
computation, they are rearranged 
so that the $LHS$ is a monomial.
%to be in this form.
%These ambiguities usually need to be eliminated in order
%for a computer to perform a calculation since automatic searches
%for classes of monomials is much easier than for sums 
%of polynomials. 
%This type
%of ``rule" in which the left hand side is not a monomial corresponds
%more closely to the way in which mathematics is actually done.

This set of rules applies to many situations.
%They
%might be worth teaching to 
%all people beginning in the area of matrix or operator algebra.
Currently (RESOL) is 
universally taught;
(RESOL4) is called the resolvent identity. 
%Thus by tradition we teach our students a GB for these circumstances.
%while only the special case (Gr0)
%are common in introductory courses. 
Also we teach our students the extremely valuable rule
$$
h(xy)x \rightarrow xh(yx) \, ,
$$
but (GENR) is not taught.
%, so students are taught much less than a complete
%set of rules.
%it is amusing to note that (GENR) is not taught so students
%are given much less than a GB.
$(GENR)$ is a short enough list of rules that 
it could be used for hand computations.
%It would be interesting to see the effect 
%on student's facility with hand computation
%if 
%%students 
%they
%were taught the 
%%complete 
%list of rules (RESOL) plus (GENR).

%%%%%%%%%%%%%%%%%%%

\fi

% ------- BEGIN NEW MAY 17th

Many of the infinite families of rules which you have just
seen are special cases of the simple rules which are 
given in this section.
These rules are a bit sophisticated in that they are
stated directly in terms of
%In order to do this, we must first briefly discuss
the functional calculus of a matrix.
The functional calculus is an
important construction in matrix
and operator theory which associates
the matrix $h(M)$
to a matrix $M$ and a polynomial $h$
in one complex variable.
More generally, one can use a function
$h$ which is analytic on the spectrum
of $M$.
The mapping $h \rightarrow h(M)$
of analytic functions to matrices
is what is called the {\bf functional calculus} of
$M$. For example, if $h(s) = \frac{1}{1-s}$, then 
$h(M)$ is $(1-M)^{-1}$. Similarly, 
one can obtain expressions like
$h(xy)=(1-xy)^{1/2}$ 
and 
$h(M)=e^{M}$
provided the eigenvalues of $xy$ and $M$ are in the right location.

This section concentrates on a particular list of rules which 
are described in terms of the functional calculus.
As you will see, a brief list of functional
calculus based rules contains a great deal of information.

\iffalse
%%%%%%%%%%%%%%

The Gr\"obner Basis machinery has found
%We find 
that relations of the form 
\begin{eqnarray}
h(xy)x&=&xh(yx) \\
yh(xy)&=&h(yx)y
\end{eqnarray}
hold
for many analytic functions $h$. We have seen this in the preNF rules where $%
h(z)=(1-z)^{-1}$and we note that these relations also hold when $%
h(z)=(1-z)^{-n}$. We therefore applied the machinery in this paper to study
this general situation. The result is a set of simple and general
substitution rules. These include some of the rules obtained in the previous
sections. This set of rules holds for all operators $x$ and $y$ on a Hilbert
space $\mathcal{H}$ with $x$, $y$, $\lambda -x$ and $\lambda -y$ invertible,
functions $h$ analytic on the spectrum of $xy$ and $yx$ and all $\lambda \ne
0$. (Technically, the following are not necessarily replacement rules for
certain $h$ since the left hand side may not be a monomial. We will discuss
this shortly.)


%%%%%%%%%%%%%%

\fi

\bigskip

\subsection{Statement of the (GENR) Rules}

The following is a set of rules which hold for
all operators $x$ and $y$ on a Hilbert space $\cal H$
with $x$, $y$, $\lambda-x$ and $\lambda- y$ invertible,
functions $h$ analytic on the spectrum of
$xy$ and $yx$ and all $\lambda \ne 0$.
(Technically, the following are not necessarily
replacement rules for certain $h$ since the left hand side
may not be a monomial. We will discuss this shortly.)

\bigskip

\centerline{GENR Rules} 
$$
h(xy)x\rightarrow xh(yx)\leqno{(Gr0)} 
$$
$$
h(yx)x^{-1}\rightarrow x^{-1}h(xy)\leqno{(Gr1)} 
$$
$$
xh(yx)(\lambda -x)^{-1}\rightarrow \lambda h(xy)(\lambda -x)^{-1}-h(xy)%
\leqno{(Gr2)} 
$$

$$
x^{-1}h(xy)(\lambda -x)^{-1}\rightarrow \lambda ^{-1}x^{-1}h(xy)+\lambda
^{-1}h(yx)(\lambda -x)^{-1}\leqno{(Gr3)}
$$
$$
(\lambda -x)^{-1}h(yx)(\lambda -x)^{-1}-(\lambda -x)^{-1}h(xy)(\lambda
-x)^{-1}\rightarrow \leqno{(Gr4)} 
$$
$$
\lambda ^{-1}(h(yx)(\lambda -x)^{-1}-(\lambda -x)^{-1}h(xy)) 
$$
$$
\mbox{\rm The\ rules\ (Gr0)\ through\ (Gr4)\ with\ $x$ and $y$ swapped.}%
\leqno{(Gr5-9)} 
$$

%Operators of the form $h(xy)$ arise, of course, in what is called the 
%\textit{functional calculus} of the operator $xy$. Examples are $%
%h(xy)=(1-xy)^{-1}$, $h(xy)=(1-xy)^{1/2}$ and $h(xy)=e^{xy}$ provided the
%eigenvalues of $xy$ are in the right location.

In the above list of rules, the expression on the left hand side of the rule
may not be a monomial. For example, see (Gr4) or set $h(z)=z+z^2$. It is
easier to automate replacement rules if the $LHS$ of a rule is a monomial.
When these rules are used for machine computation, they are rearranged,
using a term ordering, so that $LHS$ is a monomial.

This set of rules applies to many situations. Currently (RESOL) is
universally taught; (RESOL4) is called the resolvent identity. We also teach
students the extremely valuable rule 
$$
h(xy)x\rightarrow xh(yx)\,,
$$
but (GENR) is not taught. (GENR) is a short and powerful enough list of
rules that it could be used effectively in simplification by hand.

% ------- END NEW MAY 17th

%\subsection{Verification of GENR Rules}

It should be noted that it is easy to verify the
GENR Rules by hand so that they can be introduced
independent of the Gr\"obner Basis machinery.
%It is easy to check by hand that the (GENR) rules hold.
%for $\lambda\not=1$ and $\lambda\not=0$. 
For example, (Gr1) follows from (Gr0) by
multiplying (Gr0)
on both sides by $x^{-1}$ and the following calculation 
verifies (Gr3) using (RESOL) and (Gr1).
\begin{eqnarray*}
x^{-1} h(xy) (\lambda-x)^{-1}
&=&h(yx) x^{-1} (\lambda-x)^{-1}\\
&=&h(yx) (\lambda^{-1} x^{-1} \ + \ \lambda^{-1} (\lambda-x)^{-1}) \\
&=&\lambda^{-1} h(yx) x^{-1} \ + \ \lambda^{-1} h(yx) (\lambda-x)^{-1}
\end{eqnarray*}

\noindent
Of course, the verification of the GENR Rules is not the
crucial point. The point is that the GENR Rules are complete
in a sense to be discussed in 
\S \ref{subsection:endGENRdiscussion}.

%{\bf --------- ?? DELETE ---------
%
%The rules (RESOL) plus (GENR) are a GB in a sense which is
%conceptually different from what we have seen in
%the previous sections (as well as in earlier work in the GB literature).
%Roughly the idea is that these rules are valid for {\it every}
%analytic function $h$ and these  rules are a GB 
%\footnote{
%This is formalized by a 
%%e way in which this set of rules arose was from a 
%computation of a Gr\"obner basis in a related setting.
%A Gr\"obner basis can be found for polynomials in
%$x < y < x^{-1} < y^{-1} < (1-x)^{-1} < (1-y)^{-1} < S < T$
%%where $S$ and $T$ are variables and we take as starting
%relations the defining relations for the inverses and the
%relations $Sx = xT$ and $yS = Ty$ (see {\bf [HW]}). 
%For the case of $\lambda=1$, the (GENR) rules are obtained 
%by substituting $h(xy)$ for $S$
%and $h(yx)$ for $T$ in the Gr\"obner basis from {\bf [HW]}.}
%for the ideal of equations which are true for {\it every} $h$.
%This  is discussed more thoroughly in {\bf [HW]}. 


%On the other hand, this rule does not apply to all $h$.
%We think 
%of the expanded set as a complete set of 
%{\it universally applicable} rules. 
% \ From the rules (RESOL) and (GENR) we obtain, for each particular 
%analytic function $h$, an expanded set of rules:  we may replace 
%$h(xy)$ with $h(xy)^n$ and $h(yx)$ with $h(yx)^n$ for any 
%positive integer $n$; 
%and we may interchange $x$ with $y$. The rules obtained in this way are 
%all obviously valid. 

%However, when we pick a particular $h$,
%for example,  $h(xy) = (1-xy)^{-1}$, the replacement 
%rule $xyh(xy) \rightarrow h(xy) - 1$ is not a consequence of the rules in 
%the expanded set 
%(GENR) plus (RESOL) even though it holds for this particular $h$. 
%%A natural thing to try 
%Despite this
%we have found that extremely effective simplification can be 
%%performed just 
%%using the expanded set 
%obtained in practice by
%supplementing (GENR) plus (RESOL) with some of the 
%obvious rules for a particular $h$. 
%--------- END DELETE ---------
%
%\bigskip
%}
%

%That is, they are a GB in a certain rather elaborate sense which we 
%will not discuss in this paper.

%\subsection{Comparison of GENR with preNF}
%
%Of the 8 infinite families listed for preNF, we 
%find that I, IV, V, and VIII
%can be obtained from the GENR Rules 
%together with the RESOL Rules
%while the other 4 families cannot. 
%Here one
%makes the substitution
%$h(s) = (1-s)^{-n}$, so that $h(xy) = (1-xy)^{-n}$
%and $h(yx) = (1-yx)^{-n}$.
%%Thus
%%the first listed families must be consequences of 
%%just the relations (*) and
%%the defining relations for the inverses. 
%The remaining 4 families require
%the use of more particular properties of 
%$(1-xy)^{-1}$ and $(1-yx)^{-1}$.
%
%
%While this paper has not listed the NF rules,
%the NF Rules contain 16 infinite families.
%Eight of these infinite families follow from the GENR Rules
%together with the RESOL Rules.
%%These eight infinite families are $I$, $III$, $VI$,
%%$VIII$, $IX$, $XIV$ and $XVI$.
%
%Also, we mention that 
%some special relations in $(preNF)$ and
%$(NF)$
%can be obtained from the GENR Rules
%together with the RESOL Rules.
%
%%\textbf{?? If you sort out what happens for the special 
%%preNF relations,
%%that information can be included here.. }
%
%
\iffalse
%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Relation of GENR Rules to the GB for preNF}
\label{subsection:relationGENRpreNF}

Some of the eight infinite collections of polynomials from
Theorem \ref{thm:preNF} follow from $(GENR)$ 
%as indicated
%in the discussion which follows Theorem \ref{thm:preNF}
when one makes the substitutions
$h(xy) = (1-xy)^{-n}$ and
$h(yx) = (1-yx)^{-n}$.

Some of the polynomials in the basis for $(preNF)$ which
were not members of the eight infinite collection of
polynomials can also be derived from $(GENR)$. 
The first example is that $EB_{13}$ is a consequence of
$(Gr0)$ when the substitutions 
$h(xy) = (1-xy)^{-1}$ and
$h(yx) = (1-yx)^{-1}$ are made. (When the substitutions
$h(xy) = (1-xy)^{-n}$ and
$h(yx) = (1-yx)^{-n}$ are made into $(Gr0)$
for $n\ge 2$, one obtains
algebraic consequences of $EB_{13}$.) As a second example,
when the substitutions
$h(xy) = (1-xy)^{-1}$ and
$h(yx) = (1-yx)^{-1}$ are made into $(Gr1)$, then one obtains
the rule
\begin{equation}
\label{Gr1:rule}
(1-yx)^{-1} x^{-1} \rightarrow x^{-1}(1-xy)^{-1} \, .
\end{equation}
This rule is not a member of $(EB)$, since the leading term
of 
$EB_{10}$ is $x^{-1}(1-xy)^{-1}$. If one uses $EB_{10}$
to simplify (\ref{Gr1:rule}), then one obtains $EB_8$.
(When the substitutions
$h(xy) = (1-xy)^{-n}$ and
$h(yx) = (1-yx)^{-n}$ are made into $(Gr1)$ for $n\ge 2$, 
one obtains
algebraic consequences of (\ref{Gr1:rule}).)

Therefore, $(GENR)$ gives a template
for a subset of rules.

\fi

\subsection{Properties of GENR}
\label{subsection:endGENRdiscussion}

The rules $(RESOL)$ plus $(GENR)$ are a 
``complete" set of rules in a sense which is
conceptually different from a Gr\"obner Basis.
A major point is that these rules are valid for {\it every}
analytic function $h$. These  rules are a ``complete"
\footnote{
This is formalized by a 
%e way in which this set of rules arose was from a
computation of a Gr\"obner basis.
in a related setting.
A Gr\"obner basis can be found for polynomials in
$x < y < x^{-1} < y^{-1} < (1-x)^{-1} < (1-y)^{-1} < S < T$
where $S$ and $T$ are variables and we take as starting
relations the defining relations for the inverses and the
relations $Sx = xT$ and $yS = Ty$ (see {\bf [HW]})
which extract the algebraic essence of (\ref{eqn:analysisEss}).
For the case of $\lambda=1$, the (GENR) rules are obtained
by substituting $h(xy)$ for $S$  
and $h(yx)$ for $T$ in the Gr\"obner basis from {\bf [HW]}.}
set of rules 
in that they are  complete
for the ideal  generated by the key relations
on
$$
x,y,x^{-1},y^{-1},(\lambda-x)^{-1}, (\lambda-y)^{-1}, h(xy), h(yx)
$$
for {\it any} $h$ (which is analytic on the
spectrum of $xy$ and $yx$).
These key relations are 
\begin{eqnarray}
\label{eqn:analysisEss}
&&\mbox{the\ defining\ relations\ 
for\  the\  inverses\  $x^{-1}$,\  $y^{-1}$,\ 
$(\lambda-x)^{-1}$\ and\  $(\lambda-y)^{-1}$\
and}\\
&&
\nonumber
\mbox{the\ relations\
$h(xy)x - xh(yx)$\ and\ $h(yx)y - yh(xy)$.}
\end{eqnarray}
%on 
This  is discussed more thoroughly in {\bf [HW]}. 

\subsection{Using GENR with a particular functions $h$}

Now suppose we specialize to a particular $h$. 
If, for example, $h(z)=(1-z)^{-1}$, then we will have the 
same atomic expressions as we used in the
preNF situation. A major difference, however, is that 
in the preNF case we
added additional relations which come from the definition 
of $(1-xy)^{-1}$
and $(1-yx)^{-1}$. 
%In fact, the conditions (*) can be derived algebraically
%from these added conditions (they appear in the GB for preNF). 
We do not expect, nor do we find, that GENR embodies 
all the extra relations that may
hold for particular $h$. What we do expect is that GENR will provide a
useful set of easily implemented rules that at least provides simplification
in a general sense -- without using any special properties of a 
particular $h$.

%
%
% 
%%On the other hand, this rule does not apply to all $h$.
%%We think 
%%of the expanded set as a complete set of
%%{\it universally applicable} rules.
%% \ From the rules RESOL and GENR we obtain, for each particular
%%analytic function $h$, an expanded set of rules:  we may replace
%%$h(xy)$ with $h(xy)^n$ and $h(yx)$ with $h(yx)^n$ for any
%%positive integer $n$; 
%%and we may interchange $x$ with $y$. The rules obtained in this way are
%
%
%To further discuss the notion of completeness mentioned above,
%note that, for a function $h$ which is analytic on the
%spectrum of $x y$, 
%$
%h(xy)(1-xy)^{-1} - 1
%$
%need not be $0$ unless $h(z)= (1-z)^{-1}$. Therefore, the
%relation mentioned above could not appear on a list of
%relations which hold for a general $h$.
%As a consequence , if we wish to work with the  particular $h$,
% $h(xy) = (1-xy)^{-1}$, the replacement
%rule $xyh(xy) \rightarrow h(xy) - 1$ is not a consequence of the rules in
%the expanded set 
%$(GENR)$ plus $(RESOL)$ even though it holds 
%and is probably essential to our computations.

%\subsection{Comparison of GENR with preNF}

As an example, consider (preNF).

Of the 8 infinite families listed for preNF, we 
find that I, IV, V, and VIII
can be obtained from the GENR Rules 
together with the RESOL Rules
while the other 4 families cannot. 
Here one
makes the substitution
$h(s) = (1-s)^{-n}$, so that $h(xy) = (1-xy)^{-n}$
and $h(yx) = (1-yx)^{-n}$.
%Thus
%the first listed families must be consequences of 
%just the relations (*) and
%the defining relations for the inverses. 
The remaining 4 families require
the use of more particular properties of 
$(1-xy)^{-1}$ and $(1-yx)^{-1}$.


While this paper has not listed the NF rules,
the NF Rules contain 16 infinite families.
Eight of these infinite families follow from the GENR Rules
together with the RESOL Rules.
%These eight infinite families are $I$, $III$, $VI$,
%$VIII$, $IX$, $XIV$ and $XVI$.

Also, we mention that 
some special relations in $(preNF)$ and
$(NF)$
can be obtained from the GENR Rules
together with the RESOL Rules.

Even in situation besides (preNF) and (NF)
a natural thing to try 
is to supplement $(GENR)$ plus $(RESOL)$ with some of the
obvious rules for whatever particular $h$
you are using in your computations. 
We have found, in practice, that extremely effective
simplification can be done this way.
%Despite lack of definitive theory
%we have found that extremely effective simplification can in 
%practice be done this way.

%However, the bottom line is that $(GENR)$ gives a template
%for a subset of rules --- but it does not give a complete
%family for any particular $h$. It is useful for what it does
%--- but it doesn't do everything the GB technology does.



%{\bf
%
%\subsection{Genesis of the (GENR) Rules}
%
%{\bf BILL THINKS THIS SHOULD BE DELETED}
%
%We introduce variables $x<y<x^{-1}<y^{-1}<(1-x)^{-1}<(1-y)^{-1}<S<T$ and use
%the defining relations for the inverses together with the relations $Sx=xT$
%and $yS=Ty$. An infinite Basis was obtained and it was shown to be a
%Gr\"{o}bner Basis (see [HW] for details). This Basis has the property,
%however, the infinite families of rules involving $S^n$ and $T^n$ are all
%obtained by substituting $S^n$ for $S$, and $T^n$ for $T$ in a finite subset
%of the rules. This subset we have given as (GENR). We have replaced $S$ by $%
%h(xy)$ and $T$ by $h(yx)$. Since the starting relations hold in this
%setting, the (GENR) rules hold under the conditions above. Since $h(xy)^n$
%and $h(yx)^n$ also satisfy the starting conditions, all of the rules in the
%infinite family are subsumed. The (RESOL) rules together with (GENR) rules,
%if applied in this way to powers, give a set of rules which is complete in
%the sense that all algebraic consequences of our starting relations reduce
%to $0$.
%
%%It should be noted that it is also easy to verify the (GENR) rules by hand,
%%machinery. For example, the following calculation verifies (Gr3).
%%
%%\textbf{?? What are you taking as hypotheses here? Doesn't the first step
%%use Gr1 and the second RESOL?} 
%%\begin{eqnarray*}
%%x^{-1}h(xy)(\lambda -x)^{-1} &=&h(yx)x^{-1}(\lambda -x)^{-1} \\
%%&=&h(yx)(\lambda ^{-1}x^{-1}\ +\ \lambda ^{-1}(\lambda -x)^{-1}) \\
%%&=&\lambda ^{-1}h(yx)x^{-1}\ +\ \lambda ^{-1}h(yx)(\lambda -x)^{-1}
%%\end{eqnarray*}
%
%
%}
%
%
%%--- END NEW --- 
%
%\noindent
%
%\vskip 0.2 in
%
%%\end{document}
%
