Plan for PURE Math 2012 Seminar

Week 2

Monday: Polynomial division (Chapter 2, §3) – put some discussion of monomial orders defined by matrices into Tuesday’s discussion Tuesday: Lecture on monomial ideals, Dixon’s Lemma; discussion: more on monomial orders (Chapter 2, §4) Wednesday: Definition of Gröbner bases (Chapter 2, §§5,6) Buchberger’s Algorithm (omit proof of Buchberger’s S-pair Criterion) (Chapter 2, §7) Thursday: First examples – Elimination theory (Chaper 2, §8, Chapter 3, §1)

PURE Math 2012 - Seminar Week 2 Discussions - Polynomial Division, Gröbner Bases, First Applications

Day 1: The Division Algorithm in k[x_{1}, …, x_{n}]

Background

Given a monomial order, polynomials f_{1}, …, f_{s} (the divisors), and another polynomial f, we have seen an algorithm for producing quotients a_{1}, …, a_{s} and remainder r satisfying an equation:

(∗)  f = a_{1}f_{1} + ⋯ + a_{s}f_{s} + r,

and the conditions that

1) multideg(a_{i}f_{i}) ≤ multideg(f) for all i where a_{i} ≠ 0, and

2) no monomial in r is divisible by any of the LT (f_{i}).

Discussion Questions

A) Do Problem 1 from Chapter 2, §3 of “IVA” individually and compare your results. What does this say about the uniqueness of the quotients and remainders on division? Explain carefully what they depend on.

B) Do Problem 9 from Chapter 2, §3 of “IVA”. C) Problem 11 from Chapter 2, §3 of “IVA”

1) The hardest part of this is probably just understanding what all of the notation means. Work out an explicit example first. Take

\begin{aligned}f_{1} & = x^{4} + x^{2}y + y^{3} + 1 \\ f_{2} & = x^{2}y − 3 \\ f_{3} & = y^{3} − 3y + 1, \end{aligned}

use the lex order with x > y, and divide f_{1}, f_{2}, f_{3} into f = x^{5}. Draw a picture in Z_{≥0}^{2} showing the sets Δ_{i} and Δ, and verify that the conditions in part c are satisfied for your quotients a_{i} and your remainder.

2) Now work out the general proofs. An important lesson here: Never underestimate the power of working out examples to clarify things! But of course, the examples are not always the ultimate goal in mathematics since we usually want to establish general statements!)

Day 2: Dixon’s Lemma, More on Monomial Orders

A) Do Problem 4 in §4 of Chapter 2 to practice with ideas connected to Dixon’s Lemma.

The main portion of today’s discussion is devoted to some additional ideas related to monomial orders. Besides the lex, grevlex, grlex orders we discussed in class, there are many other ways to define monomial orders. The following construction gives a general way to understand the process.

Defining a Monomial Order by a Matrix

We have discussed the construction of weight orders >_{w}, where we compare two monomials x^{α} and x^{β} first by taking dot products of their exponent vectors with a fixed weight vector w, the “break ties” if α · w = β · w using another order.

Generalizing the weight orders >_{w}, we can also define monomial orders on k[x_{1}, …, x_{n}] starting from any m × n matrix M with

• m ≥ n,

• rank(M) = n,

• all entries non-negative integers.

(The same construction also works for M with non-negative real entries, but the GroebnerBasis command in Mathematica will accept only rational entries in weight vectors, so we will not discuss that extension.) Namely, suppose the rows of M are the vectors w_{1}, …, w_{n}. Then we can compare monomials x^{α} and x^{β} by first comparing their w_{1}- weights, then breaking ties sucessively with the w_{2}-weights, w_{3}-weights, and so on through the w_{m}-weights. In symbols:

(1)

x^{α} >_{M} x^{β} ⇔ w_{1} · α > w_{1} · β
or [(w_{1} · α = w_{1} · β) and (w_{2} · α > w_{2} · β)]
or [(w_{1} · α = w_{1} · β) and (w_{2} · α = w_{2} · β) and (w_{3} · α > w_{3} · β)]
or ⋯
or [(w_{1} · α = w_{1} · β) and ⋯ and (w_{m−1} · α = w_{m−1} · β) and (w_{m} · α > w_{m} · β)]

Discussion Questions

All the monomial orders we will need can be specified as >_{M} orders for appropriate matrices M.

B)

1) For instance, show that the lex order with x_{1} > … > x_{n} on k[x_{1}, …, x_{n}] is defined by M = I_{n}, the n × n identity matrix.

2) Show that the grevlex order, with x > y > z, is defined by the matrix

M_{grevlex} = ( \begin{matrix}1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} )

