\magnification = \magstep1
\centerline{MATH 392 -- Seminar in Computational Commutative Algebra}
\centerline{Second Computer Laboratory Day}
\centerline{February 18, 2019}
\bigskip
\noindent
{\it Background and Goals}
\bigskip
Maple contains a package called {\tt Groebner} that contains facilities
for defining monomial orders, finding leading terms and monomials of
polynomials carrying out the division algorithm
in $k[x_1,\ldots,x_n]$, computing Gr\"obner bases, and related
computations.  Our lab session today will introduce you to
these facilities.  Some problems at the end will be part of
Problem Set 5, due Friday, February 22.  
\bigskip
\noindent
{\it The {\tt Groebner} Package}
\bigskip
Launch Maple (preferably in the worksheet interface), then 
enter the command
\medskip
\centerline{\tt with(Groebner);}
\medskip
\noindent
The output should be the list of commands in this new package:
{\tt [Basis, FGLM, HilbertDimension, etc.]}.  
\bigskip
\noindent
{\it Monomial Orders in Maple}
\bigskip
\noindent
Maple allows you to define all of the monomial orders we have
discussed in class (and many, many others too!).  
\medskip
\item{$\bullet$} Lex orders are obtained with the specification
{\tt plex(varlist)}, where {\tt varlist} is the list of 
variables in {\it decreasing order}.  For instance {\tt plex(x,y,z)}
gives a lex order with $x > y > z$.  
\item{$\bullet$} Graded lex orders are obtained with the 
specification {\tt grlex(varlist)}
\item{$\bullet$} Graded reverse lex orders are obtained wiht
the specification {\tt tdeg(varlist)}
\medskip
\noindent
These will be included in the commands for doing polynomial
division, computing Gr\"obner bases, etc. {\it as options}.
If you ever want to check what a leading term of a polynomial
is with respect to a given monomial order, the {\tt LeadingTerm}
command returns the leading coefficient and the leading monomial.
For instance, try
\medskip
\centerline{\tt LeadingTerm(6*x*y\^{}5 + x\^{}4*y,plex(x,y));}
\centerline{\tt LeadingTerm(6*x*y\^{}5 + x\^{}4*y,tdeg(x,y));}
\medskip
\noindent
Why are the results different?
\bigskip
\noindent
{\it Polynomial Division in Maple}
\bigskip
\noindent
The multivariable polynomial division algorithm we have discussed
is implemented in the Maple command {\tt NormalForm} from 
the {\tt Groebner} package.  The format is 
\medskip
\centerline{\tt NormalForm(poly,polylist,monomialorder);}
\medskip
\noindent
where {\tt poly} is the dividend polynomial, {\tt polylist} is the list of
divisors (in square brackets, separated by commas), and {\tt monomial order}
is one of the monomial orders discussed before (or any of the others
Maple ``knows'').  

