Natalie Cate and Becca Bates – Buchberger’s Criterion and Improvements to Buchberger’s Algorithm

This is a very well-written exposition of the proof of Buchberger’s Criterion and the improvements to Buchberger’s algorithm based on the two criteria for unnecessary Spolynomial reductions. You have done an excellent and thorough job with the details here. The in-class presentation and the example you worked through were well-chosen and very illuminating. So it’s OK that you didn’t really get to the specifics of Faugère’s alternate approach in the F4 algorithm.

Some Specific Comments

0) A somewhat random initial comment – the Faugère here is also the “F” in the “FGLM” algorithm that Amy and Michelle worked on.

1) It’s not really a matter of “right and wrong,” of course. It be might be better to say something like ”h’s with extra terms producing cancellations.” We often say things like this in lectures to make the explanations more vivid, but they are best avoided in formal mathematical writing.

2) Oops – The underlined statement here is the converse of the Lemma, and that is the statement that is not true in general. Namely, as we saw in several calculations done in class, it is possible for an element f = a_{1}f_{1} +⋯+a_{s}f_{s} to leave a nonzero remainder on division by F = [f_{1}, …, f_{s}] when F is not a GB for I = ⟨F ⟩. (This can be caused, for instance, by the way the standard division algorithm works – it forces you to take the first element in the list F whose leading term divides the leading term of the intermediate dividend. When several choices are possible, some choices may lead to zero remainders, showing f →_{F} 0, while others may not lead to zero remainders.) However, if \overline{f}^{F} = 0, then f →_{F} 0, since then the expression f = a_{1}f_{1} + … a_{s}f_{s} from the division algorithm does satisfy the condition multideg(a_{i}f_{i}) ≤ multideg(f) for all i (again, by the way the division algorithm works).

3) This is just a comment for you about how the structure of the syzygies S(F) you are describing here generalizes. These properties lead to the notion of what is called a module over the ring k[x_{1}, …, x_{n}]. Roughly speaking: a module is to a ring what a vector space is to a field. More precisely, a module over any commutative ring R (with multiplicative identity element) is a set M with an addition operation and an operation of multiplication by elements of R. These operations must satisfy axioms that make (M, +) into an abelian group, distributive laws r(m + m′) = rm + rm′ and (r + s)m = rm + sm for all r, s ∈ R and m, m′ ∈ M, and finally 1m = m for all m ∈ M (where 1 is the multiplicative identity in R). What you are saying here is that S(F) has this sort of structure. It is a module over the ring R = k[x_{1}, …, x_{n}]. Later, when you mention “linear combinations” of syzygies, of course, you need to allow for general polynomial coefficients, not just constant coefficients. There is also a connection with the ideals that we studied in detail. An ideal I ⊂ R is just a module over R that is a subset of R itself. More advanced treatments of commutative algebra treat ideals and modules together, in fact, and there is also a theory of Gröbner bases for modules over polynomial rings.

Paper: Presentation: Overall Project Grade:

Renée Laverdière – The Ring of Invariants and Molien’s Theorem

Very good presentation and paper on Molien’s Theorem and the beginnings of invariant theory for finite matrix groups. There are a few specific comments I have about the content of the paper (see below). The proof of Molien, in particular, is a bit rough still (although I know that writing down the formulas you need there in TEX is a bit of a chore, and that might have caused the missing details!)

It might also have been nice to point out that the ring k[x, y]^{C_{2}} = k[x^{2}, xy, y^{2}] has the following structure. It is the image of the ring homomorphism:

\begin{matrix}φ : k[u, v, w] & → k[x, y] \\ u & ↦ x^{2} \\ v & ↦ xy \\ w & ↦ y^{2} \end{matrix}

By the First Isomorphism Theorem for rings, this says

k[x, y]^{C_{2}} ≅ k[u, v, w]/⟨uw − v^{2}⟩

(since ker(φ) = ⟨uw − v^{2}⟩). This shows that the ring of invariants can be viewed as the ring of polynomial functions on a variety V, namely V = V(uw − v^{2}) in C^{3}. This is a surface whose real points form a quadric cone. (The origin is a singular point.) It is this variety that gives the quotient space C^{2}/G in this case (see comment 4 below).

Some Specific Comments

1) Saying that GL(n, k) is the set of units in M(n, k) means that you are thinking of M(n, k) as a ring under matrix addition and multiplication. Probably better to say that explicitly.

