\magnification=\magstep1
\centerline{SIMU 1999 - Gr\"obner Basis Seminar}
\centerline{Week 2 Discussions-Monomial Orders, Polynomial Division, 
Gr\"obner Bases}
\bigskip
\noindent
{\bf Day 1: Monomial Orders}
\bigskip
In class today, we introduced the definition of a {\it monomial order\/} in 
the polyomial ring $k[x_1,\ldots,x_n]$.  This was an ordering $>$ on the 
monomials $x^\alpha$ (or equivalently on the exponent vectors $\alpha$) such 
that:
\bigskip
\item{1)}  $>$ is a total (linear) order on vectors with nonnegative integer 
components. (This means that for every pair of monomials $x^\alpha$ and 
$x^\beta$, exactly one of the following is true:  either $x^\alpha > x^\beta$,
or $x^\alpha = x^\beta$, or $x^\beta > x^\alpha$.)
\item{2)}  For all $\alpha$, $\beta$, $\gamma$, we have
$$\alpha > \beta \Rightarrow \alpha + \gamma > \beta + \gamma$$
\item{3)}  $>$ is a well-ordering.  (In other words, every non-empty subset of 
monomials or exponent vectors has a smallest element under $>$).
\bigskip
\noindent
Today, we want to think about some of the implications of this definition.
\bigskip 
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  To practice with monomial orders, do Problems 1,2 from Chapter 2, 
\S 2 of ``IVA''.
\bigskip
\item{B)}  Show that in $k[x,y]$, the graded lexicographic and graded reverse 
lexicographic orders are the same.  Is this true for $n > 2$?
\bigskip
\item{C)}  Suppose we try to define an order $>$  by omitting the first part of 
the definition of  the graded lexicographic order, so that $\alpha > \beta$ if 
the rightmost entry in $\alpha - \beta$
is negative.  Do we get a monomial order?  Why or why not?
\bigskip
\item{D)}
We could also try to define an order $>_w$ by comparing the ``total weights'' 
of two monomials with respect to a given weight vector $w$ on the variables.  
That is, for a monomial $x^\alpha$, we think of the variable $x_i$ as having 
weight$w_i$ (from the vector $w$).  We compute
$\alpha\cdot w = \alpha_1 w_1 + \cdots + \alpha_n w_n$ and say 
$x^\alpha >_w x^\beta$ if $\alpha \cdot w > \beta\cdot w$.
\itemitem{1)}  Let $n = 2$ and $w = (3,5)$.  Is $>_w$ a monomial order?  
Why or why not?
\itemitem{2)}  Let $n = 2$ again and $w = (1,\sqrt{2})$.  Same question.
\bigskip
\noindent
{\it Challenge Question}
\bigskip
What property of the components of the vector $w$ would guarantee that $>_w$ 
{\it does} define a monomial order on $k[x_1,\ldots,x_n]$?   (The fact that 
$\sqrt{2}$ is not a rational number in part 2 of D is important, but it is not 
the whole story!)
\vfill\eject
\noindent
{\bf Day 2:  More on Monomial Orders}
\bigskip
\noindent
{\it Background}
\bigskip
In addition to the {\it lex, grevlex, grlex\/} orders we discussed in 
class, there are many other ways to define monomial orders as well.
The following construction gives a very general way to understand
the process.
\bigskip
\noindent
{\it Defining a Monomial Order by a Matrix}
\bigskip
\noindent
In the lab last time, we discussed the construction of 
{\it weight orders\/} $>_w$, where we compare two monomials $x^\alpha$ and
$x^\beta$ first by taking dot products
of their exponent vectors with a fixed {\it weight vector\/}
$w$, the ``break ties'' if $\alpha\cdot w = \beta\cdot w$
using another order.