Here's a worked example.  Suppose we want to divide $f = x^5 y + xy^4$ by 
$f_1 = x^3 y + 4y, f_2 = xy^2 - 3$ using the lex order with $x > y$.  
Enter the following commands one by 
one (and press ENTER to execute):
\medskip
\centerline{\tt f := x\^{}5*y + x*y\^{}4;}
\centerline{\tt f1 := x\^{}3*y + 4*y;}
\centerline{\tt f2 := x*y\^{}2 - 3;}
\centerline{\tt NormalForm(f,[f1,f2],plex(x,y));}
\medskip
\noindent
(You could also do this in one line by putting the expressions for the polynomials
directly into the {\tt NormalForm} command.)
The output is the {\it remainder on division}.  If you want to see the quotients
too (that is, the $a_i$ in the expression
$$f = a_1 f_1 + a_2 f_2 + r)$$
you can include the option {\tt 'Q'} in the {\tt NormalForm} command, then 
print out the value of {\tt Q} afterwards:
\medskip
\centerline{\tt NormalForm(f,[f1,f2],plex(x,y),'Q');}
\centerline{\tt Q;}
\medskip
The second command will show the quotients as a list of polynomials.  Try it!
\bigskip
\noindent
{\it Gr\"obner bases}
\bigskip
Recall from last Friday's class that a {\it Gr\"obner basis} for an ideal $I$
with respect to a monomial order $>$
is a finite collection of polynomials $G = \{g_1,\ldots,g_t\}$ with the property
that 
$$\langle LT_>(I)\rangle = \langle LT_>(g_1),\ldots,LT_>(g_2)\rangle.$$
Equivalently, 
\medskip
\centerline{\it For every element $f \in I$, $LT_>(f)$ is divisible by $LT(g_i)$ for some $1\le i \le t$.}
\bigskip
\noindent
{\it Gr\"obner bases in Maple}
\bigskip
The ``workhorse'' of the {\tt Groebner} package is the {\tt Basis} command, 
which computes a Gr\"obner basis for the ideal generated by a list
of polynomials with respect to a monomial order. The basic technique for
doing this is known as Buchberger's Algorithm.  (Technical Notes:  We'll see
what that means soon.  Also, the output
will actually be the {\it unique reduced Gr\"obner basis}; we'll learn what
that means later this week.)  The format is 
\medskip
\centerline{\tt Basis(polylist,monomialorder);}
\medskip
\noindent
For example, continuing the computation from before, enter
\medskip
\centerline{\tt B := Basis([f1,f2],plex(x,y));}
\medskip
\noindent
The output should show 
$$B := [4y^6 + 27, 9x + 4y^4]$$
(or something equivalent; Maple sometimes outputs the terms in polynomials in
different orders because the way it stores them internally involves some
randomness).    

As we will see, Gr\"obner bases for ideals have especially nice properties.
In particular when we divide by a Gr\"obner basis $G$ for $I$, we have
an {\it ideal membership test}:
$$f \in I {\rm\ if\ and\ only\ if\ the\ remainder\ on\ division\ by\ } G {\rm\ is\ } 0.$$
This is {\it not true for arbitrary bases of an ideal}(!).  For example, using the same $f_1,f_2$
as above, 
$$f = y \cdot f_1 - x^2\cdot f_2 = 3x^2 + 4y^2 \in I = \langle f_1,f_2\rangle.$$
However, what happens when we compute the remainder on division of $f$ by $f_1,f_2$?
What happens when we compute the remainder on division by the Gr\"obner basis {\tt B}
computed above?   
\bigskip
\noindent
{\it Problems}
\bigskip
\noindent
(A)  Lex Gr\"obner bases are especially nice for solving systems of polynomial
equations, or finding the points in a variety.  In this problem, you 
will consider ${\bf V}(x^2 y-z^3,2xy-4z-1,z-y^2)$ in ${\bf R}^3$.  
\item{(1)}  Compute a {\it lex} 
Gr\"obner basis (say with $x > y > z$) for the ideal
$I = \langle x^2 y-z^3,2xy-4z-1,z-y^2\rangle$, and call the Gr\"obner basis $H$.
\item{(2)} (You'll want to wait until after Wednesday's class (Feb. 20) to answer this one.)
Why is it true that setting the Gr\"obner basis polynomials equal to zero gives a 
system with the same set of solutions as the original equations
$$\eqalign{x^2 y - z^3 &= 0\cr
           2xy - 4z + 1&= 0\cr
           z - y^2 & = 0?\cr}$$
\item{(3)}  Identify a polynomial containing only $z$ in your $H$; it should
be the first polynomial in the list, or {\tt H[1]}. Solve the
equation obtained by setting that polynomial equal to zero
using the command {\tt rts:=fsolve(H[1],z,complex);} to find approximations
to all the complex roots.  (In the Maple output here $I$ is the imaginary unit $I = \sqrt{-1}$.) The {\tt fsolve} command
uses an approximate {\it numerical method} to solve equations.  You can pick out the individual
roots of the $z$ equation with {\tt rts[1]}, {\tt rts[2]}, ... , {\tt rts[7]}.  
\item{(4)} Then substitute each real root back into the system of equations (use the Maple {\tt subs} command --
see the online help for how this works) and solve them for the other variables, $y$ and $x$.  How many 
real solutions $(x,y,z)$ are there?
\bigskip
\noindent
(B)  Lex Gr\"obner bases are also especially nice for ``implicitizing'' parametric
equations.  For example, consider the surface with this parametrization:
$$\eqalign{x &= t + u\cr
           y &= t^2 + 2 t u\cr
           z &= t^3 + 3 t^2 u\cr}$$
(This is the union of all the tangent lines to the twisted cubic curve.)
\item{(1)}  Plot the surface using the {\tt plot3d} command.
\item{(2)}  Compute a Gr\"obner basis for the ideal 
$$I = \langle x - t - u, y - t^2 - 2 t u, z - t^3 - 3 t^2 u\rangle$$
with respect to a lex order with $t > u > x > y > z$.  There should 
be a polynomial in your basis that depends on $x,y,z$.  This gives an
implicit equation of a surface containing the image of the parametrization
mapping above.  What is this polynomial?
\item{(3)}  Use the {\tt implicitplot3d} command to plot the surface
defined by the polynomial you found in (2).  How is it related to 
the plot from (1)?
\bye



