\magnification = \magstep1
\centerline{PURE Math 2012 Seminar}
\centerline{Week 2 Computer Laboratory Exercises}
\bigskip
\noindent
{\it Background and Goals}
\bigskip
This week, we will begin to work with some of the commands
related to monomial orders and computing Gr\"obner bases
in Sage.    Note: this time the lab problems
you are to submit are ``sprinkled through'' the 
discussion, marked {\it Exercise 1}, {\it Exercise 2}, and 
so forth.
\bigskip
\noindent
{\it Days 1,2: Lists, Defining Monomial Orders, Polynomial Division}
\bigskip
Before we start in with the division algorithm, we need to take
a bit of time and look at some of the details of {\it lists\/}
in Sage.  
\bigskip
\noindent
{\it Lists and Vectors}
\bigskip
To represent points in affine space, we use coordinate vectors.  The
same idea is also useful to represent any {\it ordered collection\/} of 
information.  In Sage, these ordered collections are called {\it lists},
and the elements of a list can be {\it anything}.
A list is indicated by a pair of {\it square brackets\/} ([,]) enclosing
the items in the list, separated by commas.  For instance, the input line
\medskip
\centerline{\tt list1 = ['a','b','c','d','e'] }
\medskip
\noindent
creates a list with five items (the letters $a,b,c,d,e$, treated as character strings,
not as symbolic variables), 
and assigns the list to the name {\tt list1}.  We have said
that lists are {\it ordered\/}.  What this means, for instance, is that
{\tt alist} above is {\it different from\/} the list
defined by {\tt list2 = ['a','d','c','e','b']}.  You can test this by entering
the definition of {\tt list2}, then the command
\medskip
\centerline{\tt list1 == list2}
\medskip
\noindent
(The $==$ is the comparison operator -- not assignment; it 
returns a True or False value indicating 
whether the two lists are identical.)

A list can 
have any number of items, including {\it no items} at all -- the empty list 
is written as {\tt []}.  The same item can also occur at several places
in a list (unlike the case for a {\it set}, which is an unordered
collection of information with no repetitions). 

The items in a list {\it do not\/} all have 
to be items of the same {\it type}.  For instance, another perfectly OK 
Sage list is the following:
\medskip
\centerline{\tt list3 = [['a','b','c'],'d','e'] }
\medskip
\noindent
where there are three items in all.  (The first list
item in {\tt list3} is the list {\tt ['a','b','c']}, and the second and third 
items are the character strings {\tt 'd','e'}.)
\vfill\eject
\noindent
{\it Some useful list operations}
\bigskip
\item{$\bullet$} The built-in {\tt len} function returns the number of 
items in a list.  (If one of the items is a list itself, it is counted
as a single item.)
\item{$\bullet$} To pick out the $i$th item in a named list (like {\tt list1}), 
you can use the notation {\tt list1[i]}.  Caution:  Lists are always
numbered starting from $0$.  So {\tt list1[1]} is actually the {\it second} element(!)
\item{$\bullet$}  You can also pick out a ``slice'' or consecutive sublist -- the items in 
the slots numbered {\tt first} to {\tt last - 1} -- from 
a list by using the format {\tt list1[first:last]}.  This gives
a list as output.  
\item{$\bullet$}  The {\tt append} operator inserts a new entry at
the end of a list.  Try {\tt list1.append('k')} to see the result.
\item{$\bullet$}  Sage has an interesting feature called ``tab-completion''
that can be used as a quick reference tool.  Try entering {\tt list1.}
and then press the TAB key.  You should see a listing of different
ways the partial command could be completed.  
\bigskip
\noindent
{\it Tuples and sets}
\bigskip
Sage also has data types called {\it tuples} and {\it sets}.  A tuple
is similar to a list, but once it is created it cannot be changed (it is 
{\it immutable}).  A set is an unordered list.  You can find information
about these in the online tutorials and manual.
\bigskip
\noindent
{\it Exercise 1}
\bigskip
\noindent
Explain, and give examples showing:
\bigskip
\item{a)}  how to insert a new item at the {\it start\/} of a list
\item{b)}  how to create a list containing the entries of a given
list, followed by a second copy of that same list
\item{c)}  how to insert a new item as the third entry from 
the start in a list
(assuming it has at least two entries to begin with)  Be careful to 
test your idea both on lists with two and with more than two entries!
\bigskip
\noindent
{\it Note:}  There are other builtin list commands not discussed
above.  Some of these tasks may be covered by one of them, but
they can also be done using the commands above.  

