Ideas for Research Projects, SIMU 1999 May 29, 1999

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.

More Applied Topics

Linkages

In mechanical engineering, robotics, etc. an important area of the study is the motions of 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öbner bases can be used to study questions about linkages already in the seminar. Several further questions could form the basis of interesting projects here.

A) To start, the students would work out the trajectory of a marked point on a general “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 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öbner basis methods!

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 every bounded portion of every variety V(f(x, y)) in 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 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.

References

1) IVA, Chapter 6 for general information on applications of Gröbner basis to questions in geometry of robots, etc.

For Topic A:

2) Merlet, J.-P. “Some Algebraic geometry problems arising in the field of mechanism theory, in: Algorithms in Algebraic Geometry and Applications Birkhäuser Progress in Mathematics 143.

For Topic B (unfortunately, neither of these are especially easy to read):

3) King, H. “Planar Linkages and Algebraic Sets”, preprint 1998

4) Kapovich, M. and Millson, J. “Universality Theorems for configuration spaces of planar linkages”, preprint, 1997

Very brief introductions to the general ideas can be found in:

5) Courant, R. and Robins H. What is Mathematics?

6) Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination.

Conformations of Cyclic Molecules

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_{6}H_{12} (and “cyclo-n-ane” C_{n}H_{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 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 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öbner 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öbner 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).

References

1) Emiris, I. and Mourrain, B. “Polynomial System Solving: the case of a six-atom molecule”, INRIA preprint 3075, 1996.

More Mathematically Intensive Topics

Hilbert-Driven Gröbner basis Calculation

The Hilbert Function of a homogeneous ideal I ⊂ k[x_{1}, …, x_{n}] is the integer-valued function H of non-negative integers s defined by

H(s) = dim_{k} k[x_{1}, …, x_{n}]_{s}/I_{s},

where k[x_{1}, …, x_{n}]_{s} denotes the vector space of homogeneous polynomials of degree s, and I_{s} ⊂ k[x_{1}, …, 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öbner bases give methods to compute the Hilbert function of an ideal. Conversely, if the Hilbert function of an ideal is known, then there are several important “shortcuts” one can take in the computation of a Gröbner 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 Gröbner basis conversion methods. It is often the case that computation of a Gröbner basis for an ideal is “easy” with respect to some orders like grevlex, but much harder with respect to other orders like lex. (Of course, we may want to know the lex basis because of its good properties for elimination of variables!) The idea of a Gröbner 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öbner 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öbner 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 Gröbner Walk (I have coded this in Maple and it will be available for the students’ use.)

References

1) IVA, Chapters 8,9 (for background on homogeneous ideals and Hilbert functions)

2) Traverso, C. “Hilbert Functions and the Buchberger Algorithm”, JSC 22 (1996), 355-376.

3) UAG, Chapter 6 (for additional information on graded modules,

Polyhedral Methods

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 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 all the monomials in a set of generators for an ideal. This is called the 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.

A) The Bézout 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.

B) Another possible area for projects would be various questions about the Gröbner 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öbner 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 polyhedral cone in 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 Gröbner fan of the ideal. The Gröbner 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öbner fan of every ideal consists of a finite number of these cones. Then the students could consider one or more of the following open-ended questions: What do the Gröbner fans of the ideals of the parametric curves α(t) = (t, t^{n}, t^{m}) for m > n ≥ 2 look like? How do you determine the Gröbner set of polynomials that is a Gröbner basis for an ideal I with respect to all monomial orders simultaneously? How?

References

1) Nice overview without proofs: DeLoera, J. “A Sample of Polyhedral Methods in Computational Algebraic Geometry”

2) Mora, T. and Robbiano, L. The Gröbner Fan of an Ideal, in: Computational Aspects of Commutative Algebra, L. Robbiano, ed.

3) UAG, Chapter 7

Automorphisms of the Affine Plane and the Jacobian Conjecture

An automorphism of the affine plane is a polynomial mapping

T : (x, y) ↦ (u(x, y), v(x, y))

which is invertible. A famous (notorious?) conjecture states that a mapping T of this form over C is invertible if and only if the Jacobian determinant:

det ( \begin{matrix}\frac{∂u}{∂x} & \frac{∂u}{∂y} \\ \frac{∂v}{∂x} & \frac{∂v}{∂y} \end{matrix} )

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 C, but also over all (finitelygenerated) Q-algebras. It is known that the components of the inverse of a polynomial mapping with degree d = 2 always have degree ≤ 2 (that is C_{2} = 2). Similarly, it was just proved last year by extensive Gröbner basis calculations that C_{3} = 9 (the inverse of every cubic polynomial automorphism of the affine plane has components of degree ≤ 9). However the cases d ≥ 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!

References

1) Fournié, Furter, Pinchon, “Computation of the Maximal Degree of the Inverse of a Cubic Automorphism of the Affine Plane with Jacobian 1 via Gröbner bases”, JSC 26 (1998), 381-386.

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.

Invariant Theory of Finite Groups

A finite matrix group is a finite subgroup of the group GL(n, k) of invertible n × 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}, …, x_{n}] via f(x) ↦ f(A · x). We say that f ∈ k[x_{1}, …, x_{n}] is an invariant of G if f(A · x) = f(x) for all A ∈ G. For example, the 6 matrices

\begin{matrix}I = ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ) , & S = ( \begin{matrix}0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} ) ,  S^{2} = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} ) \\ T_{12} = ( \begin{matrix}0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix} ) , & T_{13} = ( \begin{matrix}0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} ) ,  T_{23} = ( \begin{matrix}1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ) . \end{matrix}

form a subgroup G of GL(3, Q) (isomorphic to the symmetric group on 3 letters). The polynomials

σ_{1} = x_{1} + x_{2} + x_{3}, σ_{2} = x_{1}x_{2} + x_{1}x_{3} + x_{2}x_{3}, σ_{3} = x_{1}x_{2}x_{3}

are invariants of G, and indeed, every polynomial invariant of G can be expressed as a polynomial expression g(σ_{1}, σ_{2}, σ_{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öbner 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öbner 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}, …, x_{n}, y_{1}, …, y_{n}]

The question is to determine and prove a formula for

dim_{k} k[x_{1}, …, x_{n}, y_{1}, …, y_{n}]/I

where I is the ideal generated by the invariants of positive degree.

References

1) IVA, Chapter 7.

2) Sturmfels, Algorithms in Invariant Theory, Chapters 1 and 2.

Gröbner Bases for Modules and Applications

The theory of Gröbner bases for ideals in k[x_{1}, …, x_{n}] that we have developed in the seminar also generalizes to a theory of analogous Gröbner bases for submodules of the free modules k[x_{1}, …, 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 Padé approximating/interpolating functions and they are used both in numerical analysis and in the theory of error-control codes for the decoding problem.)

1) UAG, Chapter 4 (for background about Gröbner bases for modules)

2) Fitzpatrick, P. and Flynn, J., “A Gröbner Basis Technique for Padé Approximation”, JSC 13 (1992), 133-138.

Some Other Possible Areas for Projects

• Modular methods for Gröbner basis calculation

• Solving systems of polynomial equations f_{1} = ⋯ = f_{s} = 0 via the algebra structure

of the quotient ring

k[x_{1}, …, x_{n}]/⟨f_{1}, …, f_{s}⟩

and eigenvalues.