2) It’s true that a matrix A can act on a vector field, but the more basic action is the action on single vectors: v ↦ Av for v ∈ k^{n}. (Note: a vector field would be something like a mapping V : k^{n} → k^{n} giving a vector V (x) for each x ∈ k^{n}.)

3) “Indistinguishable” in what sense? (This means indistinguishable from the point of view of polynomial functions. Any polynomial vanishing on an orbit also vanishes on the closure of that orbit, since polynomials are continuous functions.)

4) What you wrote here doesn’t quite make sense. The two things on either side of your = sign are of two different types so they can’t really be equal. The k^{n}/G should mean the quotient space of k^{n} under the action of G (i.e. the set of orbits under the action of G). For finite groups, this set of orbits has the structure of a variety too, and the ring of polynomial functions on the quotient k^{n}/G can be identified with the ring of invariants k[x]^{G}.

5) As we discussed in office hours one time, the real reason this is true is just the fact that x ↦ A · x is homogeneous of degree 1 in the variables, so A acts on the homogeneous components of each degree in polynomials “separately” (i.e. the homogenous component of degree d in f(A·x) is just the image under A of the homogenous component of degree d in f(x). This observation makes the statement of your Theorem 3.4 almost “obvious.”

6) The Hilbert series itself makes sense over any field. However the statement of Molien’s Theorem is not necessarily true (for some G), since some of the invariants might have complex coefficients. That’s the real reason for restricting to k = C.

7) For completeness in this argument it would be good to say that you are using the linearity of the trace here

dim(V^{G}) = trace(P_{G}) = \frac{1}{|G|} ∑_{A∈G} trace(A)

which is the formula you are trying to show.

8) I think this proof got somewhat garbled (but I’m not sure if this was a problem with the complicated TEX or with your understanding of the details). Some of these formulas should have sums over d, and/or sums over A ∈ G, and you are missing z^{d}’s. Should say:

∑_{d=0}^{∞} dim(C[x]_{d}^{G})z^{d} = ∑_{d=0}^{∞} (\frac{1}{|G|} ∑_{A∈G} trace(A^{d})) z^{d}

= ∑_{d=0}^{∞} (\frac{1}{|G|} ∑_{A∈G} ( ∑_{d_{1}+···+d_{n}=d} ρ_{A,1}^{d_{1}} ⋯ ρ_{A,n}^{d_{n}})) z^{d}

Then, you interchange the two outer sums to get

\frac{1}{|G|} ∑_{A∈G} (∑_{d=0}^{∞} ( ∑_{d_{1}+···+d_{n}=d} ρ_{A,1}^{d_{1}} ⋯ ρ_{A,n}^{d_{n}})) z^{d}

Finally, you want to argue that the inner sum is the same as

\frac{1}{det(I − Az)}

This follows from some standard matrix indentities when you change basis to put A in diagonal form (formally the sum of a geometric series, as you indicate). Note that you also need k = C to say that the eigenvalues of your A’s exist in k for this argument.

9) Although the result of this computation is correct, note that you’re using det(A − zI) rather than det(I − Az) here. This happens to work for this group since

A − zI = ( \begin{matrix}−z & −1 \\ 1 & −z \end{matrix} ) ⇒ det(A − zI) = z^{2} + 1

and

I − zA = ( \begin{matrix}1 & z \\ −z & 1 \end{matrix} ) ⇒ det(I − zA) = z^{2} + 1

too. But as we discussed, you should be using det(I − zA) (the “reversed version” of the characteristic polynomial).

10) f_{3} should be f_{3} = x^{3}y − xy^{3} (you’re missing the x in the second term, which makes this nonhomogeneous!) You could also say more here! Where do the three linearly independent invariants of degree 4 come from? You have f_{2}, f_{3} and the third one is f_{1}^{2} = (x^{2} + y^{2})^{2}.

Paper:

Presentation:

Amy Borbely and Michelle Hedrick – Gröbner Basis Conversion; Adaptation of the FGLM Algorithm

Very good project on the FGLM algorithm and Gröbner Basis conversion. The presentation was quite good too (though slightly rough in a couple of spots corresponding to the specific comments below). The example was well-chosen and very illuminating, though. For the paper, it would have been nice to include an example in more than two variables. We discussed that, so I was slightly surprised not to see that. I’m slightly curious about this – was there some problem with the procedures in that case? I don’t think there should have been provided that you gave the input of the correct grevlex staircase. (I didn’t see any potential problems, though, so I’m guessing the difficulty was just seeing what was in the grevlex staircase in a case with more variables – it can be hard to visualize!).