\bigskip
\noindent
{\it Matrices in Sage}
\bigskip
If we think of a list as a row vector, then it is natural to think
of a list of lists (all of the same size) as a way to represent a 
{\it matrix\/}.  We can do this in Sage as well, as a basic way to 
deal with square or more general rectangular matrices.  For example,
\medskip
\centerline{\tt mat = [[1,2],[3,4]] }
\medskip
\noindent
creates a list of two row vectors.   This can also be
thought of as a $2\times 2$ matrix, but Sage will not see it that
way unless we explicitly say
\medskip
\centerline{\tt Mat = Matrix(mat); Mat}
\medskip
\noindent
Now you will see something like the stacked matrix format as the output.  

To select the
entry in row $i$ and column $j$ from a matrix defined this way, we could
use, for instance {\tt Mat[i,j]}.  Rows and columns are also numbered starting
from 0.  In the list-of-lists form we would use {\tt mat[i][j]} -- here 
{\tt mat[i]} is the $i$th row, so
{\tt mat[i][j]} is the $j$th entry in that row.

\bigskip
\noindent
{\it Working in Sage/Singular}
\bigskip
Note:  From now on, we will essentially be using Sage as an 
interface to Singular (a package for computational commutative
algebra, algebraic geometry, and singularity theory).  There
are several ways to do this, giving progressively more direct 
access to the underlying functionalities of the Singular system. 
But by far the easiest way to get
started is to use Sage-level commands for defining polynomial
rings, ideals, and then computing Gr\"obner bases, etc.  This
has the advantage that the output of the commands will be
Sage objects of types we can predict (rather than Singular objects).     

