Mathematics 392 – Seminar in Computational Commutative Algebra Final Project – Topics and Schedule October 6, 2006

General Information

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öbner 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 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.

Schedule

Here are some important dates for the projects:

1. 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.

2. 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.

3. November 29, December 1, possibly December 4 Oral presentations. We will schedule who goes which day later in the semester.

4. Monday, December 4: Final project papers due.

Possible Project Topics

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.

1. Buchberger’s Criterion and Improvements to Buchberger’s Algorithm

For this project, the main goals would be:

• To learn and present the proof of Buchberger’s Criterion for Gröbner bases – that is the statement that G is a Gröbner basis if and only if

\overline{S(g_{i}, g_{j})}^{G} = 0

for all pairs g_{i}, g_{j} ∈ G with i ≠ j.

• 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.

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 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ère, who have developed entirely different ways of computing Gröbner bases that can outperform any form of Buchberger (the “F4” and “F5” algorithms).

References

a) Start with Sections 2.6 and 2.9 of Ideals, Varieties, and Algorithms for the basics. A number of references to original articles are given in Section 2.9

b) J.-C. Faugère, “A new efficient algorithm for computing Grobner bases (F 4).” Journal of Pure and Applied Algebra, 139 (1999), 61–88 (in Science Library)

2. The FGLM Gröbner Basis Conversion Algorithm

Because lex Gröbner 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 lex Gröbner 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öbner basis with respect to some “easier” order first (usually grevlex), then convert the the grevlex Gröbner basis to the desired lex Gröbner basis by some other transformations. The first published Gröbner basis conversion algorithm was described by Faugère, 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 zero-dimensional ideal I. For ideals I in Q[x_{1}, …, x_{n}], for example, this condition means that the set of points in V(I) is finite, even if we allow solutions that have components in the algebraically closed field C. If you choose this project, you would learn how and why this method works, and present some examples. Then, you could either:

a) Implement the FGLM algorithm (converting to a lex order) in the Maple programming language, test it on examples, see how your implementation performs relative to the

    fglm command in the Groebner package, etc. or

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?

References

a) Chapter 5, section 3 of “IVA” for background about what it means for an ideal to be zero-dimensional.

b) (“straight from the horse’s mouth”) Faugère, J.C., Gianni, P., Lazard, D., and Mora, T. “Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering,” Journal of Symbolic Computation 16 (1993), 329-344 (in Science Library).

c) Chapter 2, §3 of Cox, Little, O’Shea Using Algebraic Geometry

d) Becker, T. and Weispfenning, V. Gröbner Bases, Chapter 9, §1.

3. The Gröbner Fan 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). Recall that on a recent problem set we studied the “weight orders” >_{u,σ}, where

x^{α} >_{u,σ} x^{β} ⇔ \{ \begin{matrix}u · α > u · β & or \\ u · α = u · β & and x^{α} >_{σ} x^{β} \end{matrix}

In fact, 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öbner 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 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 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 you could consider one or more of the following open-ended questions: What does the Gröbner fan of the ideal of the twisted cubic in k^{3} look like? What about the ideals of the parametric curves α(t) = (t, t^{n}, t^{m}) for m > n ≥ 2? How do you determine the Gröbner fan of an ideal I in general? Is it possible to find a finite set of polynomials that is a Gröbner basis for an ideal I with respect to all monomial orders simultaneously? How?

References

a) (“straight from the horse’s mouth” again) Mora, T. and Robbiano, L. “The Gröbner Fan of an Ideal”, in: Computational Aspects of Commutative Algebra, L. Robbiano, ed. (in Science Library)

b) Also see Chapter 8, section 4 of Cox, Little, O’Shea, Using Algebraic Geometry, 2nd ed.

4. An Application – Conformations of Cyclic Molecules

This topic would introduce you to an application of Gröbner bases, resultants, etc. in 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, 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).

Reference

a) Emiris, I. and Mourrain, B. “Computer Algebra Methods for Studying and Computing Molecular Conformations” Algorithmica, Special Issue on Algorithms for Computational Biology, 25 (1999). A preliminary version of the article can be downloaded free

    of charge from http://citeseer.comp.nus.edu.sg/emiris97computer.html

b) also see: von zur Gathen, J. and Gerhard, J. Modern Computer Algebra, section 24.4.

5. A “Pure” Topic – Invariant Theory of Finite Groups and Molien’s Theorem

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 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ö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, you 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 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 simultaneously. We write S_{t}^{G} for this space of invariants (S = k[x_{1}, …, 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:

∑_{t=0}^{∞} dim_{C}(S_{t}^{G})u^{t} = \frac{1}{|G|} ∑_{g∈G} \frac{1}{det(I − ug)}.

References

a) IVA, Chapter 7.

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

c) Cox, Little, O’Shea, Using Algebraic Geometry, Chapter 6 for background needed for Molien’s Theorem.