\magnification=\magstep1
\noindent
Plan for PURE Math 2012 Seminar
\bigskip
\noindent
{\it Week 2}
\bigskip
\item{} Monday:  Polynomial division (Chapter 2, \S 3) -- put some discussion of 
monomial orders defined by matrices into Tuesday's discussion 
\item{} Tuesday:  Lecture on monomial ideals, Dixon's Lemma; discussion: more on monomial
orders (Chapter 2, \S 4) 
\item{} Wednesday: Definition of Gr\"obner bases (Chapter 2, \S\S 5,6) Buchberger's Algorithm (omit proof of Buchberger's $S$-pair Criterion) (Chapter 2, \S 7)
\item{} Thursday: First examples -- Elimination theory (Chaper 2, \S 8, Chapter 3, \S 1)
\vfill\eject
\centerline{PURE Math 2012 - Seminar}
\centerline{Week 2 Discussions - Polynomial Division, Gr\"obner Bases, First Applications}
\bigskip
\noindent
{\it Day 1:  The Division Algorithm in $k[x_1,\ldots,x_n]$}
\bigskip
\noindent
{\it Background}
\bigskip
Given a monomial order, polynomials $f_1,\ldots,f_s$ (the divisors), and another 
polynomial $f$, we have seen an algorithm for producing 
quotients $a_1,\ldots,a_s$ and remainder $r$ satisfying an equation:
$$f = a_1 f_1 + \cdots + a_s f_s + r,\leqno(*)$$
and the conditions that 
\item{1)} $multideg(a_i f_i) \le multideg(f)$ for all $i$ where $a_i \ne 0$, and 
\item{2)} no monomial in $r$ is divisible by any of the $LT(f_i)$.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  Do Problem 1 from Chapter 2, \S 3 of ``IVA'' individually and 
compare your results.
What does this say about the uniqueness of the quotients and remainders on 
division?  Explain carefully what they depend on.  
\item{B)}  Do Problem 9 from Chapter 2, \S 3 of ``IVA''.
\item{C)}  Problem 11 from Chapter 2, \S 3 of ``IVA''
\itemitem{1)}      
The hardest part of this is probably just understanding what all of the notation 
means.  Work out an explicit example
first.  Take
$$\eqalign{f_1 &= x^4 + x^2 y + y^3 + 1\cr
           f_2 &= x^2 y - 3\cr 
           f_3 &= y^3 - 3y + 1,\cr}$$
use the {\it lex} order with $x > y$, and divide $f_1,f_2,f_3$ into $f = x^5$.  
Draw a picture in ${\bf Z}_{\ge 0}^2$ showing the sets $\Delta_i$ and $\Delta$, 
and verify that the conditions in part c are satisfied
for your quotients $a_i$ and your remainder.  
\itemitem{2)}  Now work out the general proofs.  An important lesson here:
Never underestimate the power of working out examples to clarify things!  But
of course, the examples are not always the ultimate goal in mathematics since
we usually want to establish general statements!)
\bigskip
\noindent
{\it Day 2:  Dixon's Lemma, More on Monomial Orders}
\bigskip
\noindent
A)  Do Problem 4 in \S 4 of Chapter 2 to 
practice with ideas connected to Dixon's Lemma.
\bigskip
\noindent
The main portion of today's discussion is devoted to some
additional ideas related to monomial orders.
Besides the {\it lex, grevlex, grlex\/} orders we discussed in 
class, there are many other ways to define monomial orders.
The following construction gives a general way to understand
the process.
\bigskip
\noindent
{\it Defining a Monomial Order by a Matrix}
\bigskip
\noindent
We have discussed the construction of 
{\it weight orders\/} $>_w$, where we compare two monomials $x^\alpha$ and
$x^\beta$ first by taking dot products
of their exponent vectors with a fixed {\it weight vector\/}
$w$, the ``break ties'' if $\alpha\cdot w = \beta\cdot w$
using another order.

Generalizing the weight orders $>_w$, we can also 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
(The same construction also works for $M$ with non-negative real entries, but the 
{\tt GroebnerBasis} command in Mathematica will accept only rational entries in 
weight vectors, so we will 
not discuss that extension.)  Namely, suppose 
the {\it 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 through 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} \leqno(1)$$
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
All the monomial orders we will need 
can be specified as $>_M$ orders for 
appropriate matrices $M$.  
\bigskip
\noindent
B)
\bigskip
\item{1)} For instance, show that the {\it lex} order 
with $x_1 > \ldots > x_n$ on $k[x_1,\ldots,x_n]$
is defined by $M = I_n$, the $n\times n$ identity matrix.
\item{2)}  Show that the {\it grevlex} order, with $x > y > z$,
is defined by the matrix
$$M_{grevlex} = \pmatrix{1&1&1\cr
                 1&1&0\cr
                 1&0&0\cr}$$