(The same pattern works for polynomial rings in any number of variables.)

3) Negative entries can also appear in these matrices. For instance, show that the grevlex order with x > y > z could also defined using

M_{grevlex} = ( \begin{matrix}1 & 1 & 1 \\ 0 & 0 & −1 \\ 0 & −1 & 0 \end{matrix} )

What is the corresponding matrix for the grevlex order with x_{1} > x_{2} > ⋯ > x_{n}?

C) The grlex (graded lex) order in k[x, y, z] compares monomials first by total degree (weight vector w_{1} = [1, 1, 1]), then breaks ties by the lex order. This shows >_{grlex}=>_{M} for the matrix M here:

M = M_{grlex} = ( \begin{matrix}1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} )

Show that we could also use

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

That is, show the last row in M is actually superfluous. (Hint: Making comparisons as in (1), when would we ever need to use the last row?)

D) Show that if the m × n matrix of rational numbers M satisfies

• m ≥ n,

• rank(M) = n (the largest possible for a matrix of this shape),

• the uppermost nonzero entry in each column (i.e. the first nonzero entry down from the top of the column) is positive.

then (1) defines a monomial order >_{M}. Be sure you see and explain why the condition on the rank of M is necessary.

E) In Sage/Singular, we can define monomial orders by this process. For instance, to define a weight order with w = (2, 4, 8) and ties broken by grevlex with x > y > z, it might be most natural to use

M = ( \begin{matrix}2 & 4 & 8 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 0 \end{matrix} )

But Singular requires an invertible square matrix to define a monomial order. So, we need to pick a set of n = 3 linearly independent rows out of this matrix M. But which ones?? The choice of any three linearly independent rows gives some monomial order, but it may not be the one we want. Here is an example. Consider the two matrices:

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

(In M′ we have omitted the fourth row of M, while in M′′, we have omitted the third row of M.)

1) Consider the monomials x^{2}z^{2} and y^{3}z. Which is bigger under the matrix order >_{M′}? Which is bigger under the matrix order >_{M′′}? Which should be bigger under the weight order >_{w,grevlex} (comparing w-weights first, then breaking ties with >_{grevlex})? What does this say about the matrices M′ and M′′ – which is not the “right” 3 × 3 matrix to use?

2) Given an m×n matrix M defining an order >_{M}, describe a general method for picking the correct n × n submatrix M′ of M to define the same order, and prove that your method is correct.

Day 3: Gröbner Bases (Finally!)

Background

We have now seen the definition of a Gröbner basis. Given an ideal I ⊂ k[x_{1}, …, x_{n}] and a monomial order >, a Gröbner basis for I is a set of polynomials {g_{1}, …, g_{t}} ⊂ I with the property that the leading terms of the g_{i} generate the ideal of all leading terms of elements of I: in symbols:

⟨LT (g_{1}), …, LT (g_{t})⟩ = ⟨LT (I)⟩.

Gröbner bases exist for all non-zero ideals because of the result we called Dickson’s Lemma. Recall the idea: Every monomial ideal has a finite generating set. So if we apply this to the monomial ideal ⟨LT (I)⟩ and get a finite generating set {x^{α(1)}, …, x^{α(t)}}, then there are polynomials g_{i} ∈ I with LT (g_{i}) = x^{α(i)} for all i, and the g_{i} form a Gröbner basis for I by the definition. Soon, we will learn a criterion for when a set is a Gröbner basis and an algorithm for finding them (both discovered by the Austrian mathematician Bruno Buchberger). For now, we want to get a feeling for what the definition means.

The S-polynomial of two polynomials f, g with respect to a monomial order > is defined in “IVA” as:

S(f, g) = \frac{x^{γ}}{LT (f)}f − \frac{x^{γ}}{LT (g)}g,

where x^{γ} = LCM(LM(f), LM(g)). By Buchberger’s Criterion, we know that G = {g_{1}, …, g_{t}} ⊂ I is a Gröbner basis for I if and only if

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

for all pairs (i, j) with 1 ≤ i < j ≤ t.

This gives the idea behind an algorithm for computing Gröbner bases we discussed in class, starting from an arbitrary ideal basis F = {f_{1}, …, f_{s}} for I. We start with G = F, compute S-polynomial remainders, and adjoin any non-zero polynomials we find to the set G. This process is iterated until Buchberger’s Criterion is satisfied, and we have a Gröbner basis. The resulting algorithm is called Buchberger’s Algorithm for Gröbner bases.

Discussion Questions

From Chapter 2, §5 of “IVA” do: A) Problem 5. (This gives an alternate form of the condition defining a Gröbner basis

that is sometimes useful.) B) Problem 6. (This is probably the most useful property of Gröbner bases: If G is a

Gröbner basis for I and f ∈ I, then the remainder on division of f by G is guaranteed to be zero!)