\bigskip
\noindent
{\it Monomial orders in Sage/Singular}
\bigskip
To set up Sage to do computations in a polynomial ring 
with a specified collection of variables, using a particular 
monomial order, we can use the {\tt Polynomial Ring} command
seen earlier, but include an option that specifies a 
particular monomial order to be used for all operations 
involving that information in that ring.  For example,
to set up a ring in 4 variables $x,y,z,w$ with coefficients
in ${\bf Q}$ and the 
lex order with $x > y > z > w$ we could say
\medskip
\centerline{\tt R.<x,y,z,w> = PolynomialRing(QQ,order='lex')}
\medskip
\noindent
Other builtin options for defining orders include:
\medskip
\item{$\bullet$} {\tt 'deglex'} for the graded lex order
\item{$\bullet$} {\tt 'degrevlex'} for the graded reverse lex order
\item{$\bullet$} {\tt 'wdegrevlex'}  for the order $>_{w,grevlex}$ defined by comparing 
monomials with a positive integer component weight vector $w$ first, breaking
ties with graded reverse lex.  Here is an example showing the syntax for the
monomial order specification using the weight vector $w = (4,3,2,1)$ of length 4 
(the number of variables):
\medskip
\centerline{\tt S.<x,y,z,w> = PolynomialRing(QQ,order=TermOrder('wdegrevlex',(4,3,2,1)))}
\medskip
\item{$\bullet$} Sage also has a completely general way to specify monomial orders
using matrices that we will see shortly.
\medskip
Once the ring has been defined with a specified order, there are built-in operators
that select leading monomials and leading coefficients:
\medskip
\item{$\bullet$} {\tt f.lt()} gives the leading term (including the coefficient)
\item{$\bullet$} {\tt f.lm()} gives the leading monomial (without the coefficient)
\item{$\bullet$} {\tt f.lc()} gives the leading coefficient. 
\medskip
\noindent
There is also an operator that performs the multivariable polynomial
division algorithm using a given list of divisors, and returns the remainder:
\medskip
\item{$\bullet$} {\tt f.reduce(L)}
\medskip
\noindent
The list {\tt L} here can be any list of polynomials in the base ring
containing the polynomial $f$.  {\it The division is performed using an algorithm
that does not always give the same results as the one we discussed in class, though.}
If you want to duplicate that entirely, the following Sage function can be used,
after setting up the appropriate ring definition:
\medskip
\leftline{\tt def PolyDiv(f,PList):}
\leftline{\tt $\quad$   s = len(PList)}
\leftline{\tt $\quad$   a = [0 for i in range(0,s)]}
\leftline{\tt $\quad$   r = 0}
\leftline{\tt $\quad$   p = f}
\leftline{\tt $\quad$   while p <> 0:}
\leftline{\tt $\quad\quad$       i = 0}
\leftline{\tt $\quad\quad$       divocc = False}
\leftline{\tt $\quad\quad$       while (i < s) and (divocc == False):}
\leftline{\tt $\quad\quad\quad$            q = p.lt()/PList[i].lt()}
\leftline{\tt $\quad\quad\quad$            if q in R:}
\leftline{\tt $\quad\quad\quad\quad$                a[i] = a[i] + q}
\leftline{\tt $\quad\quad\quad\quad$                p = R(p - q*PList[i])}
\leftline{\tt $\quad\quad\quad\quad$                divocc = True}
\leftline{\tt $\quad\quad\quad$            else:}
\leftline{\tt $\quad\quad\quad\quad$                i = i + 1}
\leftline{\tt $\quad\quad$       if divocc == False:}
\leftline{\tt $\quad\quad\quad$            r = r + p.lt()}
\leftline{\tt $\quad\quad\quad$            p = p - p.lt()}
\leftline{\tt $\quad$    return(a,r)}
\bigskip
\noindent
{\it Exercise 2}
\bigskip
We did problem 1 from Chapter 2, \S 3 of ``IVA'' in discussion.
Check your work using Sage.
\bigskip
\noindent
{\it Exercise 3}
\bigskip
Do problems 5-8 in Chapter 2, \S 3 of ``IVA'' using Sage.
\bigskip
\noindent 
\bigskip
\noindent
{\it Defining a Monomial Order by a Matrix}
\bigskip
\noindent
In discussion today, we saw that we can
generalize the weight orders $>_w$, to 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
Namely, suppose 
the 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 until 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} $$
All monomial orders can be specified as $>_M$ orders for appropriate 
matrices $M$.  In Sage, $M$ must be an invertible square matrix with integer entries.
\bigskip
\noindent
To specify that we want to use the matrix order defined
by a suitable square matrix {\tt wmat}, in the ring definition, we enter 
\medskip
\centerline{\tt order = TermOrder(wmat)}
\medskip
\noindent
The matrix {\tt wmat} itself can be specified as above using {\tt Matrix} 
applied to the list of lists as above, either
first in a command assigning the matrix to a name, or else
directly in the {\tt TermOrder} option.  The list of variables in
the ring definition indicates
which components in the weight vectors (the rows of {\tt wmat}) apply to 
which variables. 
For example, if for some reason we did not want to use the 
builtin lex order, we could define something equivalent
on ${\bf Q}[x,y,z]$ using 
\medskip
\centerline{\tt order = TermOrder(Matrix([[1,0,0],[0,1,0],[0,0,1]])}
\bigskip
\noindent
{\it Exercise 4}
\bigskip
What matrix would define the weight order 
on ${\bf Q}[x,y,z]$ where we compare exponents first with 
the weight vector $(1,3,7)$, then break ties using the 
lex order?  
Create an appropriate matrix term order in Sage, and 
repeat the division from Exercise 2a in Chapter 2, \S 3 from ``IVA''.
\bigskip
\noindent
{\it Additional Examples of Monomial Orders}
\bigskip
Exercises 10 and 12 from Chapter 2, \S 5 of ``IVA'' contain two additional
important examples of monomial orders -- the {\it product\/} orders, 
and Bayer and Stillman's {\it elimination\/} orders.
\bigskip
\noindent
{\it Exercise 5}
\bigskip
\noindent
Let $R = {\bf Q}[x_1,x_2,x_3,y_1,y_2,y_3,y_4]$.
\bigskip
\item{a)} Using the matrix order setup in Sage, 
determine how to define a mixed order $>_{mixed}$ on $R$ where
$$x^\alpha y^\beta >_{mixed} x^\gamma y^\delta \Leftrightarrow 
x^\alpha >_{lex} x^\gamma\ {\rm or}\ ((x^\alpha = x^\gamma)\ {\rm and}\ 
(y^\beta >_{grevlex} y^\delta)).$$
(Hint: Think of making the matrix from ``blocks'' like the ones we have
seen for the orders separately.)
\item{b)} Using Sage's setup,
determine how to define the elimination order $>_3$ from Exercise 12.
\bigskip
\noindent
{\it Days 3,4: Gr\"obner Bases}
\bigskip
Now, we are ready to use Sage to compute Gr\"obner bases of some ideals.
We will use these computations to decide ideal membership.  
In addition, with lexicographic Gr\"obner bases we will see additional
examples related to the Elimination and Extension Theorems from Chapter 3, \S 1.
\bigskip
\noindent
{\it Exercise 6}
\bigskip
Do parts a,b,d from Problem 5 in Chapter 2, \S 6 of ``IVA'' using 
lex order with $x > y > z$, lex with $z > y > z$, and then
graded lex with $x > y > z$.  (Note: Sage doesn't have a 
directly accessible S-polynomial operator, so you will need
to do this ``by hand.'')  What is the answer to the following
problem 6 based on the results?  
\bigskip
\noindent
{\it Buchberger's Criterion}
\bigskip
Recall that Buchberger's Criterion says $G = \{g_1, \ldots, g_t\}$ is a
Gr\"obner basis for the ideal it generates if and only if for all pairs
$i \ne j$, 
$$\overline{S(g_i,g_j)}^G = 0,$$
where $\overline{f}^G$ is the remainder on division by $G$.  Although we 
will be skipping the proof of this fact, it is very important -- it is 
the foundation for the algorithm for computing Gr\"obner bases
that we will introduce tomorrow.
\bigskip
\noindent
{\it Exercise 7}
\bigskip
Using Buchberger's Criterion, 
do parts a and c of problem 9 in Chapter 2, \S 6 of ``IVA.''  
The remainders can be computed via the builtin command {\tt reduce}
we discussed before.  
\bigskip
\noindent
{\it Buchberger's Algorithm}
\bigskip
Starting from any set of generators for an ideal $I$, Buchberger's Algorithm
produces a Gr\"obner basis for $I$ by building up a set of polynomials
in the ideal for which Buchberger's Criterion is satisfied.  This is
done by adjoining any nonzero $S$-polynomials that are discovered
in applying the criterion to the current set of polynomials.  The 
pseudocode description is given on p. 87 of ``IVA'' and was discussed
in class.  
\bigskip
\noindent
{\it Exercise 8}
\bigskip
Using Sage to ``automate'' the calculation of the $S$-polynomials,
but controling the current list of polynomials ``by hand,'' apply 
Buchberger's Algorithm to find a Gr\"obner basis of the ideal
$$\langle x^2 - xy + 1, x y - y + 2\rangle$$
using lex order with $x > y$, then lex with $y > x$, and finally
the matrix order for 
$$M = \pmatrix{2 & 5\cr
               3 & 1\cr}.$$
If you are feeling really confident of your Sage skills, it would also be 
possible to code a Sage function carrying out the basic Buchberger algorithm 
from the text.  
\bigskip
\noindent
{\it Exercise 9}
\bigskip
There is a builtin {\tt groebner\_basis()} operator in Sage as well that
can be applied to an ideal (with a particular set of generators) in a 
polynomial ring.
To apply it, you would first define the ring, second the ideal, and then
compute the Gr\"obner basis like this:
\medskip
\centerline{\tt RR.<x,y> = PolynomialRing(QQ,order='lex')}
\centerline{\tt I = Ideal([x\^{}2 + 7*x*y\^{}3 + 1, x\^{}2*y\^{}2 - 4*y - 1])}
\centerline{\tt B = I.groebner\_basis()}
\centerline{\tt B}
\medskip
\noindent 
What happens if you 
apply it to the ideal from Exercise 8 with the monomial orders given there?
Show that the bases that Sage finds generate the same ideal
as your answers.  (Recall the ideal membership test based on remainders.)
\bigskip
\noindent
{\it Exercise 10}
\bigskip 
\item{a)}  Do Problems 1 and 3 in Chapter 2, \S 8 using Sage.
\item{b)}  Do Problem 4 in Chapter 3, \S 1 using Sage.
\bye