(The same pattern works for polynomial rings in any
number of variables.)
\item{3)}  Negative entries can also appear in these 
matrices.  For instance, show that the {\it grevlex} order
with $x > y > z$ could also defined using
$$M_{grevlex} = \pmatrix{1&1&1\cr
                         0&0&-1\cr
                         0&-1&0\cr}$$
What is the corresponding matrix for the {\it grevlex}
order with $x_1 > x_2 > \cdots > x_n$?
\bigskip
\noindent
C) The {\it grlex} (graded lex) order in $k[x,y,z]$ compares
monomials first by total degree (weight vector $w_1 = [1,1,1]$),
then breaks ties by the {\it lex order}.  This shows $>_{grlex} = >_M$
for the matrix $M$ here:
$$M = M_{grlex} = \pmatrix{1&1&1\cr
                           1&0&0\cr
                           0&1&0\cr
                           0&0&1\cr}$$
Show that we could also use
$$M' = \pmatrix{1&1&1\cr
                1&0&0\cr
                0&1&0\cr}$$
That is, show the last row in $M$ is actually superfluous.
(Hint:  Making comparisons as in (1), when would we ever need
to use the last row?)
\bigskip
\noindent
D) Show that if the $m\times n$ matrix of rational numbers $M$ satisfies
\medskip
\item{$\bullet$} $m\ge n$,
\item{$\bullet$} ${\rm rank}(M) = n$ (the largest possible for a matrix
of this shape),
\item{$\bullet$} the uppermost nonzero entry
in each {\it column} (i.e. the first nonzero entry down from the top of the
column) is positive.
\medskip
\noindent
then (1) defines a monomial order $>_M$.  Be sure you see and
explain why the condition on the rank of $M$ is necessary. 
\bigskip
\noindent
E)  In Sage/Singular, we can define monomial orders by this process.   
For instance, to define a weight order with
$w = (2,4,8)$ and ties broken by {\it grevlex} with 
$x > y > z$, it might be most natural to use 
$$M = \pmatrix{2&4&8\cr
               1&1&1\cr
               1&1&0\cr
               1&0&0\cr}$$
But Singular requires an invertible square matrix
to define a monomial order.  So, we need to pick
a set of $n=3$ linearly independent rows out of this matrix
$M$.  But which ones??  The choice of any three linearly
independent rows gives {\it some monomial order\/}, but it
may not be the one we want.  Here is an example.  Consider
the two matrices:
$$M' = \pmatrix{2&4&8\cr
                1&1&1\cr
                1&1&0\cr} \qquad
M'' = \pmatrix{2&4&8\cr
                1&1&1\cr
                1&0&0\cr}$$