C) Problems 7, 8. (Suggestion: Try “making” some other polynomials in the ideals, and see if you can tell whether the condition for Gröbner bases from Problem 5 is always true.)

D) Consider an ideal I ⊂ k[u_{1}, …, u_{m}, v_{1}, …, v_{n}] for n, m ≥ 1 generated by polynomials of the following form:

I = ⟨v_{1} − f_{1}(u_{1}, …, u_{m}), …, v_{n} − f_{n}(u_{1}, …, u_{m})⟩

where the f_{i} are arbitrary polynomials. Show that the given generators form a Gröbner basis for I with respect to some particular monomial order (which one?).

E) Let f_{1} = x^{3}y − x and f_{2} = y^{2} − x.

1) Is {f_{1}, f_{2}} a Gröbner basis for I = ⟨f_{1}, f_{2}⟩ with respect to the lex order, x > y or with y > x? Why or why not?

2) Apply Buchberger’s Algorithm to find Gröbner bases for the ideal I = ⟨f_{1}, f_{2}⟩ first using the lex order with x > y, and second using the lex order with y < x. Your results should look quite different.

Day 4: Elimination

We have now seen the Elimination and Extension Theorems from Chapter 3, §1. The Elimination Theorem shows that lexicographic Gröbner bases systematically eliminate variables “as much as possible” in the following sense.

• (Elimination Theorem) Let I be an ideal in k[x_{1}, …, x_{n}], and G a Gröbner basis of I with respect to the lex order with x_{1} > x_{2} > ⋯ > x_{n}. Let I_{i} = I ∩ k[x_{i+1}, …, n] be the ith elimination ideal of I. Then G_{i} = G ∩ k[x_{i+1}, …, n] is a Gröbner basis of I_{i} for each i, 1 ≤ i ≤ n − 1.

• The Extension Theorem then gives a condition under which (a_{i+1}, …, a_{n}) ∈ V (I_{i}) can be extended to (a_{i}, a_{i+1}, …, a_{n}) ∈ V (I_{i}).

Discussion Questions

A) Using Sage/Singular, I computed a Gröbner basis for the ideal I = ⟨x^{2} + y^{2} + z^{2} − 4, xz − y, y^{2} − z^{2} + 1⟩ with respect to the lex order, x > y > z, and found the output:

2z^{4} − 4z^{2} − 1, y^{2} − z^{2} + 1, x − 2yz^{3} + 4yz.

1) Using the Elimination Theorem, give Gröbner bases for the elimination ideals I_{1} = k[y, z] and I_{2} = k[z].

2) What does the Extension Theorem say about the number of points in the variety V(I) ∈ C^{2}? What are those points?

B) In this problem, we will see reasons for some of the patterns you may have noticed in various examples. Let V be a finite set in C^{n} and let I = I(V) = ⟨f_{1}, …, f_{s}⟩ ⊂ C[x_{1}, …, x_{n}] be the ideal of all polynomials that are zero at all the points of V.

1) Show that for each i, 1 ≤ i ≤ n, I must include a nonzero polynomial p_{i}(x_{i}) that depends only on the variable x_{i}.

2) Show that if we compute a Gröbner basis G for I with respect to a lex order >_{i} with x_{i} as the last - i.e. smallest variable, then p_{i}(x_{i}) must appear in that Gröbner basis G. (Hint: If cx_{i}^{α} = LT_{>_{i}}(p_{i}(x_{i})) is the leading term of p_{i}(x_{i}), then some Gröbner basis element g in G must have a leading term (with respect to this special lex order >_{i} which divides cx_{i}^{α}. What does that say about the form of g?

3) Let V be a finite set in C^{3} which is in “general position” in the sense that the zcoordinates of the points of V are distinct. Let I = I(V). What does the Gröbner basis for I = I(V) with respect to the lex order, x > y > z look like? (How many polynomials will it contain, what are their forms, etc.?)

4) What would the corresponding statement be for finite V in “general position” in C^{n} for general n ≥ 2?

Additional Hints for 3 and 4: Note that the “general position” hypothesis is not satisfied, for instance, for the Gröbner basis from question B above (Why not?) Think about what part 2 tells you here. You will get one of the Gröbner basis elements that way. Then, what do the others look like? For instance, is there a polynomial of the form y − f(z) in the ideal (hence in the first elimination ideal I ∩ C[y, z]? Must it appear in the lex Gröbner basis? If so, why? Then, what about polynomials involving x? The answer is a special case of a result sometimes called the “Shape Lemma.”