Mathematics 392 – Seminar in Computational Commutative Algebra Selected Solutions – Problem Set 4 October 2, 2006

2.4/12 a) Given u ∈ Z_{≥0}^{n} and another monomial order >_{σ}, we define the weight order >_{u,σ} by

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

To show that >_{u,σ} is a monomial order, we will use Corollary 6.

(i) First for every pair of monomials x^{α} and x^{β}, either u · α > u · β, or u · α = u · β, or u · α < u · β. In the first case, x^{α} >_{u,σ} x^{β}; in the last case x^{β} >_{u,σ} x^{α}. In the case u · α = u · β, then we go on and compare using the >_{σ} order. Since that is a monomial order, either x^{α} >_{σ} x^{β}, or x^{α} = x^{β}, or x^{β} >_{σ} x^{α}. We have shown that >_{u,σ} is a total order.

(ii) Assume x^{α} >_{u,σ} x^{β} and let x^{γ} be another monomial. If u · α > u · β, then by the bilinearity of the dot product:

u · (α + γ) = u · α + u · γ > u · β + u · γ = u · (β + γ).

This shows x^{α+γ} >_{u,σ} x^{β+γ} in this case. If u · α = u · β, then x^{α} >_{σ} x^{β}. Since >_{σ} is a monomial order, it follows that x^{α+γ} >_{σ} x^{β+γ} also. So x^{α+γ} >_{u,σ} x^{β+γ} in this case also.

(iii) Finally, since u, α ∈ Z_{≥0}^{n}, u · α ≥ 0. If u · α > 0 then x^{α} >_{u,σ} 1. On the other hand, if u · α = 0, then we compare x^{α} with 1 using the >_{σ} order. Since >_{σ} is a monomial order x^{α} ≥_{σ} 1. Hence for all α, x^{α} ≥_{u,σ} 1, and the criterion of Corollary 6 is satisfied.

d) Let u = (1, …, 1, 0, …, 0) with i 1’s at the start. Define the elimination order >_{i} to be >_{u,grevlex}. Suppose x^{α} is any monomial containing one of the variables x_{j}, 1 ≤ j ≤ i, and x^{β} is any monomial containing only x_{i+1}, …, x_{n}. Then some α_{j} > 0 for 1 ≤ j ≤ i, and β_{j} = 0 for all 1 ≤ j ≤ i. Hence

\begin{aligned}u & = (1, …, 1, 0 … 0) \\ α & = (α_{1}, …, α_{i}, ∗, …, ∗) ⇒ u · α > 0 \\ β & = (0, …, 0, β_{i+1}, …, β_{n}) ⇒ u · β = 0 \end{aligned}

By the definition of the >_{i} order, x^{α} >_{i} x^{β} since u · α > u · β for these monomials.

2.5/8. (Note: for the following proof we assume k = R, or some other infinite field. The same conclusion is valid in all cases, but a slightly different proof would be needed if k is finite).

Let > be the lex order with x > y > z. We claim G = {x − z^{2}, y − z^{3}} is a Gröbner basis for I = ⟨G⟩. To show this, using the result of Problem 5, we must prove that if f ∈ I, then LT_{>}(f) is divisible by either x = LT_{>}(x − z^{2}) or y = LT_{>}(y − z^{3}). Begin by applying the division algorithm (same lex order) to write

(1)  f = a(x − z^{2}) + b(y − z^{3}) + r.

Since no term in r is divisible by either x or y, r is a polynomial in z alone. But now notice that V (x − z^{2}, y − z^{3}) is a twisted cubic curve, parametrized by z:

V (x − z^{2}, y − z^{3}) = {(z^{2}, z^{3}, z) : z ∈ R}.

If we substitute x = z^{2} and y = z^{3}, then since f ∈ I, f(z^{2}, z^{3}, z) = 0 for all z and we get

0 = a · 0 + b · 0 + r(z)

for all z ∈ R. Hence r is the zero polynomial. But then consider what happened at the first step of the division that produced the equation (1). Either x = LT_{>}(x − z^{2}) or y = LT_{>}(y−z^{3}) must have divided LT_{>}(f), or else a nonzero term would have been placed in r.

2.5/9. The idea here is the same as in 8. The kernel of the echelon form matrix is a vector subspace V of k^{n}, which can be parametrized by substituting values for the “free variables” in the corresponding system of linear equations. When we take another polynomial f in the ideal I = ⟨g_{1}, …, g_{m}⟩ generated by the linear polynomials from the rows of the matrix, it vanishes on the subspace V. So we apply the division algorithm, using any monomial order that makes the leading term of g_{i} equal to the term from the 1 in the leftmost nonzero position on that row. The result is

f = a_{1}g_{1} + … a_{m}g_{m} + r

where r depends only on the free variables in the linear system. Substituting the parametrization for V shows that r must be the zero polynomial. But then LT (f) is a multiple of LT (g_{i}) for some i. Hence {g_{1}, …, g_{m}} is a Gröbner basis by the result from Problem 5.

2.5/10. We want to use the result from Problem 5 again. Let I = ⟨g⟩ be a principal ideal, and let G be any set containing g. We claim that G is a Gröbner basis for I. This follows from the fact that for any two polynomials g, h and any monomial order >:

LT_{>}(hg) = LT_{>}(h)LT_{>}(g).

This is a consequence of the compatibility of > with multiplication in k[x_{1}, …, x_{n}]. Proof goes like this: Let x^{α} = LM_{>}(g) and x^{β} = LM_{>}(h). Every term in the product hg is cx^{γ}x^{δ} for some x^{γ} in h and some x^{δ} in g. But then

x^{γ}x^{δ} ≤ LT_{>}(h)x^{δ} ≤ LT_{>}(h)LT_{>}(g).

If f ∈ I, then f = hg for some h. Hence LT_{>}(f) is a multiple of LT_{>}(g) by the above. Hence G is a Gröbner basis for I.