Generalizing the weight orders $>_w$, we can also define monomial
orders on $k[x_1,\ldots, x_n]$ starting from any $m\times n$ matrix
$M$ with
\medskip
\item{$\bullet$} $m\ge n$,
\item{$\bullet$} ${\rm rank}(M) = n$,
\item{$\bullet$} all entries non-negative integers.  
\medskip
\noindent
(The same construction
also works for $M$ with non-negative real entries, but the 
{\tt Groebner} package will accept only integer entries, so we will 
not discuss that extension.)  Namely, suppose 
the {\it rows\/} of $M$ are the vectors $w_1,\ldots,w_n$.  Then we can compare 
monomials $x^\alpha$ and $x^\beta$ by first comparing their $w_1$-weights, 
then breaking ties sucessively with the $w_2$-weights, $w_3$-weights, and
so on through the $w_m$-weights.  In symbols:
$$\eqalign{x^\alpha &>_M x^\beta \Leftrightarrow
w_1\cdot \alpha > w_1\cdot \beta\cr
&\quad {\rm or}\ [(w_1\cdot \alpha = w_1\cdot \beta)
\ {\rm and }\ (w_2\cdot\alpha > w_2\cdot \beta)]\cr
&\quad {\rm or}\ [(w_1\cdot \alpha = w_1\cdot \beta)
\ {\rm and }\ (w_2\cdot\alpha = w_2\cdot \beta)\ {\rm and}\ (w_3\cdot\alpha >
w_3\cdot\beta)]\cr
&\quad {\rm or}\ \cdots\cr
&\quad {\rm or}\ [(w_1\cdot \alpha = w_1\cdot \beta)\ {\rm and}\ \cdots
\ {\rm and }\ (w_{m-1}\cdot\alpha = w_{m-1}\cdot \beta)\ {\rm and}\ 
(w_m\cdot\alpha > w_m\cdot\beta)]\cr} \eqno(1)$$
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)} Show that if the matrix $M$ satisfies
\itemitem{$\bullet$} $m\ge n$,
\itemitem{$\bullet$} ${\rm rank}(M) = n$,
\itemitem{$\bullet$} all entries non-negative integers
\item{} then (1) defines a monomial order $>_M$.  Be sure you see and
explain why the condition on the rank of$M$ is necessary. 
\bigskip
\item{B)}  All the monomial orders we will need 
can be specified as $>_M$ orders for 
appropriate matrices $M$.  For instance, show that the {\it lex} order 
with $x > y > z$ on ${\bf Q}[x,y,z]$
is defined by the identity matrix
$$M_1 = \pmatrix{1&0&0\cr
                 0&1&0\cr
                 0&0&1\cr}$$
Show that the {\it grevlex} order, with $x > y > z$,
 is defined by the matrix
$$M_2 = \pmatrix{1&1&1\cr
                 1&1&0\cr
                 1&0&0\cr}$$
(The same patterns work for polynomial rings in any
number of variables.)
\bigskip
\item{C)}The {\it grlex} (graded lex) order compares
monomials first by total degree (weight vector $w_1 = [1,1,1]$),
then breaks ties by the {\it lex order}.  This shows $>_{grlex} = >_M$
for the matrix
$$M_3 = \pmatrix{1&1&1\cr
                 1&0&0\cr
                 0&1&0\cr
                 0&0&1\cr}$$
Show that we could also use
$$M_3' = \pmatrix{1&1&1\cr
                  1&0&0\cr
                  0&1&0\cr}$$
That is, show the last row in $M_3$ is actually superfluous.
(Hint:  Making comparisons as in (1) when would we ever need
to use the last row?)
\bigskip
\item{D)}  In Maple, we can define monomial orders by this process,
but we must use {\it square\/} $n\times n$ matrices.   For instance,
to define a weight order with
$w = (2,4,8)$ and ties broken by {\it grevlex} with 
$x > y > z$, it is most natural to
use 
$$M = \pmatrix{2&4&8\cr
               1&1&1\cr
               1&1&0\cr
               1&0&0\cr}$$
But Maple will not accept this!  We need to pick
a set of $n=3$ linearly independent rows out of this matrix
$M$.  But which ones??  The choice of any three linearly
independent rows gives {\it some monomial order\/}, but it
may not be the one we want.  Here is an example.  Consider
the two matrices:
$$M' = \pmatrix{2&4&8\cr
                1&1&1\cr
                1&1&0\cr} \qquad
M'' = \pmatrix{2&4&8\cr
                1&1&1\cr
                1&0&0\cr}$$
