\magnification=\magstep1
\centerline{\bf Ideas for Research Projects, SIMU 1999}
\centerline{\it May 29, 1999}
\bigskip
\noindent
The following are ideas for the research group projects for the final
three weeks of SIMU 1999.  I expect we should have three or four
groups of three or four students each, so not all of these projects
will be ``taken''.  However, there should be a sufficient
range of possibilities here so that all groups can find something
appropriate for their interests, their backgrounds and strengths, their
proficiency with Maple, their programming skill, and so forth.
\bigskip
\noindent
{\it More Applied Topics}
\bigskip
\noindent
{\it Linkages}
\bigskip
In mechanical engineering, robotics, etc. an important area of the 
study is the motions of {\it mechanical linkages\/} -- collections of 
rigid segments joined by joints of various types. 
(For example, simple planar linkages would have rigid segments
of fixed length, joined by revolute joints.)  We will have looked at a 
few examples of how varieties and Gr\"obner bases
can be used to study questions about linkages already in the seminar.
Several further questions could form the basis of interesting projects here.
\bigskip
\noindent
A)  To start, the students would work out the trajectory of a 
marked point on a general {\it ``four-bar''} linkage (these are called Watt curves,
after James Watt, the inventor of the steam engine -- see below)
to investigate questions like: What kinds
of curves can you get here by changing the lengths of the segments
in the linkage, etc.?  Then, a 3-RPR parallel manipulator is a planar 
robot linkage consisting of three ``arms'' each fixed at one end
with a revolute joint; each containing a prismatic joint, 
and each attached via a second revolute joint to one common 
end-effector.  A question for which no really good general answer is
known at present is: How can we determine the {\it maximal workspace\/}
of the robot -- the set of all points reachable by the end-effector,
given the locations of the fixed ends of the arms, the minimum and 
maximum lengths of the prismatic joints, etc.?
This is a good problem, and it can be attacked by Gr\"obner basis
methods!
\bigskip
\noindent
B)  Another, more mathematically-oriented, question here is
as follows.  The original interest in linkages started in the 19th century
with the invention of steam engines for farm implements, manufacturing,
locomotives, etc.  One of the early questions in the subject
was: How can a linkage be constructed to ``turn circular
motion in to straight-line motion''?  This was eventually solved
by a French engineer named Peaucellier.   Another well-known
mathematician of the time, A. Kempe, studied linkages in great
detail.  (He also published an incorrect proof of the 4-color theorem!)
Kempe sketched a proof of a theorem that says that {\it every\/} bounded 
portion of every variety ${\bf V}(f(x,y))$ in ${\bf R}^2$
can be ``drawn'' by following the trajectory of some point in a suitable
mechanical linkage (!)  For this topic, the students would learn the ideas behind
Kempe's proof, which gives (in principle) a method to synthesize
a linkage to draw an arc of any given variety, given the polynomial
equation $f(x,y) = 0$.  One unfortunate aspect of Kempe's approach is that
the linkages he would find to construct even simple curves like ellipses
are extremely complicated.  Try one to see what I mean!  His approach yields  
an {\it existence proof\/} for the linkage.  It
is far from a practical construction of a minimal (or close-to-minimal)
linkage for a given curve.  Another possible part of the project would be 
to try to address the following questions: Are there simplifications that 
are possible here?  Are there better upper bounds for the number of segments 
in a linkage one would need to draw a general curve of a given degree.  
\bigskip
\noindent
{\bf References}
\bigskip
\noindent
\item{1)}  IVA, Chapter 6 for general information on applications
of Gr\"obner basis to questions in geometry of robots, etc.
\bigskip
\noindent
For Topic A:
\item{2)}  Merlet, J.-P. ``Some Algebraic geometry problems arising
in the field of mechanism theory, in: Algorithms in Algebraic Geometry
and Applications Birkh\"auser Progress in Mathematics 143.
\bigskip
\noindent 
For Topic B (unfortunately, neither of these are especially easy to read):
\item{3)}  King, H. ``Planar Linkages and Algebraic Sets'', preprint 1998
\item{4)}  Kapovich, M. and Millson, J. ``Universality Theorems for
configuration spaces of planar linkages'', preprint, 1997 
\bigskip
\noindent
Very brief introductions to the general ideas can be found in:
\item{5)}  Courant, R. and Robins H.  What is Mathematics? 
\item{6)}  Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination.
\bigskip
\noindent
{\it Conformations of Cyclic Molecules}
\bigskip
This topic is closely related to the previous one, but it comes from 
a different applications domain -- 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, the students would first
work through the geometry of the cyclic 6-atom molecules, investigate
their possible conformations using methods called the FGLM or Gr\"obner 
Walk (I have these coded in Maple for the students to use)
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
{\bf References}
\bigskip
\item{1)}  Emiris, I. and Mourrain, B.  ``Polynomial System Solving:
the case of a six-atom molecule'', INRIA preprint 3075, 1996.
\bigskip
\noindent
{\it More Mathematically Intensive Topics}
\bigskip
\noindent
{\it Hilbert-Driven Gr\"obner basis Calculation}
\bigskip
The Hilbert Function of a homogeneous ideal $I \subset k[x_1,\ldots,x_n]$ 
is the integer-valued function $H$ of non-negative integers $s$ defined by 
$$H(s) = \dim_k k[x_1,\ldots,x_n]_s/I_s,$$
where $k[x_1,\ldots,x_n]_s$ denotes the vector space of 
homogeneous polynomials of degree $s$, and $I_s \subset k[x_1,\ldots,x_n]_s$
is the subspace of polynomials of degree $s$ belonging to the ideal $I$.  
(In other words, the larger the value of $H(s)$, the ``smaller'' the ideal
is in degree $s$.)  Gr\"obner bases give methods to compute the Hilbert 
function of an ideal.  Conversely, if the Hilbert function of an ideal is 
{\it known\/},
then there are several important ``shortcuts'' one can take in the
computation of a Gr\"obner basis!  This is the theme of the paper
by Traverso listed below.  

One important place where these observations
are potentially of use is the area of {\it Gr\"obner basis conversion methods\/}.
It is often the case that computation of a Gr\"obner basis for an ideal
is ``easy'' with respect to some orders like {\it grevlex\/}, but much
harder with respect to other orders like {\it lex\/}.  (Of course, we
may want to know the {\it lex\/} basis because of its good properties
for elimination of variables!)  The idea of 
a Gr\"obner basis conversion method is to do the easy calculation
first, derive all the information we can from that (such as the 
the Hilbert function of the ideal), then apply a simpler method
to convert from the Gr\"obner basis for the easy order to one for the 
more complicated one.  Traverso's paper sketches some ideas for 
an example of this type.

The goals of a project here would be first to learn the ``yoga'' of 
Hilbert functions, and work lots of examples.  Then, using Traverso's
hints, the students would implement a ``Hilbert function-driven'' version of 
Buchberger's algorithm and apply it to some Gr\"obner basis conversion
problems I will supply.  A side issue here would be to gather
some experimental data to compare the 
efficiency of this method with the efficiency of 
another basis conversion algorithm called the {\it Gr\"obner Walk\/} 
(I have coded this in Maple and it will be available for the students' use.)
\bigskip
\noindent
{\bf References}
\bigskip
\item{1)}  IVA, Chapters 8,9 (for background on homogeneous ideals
and Hilbert functions)
\item{2)}  Traverso, C. ``Hilbert Functions and the Buchberger Algorithm'',
JSC 22 (1996), 355-376.
\item{3)}  UAG, Chapter 6 (for additional information on graded modules,
\bigskip
\noindent
{\it Polyhedral Methods}
\bigskip
Ever since Newton introduced the so-called Newton polygon of
a polynomial in two variables, it has been understood that 
much of the structure of systems of polynomials in several variables
is tied up in the {\it vectors of exponents\/} appearing in their terms.  
We have studied one such connection in Dixon's Lemma, the ``staircase'' of 
a zero-dimensional ideal, and so forth.  Instead of looking at the staircase 
of an ideal (which comes from the exponents of the leading terms), we
could also study the smallest convex polygon (or polyhedron in higher
dimensions) containing the exponent vectors of {\it all\/} the monomials 
in a set of generators for an ideal.  This is called the 
{\it Newton polyhedron\/} of the generating set.  In recent years 
the connection between real polyhedral geometry and systems of 
polynomials has really ``taken off''; there are several very interesting
possible project topics in this area.
\bigskip
\item{A)} The B\'ezout and BKK bounds -- using polyhedral methods,
it is possible to derive very useful upper bounds on the numbers
of solutions of systems of polynomial equations.  The BKK bound
usually gives more information, but it deals only with solutions
of a system where all coordinates are non-zero.  A possible goal
for a project in this area might be to implement a ``smart'' BKK
bound procedure that would take a system of polynomials generating
a zero-dimensional ideal and compute an upper bound on the number
of solutions including any with zero coordinates.  
\item{B)}  Another possible area for projects would be
various questions about the Gr\"obner Fan (or State Polytope) of an ideal
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).   The basic idea is that ``most'' weight vectors
will pick out a unique leading term of highest weight in each of the 
elements of an 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 Gr\"obner fan is the ``normal fan'' of a polytope called the 
state polytope 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 the students could consider one or more of the following
open-ended questions:  What do the Gr\"obner fans of the
ideals of the parametric curves 
$\alpha(t) = (t,t^n,t^m)$ for $m > n \ge 2$ look like?  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
{\bf References}
\bigskip
\item{1)} Nice overview without proofs: DeLoera, J. ``A Sample of Polyhedral
Methods in Computational Algebraic Geometry''
\item{2)} Mora, T. and 
Robbiano, L. {\sl The Gr\"obner Fan of an Ideal}, in: {\sl Computational
Aspects of Commutative Algebra}, L. Robbiano, ed.
\item{3)} UAG, Chapter 7
\bigskip
\noindent
{\it Automorphisms of the Affine Plane and the Jacobian Conjecture}
\bigskip
An automorphism of the affine plane is a polynomial mapping 
$$T : (x,y) \mapsto (u(x,y),v(x,y))$$
which is invertible.  A famous (notorious?) conjecture
states that a mapping $T$ of this form over ${\bf C}$ is invertible if 
and only if the Jacobian determinant:
$$det \pmatrix{ {\partial u\over \partial x} & {\partial u\over \partial y}\cr
                {\partial v\over \partial x} & {\partial v\over \partial y}\cr}$$
