\magnification=\magstep1
\overfullrule=0pt
\centerline{SIMU 1998 - Gr\"obner Bases Seminar}
\centerline{Week 3 Discussions}
\bigskip
\noindent
{\it Day 1:  $S$-Polynomials and Buchberger's Algorithm}
\bigskip
The $S$-polynomial of two polynomials $f,g$ with respect to a monomial
order $>$ is defined in ``IVA'' as:
$$S(f,g) = {x^\gamma \over LT(f)} f  -  {x^\gamma \over LT(g)} g, $$
where $x^\gamma = LCM(LM(f),LM(g))$.  By Buchberger's Criterion, 
we know that $G = \{g_1,\ldots,g_t\} \subset I$ is a Gr\"obner basis
for $I$ if and only if 
$$\overline{S(g_i,g_j)}^G  = 0$$
for all pairs $(i,j)$ with $1 \le i < j \le t$.   

This gives the idea behind (I almost said ``the basis for'' (!)) an algorithm for 
computing Gr\"obner bases we discussed in class, starting from an 
arbitrary ideal basis $F=\{f_1,\ldots,f_s\}$ for $I$.  We start with $G = F$,  compute 
$S$-polynomial remainders, and adjoin any non-zero polynomials
we find to the set $G$.   This process is iterated until Buchberger's Criterion is 
satisfied, and we have a Gr\"obner basis.   The resulting algorithm is called
{\it Buchberger's Algorithm\/} for Gr\"obner bases.
\bigskip
\noindent
{\it  Discussion Questions}
\bigskip
\item{A)}  Let $f_1 = x^3y - x$ and $f_2 = y^2 - 1$.  
\itemitem{1)}  Is $\{f_1,f_2\}$ a Gr\"obner basis
for $I = \langle f_1,f_2\rangle$ with respect to the {\it lex} order, $x > y$?  Why or why 
not?  
\itemitem{2)}  Apply Buchberger's Algorithm to find a Gr\"obner basis for this
ideal.
\bigskip
\item{B)}  Pick a monomial order $>$, and let $f,g\in k[x_1,\ldots,x_n]$ be two polynomials such that
the leading coefficient in each is 1, and  
$LM(f)$ and $LM(g)$ are {\it relatively prime} (that is, the gcd of the leading monomials is 1).  
\bigskip
\itemitem{1)}  Show that in this situation 
$$S(f,g) = -(g - LT(g))f  + (f - LT(f))g$$
\itemitem{2)}  From part 1, show that $LT(S(f,g))$ is still divisible by either $LT(f)$ or $LT(g)$ (in fact
if we write $g - LT(g) = q$ and $f - LT(f) = p$, then show that $LT(S(f,g))$ is equal either to 
$-LT(f)LT(q)$ or to $LT(g)LT(p)$.  
\itemitem{3)}  Suppose we are performing Buchberger's Algorithm and we notice
that in our $F = (f_1,\ldots,f_s)$ two of the polynomials (say $f_i$ and $f_j$) have leading terms
that are relatively prime.  Does this mean that $\overline{S(f_i,f_j)}^F = 0$?  Why or why not?
 ({\it Be careful!})
\bigskip
\item{} It can be shown (even taking 3 into account), that in Buchberger's Algorithm,
 it is not necessary to check