(In $M'$ we have omitted the fourth row of $M$, while
in $M''$, we have omitted the third row of $M$.)  
\medskip
\item{1)}  Consider the monomials $x^2z^2$ and
$y^3z$.  Which is bigger under the matrix order $>_{M'}$?
Which is bigger under the matrix order $>_{M''}$?
Which should be bigger under the weight order $>_{w,grevlex}$
(comparing $w$-weights first, then breaking ties with 
$>_{grevlex}$)?  What does this say about the matrices
$M'$ and $M''$ -- which is {\it not} the ``right'' $3\times 3$
matrix to use?
\item{2)}  Given an $m \times n$ matrix $M$ defining
an order $>_M$, describe a general method for picking 
the correct $n\times n$ submatrix $M'$ of $M$ to 
define the same order, and prove
that your method is correct.  
\bigskip
\noindent
{\it Day 3:  Gr\"obner Bases (Finally!)}
\bigskip
\noindent
{\it Background}
\bigskip
We have now seen the definition of a {\it Gr\"obner basis}.  Given an ideal 
$I \subset k[x_1,\ldots,x_n]$ and a monomial order $>$, a Gr\"obner basis for 
$I$ is a set of polynomials $\{g_1,\ldots,g_t\} \subset I$ with
the property that the leading terms of the $g_i$ generate the ideal of all 
leading terms of elements of $I$:  in symbols:
$$\langle LT(g_1),\ldots,LT(g_t)\rangle = \langle LT(I)\rangle.$$
Gr\"obner bases exist for all non-zero ideals because of the result we called 
Dickson's Lemma.  Recall the 
idea:  Every monomial ideal has a finite generating set.  So if we apply this 
to the monomial ideal
$\langle LT(I)\rangle$ and get a finite generating set 
$\{x^{\alpha(1)},\ldots, x^{\alpha(t)}\}$, then 
there are polynomials $g_i \in I$ with $LT(g_i) = x^{\alpha(i)}$ for all $i$, 
and the $g_i$ form a Gr\"obner basis for $I$ by the definition.  Soon, 
we will learn a criterion for when
a set is a Gr\"obner basis and an algorithm for finding them (both discovered 
by the Austrian mathematician Bruno Buchberger).  For now, we want to get a 
feeling for what the definition means.

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 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
\noindent
From Chapter 2, \S 5 of ``IVA'' do:
\item{A)}  Problem 5.  (This gives an alternate form of the condition defining 
a Gr\"obner basis that is sometimes useful.)
\item{B)}  Problem 6.  (This is probably the most useful property of Gr\"obner 
bases:  If $G$ is a Gr\"obner basis for $I$ and $f \in I$, then the remainder 
on division of $f$ by $G$ is guaranteed to be zero!)
\item{C)}  Problems 7, 8.  ({\it Suggestion:}  Try ``making'' some other 
polynomials in the ideals, and see if you can tell whether the condition
for Gr\"obner bases from Problem 5 is always true.)
\item{D)} 
Consider an ideal $I \subset k[u_1,\ldots,u_m,v_1,\ldots,v_n]$
for $n,m\ge 1$ generated by polynomials of the following form:
$$I = \langle v_1 - f_1(u_1,\ldots,u_m), \ldots, v_n - f_n(u_1,\ldots,u_m)\rangle$$
where the $f_i$ are arbitrary polynomials.  Show that the given generators form 
a Gr\"obner basis for $I$ with respect to some 
particular monomial order (which one?).  
\item{E)}   Let $f_1 = x^3y - x$ and $f_2 = y^2 - x$.  
\bigskip
\item{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$ or with
$y > x$?  Why or why not?  
\item{2)}  Apply Buchberger's Algorithm to find Gr\"obner bases for the ideal 
$I = \langle f_1,f_2\rangle$ first using the lex order with $x > y$, 
and second using the lex order with $y < x$.  Your
results should look quite different.
\bigskip
\noindent
{\it Day 4:  Elimination}
\bigskip
We have now seen the Elimination and Extension Theorems from Chapter 3, \S 1.  
The Elimination Theorem shows that lexicographic Gr\"obner bases systematically
eliminate variables ``as much as possible'' in the following sense.
\item{$\bullet$}  (Elimination Theorem)  Let $I$ be an 
ideal in $k[x_1,\ldots,x_n]$, and $G$ a Gr\"obner basis of $I$ with respect to
the {\it lex} order with
$x_1 > x_2 > \cdots > x_n$.  Let
$I_i = I \cap k[x_{i+1},\ldots,n]$ be the $i$th elimination ideal of $I$.  Then
$G_i = G\cap k[x_{i+1},\ldots,n]$ is a Gr\"obner basis of $I_i$ for each
$i$, $1 \le i \le n-1$.  
\item{$\bullet$}  The Extension Theorem then gives a condition under
which $(a_{i+1},\ldots,a_n) \in V(I_i)$ can be extended to 
$(a_i,a_{i+1},\ldots,a_n) \in V(I_i)$.  
\bigskip
\noindent
{\it  Discussion Questions}
\bigskip
\noindent
A)   Using Sage/Singular, 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 the output:
$$2z^4-4z^2-1, y^2-z^2+1, x-2 y z^3+4yz.$$
\bigskip
\item{1)}  Using the Elimination Theorem, give Gr\"obner bases
for the elimination ideals $I_1 = k[y,z]$ and $I_2 = k[z]$.
\item{2)}  What does the Extension Theorem 
say about the number of points in the variety 
${\bf V}(I)\in {\bf C}^2$?  What are those points?
\bigskip
\noindent
B)  In this problem, we will see reasons for some of the 
patterns you may have noticed in various examples.
Let $V$ be a finite set in ${\bf C}^n$ and let 
$I = {\bf I}(V) = \langle f_1,\ldots, f_s\rangle \subset {\bf C}[x_1,\ldots,x_n]$ 
be the ideal of all polynomials that are zero at all the points of  $V$. 
\bigskip
\item{1)} Show that for each $i$, $1 \le i \le n$, $I$ must include a
nonzero polynomial $p_i(x_i)$ that depends only on the variable $x_i$.
\item{2)}  Show that if we compute a Gr\"obner basis $G$ for $I$ with 
respect to a lex order $>_i$
with $x_i$ as the {\it last - i.e. smallest} variable, 
then $p_i(x_i)$ must appear in that Gr\"obner basis $G$.  (Hint:
If $c x_i^\alpha = LT_{>_i}(p_i(x_i))$ is the leading term of $p_i(x_i)$, then
some Gr\"obner basis element $g$ in $G$ must have a leading term (with respect
to this special {\it lex} order $>_i$ which divides $c x_i^\alpha$.
What does that say about the form of $g$?
\item{3)}  Let $V$ be a finite set in ${\bf C}^3$ which is in {\it ``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?  (How many polynomials
will it contain, what are their forms, etc.?)
\item{4)}  What would the corresponding statement be for finite $V$
in ``general position'' in ${\bf C}^n$ for general $n \ge 2$?
\bigskip
\noindent
{\it Additional Hints for 3 and 4}:   Note that the ``general position'' hypothesis is 
{\it not} satisfied, for instance, for the Gr\"obner basis from question B 
above ({\it Why not?})  Think about what part 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 C}[y,z]$? Must it appear in the {\it lex} Gr\"obner basis?  
If so, why?  Then, what about polynomials involving  $x$?  
The answer is a special case of a result sometimes called the ``Shape Lemma.''
\bye

