\magnification = \magstep1
\centerline{SIMU 1999--Gr\"obner Bases Seminar}
\centerline{Week 2 Computer Laboratory Exercises}
\bigskip
\noindent
{\bf Background and Goals}
\bigskip
This week, we will begin to work with some of the commands in 
the {\tt Groebner} package of Maple, which will be one of our main
tools for the remainder of the Institute.  This package is new 
in Release 5 of Maple.  It represents a big advance (both in flexibility
and in performance) over the previous Gr\"obner basis package (called
{\tt grobner})!  The old package is still distributed with Maple, so 
do not get confused if you see both names.  We want the {\tt Groebner}
package.
\bigskip
\noindent
{\bf Days 1,2:  New Maple Data Structures, Defining Monomial Orders}
\bigskip
Before we start in with the {\tt Groebner} package, we need to take
a bit of time and look at some new ways of {\it structuring information\/}
in Maple.  
\bigskip
\noindent
{\it Lists or Vectors}
\bigskip
To represent points in affine space, we use coordinate vectors.  The
same idea is also useful to represent any {\it ordered collection\/} of 
information.  In Maple, these ordered collections are called {\it lists}.
A list is indicated by a pair of {\it square brackets\/} ([,]) enclosing
the items in the list, separated by commas.  For instance, the input line
\medskip
\centerline{\tt list1 := [a,b,c,d,e];}
\medskip
\noindent
creates a list with five items (the letters $a,b,c,d,e$, treated as symbolic
variables) and assigns the list to the name {\tt list1}.  We have said
that lists are {\it ordered\/}.  What this means, for instance, is that
{\tt alist} above is {\it different from\/} the list
defined by {\tt list2 := [a,d,c,e,b];}.  You can test this by entering
the definition of {\tt list2}, then the command
\medskip
\centerline{\tt evalb(list1 = list2);}
\medskip
\noindent
(The $=$ is the comparison operator -- not assignment; the {\tt evalb}
function returns a true or false (``$\underline{b}$oolean'') value indicating 
whether the two lists are equal.)

A list can 
have any number of items, including {\it no items} at all -- the empty list 
is written as {\tt []}.  The same item can also occur at several places
in a list (unlike the case for a {\it set}, which is an unordered
collection of information with no repetitions.  Sets can also be
defined and manipulated in Maple.  The notation for a set is 
{\tt $\{$item1,item2, ... itemn$\}$ }).

The items in a list can be any legal Maple objects -- constants, variables,
polynomials, expressions, other lists, ... .  For example, in many 
of our calculations, we will be dealing with lists of polynomials
in a ring $k[x_1,\ldots,x_n]$.  We will think of these as particular
lists of generators for ideals $I \subset k[x_1,\ldots,x_n]$.
For example,
\medskip
\centerline{\tt Id := [x\^{}3-y\^{}2+2*y,x*y-y-4*z,z\^{}4-1];}
\medskip
\noindent
would be one way to represent the ideal
$$Id = \langle x^3 - y^2 + 2y, xy - y - 4z,z^4-1\rangle,$$
(recall that the ideal contains all the polynomials
$$g_1\cdot(x^3 - y^2 + 2y)+g_2\cdot(xy - y - 4z)+g_3\cdot(z^4-1)$$
for $g_1,g_2,g_3\in {\bf Q}[x,y,z]$.
The list notation will parallel our notation from class for the ideal 
generated by a given set: $I = \langle f_1,\ldots,f_s\rangle$.

The items in a list {\it do not\/} all have 
to be items of the same {\it type}.  For instance, another perfectly OK 
Maple list is the following:
\medskip
\centerline{\tt list3 := [[a,b,c],d,e];}
\medskip
\noindent
where there are three items in all.  (The first list
item in {\tt list3} is the list {\tt [a,b,c]}, and the second and third 
items are the symbolic variables $d,e$.)

\bigskip
\noindent
{\it Some useful list operations}
\bigskip
\item{$\bullet$}  The built-in function {\tt op} returns the items in 
a list, separated by commas, in the order they appear in the list.
\bigskip
\noindent
This is particularly useful for manipulations of lists such as 
adding new entries.  For instance, enter the command
\medskip
\centerline{\tt list1 := [op(list1),f];}
\medskip
\noindent
What this does is as follows:
\medskip
\item{1)} first, the {\tt op} function returns the items from the 
{\it ``old''\/} {\tt list1}.
\item{2)} second, the new item $f$ is appended to the end after a new
comma
\item{3)} third (since the right hand side is in a new set of square brackets),
a new list is created containing the old entries from {\tt list1} and the 
new one  
\item{4)} finally, the new list is assigned back to the name {\tt list1}.
(When this is done the old value of {\tt list1} is ``erased''.)
\bigskip
\noindent
Additional commands:
\bigskip
\item{$\bullet$} The built-in {\tt nops} function returns the number of 
items in a list.  (If one of the items is a list itself, it is counted
as a single item.)
\item{$\bullet$} To pick out the $i$th item in a named list (like {\tt list1}), 
you can use either the notation {\tt list1[i]}, or {\tt op(i,list1)}.
\item{$\bullet$}  You can also pick out a consecutive sublist -- the items in 
the slots numbered {\tt first} to {\tt last} -- from 
a list by using the format {\tt list1[first..last]}.  This gives
a list as output.  The alternate form
{\tt op(first..last,list1)} gives the items in that part of the list.
\bigskip
\noindent
{\it Exercise 1}
\bigskip
\noindent
Explain, and give examples showing:
\bigskip
\item{a)}  how to append a new item at the {\it start\/} of a list
\item{b)}  how to create a list containing the entries of a given
list, followed by a second copy of that same list
\item{c)}  how to select the {\it last\/} item in a list (without
counting the number of items yourself!)
\item{d)}  how to insert a new item as the third entry from 
the start in a list
(assuming it has at least two entries to begin with)?  Be careful to 
test your idea on lists with two and with more than two entries!
\bigskip
\noindent
{\it Matrices}
\bigskip
If we think of a list as a row vector, then it is natural to think
of a list of lists (all of the same size) as a way to represent a 
{\it matrix\/}.  We can do this in Maple as well, as a basic way to 
deal with square or more general rectangular matrices.  For example,
\medskip
\centerline{\tt mat:=[[x,y],[u,v]];}
\medskip
\noindent
creates a list of two row vectors, or a $2\times 2$ matrix.  To select the
entry in row $i$ and column $j$ from a matrix defined this way, we could
use, for instance {\tt mat[i][j]}  ({\tt mat[i]} is the $i$th row, so
{\tt mat[i][j]} is the $j$th entry in that row).
\bigskip
\noindent
{\it First Steps with the Groebner Package}
\bigskip
{\it All the commands in the {\tt Groebner} package are accessible if (and 
only 
if) you have loaded the package in your current Maple session, using
{\tt with}.}

