\magnification=\magstep1
\centerline{Mathematics 392 -- Seminar in Computational Commutative Algebra}
\centerline{Final Project -- Topics and Schedule}
\centerline{October 6, 2006}
\bigskip
\noindent
{\it General Information}
\bigskip
Recall from the course syllabus that one of the assignments for this seminar
will be a final project leading to a paper of 10 to 15 pages
and an oral presentation of about 25 minutes duration 
to the class.  Several suggested topics are 
given below.  All of them take material we have learned in this course 
and extend it in new directions.  I will also be happy entertain any 
ideas you might have about designing a project topic of your own.  If 
there is some subject you are interested in where solving polynomial
equations or Gr\"obner basis techniques might come up, please do not hesitate
to discuss it with me and see if there is a possible project there.

You will work in pairs or individually if you prefer on these projects. 
(Since we have an odd number of people, I would also be willing
to let three people work together if that is what you 
prefer, but then I would expect a somewhat more extensive project
paper exploring several different aspects of a topic).   
If you need help putting a group together, be sure to talk to me 
{\it well before October 20}.  

In working on this paper, you should follow the same procedures you would
follow in preparing a research paper for any other course, and 
of course the College Policy on Academic Honesty applies
here, as it does to all of your work.  Your grade will
depend on the thoroughness of your research, the degree of independent
thought about the subject revealed through your work, the organization
of the paper, and the quality of your writing and oral presentation. 