For your general knowledge about this area – there are other GB conversion algorithms that are not limited to the case of zero-dimensional ideals, and a lot of additional work has been done since the original FGLM paper. One method, called the “Gröbner Walk” makes use of the construction of the Gröbner fan that Katie worked on for her project. The algorithm “walks through the fan” and converts every time you cross from one cone into another. This sounds like a lot of work, but the conversion is usually not too difficult when the cones are adjacent. Another (maybe better) method is called the “Hilbert-function-driven method.” It uses some of the same ideas about counting dimensions of subspaces of ideals of different homogeneous degrees as in Renee’s talk.

Some Specific Comments

1) Actually, although in practice you would always make the input GB a reduced GB in the starting order M_{1}, there isn’t any reason it has to be reduced. The reason that isn’t necessary is that remainders are well-defined and unique when you divide by any GB for the ideal with respect to the M_{1} order (recall Exercise 1 in Section 2.6 of “IVA”).

2) Not exactly. The monomials in Blex are actually the “lexicographic staircase” monomials when the algorithm terminates. You’re not using them for the remainder calculations. They correspond to the rows in your A-matrix.

3) Normally, you say that an ideal is zero-dimensional, not a Gröbner basis. This is just a matter of how the terminology is defined. But one point that is not too well-explained here in the paper (or in the presentation) was just what this means. Let Q ⊂ k Saying an ideal I ⊂ k[x_{1}, …, x_{n}] is zero-dimensional means (by definition) that in C^{n}, V(I) is a finite set. Then Theorem 6 in Section 5.3 of “IVA” gives a collection of equivalent statements, including the one you used regarding the leading terms of any GB for I (for each i the existence of some g ∈ GB such that LM(g) = x_{i}^{m_{i}} for some m_{i} ≥ 0).

Paper:

Presentation:

Katie Fitzpatrick – The Gröbner Fan of an Ideal

Very good presentation and paper on Gröbner fans. I can tell you probably have not had too much experience giving presentations like this. What you did was very good and the twisted cubic example was very instructive; the only thing I would suggest is to perhaps try to write a bit more on the board (even at the expense of that slowing you down somewhat). Sometimes what you wrote was only a (slightly cryptic) part of what you were saying and that made it difficult for a listener to get back into the flow if he or she had to think about a point you were making or his/her attention was distracted momentarily.

The last example is also good (the + sign in the second generator is actually OK, I guess). I was actually thinking of a different way to generalize the twisted cubic. The ideal defining any parametric curve of the form α(t) = (t, t^{m}, t^{n}) will also give an ideal whose Gröbner fan has a ray common to all cones: namely the homogeneous weight vector (1, m, n).

Some Specific Comments

1) The fact that matrix orders represent all monomial orders is actually a theorem of an Italian mathematician named Lorenzo Robbiano. This result was actually a “big deal” in the subject when it first appeared.

2) An interesting aspect of the matrices defining some orders like the grevlex is that the same order is represented if you add scalar multiples of “higher” rows (i.e. smaller row index) to “lower” row (i.e. larger row index) in the matrix. (Think about how the comparison works!) This means that you actually never need to use negative entries in vectors either (all rows of the matrix can be vectors in the positive orthant). For instance, the grevlex order, x > y > z, in k[x, y, z] can also be defined by the matrix obtained by adding row 1 to row 2 and then the resulting row 2 to row 3:

M′_{2} = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} )

This observation is useful, for instance, since some software restricts the weight matrices to have nonnegative integer entries in each row.

3) Of course, there are several sets inequalities defining C_{G} in general – one set from each of the elements of G. So to make that perfectly clear it would be good to say explicitly: “for all i, 1 ≤ i ≤ t.”

4) In the proof that Mon(I) is finite for all ideals, the one point that wasn’t completely clear was that when you find the set Σ_{1} and the monomial ideal N_{1}, you then actually want to argue that the given set of generators {f_{1}, …, f_{s}} for I cannot be a Gröbner basis of I with respect to any of the orders in Σ_{1}. (Reason: if it is for any one, then it has to be for all of them. But the starting set Σ is chosen so that the ideals ⟨LT_{>}(I)⟨ for > in Σ were all distinct.) That’s what allows you to say there must be some other f_{s+1} and some leading term that is not divisible by any of the leading terms of f_{i}, i = 1, …, s. Then you repeat the same argument to produce the chains

