\magnification = \magstep1
\centerline{SIMU 1998--Gr\"obner Bases Seminar}
\centerline{Week 3 Computer Laboratory Exercises}
\bigskip
\noindent
{\bf Background and Goals}
\bigskip
This week, 
we will work through examples of 
Buchberger's Algorithm for Gr\"obner bases using new functions from 
the {\tt Groebner} package, and then introduce the full implementation
of that algorithm in the {\tt gbasis} command.
\bigskip
\noindent
{\bf Lab Work}
\bigskip
We have now seen the definition of a Gr\"obner basis for an ideal
$I \subset k[x_1,\ldots, x_n]$  (with respect to a given monomial order)
-- it is a collection of polynomials $g_1,\ldots, g_t \in I$ such
that the monomial ideals $\langle LT(I)\rangle$
and $\langle LT(g_1),\ldots,LT(g_t)\rangle$ are equal (or equivalently,
such that the leading term of every $f \in I$ is divisible by 
$LT(g_i)$ for some $1 \le i \le t$).  Specifying the monomial order is 
necessary, of course, to identify the leading terms.  A Gr\"obner basis 
for $I$ with respect to one monomial order will rarely be a Gr\"obner basis
for $I$ with respect to a ``randomly chosen'' second monomial order too.

Today, we want to consider
whether or not given sets of generators for an ideal are Gr\"obner bases
and do some examples related to Buchberger's Criterion:

\bigskip
\noindent
{\it $G = \{g_1,\ldots,g_t\} \subset I$ is a Gr\"obner basis for $I$
if and only if the $S$-polynomial remainder $\overline{S(g_i,g_j)}^G$
is equal to zero for all $1\le i < j \le t$.}
\bigskip
\noindent
We will also consider the Buchberger Algorithm.

The building blocks we will need are the computation of $S$-polynomials
and the remainder computation we used before with {\tt normalf}.
The command for $S$-polynomial calculation in the {\tt Groebner}
package is called {\tt spoly} (note the lower-case s).  The format is
\medskip
\centerline{\tt spoly(p,q,monomialorder);}
\medskip
\noindent
where $p$ and $q$ are the polynomials, and {\tt monomialorder} is
specified as before.  One important thing to note here:  The $S$-polynomial
computed by Maple will only agree with the results of the formula
in ``IVA'' up to a non-zero constant multiple.  This is because 
Maple's command is set up {\it not to introduce denominators\/}
when the coefficients of the original polynomial are integers.  In 
other words, the result computed by the command 
{\tt spoly(p,q,monomialorder);} is 
$${\rm lcm}(LT(p),LT(q))\cdot \left({1\over LT(p)}\cdot p - 
{1\over LT(q)}\cdot q
\right)$$
(where the lcm includes the lcm of the integer coefficients as well).
For example, the Maple command
\medskip
\centerline{\tt spoly(3*x*y - x,4*y\^{}2 - 1,plex(x,y));}
\medskip
\noindent 
produces output 
$$ -4 x y + 3 x $$
which is different than what you would get using the formula in ``IVA'':
$$S(3xy-x,4y^2-1) = {y\over 3}(3xy-x) - {x\over 4}(4y^2-1) = {-1\over 3}xy + {1\over 4}x$$
The two results differ by a factor of $12$.  This does not affect the usability
of Maple's result in any way though (it is another {\it implementation choice}, 
made to avoid potential ``blow-ups'' in the amount of space needed to store the 
coefficients in complicated polynomials).  
\bigskip
\noindent
{\it Exercise 1}
\bigskip
\item{a)} Verify by Buchberger's Criterion that $G = [x+z^3,y-z^7]$ is a Gr\"obner
basis for the ideal it generates with respect to the {\it lex} order, $x > y > z$.
\item{b)}  Divide $f = xy$ by $G$ and also by $G' = [y-z^7,x+z^3]$ (reversing
the order of the divisors) using 
the {\tt DivQuots} procedure from last week.  Are 
the remainders the same?  Are the quotients the same?  
\bigskip
\noindent
{\it Exercise 2}
\bigskip
Do problem 9, parts a,c from Chapter 2, \S 6 of ``IVA''.
\bigskip
\noindent
{\it Buchberger's Algorithm}
\bigskip
The Buchberger Criterion we quoted above leads directly to the rudimentary 
algorithm for computing a Gr\"obner basis of an ideal with respect to 
a given monomial order discussed in Chapter 2, \S 7 in ``IVA''.  The 
idea is to compute $S$-polynomials of all pairs of polynomials from the list
we start with, take the remainders of those $S$-polynomials 
on division by the current list of polynomials, adjoin any non-zero remainders 
to the list, and repeat until no more changes occur (that is, until all the 
remainders are zero).  To get a feeling for how this actually works before we 
start letting Maple do {\it all the work\/} for us, we want to do a few 
examples of this ``by hand'' as in Example 1 from \S 7 of Chapter 2.
\bigskip
\noindent
{\it Exercise 3}
\bigskip
Verify that all the necessary $S$-polynomial remainders are 
in fact zero in the final list of polynomials from Example 1 in \S 7 of Chapter 2.
\bigskip
\noindent
{\it Exercise 4}
\bigskip
Do problem 2, parts a and b from that section.
\vfill\eject
\noindent
{\it Exercise 5}
\bigskip
Develop a Maple procedure to perform the ``basic'' Buchberger
algorithm presented in Theorem 2 of Chapter 2, \S 7.  Use
the {\tt ExtEuc} and {\tt DivQuots} procedures as models
for the Maple syntax.  You can also consult the Maple
``programming primer'' in the file {\tt f:/users/simu/Little/primer.mws}
as a reference.
\bigskip
\noindent
{\it ``The Big Guns'': The {\tt gbasis} Command}
\bigskip
In realistic examples, doing Buchberger's Algorithm ``by hand'', or even
by a procedure implementing the rudimentary form of the algorithm 
from Theorem 2 of \S 7 of Chapter 2, would be hopelessly slow.  Fortunately, 
numerous improvements have been made (see the optional \S 9 from Chapter 
2 of ``IVA'' if you are interested in learning more about some of them) 
and implemented in the {\tt gbasis} command of Maple (and similar packages
for other computer algebra systems such as {\it Mathematica}, Axiom, REDUCE, etc.)
\bigskip
\noindent
{\it The {\tt gbasis} Command}
\bigskip
The ``workhorse'' of the {\tt Groebner} package is the {\tt gbasis} command, 
which computes (up to constant multiples) the unique {\it reduced Gr\"obner
basis\/}
of the ideal generated by a given collection of polynomials with respect to 
a given monomial order.  Reduced Gr\"obner bases $G = \{g_1,\ldots,g_t\}$ are ones in which 
the leading terms form a minimal set of generators for $\langle LT(I) \rangle$, 
and in each $g_i$, there are no terms divisible by the $LT(g_j)$ for $j \ne i$.
In other words, the $g_i$ are ``inter-reduced''.  The format is 
\medskip
\centerline{\tt gbasis(Plist,monomialorder);}
\medskip
\noindent
where $Plist$ is a list of polynomials, and monomialorder is defined as before.
For example, 
\medskip
\centerline{\tt gbasis([x*y + y + 1,x*y\^{}2 - 2*x + 1],plex(x,y));}
\medskip
\noindent
produces the output
$$[-3 y - 2 + y^3  + y^2 , 2 x - 1 + y^2  + y]$$
which is (up to constant multiple of the second polynomial) the reduced
{\it lex} Gr\"obner basis for the ideal generated by the original 
two polynomials ($x > y$).

(One comment:  The polynomials in $Plist$ can contain {\it other variables\/}
besides the ones set up in the definition of the polynomial ring, and/or the 
definition of the monomial order.  If that is true, then those additional variables
are treated as symbolic parameters in the coefficients.  For example
\medskip
\centerline{\tt gbasis([x*y + y + a,x*y\^{}2 - 2*x + 1],plex(x,y));}
\medskip
\noindent
produces the output:
$$[y^3  + y^2 a - 3 y - 2 a, 2 x + y^2  + a y - 1]$$
This raises an important and interesting question -- can we always substitute
constant values for $a$ into the general form of the Gr\"obner basis to 
obtain the basis for the corresponding ideal with constant coefficients?  It
worked here, but for example, suppose you had a symbolic parameter appearing
in a leading term, and you substituted the value zero.  What would happen then??)
\bigskip
\noindent
{\it A ``Sampler'' of Applications}
\bigskip
\noindent
{\it Exercise 6 -- Ideal Membership}
\bigskip
Do problem 1 from Chapter 2, \S 8 of ``IVA''. 
\bigskip
\noindent
{\it Exercise 7 -- Solving Systems of Equations}
\bigskip
\noindent
\item{a)} Find the points in ${\bf V}(x^2 y-z^3,2xy-4z-1,z-y^2)$
in ${\bf R}^3$.  Suggestions:  Compute a {\it lex} 
Gr\"obner basis (say with $x > y > z$), and call the Gr\"obner basis $H$.
Identify a polynomial containing only $z$ in your output; 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 fsolve(H[1],z,complex);} to find approximations
to all the complex roots.  The {\tt fsolve} command
uses an approximate {\it numerical method} to solve equations.  Then 
substitute each real root back into the other equations (use {\tt subs} --
see the online help) and solve them for the other variables.
\item{b)} Do problem 4 from Chapter 2, \S 8 of ``IVA''.  (The system here has
the first three polynomials the same as the three polynomials in part a, plus
an additional fourth polynomial.)  What does the Gr\"obner basis
computation tell you here?
\bigskip
\noindent
{\it Exercise 8 -- Implicitization of Parametric Curves and Surfaces}
\bigskip
\item{a)}  Problem 7, Chapter 2, \S 8 of ``IVA''.
\item{b)}  Problem 8, Chapter 2, \S 8 of ``IVA''.
\item{c)}  Problem 9, Chapter 2, \S 8 of ``IVA''.  
\item{d)}  Generate a composite graphics image showing the parametric curve
from problem 9, and an implicit plot of the surface from problem 8.  How
does this relate to your answer to part c of Problem 9?
\bigskip
\noindent
{\it ``Extra Credit'': Exercise 9 -- Identities}
\bigskip
Do problem 11, Chapter 2, \S 8 of ``IVA''.
\bye