\bigskip
\noindent
{\it Monomial (or Term) Orders}
\bigskip
Although it is not strictly necessary for many things, it 
makes sense to get in the habit of starting a session
with the {\tt Groebner} package by defining the polynomial ring you 
want to work in.  This is done by first loading another package called
{\tt Ore\_algebra}, then defining the polynomial ring using the
{\tt poly\_algebra} command.  (The {\tt Ore\_algebra} package
gives a way to work in a fairly extensive class of possibly noncommutative
rings, which are defined by specifying commutation laws between the generators
of the ring over the field of constants.  For polynomial
rings, the commutation law is as simple as possible:  $xy - yx = 0$
for all $x,y$.  A version of Gr\"obner basis theory is 
valid in all of these rings.)
For example to define the ring ${\bf Q}[x,y,z]$ you would use:
\medskip
\centerline{\tt with(Ore\_algebra);}
\centerline{\tt ring := poly\_algebra(x,y,z);}
\medskip

As we have seen in class, the first step toward Gr\"obner bases is defining
various orders on the monomials in several variables.  The Groebner package
has a completely general way to do this, and also several simplified
predefined special cases for you to use.  For example:
\bigskip
\item{$\bullet$} the {\it lexicographic} order in $k[x_1,\ldots,x_n]$
with 
$$x_1 > x_2 > \cdots > x_n$$
is represented by {\tt plex(x1, ... , xn)}.  (Note: The ordering of 
the variables is determined by the order in which you list
them inside the {\tt plex()}.  Also, you cannot use
the dots in actual commands; you need to list out all the variables
explicitly.)
\item{$\bullet$} the {\it graded reverse lex order} in 
$k[x_1,\ldots,x_n]$ with 
$$x_1 > x_2 > \cdots > x_n$$
is represented by {\tt tdeg(x1, ... , xn)}.
\item{$\bullet$} From discussion, we know that one can also
define monomial
orders in $k[x_1,\ldots,x_n]$ called {\it weight orders}, $>_w$.
We compare two monomials $x^\alpha$ and
$x^\beta$ first by taking dot products with a fixed {\it weight vector}
$w$, then ``breaking ties'' using another order $>_\sigma$.  That is
$$x^\alpha >_w x^\beta \Leftrightarrow
w\cdot \alpha > w\cdot \beta\ {\rm or}\ [(w\cdot \alpha = w\cdot \beta)
\ {\rm and}\ (x^\alpha >_{\sigma} x^\beta)]$$
This type of order is represented in Maple by 
\medskip
\centerline{\tt wdeg([w1, ..., wn],[x1, ... ,xn])}
\medskip
\noindent
The $>_\sigma$ order here is the (non-graded) {\it reverse lex}
order:  $\alpha >_\sigma \beta$ if in $\alpha - \beta$, the 
rightmost non-zero element is negative.  (This is not a monomial
order itself, but it can be used to break ties here; do you see
why?)  Note: the weights and 
variables are vectors (lists) in this form.  The {\it weight vector 
always comes first\/}, and its entries must be integers. 
\bigskip
\noindent
To actually define termorders on the polynomial ring {\tt ring}
defined above, you can enter the following commands ({\tt termorder}
is one of the {\tt Groebner package commands})
\medskip
\centerline{\tt MO1 := termorder(ring,plex(x,y,z));}
\centerline{\tt MO2 := termorder(ring,plex(y,z,x));}
\centerline{\tt MO3 := termorder(ring,tdeg(x,y,z));}
\centerline{\tt MO4 := termorder(ring,wdeg([2,4,8],[x,y,z]));}
\medskip
\noindent
Then {\tt MO1} and {\tt MO2} are two different {\it lex} orders, 
{\tt MO2} is the {\it grevlex} order with $x > y > z$, and 
{\tt MO4} is the weight order $>_w$ for $w = [2,4,8]$.
\bigskip
\noindent
{\it The Leading Monomial of a Polynomial}
\bigskip
The {\tt leadterm} function in the {\tt Groebner} package selects the 
leading monomial in a polynomial according to a specified order.
Its format is {\tt leadterm(poly,order);}.  There is a very similar
command called {\tt leadmon} as well.  The output of {\tt leadmon}
will be a pair of values, first the constant leading coefficient
of the polynomial, then after a comma, the actual leading monomial.
(Note that the author of the {\tt Groebner} package uses the opposite 
terminology for ``terms'' and ``monomials'' from what we did in IVA!  For
them, a ``term'' always has coefficient 1 and a monomial can have any 
coefficient $c \in k$.)
\bigskip
\noindent
{\it Exercise 2}
\bigskip
Using each of the four monomial orders defined above, find the leading 
monomial of 
$$ p(x,y,z) = x^3 z - 5 xyz^3 + 7 y^5 - 3 x^2 y^4 $$
and verify your results by hand.
\bigskip
\noindent
{\it Defining a Monomial Order by a Matrix}
\bigskip
\noindent
In discussion today, we saw that we can
generalize the weight orders $>_w$, to 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
Namely, suppose 
the 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 until 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} $$
All monomial orders can be specified as $>_M$ orders for appropriate 
matrices $M$.  
\bigskip
\noindent
To define a matrix order in the Maple {\tt Groebner} package, we enter 
a command like this
\medskip
\centerline{\tt MO := termorder(ring,'matrix'(M,varlist));}
\medskip
\noindent
(single quotes around the word {\it matrix\/}).
The matrix $M$ itself is entered as a list of lists as defined above, either
first in a command assigning the matrix to a name, or else
directly in the {\tt termorder} command.  The {\tt varlist} is the 
list of variables.  The ordering you give here will correspond to
the ordering of the components in the exponent vectors.
For example, if for some reason we did not want to use the 
builtin {\it lex} order, we could define something equivalent
on ${\bf Q}[x,y,z]$ using 
\medskip
\centerline{\tt MO := termorder(ring,'matrix'([[1,0,0],[0,1,0],[0,0,1]],[x,y,z]));}
\bigskip
\noindent
{\it Exercise 3}
\bigskip
What matrix would define the weight order 
{\tt MO4} on ${\bf Q}[x,y,z]$
defined above?  Create an appropriate matrix term order in Maple, and test 
it by finding the leading term of $f = x y^4 z + 4z^4$, and a polynomial
of your choice.  (You will need to think about how to get a 
square $3\times 3$ matrix to represent computing $[2,4,8]$-weights
first, then breaking ties with the non-graded reverse lex order).
\bigskip
\noindent
{\it Additional Examples of Monomial Orders}
\bigskip
Exercises 10 and 12 from Chapter 2, \S 5 of ``IVA'' contain two additional
important examples of monomial orders -- the {\it product\/} orders, 
and Bayer and Stillman's {\it elimination\/} orders.
\bigskip
\noindent
{\it Exercise 4}
\bigskip
\noindent
Let $R = {\bf Q}[x_1,x_2,x_3,y_1,y_2,y_3,y_4]$.
\bigskip
\item{a)} Using the matrix order setup from the {\tt Groebner} package, 
determine how to define a mixed order $>_{mixed}$ on $R$ where
$$x^\alpha y^\beta >_{mixed} x^\gamma y^\delta \Leftrightarrow 
x^\alpha >_{lex} x^\gamma\ {\rm or}\ ((x^\alpha = x^\gamma)\ {\rm and}\ 
(y^\beta >_{grevlex} y^\delta)).$$
(Hint: Think of making the matrix from ``blocks'' like the ones above.)
\item{b)} Using the {\tt Groebner} package,
determine how to define the elimination order $>_3$ from Exercise 12.
\bigskip
\noindent
{\bf Days 3,4: The Division Algorithm in $k[x_1,\ldots,x_n]$}
\bigskip
In these labs we will want to use Maple to work out some examples with
the division algorithm for multivariable polynomials.  The 
{\tt Groebner} package contains a command called {\tt normalf}
which computes the remainder on division of a given polynomial $f$
by a list of polynomials $f_1,\ldots, f_s$.  Unfortunately, the
quotients $a_i$ in the expression 
$$f = a_1 f_1 +\cdots + a_s f_s + r$$
are not saved or displayed.  

To see the quotients on division, we
will need to use a ``home-grown'' version of division called
{\tt DivQuots} that follows the algorithm in Chapter 2, \S 3 of ``IVA''
exactly.  (NOTE: This uses several functions from 
the {\tt Groebner} package, so you should {\it also} load
that if you want to do division with quotients.)
We have mentioned before that Maple actually
contains a fully-developed built-in {\it programming language}, including
comparisons, loops, etc.  This means that (if necessary) it is 
possible to write programs, or {\it procedures} in Maple to make new
commands not part of the basic system available to users.  The
{\tt DivQuots} procedure we will use is such a case.  We will actually
look at the Maple code next week.  For now, let's just use this
new command.


In order to use it, 
you will need to read in the Maple code for the procedure from the 
class network drive.  You do this in a Maple worksheet by entering the
command
\medskip
\centerline{\tt read `f:/users/simu/Little/dq.map`;}
\medskip
\medskip
So that you can have a copy of this to use whenever you want, you can
also ``drag and drop'' the icon for the file dq from this directory to 
your own network directory.  You will probably also want to keep this
on one of your diskettes if you want access to it at Palmas.
\noindent
The format of {\tt DivQuots} is 
\medskip
\centerline{\tt DivQuots(f,Plist,MO);}
\medskip
\noindent
where $f$ is the dividend polynomial, $Plist$ is the list of divisors
(a list of polynomials), 
and $MO$ is the monomial order you want
use to pick out leading terms in the division process,
defined according to the rules discussed above for monomial orders
in the {\tt Groebner} package.  $Plist$ is a Maple {\it list} -- the 
ordering is important!

The output of DivQuots consists of two parts.  First, comes 
the list of quotients.  Following that comes the remainder.  
If you assign the output of DivQuots to a name, for example:
\medskip
\centerline{\tt 
dq:=DivQuots(x\^{}5+x\^{}3*y*z+1,[3*x\^{}2+x*y+1,x*z-y+z],plex(x,y,z));}
\medskip
\noindent
then {\tt dq[1]} is the list of quotients (so {\tt dq[1][2]})
is the quotient corresponding to the second divisor), and {\tt dq[2]} 
is the remainder.  The quotients and the remainder will, in general, 
depend on the monomial order you are using.  For example, compare the 
output of the command above with the output of 
\medskip
\centerline{\tt
DivQuots(x\^{}5+x\^{}3*y*z+1,[3*x\^{}2+x*y+1,x*z-y+z],wdeg([1,8,1],[x,y,z]));}
\medskip
\noindent
{\it Exercise 5}
\bigskip
Check that both sets of output are correct.  (How?  Recall the 
quotients $a_1,\ldots,a_s$ and the remainder $r$ are supposed
to satisfy $f = a_1f_1 + \cdots + a_s f_s + r$, the leading term of 
each of the $a_i f_i$ is supposed to be less than or equal to the 
leading term of $f$ in the given order, and no term in $r$ is 
supposed to be divisible by any leading term of one of the $f_i$.)
\bigskip
\noindent
{\it Exercise 6}
\bigskip
We did problems 1 and 2 from Chapter 2, \S 3 of ``IVA'' in discussion.
Check your work using Maple.
\bigskip
\noindent
{\it Exercise 7}
\bigskip
Do problems 5-8 in Chapter 2, \S 3 of ``IVA''.
\bigskip
\noindent 
Note: The built-in {\tt normalf} command in the {\tt Groebner} package
only computes a remainder on division (no quotients).  Its format is 
\medskip
\centerline{\tt normalf(f,Plist,MO);}
\medskip
\noindent
where $f$, $Plist$, and $MO$ are as above for the {\tt DivQuots} 
procedure. 
\bye