(In $M'$ we have omitted the fourth row of $M$, while
in $M''$, we have omitted the third row of $M$.)  
\itemitem{1)}  Consider the monomials $x^2z^2$ and
$y^3z$.  Which is bigger under the matrix order $>_{M'}$?
Which is bigger under the matrix order $>_{M''}$?
Which should be bigger under the weight order $>_{w,grevlex}$
(comparing $w$-weights first, then breaking ties with 
$>_{grevlex}$)?  What does this say about the matrices
$M'$ and $M''$ -- which is the ``right'' $3\times 3$
matrix to use?
\item{2)}  Given an $m \times n$ matrix $M$ defining
an order $>_M$, describe a general method for picking 
the correct $n\times n$ submatrix $M'$ of $M$ to 
define the same order.
\bigskip
\noindent
{\bf Day 3:  The Division Algorithm in $k[x_1,\ldots,x_n]$}
\bigskip
\noindent
{\it Background}
\bigskip
Given a monomial order, polynomials $f_1,\ldots,f_s$ (the divisors), and another 
polynomial $f$, we have seen an algorithm for producing 
quotients $a_1,\ldots,a_s$ and remainder $r$ satisfying an equation:
$$f = a_1 f_1 + \cdots + a_s f_s + r,\leqno(*)$$
and the conditions that 
\item{1)} $multideg(a_i f_i) \le multideg(f)$ for all $i$ where $a_i \ne 0$, and 
\item{2)} no monomial in $r$ is divisible by any of the $LT(f_i)$.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  Do Problems 1,2 from Chapter 2, \S 3 of ``IVA'' individually and 
compare your results.
What does this say about the uniqueness of the quotients and remainders on 
division?  Explain carefully what they depend on.  
\item{B)}  Do Problem 9 from Chapter 2, \S 3 of ``IVA''.
\item{C)}  Do Problem 11 from Chapter 2, \S 3 of ``IVA''.  ({\it Suggestion:\/}  
The hardest part of this is probably just understanding what all of the notation 
means.  Try working out an explicit example
first, maybe with $f_1 = x^4 + x^2 y + y^3 + 1$, $f_2 = x^2 y - 3$, 
$f_3 = y^3 - 3y + 1$using the {\it lex} order with $x > y$, and $f = x^5$.  
Draw a picture in ${\bf Z}_{\ge 0}^2$ showing the sets $\Delta_i$ and $\Delta$, 
and verify that the conditions in part c are satisfied
for your quotients $a_i$ and your remainder.  Then think about what happens 
in division and work out the general proofs.)
\bigskip
\noindent
{\bf Day 4:  Gr\"obner Bases (Finally!)}
\bigskip
\noindent
{\it Background}
\bigskip
We have now seen the definition of a {\it Gr\"obner basis}.  Given an ideal 
$I \subset k[x_1,\ldots,x_n]$ and a monomial order $>$, a Gr\"obner basis for 
$I$ is a set of polynomials $\{g_1,\ldots,g_t\}$ with
the property that the leading terms of the $g_i$ generate the ideal of all 
leading terms of elements of $I$:  in symbols:
$$\langle LT(g_1),\ldots,LT(g_t)\rangle = \langle LT(I)\rangle.$$
Gr\"obner bases exist for all non-zero ideals because of the result we called 
Dickson's Lemma.  Recall the 
idea:  Every monomial ideal has a finite generating set.  So if we apply this 
to the monomial ideal
$\langle LT(I)\rangle$ and get a finite generating set 
$\{x^{\alpha(1)},\ldots, x^{\alpha(t)}\}$, then 
there are polynomials $g_i \in I$ with $LT(g_i) = x^{\alpha(i)}$ for all $i$, 
and the $g_i$ form a Gr\"obner basis for $I$ by the definition.  Next week, 
we will learn a criterion for when
a set is a Gr\"obner basis and an algorithm for finding them (both discovered 
by the Austrian mathematician Bruno Buchberger).  For now, we want to get a 
feeling for what the definition means.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
From Chapter 2, \S 5 of ``IVA'' do:
\item{A)}  Problem 5.  (This gives an alternate form of the condition defining 
a Gr\"obner basis that is sometimes useful.)
\item{B)}  Problem 6.  (This is probably the most useful property of Gr\"obner 
bases:  If $G$ is a Gr\"obner basis for $I$ and $f \in I$, then the remainder 
on division of $f$ by $G$ is guaranteed to be zero!)
\item{C)}  Problems 7, 8.  ({\it Suggestion:}  Try ``making'' some other 
polynomials in the ideals, and see if you can tell whether the condition
for Gr\"obner bases from problem 5 is always true.)
\bigskip
\noindent
{\it Challenge Question\/}
\bigskip
 Consider an ideal $I \subset k[u_1,\ldots,u_m,v_1,\ldots,v_n]$
for $n,m\ge 1$ generated by polynomials of the following form:
$$I = \langle v_1 - f_1(u_1,\ldots,u_m), \ldots, v_n - f_n(u_1,\ldots,u_m)\rangle$$
where the $f_i$ are arbitrary polynomials.  Show that the given generators form 
a Gr\"obner basis for $I$ with respect to some 
particular monomial order (which one?).  
\bye

