\magnification=\magstep1
\centerline{Mathematics 392 -- Seminar in Computational Commutative Algebra}
\centerline{Lab Day 2/Problem Set 5 -- Gr\"obner Bases in Maple}
\centerline{September 29, 2006}
\bigskip
\noindent
{\it Background}
\bigskip
We have now seen the definition of a Gr\"obner basis for an 
ideal, with respect to a monomial order $>$.  Recall $G = \{g_1,\ldots,g_t\}$
is a Gr\"obner basis for $I$ if 
\bigskip
\item{$\bullet$}  All $g_i \in I$, and 
\item{$\bullet$}  $\langle LT_>(g_1),\ldots,LT_>(g_t)\rangle = \langle LT_>(I)\rangle$. 
(Equivalently, for every $f \in I$, $LT_>(f)$ is divisible
by $LT_>(g_i)$ for some $i$.)
\bigskip
\noindent
We will discuss an {\it algorithm}, called {\it Buchberger's algorithm}
for computing a Gr\"obner basis from any generating set of $I$ next week.
For now, let's just learn how to use Maple's implementation of that
algorithm, treating it as a sort of ``black box''. 
\bigskip
\noindent
{\it Maple's {\tt Groebner} package}
\bigskip
All the procedures dealing with monomial orders, the division algorithm,
Gr\"obner bases, etc. are contained in a package that you'll need to load 
first, with the command
\medskip
\centerline{\tt with(Groebner);}
\medskip
\noindent
(N.B. no umlauts in Maple, so the alternate English spelling is the
name of the command!) 

\bigskip
\noindent
{\tt NormalForm} -- {\it Remainder on Division}
\bigskip
The command that performs the division algorithm is called {\it NormalForm}.  
It returns only the {\it remainder on division}, which can be thought of 
as a sort of {\it normal, or reduced form} for the input polynomial
$f$ with respect to the divisor polynomials $f_1,\ldots,f_s$.
The format for the command is 
\bigskip
\centerline{\tt NormalForm(f,PList,monorder);}
\bigskip
\noindent
where {\tt f} is the polynomial you are dividing, {\tt PList}
is the list of divisors, and {\tt monorder} specifies the monomial 
order.  Almost any monomial order can be defined in Maple.  To 
get the two we will use today, use
\medskip
\item{$\bullet$} {\tt plex(x,y)} for the lexicographic order with $x > y$,
{\tt plex(y,x)} for lexicographic order with $y > x$, and similarly
if there are more than 2 variables.
\item{$\bullet$} {\tt tdeg(x,y)} is the graded reverse lex order
with $x > y$, {\tt tdeg(y,z,x)} would give graded reverse lex 
with $y > z > x$, and so forth.
\medskip
\noindent
For example, enter 
\medskip
\centerline{\tt PList:=[x\^{}2*y+x\^{}2+1,x\^{}3+x*y+2];}
\centerline{\tt f:=expand((x\^{}4*y+x\^{}2*y\^{}3)*PList[1]+y\^{}2*PList[2]);}
\centerline{\tt NormalForm(f,PList,plex(x,y));}
\medskip
\noindent
to divide 
$$f = (x^4y + x^2y^3)(x^2y + x^2 + 1) + (y^2)(x^3 + xy + 2)$$
by 
$$[f_1,f_2] = [x^2 y + x^2 + 1, x^3 + xy + 2],$$
using the lex order with $x > y$.  
{\it Question}:  What does the result say about $\{f_1,f_2\}$ as a set
of generators for the ideal $I = \langle f_1, f_2\rangle$.  
\bigskip
\noindent
{\tt Basis} -- Gr\"obner Basis Computation
\bigskip
The command for computing a Gr\"obner basis of an ideal generated
by a given list of polynomials is called {\tt Basis}.  The
format is 
\bigskip
\centerline{\tt Basis(Plist,monorder);}
\bigskip
\noindent
where {\tt Plist} is the list of generators for your ideal, and 
{\tt monorder} is the monomial order to be used.  Enter
\medskip
\centerline{\tt Blex:=Basis(Plist,plex(x,y));}
\medskip
\noindent
to compute the {\it lex} Gr\"obner basis for $I = \langle f_1,f_2\rangle$
as above ({\it lex} order with $x > y$).  
\bigskip
\noindent
{\it Questions}
\bigskip
\item{1.}  What is the monomial ideal $\langle LT_{>_{lex}}(I)\rangle$
here?  (Think of the definition of a Gr\"obner basis from last time.) 
How does this relate to the ideal 
$\langle LT_{>_{lex}}(f_1), LT_{>_{lex}}(f_2)\rangle$?
\item{2.}  Find the remainder on division of the polynomial $f$
from before with respect to {\tt Blex}.  Is this what you expect?  Why?
\item{3.}  Look carefully at the terms in the two polynomials in 
{\tt Blex}.  What do you notice?  If you were trying to determine
the points in the variety $V = {\bf V}(f_1,f_2)$, how would this
Gr\"obner basis help?  What would you do to find $V$?
\item{4.}  To carry out the process you described in 2 in Maple, 
you can solve a one-variable polynomial by an approximate numerical
method and find all its complex roots with a command like this:
\medskip
\centerline{\tt fsolve(Blex[1],y,complex);}
\medskip
\item{} Then substitute each $y$-value into the other equation
to find $x$.  Do this, then find all the points in $V = V(f_1,f_2)$.
Maple notes:
When you call the {\it lex} Gr\"obner basis {\tt Blex}, then 
{\tt Blex[1]} is the first polynomial in the basis, and {\tt Blex[2]}
is the second.  Look up the {\tt subs} command in the 
on-line help to see how 
to substitute a value into an expression like a polynomial, if you
haven't seen that before.  
\item{5.}  What happens if you compute a Gr\"obner basis for 
$I$, but with respect to a {\it lex order} with $y > x$?
Describe the form of the polynomials you get.  
\item{6.}  Now compute the Gr\"obner basis for the same $I$, but
with respect to the {\it grevlex} order with $x > y$.  
(Your results should be different!)  Does this Gr\"obner
basis have the same properties as the {\it lex} ones?
\item{7.}  What is the monomial ideal $\langle LT_{>_{grevlex}}(I)\rangle$?
(Try to determine the leading terms in the Gr\"obner basis elements
``by hand'' first; you can then check your work using the 
{\tt LeadingTerm} command from the {\tt Groebner} package.  Note:
If you call the {\it grevlex} Gr\"obner basis {\tt Bgrev}, then 
{\tt Bgrev[1]} is the first polynomial in the basis, {\tt Bgrev[2]}
is the second, and so forth.
\bigskip
\noindent
{\it Additional Problems}
\bigskip
Do the following problems from section 2.8, 
using Maple to 
carry out the necessary calculations.  Your worksheet(s) for
these computations, together with explanations, hand calculations
to set up the polynomials, etc. will be your problem set for 
the week.  
\item{$\bullet$} 2, 
\item{$\bullet$} 3 (``the method of Examples 2 and 3''
is essentially what we did in parts 3 and 4 above; it would 
be good to look over the calculations in the text too!), 
\item{$\bullet$} 8, 
\item{$\bullet$} 9 (it would be nice to include graphics illustrating 
the varieties from 8 and 9 -- see the help for 
{\tt plot3d} to see how to plot parametric curves and surfaces
in ${\bf R}^3$), 
\item{$\bullet$} 10
\bye