Σ ⊃ Σ_{1} ⊃ Σ_{2} ⊃ ⋯

and c

N_{1} ⊂ N_{2} ⊂ ⋯

Paper:

Presentation:

Julianne Kulevich – Computer Algebra Methods for Studying and Computing Molecular Conformations

This was a good project and presentation, although I have some specific comments and suggestions about things you could have added or done differently. The main comment here is 1 below. It’s sometimes important in working on applied problems like this to make sure you really understand where the equations you end up solving come from in some detail.

Some Specific Comments

1) I was hoping to see some more details about how these equations are derived, both in the paper and when I asked you about this in the presentation. That’s what you need to make the connection between the solutions (t_{1}, t_{2}, t_{3}) of the transformed equations and the actual geometry of the molecules they represent. These equations can be derived like this. For instance, introduce coordinates so P_{6} is the origin and \overline{P_{6}P_{4}} is the x-axis . Then from the geometry of the triangles ΔP_{4}P_{5}P_{6} and ΔP_{2}P_{4}P_{6}, the coordinates of P_{5} are

(L_{6} cos(a_{1}), L_{6} cos(a_{1}) cos(θ_{3}), L_{6} sin(a_{1}) sin(θ_{3}))

where a_{1} is the angle at P_{6} in the “flap triangle” ΔP_{4}P_{5}P_{6}. Similarly, but with somewhat more work you get the coordinates of P_{1} are

(L_{1} (cos(a_{3}) cos(a_{2}) + sin(a_{3}) sin(a_{2}) cos(θ_{1})) ,
L_{1} (sin(a_{2}) cos(a_{3}) − sin(a_{3}) cos(a_{2}) cos(θ_{1}) ,
L_{1} sin(a_{3}) sin(θ_{1}))

where a_{2} is the angle in the base triangle at P_{6} and a_{3} is the angle in the flap triangle ΔP_{1}P_{2}P_{6}. Then the first equation comes from the fact that you know the bond angle at P_{6} so the dot product of the vectors P_{1} and P_{5} satisfies:

P_{1} · P_{5} − ∥P_{1}∥∥P_{5}∥ cos(ψ_{6}) = 0

You can work out this equation and get the explicit forms of the α_{2j} in terms of L_{6}, L_{1}, and the sines and cosines of the angles a_{1}, a_{2}, a_{3}. Similarly, the other two equations come from the angles at P_{2} and P_{4}.

2) I’m not 100% certain about the relative magnitudes of the improvements from a) better implementation of GB’s in Maple 10, and b) faster computer hardware on our radius server (and more memory space for intermediate computations) versus what Emiris and Mourrain had to work with in 1998. I would guess that both had an impact, but perhaps the software improvements had more effect.

3) The large coefficients in the final result are just the “tip of the iceberg.” In the computation of the lex GB you are actually building up more and more polynomials with these huge coefficients as you go along. The final reduced GB has only three elements, but intermediate stages could have many more, with even more terms than the polynomials here. In practical terms, this means that the amount of information you need to store in the course of the calculation can easily fill up the whole amount of memory available (and more). When that happens, programs like Maple will actually write polynomials (or parts of them) to temporary storage on the main hard disk of the computer system, and read them back in as those polynomials are used. This “swapping” information in and out of memory ends up taking up so much time and computing power to manage that the computation grinds to a halt.

4) It’s not entirely clear from the way you set up the solving why there are only four different solution vectors (x, y, z) = (t_{1}, t_{2}, t_{3}). It would have been better to use the full lex GB and the Extension Theorem. (Note that the other two GB polynomials have the form y − p_{15}(z), x − q_{15}(z), where the p_{15} and q_{15} are polynomials in z alone, each of degree 15. This shows directly that each value of z gives only one x and one y. If you plug one of the four real solutions of the z-equation into the other polynomials in the Gröbner basis you get one value of y and one value of x in each case.) Your way makes it look like there might be more than one solution vector with each z-value. It’s not easy to tell which x’s go with which y’s to give full solutions.

5) If you had done the derivation of the equations in more detail, you could have worked backwards to solve for the actual locations of the P_{i} and plotted them yourself using Maple(!)

6) We didn’t study Cayley-Menger matrices in this course, so to include this discussion, it would have been much better to say more about this. What does the matrix represent? What do you do with it?

Paper:

Presentation: