\subsubsection{Ordering}
\label{suborder}

We will now formalize the notion of simplicity.
This amounts to ordering the terms
occurring in the polynomial expressions
which arise in a particular problem. An ordering
determines which term of a polynomial is the 
leading term and hence the $LHS$ and $RHS$ of
the associated replacement rule. In this section we
will choose an ordering so that terms lower in the
order are those which one would intuitively regard as simpler.
With this choice, the replacement rules do replace more complicated
expressions by simpler ones.

Many choices of ordering are possible.
In part II we will see some examples which show that the
size of the Gr\"obner Basis (the ``complete set of rules")
can be affected by changes in ordering of terms.

Let us consider polynomials in an ordered
alphabet of noncommuting variables. For simplicity,
we will start with polynomials in the letters 
$a$, $b$, $c$, $\ldots$ with the natural ordering
$a<b<c<\ldots$. A polynomial is a sum of terms of
the form $\lambda N$ where $\lambda$ is a number
(the coefficient) and $N$ is a ``word"
in the letters. We put an ordering on terms by
ordering the words.

\begin{defin}
If $M$ and $N$ are two words, we say that $M<N$
if either length$(M) <$ length$(N)$ or
$M$ comes before $N$ in the dictionary.
\end{defin}

The ordering described above is called the 
graded lexicographic ordering.


%Now we describe
%how one formalizes the notion of complicated verses simple.
%As already explained this amounts to 
%imposing an ordering on the monic monomials which
%occur in your problem. We shall only permit
%certain types of ordering
%in our theory. {\BF The choice of ordering effects
%not only which term of a polynomial will be considered
%the leading term, but also how large a set the 
%``complete sets of rules'' discussed in the last subsection
%are. In fact, as will be mentioned in sections 5 and 6,
%in some examples, by using one order, a finite ``complete set of rules"
%can be found, but with an other order, every
%complete set of rules must be infinite.}

%Since monomials are special cases of polynomials
%any ordering we impose on the polynomials induces one on the
%monomials.

%Let $M$ and $N$ be words in an ordered alphabet
%\footnote{In Example \ref{example:1pt7}, the ordered
%alphabet consists of the `letters' $x$, $x^{-1}$ and
%$(1-x)^{-1}$ with the order $x<x^{-1}<(1-x)^{-1}$.
%A word in this ordered alphabet is a product of letters
%with repetitions in any order
%(e.g, $x (1-x)^{-1} x x x^{-1}$ is a word).  
%A monomial is the product of a scalar and a word.
%}.
%We say 
%that
%the $M \le N$ if and only if 
%$$
%\mbox{either\ }  \mbox{length}(M) < \mbox{length}(N)$$
%\mbox{or\ length}(M) = \mbox{length}(N)
%and $M$ would come before $N$ in a dictionary based on this
%ordered alphabet.      
%
%This is  called {\it \BF graded  lexicographic ordering} 
%of the words.

%We begin with two examples of graded lexicographic 
%orders.

\begin{example}
\label{example:1pt5} 
{ \rm
If $a<b<c$ then the monomials of degree $3$ are ordered
$$\matrix{aaa<aab<aac<aba<abb<abc<aca<acb<acc<baa<bab<\hfill\cr
bac<bba<bbb<bbc<bca<bcb<bcc<caa<cab<cac<cba<\hfill\cr
cbb<cbc<cca<ccb<ccc\hfill\cr}$$
These are all taken to be bigger than any monomial of degree 2.
}
\hfill\endproof
\end{example}

It will be convenient for us to talk about
polynomials in symbols like $x$, $y$, $(1-xy)^{-1}$, etc.
In spite of the notation, these symbols are treated
as if they were letters. The definition given for
ordering of terms becomes meaningful as soon as we give
an ordering to the symbols. Thus if we declare that
$x<y<(1-xy)^{-1}$, an ordering is induced on the
terms of polynomials in these symbols.


%The ordering this imposes on polynomials goes as follows:

%We now can define  $f < g$. We put the terms of these polynomials in 
%decreasing order  $f = f_1 + \cdots + f_s$, $ g = g_1 + \cdots + g_t$.  
%We will say that $f < g$ if the order of $f_i$ and the order of $g_i$ are the same for 
%$i=1,\ldots,(a-1)$ but $fa < ga$. We will regard $f$ as simpler than $g$ 
%if $f < g$ in 
%this order. 

%%Another example is

\begin{example}
\label{example:1pt6}
{\rm
Lets us write a graded lexicographic order 
down for the case where there are
three symbols $x$, $y$ and $(1-xy)^{-1}$. 
Let us take
the ordering on degree one monomials to be
$$x < y < (1-xy)^{-1}$$
This plays the role of alphabetical order in the lexicographic order.
It naturally induces the order
$$
xx\,
\,<xy\,
<\,x(1-xy)^{-1}\,
<\,yx\,
<\,yy\,
<\,y(1-xy)^{-1}\,
<\,
$$
$$(1-xy)^{-1} x \,
<\,(1-xy)^{-1} y\,
<\,(1-xy)^{-1} (1-xy)^{-1}
$$
on degree 2 monomials and similarly induces an order
%by analogy 
on degree 3 monomials, etc.
}
\hfill\endproof
\end{example}

%In this paper, the {\BF only orderings} considered are
%graded lexicographic. 
%This is the ordering we use to 
%convert  equations to rules. 
%Namely, in any equation 
%put the highest order monomial on the $LHS$ of the rule
%so that it gets replaced by the negation of the
%sums of lower order monomials.
%The reason we insist on having a  total order is to rule out the possibility of
%infinite cycles where one makes one replacement and 
%a few steps later reverse
%it and then repeat.

%Every polynomial $f$ is a sum of monomials 
%{\BF 
%Note for WAVRIK: f is a sum of weighted monic monomials.
%The order is on the monic monomials, not the 
%monomials (with coefficients). How to state this
%elegantly??)
%}
%Exactly one of the
%monomials is largest in the order. We call this the leading term of $f$ and 
%denote it $LT(f)$.

%Another way to view this is by saying that our rules push the more 
%complicated elements to the right of a monomial,
%for example,
%$aab < baa$
%will generate rules with the property
%$baa \rightarrow aab + ...$.
