Noncommutative Groebner Bases: Theory and Applications

Edward L. Green

%\footnotetext{1991 Mathematics Subject Classification.
%Primary 16W50; Secondary 16G20}}

\thanks{Partial support was received
from a grant from the National Science Foundation}

Department of Mathematics
Virginia Polytechnic Institute and State University
Blacksburg, Virgina USA


\section{Overview} The talk will be divided as
follows:

\begin{enumerate}
\item Brief introduction to noncommutative \grb bases.

\begin{enumerate}
\item Path algebras and admissible orders.

\item Definition of \grb bases.

\item Basic properties of \grb bases.

\item Construction of \grb bases.

\end{enumerate}
\item Applications of \grb bases.

\begin{enumerate}
\item Computational approach to ideal and module theory.

\item Projective resolutions.

\item Koszul algebras.

\item Poincar\'e-Birhkoff-Witt bases.
\end{enumerate}
\end{enumerate}



\section{Introduction to noncommutative \grb bases}

The theory
of noncommutative \grb bases can be applied to
the class of algebras called {\it path algebras}.
Let $K$ be a field which we fix for the remainder of the
talk.  Let $\G$ be finite directed graph (which, in the
representation theory of algebras is called a {\it quiver}).
The path algebra, denoted $K\G$, is the $K$-algebra
with $K$-basis the finite directed paths in $\G$.  The
multiplicative structure is induced by linearly extending
the following multiplication on the basis of paths.
Multiplication of paths is given by concatenation or
$0$.  That is, if $p$ and $q$ are finite directed paths
then
$$p\cdot q = \lbrace{\begin{array}{cc} pq &
\mbox{if the terminus vertex of }{p = }\mbox{ the
origin vertex of }q \\
0& \mbox{ otherwise.}\end{array}}$$

Note that the set of paths form a monoid with $0$
and that the path algebra is just the monoid algebra
(defined in a similar fashion as
a group algebra or semigroup algebra).
If $\G$ is the graph with one vertex $v$ and $n$ loops
at $v$, $x_1,\dots,x_n$, then it is not hard to see that
the path algebra $K\G$ is isomorphic to the free associative
algebra in $n$ noncommuting variables.  Hence the class of
path algebras includes free algebras.

For the theory of \grb bases we need an admissible order.
A well-order $<$ on the set of paths in $\G$ is called
an {\it admissible order} if satisfies the following
three conditions:

\begin{itemize}

\item[A1.] If $p,q,r$ are paths with $p<q$, then
$rp<rq$ if both $rp$ and $rq$ are nonzero.

\item[A2.] If $p,q,s$ are paths with $p<q$, then
$ps<qs$ if both $ps$ and $qs$ are nonzero.

\item[A3.] If $p,q,r,s$ are paths with $p=qrs$, then
$r <p$.

\end{itemize}

We will discuss some admissble orders such as the
length-lexicographic order, the
degree-reverse
lexicographic order and  the noncommutative lexicographic order.
We fix an admissible order $<$ on the paths of $\G$.
Every nonzero element, $x=\sum_{i=1}^n\alpha_ip_i$, of $K\G$
has a largest occuring path which we call the {\it tip of
$x$}. Thus $p_i =\tip(x)$ if $p_i \ge p_j$ for $j=1,\dots,n$.

Let $I$ be a (two-sided) ideal in $K\G$.  Let $\tip(I)
=\{p\,|\, p=\tip(x)$
\linebreak $ \mbox{for some } x\in I\}$.  Thus
$\tip(I)$ is the set of paths that are ``leading
terms'' of elements of $I$.  Let $\nontip(I)$ be set of
paths that are not in $\tip(I)$.   A {\it \grb basis
for $I$ with respect to $<$} is a set $\G$ of elements
of $I$ such that if $p\in \tip(I)$ then there is some
$g\in\G$ such that $\tip(g)$ divides $p$; we say the path
$q$ {\it divides } $p$ if
there exist paths $r$ and $s$ such that $p = rqs$.

For the remainder of the first part of my talk I will
describe some of the basic properties of \grb bases. These
include existence and construction of \grb
bases.  I will describe
the normal form of elements and why these forms are
fundamental
to computations using \grb bases.  Emphasis will
be placed on the fact that, as a $K$ vector space,
$K\G$ decomposes into $I\oplus \Span_K(\nontip(I))$.
For example, we show how
this decompostion implies the existence and
uniqueness of a reduced \grb basis, even if the \grb
basis is infinite.  The above decomposition is the
main idea in using \grb bases to study the quotient
ring $K\G/I$.  We will briefly address
the question of infinite versus
finite \grb bases will be addressed.

\section{Applications}

This part of my talk deals with some of
the applications that I have
given for \grb bases.  I begin by discussing how the theory
of \grb bases can be used in the study ideals and modules.
The existence of normal forms, which is
a consequence of the vector space decomposition of $K\G$
described above, plays a fundamental role in this
application.  After discussing other ways of employing
the theory,
such as the computation of module bases and of hom-sets,
I will show how \grb bases can be used
to produce projective resolutions of modules.

Let $K\G$ be a path algebra and give each
arrow in $\G$ a positive weight.  This provides $K\G$ with
a nonnegative ${\bf Z}$-grading with paths being
homogeneous elements.  Suppose that $I$ is
an ideal in $K\G$ which
is generated by homogeneous elements in this grading.
Then the quotient ring $\LL = K\G/I$ inherits a  positive
grading.  We say $\LL$ is a {\it Koszul algebra} if
itS cohomology ring $\Ext^{*}_{\LL}(\LL/\br,\LL/\br)$
is generated in degrees $0$ and $1$, where $\br$ is the
graded Jacobson radical of $\LL$.  Koszul algebras have
appeared in topology, algebraic geometry and in the
theory of quantum groups.

We briefly describe the following two results.

\begin{thm}(G.-Huang) Suppose that the reduced \grb
basis of $I$ is composed of linear combinations of
paths of length exactly $2$.  Then $K\G/I$ is a Koszul
algebra.  \end{thm}



\begin{thm} Suppose that $I$ is generated by linear combinations
of paths of length at most $2$ (and $<$ is the length-lexicographic
order).  Then $K\G/I$ has a PBW basis if and only if there
is \grb basis of $I$ consisting of elements which are
linear combinations of paths of length at most $2$. Hence,
if $I$ is generated by linear combinations of paths of
length $2$ and $\LL =K\G/I$ has a PBW basis, then $\LL$
is Koszul algebra.
\end{thm}