is a nonzero constant.  Although many partial results are known and
this question has been studied for about 50 years, there is no 
known proof(!)  One promising reduction has been achieved by H. Bass.
The ``Jacobian Conjecture'' is true for mappings $T$ of degree $d$
if and only if there is a uniform bound $C_d$ on the degrees of the 
components of the inverse mappings of automorphisms of the affine
plane not only over ${\bf C}$, but also over all (finitely-generated)
${\bf Q}$-algebras.  It is known that the components
of the inverse of a polynomial
mapping with degree $d = 2$ always have degree $\le 2$ (that is $C_2 = 2$).
Similarly, it was just proved last year by extensive Gr\"obner basis
calculations that $C_3 = 9$ (the inverse of every cubic polynomial
automorphism of the affine plane has components of degree $\le 9$).
However the cases $d \ge 4$ are essentially completely open as of now.  The main
goal for this project would be to try to attack the $d = 4$ case,
conjecture and hopefully prove a value for $C_4$.  The computations for 
$d=3$ are already rather complicated, so cleverness,
and/or a new idea will be needed here!
\bigskip
\noindent
{\bf References}
\bigskip
\item{1)}  Fourni\'e, Furter, Pinchon, ``Computation of the Maximal
Degree of the Inverse of a Cubic Automorphism of the Affine Plane with
Jacobian 1 via Gr\"obner bases'', JSC 26 (1998), 381-386.
\item{2)}  Van den Essen, ``A criterion to decide if a polynomial
map is invertible and to compute the inverse'', Communications in 
Algebra 18 (1990), 3183-3186.
\bigskip
\noindent
{\it Invariant Theory of Finite Groups}  
\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 still 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, students 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 final
goal for the project would be to do some work related to a famous
(notorious?) conjecture of Haiman about the invariants of the 
diagonal action of the symmetric group $S_n$ on the ring
$$k[x_1,\ldots,x_n,y_1,\ldots,y_n]$$
The question is to determine and prove a formula for 
$$\dim_k k[x_1,\ldots,x_n,y_1,\ldots,y_n]/I$$
where $I$ is the ideal generated by the invariants of positive degree.
\bigskip
\noindent
{\bf References}
\bigskip
\item{1)}  IVA, Chapter 7.
\item{2)}  Sturmfels, {\it Algorithms in Invariant Theory}, Chapters 1 and 2.
\bigskip
\noindent
{\it Gr\"obner Bases for Modules and Applications\/}
\bigskip
The theory of Gr\"obner bases for ideals in $k[x_1,\ldots,x_n]$ that
we have developed in the seminar also generalizes to a theory 
of analogous Gr\"obner bases for submodules of the free modules
$k[x_1,\ldots,x_n]^t$ over the polynomial ring.  The first
goal for this project topic would be to learn about the ideas
involved here.  Then, the students would look at one very nice application
of these ideas to the construction of rational functions in 
one or more variables interpolating a given collection of 
data points.  (These are called {\it Pad\'e} approximating/interpolating functions and
they are used both in numerical analysis and in the theory of 
error-control codes for the decoding problem.)
\bigskip
\noindent
\item{1)} UAG, Chapter 4 (for background about Gr\"obner bases for modules)
\item{2)} Fitzpatrick, P. and Flynn, J., ``A Gr\"obner Basis
Technique for Pad\'e Approximation'', JSC 13 (1992), 133-138.
\bigskip
\noindent
{\it Some Other Possible Areas for Projects}
\bigskip
\item{$\bullet$}  Modular methods for Gr\"obner basis calculation
\item{$\bullet$}  Solving systems of polynomial equations $f_1 = \cdots = f_s = 0$
via the algebra structure of the quotient ring
$$k[x_1,\ldots,x_n]/\langle f_1,\ldots,f_s\rangle$$
and eigenvalues.
\bye