Your papers should be word-processed or typed, one side only,
double-spaced.  Equations can be entered by hand if necessary.
You can also use the TeX mathematical typesetting system (which
is what I use for the handouts).  See me for a tutorial on its use.
Your paper should include a bibliography listing all the sources
you consulted.  Direct quotations should be identified with foot-
or end-notes.  
\bigskip
\noindent
{\it Schedule}
\bigskip
\noindent
Here are some important dates for the projects:
\bigskip
\item{1.}  {\it Friday, October 20 (or before)}: 
Please inform me which topic you 
have chosen to work on and who you will be working with.  You can
do this by sending me a short email message, or by talking to me in person.
\item{2.}  {\it Week of November 13 - November 17}:  During this week, I 
would like to meet with each group (during office hours, or whenever 
is convenient for you) to discuss your progress on the project.  Of 
course, you're always welcome at other times too if you need help.
\item{3.}  {\it November 29, December 1, possibly December 4} 
Oral presentations.  We will schedule who goes which day later in 
the semester.  
\item{4.}  {\it Monday, December 4}:  Final project papers due.  
\bigskip
\noindent
{\it Possible Project Topics}
\bigskip
\noindent
{\it Important Note:}  I would prefer that only one group 
works on any one of the following topics, unless the groups
end up specializing in really different aspects of a topic
with several different possible directions.
\bigskip
\noindent
{\it 1. Buchberger's Criterion and Improvements to Buchberger's Algorithm}
\bigskip
\noindent
For this project, the main goals would be:
\medskip
\item{$\bullet$} To learn and present the proof of Buchberger's Criterion
for Gr\"obner bases -- that is the statement that $G$ is a Gr\"obner
basis if and only if 
$$\overline{S(g_i,g_j)}^{\,G} = 0$$
for all pairs $g_i,g_j \in G$ with $i \ne j$.
\item{$\bullet$} Then, to study some of the strategies that people have
used to improve the rudimentary form of the Buchberger algorithm 
that we discussed in class.  
\medskip
\noindent
Some of the improvements that people have developed include strategies for ordering
the list of polynomials so that $S$-polynomials are more likely to reduce
to zero, criteria for detecting when remainder calculations are
{\it unnecessary} (which can be a big time saver -- the most computationally
intensive part of Buchberger's algorithm is the remainder calculations), 
and other types of ``tweaks'' and modifications.  

If you want to delve even more deeply into this circle of ideas, 
another possible topic to consider would be the recent work of other
mathematicians such as Jean-Charles Faug\`ere, who have developed entirely 
different ways of computing Gr\"obner bases that can outperform any
form of Buchberger (the ``F4'' and ``F5'' algorithms).

\bigskip
\noindent
{\it References}
\bigskip
\item{a)}  Start with Sections 2.6 and 2.9 of {\it Ideals, Varieties, and Algorithms}
for the basics.  A number of references to original articles are given in Section 2.9
\item{b)}  J.-C. Faug\`ere, ``A new efficient algorithm for computing Grobner bases (F 4).'' 
{\it Journal of Pure and Applied Algebra}, {\bf 139} (1999), 61--88 (in Science Library)
\bigskip
\noindent
{\it 2. The FGLM Gr\"obner Basis Conversion Algorithm}
\bigskip
Because {\it lex} Gr\"obner bases are so useful for elimination
of variables, having efficient methods to compute them is a topic
of major interest.  Unfortunately, the very properties that make
{\it lex} Gr\"obner bases so useful also make them very difficult
to compute in many cases.  So, instead of trying to compute them 
directly via Buchberger's algorithm, an alternate strategy is
to compute a Gr\"obner basis with respect to some ``easier''
order first (usually {\it grevlex}), then {\it convert}
the the {\it grevlex} Gr\"obner basis to the desired {\it lex}
Gr\"obner basis by some other transformations.  
The first published Gr\"obner basis conversion algorithm was described by 
Faug\`ere, Gianni, Lazard, and Mora and described  in a joint paper by those 
four authors.  As a result, it is called the ``FGLM'' algorithm.
Mathematicians always name things after their inventors 
(or is it discoverers?).
 
The basic form of the algorithm works for a {\it zero-dimensional\/} 
ideal $I$.  For ideals $I$ in ${\bf Q}[x_1,\ldots,x_n]$, for example, 
this condition means that the set of points in ${\bf V}(I)$ is 
{\it finite\/}, even if we allow solutions that have components in 
the algebraically closed field ${\bf C}$.  
If you choose this project, you would learn 
how and why this method works, and present some
examples.  Then, you could either:
\item{a)}  Implement the FGLM algorithm (converting to a {\it lex} order) 
in the Maple programming language, test it on examples, see how your 
implementation performs relative to the {\tt fglm} command in the 
{\tt Groebner package}, etc.  {\it or}
\item{b)}  Think about whether FGLM can be extended to ideals that are 
more general than $0$-dimensional ideals - for instance, might there 
be some additional information about the monomial order or the ideal
that would allow the same kind of approach to be used, even if 
the ideal is not 0-dimensional?
\bigskip
\noindent
{\it References}
\bigskip
\item{a)}  Chapter 5, section 3 of ``IVA'' for background about what it 
means for an ideal to be zero-dimensional.
\item{b)}  (``straight from the horse's mouth'') Faug\`ere, J.C., 
Gianni, P., Lazard, D., and Mora, T.  ``Efficient Computation of 
Zero-dimensional Gr\"obner Bases by Change of Ordering,'' 
{\it Journal of Symbolic Computation} {\bf 16} (1993), 329-344 (in Science Library).
\item{c)}  Chapter 2, \S 3 of Cox, Little, O'Shea {\it Using Algebraic Geometry}
\item{d)}  Becker, T. and Weispfenning, V.  {\it Gr\"obner Bases}, 
Chapter 9, \S 1.
\bigskip
\noindent
{\it 3.  The Gr\"obner Fan of an Ideal}
\bigskip
This topic would be best for a group who wanted to gain a deeper theoretical
understanding of the different Gr\"obner bases for a given ideal (i.e.
what happens when you change the monomial ordering, and what all of 
the possibilities are).  Recall that on a recent problem set we
studied the ``weight orders'' $>_{u,\sigma}$, where 
$$x^\alpha >_{u,\sigma} x^\beta \Leftrightarrow 
\cases{u\cdot\alpha > u\cdot\beta & or\cr
       u\cdot\alpha = u\cdot\beta & and $x^\alpha >_\sigma x^\beta$\cr}$$
In fact, {\it every} monomial order can be viewed as one of these(!)
Suppose we are interested in studying a particular ideal $I$ and all
of its different possible Gr\"obner bases.
The basic idea here is that ``most'' weight vectors $u$
will pick out a unique leading term of highest weight in each of the 
elements of the given ideal $I$.  The set of weight vectors that select the 
same leading terms (for all elements of $I$) forms a {\it polyhedral cone}
in ${\bf R}^n$ -- a set closed under positive scalar multiples, and 
with boundary defined by a finite collection of hyperplanes.  The collection
of all these cones is called the {\it Gr\"obner fan} of the ideal.  The first 
main goal of this project would be to work through and present a proof that
the Gr\"obner fan of every ideal consists of a {\it finite} number of 
these cones.  Then you could consider one or more of the following
open-ended questions:  What does the Gr\"obner fan of the ideal of the 
twisted cubic in $k^3$ look like?  What about the
ideals of the parametric curves 
$\alpha(t) = (t,t^n,t^m)$ for $m > n \ge 2$?  How do you determine the Gr\"obner
fan of an ideal $I$ in general?  Is it possible to find a finite set of 
polynomials that is a Gr\"obner basis for an ideal $I$ with respect
to {\it all\/} monomial orders simultaneously?  How?
\bigskip
\noindent
{\it References}
\bigskip
\item{a)}  (``straight from the horse's mouth" again)  Mora, T. and 
Robbiano, L. ``The Gr\"obner Fan of an Ideal'', in: {\it Computational
Aspects of Commutative Algebra}, L. Robbiano, ed.  (in Science Library)
\item{b)}  Also see Chapter 8, section 4 of Cox, Little, O'Shea,
{\it Using Algebraic Geometry}, 2nd ed.
\bigskip
\noindent
{\it 4. An Application -- Conformations of Cyclic Molecules}
\bigskip
This topic would introduce you to an application of Gr\"obner bases,
resultants, etc.  in the area of computational chemistry.
A simplified model for cyclic molecules like cyclohexane: $C_6H_{12}$ (and
``cyclo-$n$-ane'' $C_nH_{2n}$ more generally) is to ignore the hydrogen
atoms attacted to the cyclic ``backbone'' of the molecule and
translate the minimum energy constraints that would 
describe the physically observable forms of the molecule
into geometric constraints on the {\it lengths\/} of the bonds between 
the carbons and the bond angles at each carbon atom.  
This leads to a system of algebraic
equations that describe the possible {\it conformations\/} or geometric
forms for molecules of the given type.  (For example, cyclohexane comes
in both ``boat'' and ``chair'' conformations; the difference between
these is described by different values for two angles between
planes formed by triples of carbon atoms.)  
So no specific knowledge of chemistry
is necessary to work on this topic -- the chemistry is converted into
questions in pure geometry and algebra!

The equations are 
sufficiently complicated, though, that some clever Gr\"obner techniques are
necessary to solve them.  For this project, you would first
work through the geometry of the cyclic 6-atom molecules, investigate
their possible conformations using ``whatever methods work''
to solve the systems of equations.  Then the main focus of the project 
would be to study the analogous questions
for 7-atom cyclic molecules (cycloheptane, for instance).
\bigskip
\noindent
{\it Reference}
\bigskip
\item{a)}  Emiris, I. and Mourrain, B. 
``Computer Algebra Methods for Studying and Computing Molecular Conformations''
{\it Algorithmica}, Special Issue on Algorithms for Computational Biology, {\bf 25}
(1999).  A preliminary version of the article can be 
downloaded free of charge from 
{\tt http://citeseer.comp.nus.edu.sg/emiris97computer.html}
\item{b)} also see: von zur Gathen, J. and Gerhard, J.  {\it Modern Computer Algebra}, 
section 24.4.  
\bigskip
\noindent
{\it 5.  A ``Pure'' Topic -- Invariant Theory of Finite Groups and 
Molien's Theorem}  
\bigskip
A finite matrix group is a finite subgroup of the group $GL(n,k)$ 
of invertible $n\times n$ matrices with entries in the field $k$.  
Each element $A$ of a matrix group $G$ also acts on the polynomial
ring $k[x_1,\ldots,x_n]$ via $f(x) \mapsto f(A\cdot x)$.  We
say that $f \in k[x_1,\ldots,x_n]$ is an {\it invariant\/} of $G$ 
if $f(A \cdot x) = f(x)$ for all $A \in G$.  For example, the 6 
matrices
$$\eqalign{ I =\pmatrix{1&0&0\cr
                             0&1&0\cr
                             0&0&1\cr},\qquad &S = \pmatrix{0&0&1\cr
                         1&0&0\cr
                         0&1&0\cr}, \qquad
           S^2 =\pmatrix{0&1&0\cr
                          0&0&1\cr
                          1&0&0\cr}\cr
           T_{12} = \pmatrix{0&1&0\cr
                              1&0&0\cr
                              0&0&1\cr},\qquad
           &T_{13} = \pmatrix{0&0&1\cr
                    0&1&0\cr
                    1&0&0\cr}, \qquad 
           T_{23} = \pmatrix{1&0&0\cr
                              0&0&1\cr
                              0&1&0\cr}.\cr}$$
form a subgroup $G$ of $GL(3,{\bf Q})$ (isomorphic to the symmetric
group on 3 letters).  The polynomials
$$\sigma_1 = x_1 + x_2 + x_3,\ \sigma_2 = x_1x_2 + x_1x_3 + x_2 x_3,\
\sigma_3 = x_1 x_2 x_3$$ 
are invariants of $G$, and indeed, {\it every\/} polynomial invariant
of $G$ can be expressed as a polynomial expression 
$g(\sigma_1,\sigma_2,\sigma_3)$.  
Invariant theory is the study of the structure
of the invariants of matrix groups such as this.  It was a very 
``hot topic'' in 19th century mathematics and it has a number of important
applications.  But eventually the computations that 
people wanted to carry out essentially became too difficult to do by 
hand, and at the same time mathematics as a whole moved in a much
more abstract direction.  Gr\"obner basis methods (and other techniques
from computational algebra) have made possible
a resurgence of interest and renewed progress in invariant theory.  

For this topic, you would learn about the basic ideas involved
(topics: Gr\"obner basis test for subring membership,
the Reynolds operator and Noether's theorem which shows
finite generation of rings of invariants, Molien's theorem)
and study the rings of invariants in some interesting cases.  
The goal would be to present a proof of Molien's theorem, which 
gives a truly beautiful and wonderful formula for computing the 
dimension of the vector space of invariants of $G$ in the homogeneous 
polynomials of degree $t$, for all $t$ {\it simultaneously}.  
We write $S_t^G$ for 
this space of invariants ($S = k[x_1,\ldots,x_n]$ is the 
polynomial ring $G$ acts on; $S_t$ is the vector subspace
of homogeneous polynomials of degree $t$).  
Then Molien's theorem says:
$$\sum_{t=0}^\infty \dim_{\bf C}(S_t^G) u^t = 
{1\over |G|}\sum_{g\in G} {1\over \det(I - ug)}.$$
\bigskip
\noindent
{\bf References}
\bigskip
\item{a)}  IVA, Chapter 7.
\item{b)}  Sturmfels, {\it Algorithms in Invariant Theory}, Chapters 1 and 2.
\item{c)}  Cox, Little, O'Shea, {\it Using Algebraic Geometry}, Chapter 6 for
background needed for Molien's Theorem.
\bye