that $\overline{S(f_i,f_j)}^F = 0$ whenever $LT(f_i)$ and $LT(f_j)$ are relatively
prime.  This leads to savings in computational effort in many examples!
\bigskip
\noindent
{\it Day 2:  Solving Systems of Equations}
\bigskip
Today, we want to begin looking at some of the (mathematical) applications of 
Gr\"obner bases.  Applications to other real world problems are often made by 
translating the question under consideration into a question about systems of polynomial
equations, then proceeding as below.
\bigskip
\noindent
{\it  Discussion Questions}
\bigskip
\item{A)}  Show that if $G = \{g_1,\ldots,g_t\}$ is a Gr\"obner basis for $I = \langle f_1,\ldots, f_s\rangle$,
then ${\bf V}(g_1,\ldots,g_t) = {\bf V}(f_1,\ldots,f_s)$ in $k^n$.
\bigskip
\item{B)}   Using Maple, I computed a Gr\"obner basis for the ideal $I = \langle x^2+y^2+z^2-4,xz - y, y^2 - z^2+1 \rangle$ with respect to the {\it lex} order, $x > y > z$, and found:
$$[2z^4-4z^2-1, y^2-z^2+1, x-2 y z^3+4yz]$$
What does this say about the number of points in the variety ${\bf V}(I)\in {\bf R}^2$?  What are those points?
\bigskip
\item{C)}  Let $V$ be a finite set in ${\bf R}^n$, and let $I = I(V) = \langle f_1,\ldots, f_s\rangle \subset {\bf R}[x_1,\ldots,x_n]$ be the ideal of all polynomials that are zero at all the points of  $V$. 
\bigskip
\itemitem{1)} Show that for each $i$, $1 \le i \le n$, $I$ must include polynomials $p_i$ that depend only 
on the variable $x_i$.
\itemitem{2)}  Explain why if we compute a Gr\"obner basis $G$ for $I$ with respect to a lex order with 
$x_i$ as the {\it last - i.e. smallest} variable, then $p_i(x_i)$ must appear in that Gr\"obner basis $G$.
\bigskip
\noindent
{\it Day 3:  The Implicitization Problem}
\bigskip
\noindent
Today, we will reconsider the implicitization problem for  polynomial parametric curves and surfaces.
Our goal is to show that any such curve or surface is (at least) contained in a variety.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
We consider parametric curves in the plane, given as $x = f(t), y = g(t)$, where $f(t),g(t) \in {\bf R}[t]$ first.  
\bigskip
\item{A)}  Show that for all $m \ge 0$, 
the total number of monomials $x^ay^b$ of total degree $a+b \le m$ is equal to the binomial
coefficient ${m + 2 \choose 2}$.  
\bigskip
\item{B)}  Show that if we substitute $x = f(t)$ and $y = g(t)$ into all of the monomials
$x^a y^b$ with $a + b \le m$, then for $m$ sufficiently large, we obtain a {\it linearly dependent}
collection of polynomials in $k[t]$.  
\bigskip
\item{C)}  Deduce from question B that every curve in ${\bf R}^2$ that is 
given by a polynomial parametrization $x = f(t)$, $y = g(t)$ is contained in ${\bf V}(F)$ for
some nonzero $F(x,y) \in {\bf R}[x,y]$.
\bigskip
\item{D)}  Generalize your arguments in questions A,B,C to show that every surface in 
${\bf R}^3$ with a polynomial parametrization $x = f(t,u), y = g(t,u), z = h(t,u)$ is
contained in ${\bf V}(F)$ for some nonzero $F(x,y,z) \in {\bf R}[x,y,z]$.
\bigskip
\noindent
{\it Day 4:  The ``Shape'' of the {\it lex} Gr\"obner basis for $I = {\bf I}(V)$
for a finite set}
\bigskip
Today, we want to try to put together a lot of what we have studied to 
answer the following question:
\bigskip
\noindent
{\it Let $V$ be a finite set in ${\bf R}^3$ which is in ``general position'' in
the sense that the $z$-coordinates of the points of  $V$ are distinct.  Let 
$I = {\bf  I}(V)$.  What does the Gr\"obner basis for $I = {\bf I}(V)$ 
with respect to the {\it lex} order, $x > y > z$ look like?}
\bigskip
\noindent
The answer is a result sometimes called the ``Shape Lemma''.    Some suggestions:  First note that the ``general position'' hypothesis is 
{\it not} satisfied, for instance, for the Gr\"obner basis from question B on 
Day 2(!) ({\it Why not?})
Then think about what part 2 of Question C from Day 2 tells you here.  You will
get one of the Gr\"obner basis elements that way.  Then, what do the others look
like?  For instance, is there a polynomial of the form $y - f(z)$ in the ideal (hence
in the first elimination ideal $I \cap {\bf R}[y,z]$?
Must it appear in the {\it lex} Gr\"obner basis?  If so, why?  Then, what about
polynomials involving  $x$?
\bye