MAS400: Solutions 4

Throughout this sheet F will denote an arbitrary field unless otherwise stated.

1. Let f_{1} = xy − 1 and f_{2} = y^{2} − 1 be elements of ℚ[x, y]. Show that {f_{1}, f_{2}} is not a Gröbner basis for ⟨f_{1}, f_{2}⟩, with respect to ⩽_{lex} and x > y.

If {f_{1}, f_{2}} is a Gröbner basis then f rem (f_{1}, f_{2}) = f rem (f_{2}, f_{1}) for all f ∈ ℚ[x, y]. However, in lectures we saw that x^{2}y+xy^{2}+y^{2} rem (f_{1}, f_{2}) = x+y+1, while x^{2}y+xy^{2}+y^{2} rem (f_{2}, f_{1}) = 2x+1 (the latter calculation was left as an exercise).

Alternatively: Newer technology (Theorem T) indicates we must consider whether S(f_{1}, f_{2}) rem (f_{1}, f_{2}) = 0. We have lcm(lm f_{1}, lm f_{2}) = xy^{2}, so that S(f_{1}, f_{2}) = \frac{xy^{2}}{xy} f_{1} − \frac{xy^{2}}{y^{2}} f_{2} = yf_{1} − xf_{2} = −y + x. Multivariate division of S(f_{1}, f_{2}) by (f_{1}, f_{2}) or (f_{2}, f_{1}) gives q_{1} = q_{2} = 0 and remainder x − y ≠ 0, regardless of the monomial order chosen, so that {f_{1}, f_{2}} is not a Gröbner basis for ⟨f_{1}, f_{2}⟩. (Note that in this case it is fairly easy to spot a suitable linear combination f = p_{1}f_{1} + p_{2}f_{2} of f_{1} and f_{2} such that f rem (f_{1}, f_{2}) ≠ 0; Theorem T and the S-polynomials just provides a systematic way of finding suitable linear combinations.)

2. Let G = {g_{1}, …, g_{t}} ⊆ F [x_{1}, …, x_{n}] with 0 ∉ G. Suppose that, with respect to a fixed monomial

order, we have:

∀f ∈ ⟨g_{1}, …, g_{t}⟩, f rem (g_{1}, …, g_{t}) = 0.

Show that G is a Gröbner basis for ⟨G⟩.

We consider the algorithm MultivariateDivision. On each iteration of the while-loop we may add lt p to r, or leave r unchanged. But each iteration of the while-loop also strictly decreases mdeg p, so no term that is added to r can cancel previous terms. For f ∈ ⟨G⟩ the eventual remainder is zero, and so the else-part of the if-loop in the while-loop is never executed; therefore at all times during the execution of MultivariateDivision we have p = 0 or that lt p is divisible by (at least) one of the lt g_{i}. If f ≠ 0 then upon starting the first iteration of the while loop we have p = f, so that lt f is divisible by (at least) one of the lt g_{i}, and thus lt f ∈ ⟨lt g_{1}, …, lt g_{t}⟩. Therefore ⟨lt(⟨G⟩)⟩ ⩽ ⟨lt g_{1}, …, lt g_{t}⟩, and so G is a Gröbner basis for ⟨G⟩.

3. Let R be a ring (commutative with 1). Show that each ideal of R is finitely generated if and only if there are no infinite ascending chains of ideals:

I_{0} < I_{1} < I_{2} < I_{3} < · · · .

NB: I have proved a very similar result in lectures.

IF I is not finitely generated then we define I_{0} = 0, and I_{m} for m ⩾ 1 recursively as follows: We pick r_{m} ∈ I \I_{m−1}. Since I_{m−1} = ⟨r_{1}, …, r_{m−1}⟩ is finitely generated and I is not, we can always pick such an r_{m} for all m. Then I_{0} < I_{1} < I_{2} < ⋯ is a strictly ascending chain of R-ideals contained in I.

If each ideal is finitely generated we let I_{0} ⩽ I_{1} ⩽ I_{2} ⩽ ⋯ be an ascending chain of ideals (possibly with equalities at various points). Now I = ⋃_{n=0}^{∞} I_{n} is also an ideal (exercise), and so I is finitely generated, say I = ⟨r_{1}, …, r_{s}⟩. For i ∈ {1, …, s} there exists n_{i} ∈ ℕ such that r_{i} ∈ I_{n_{i}}. Let N = max(n_{1}, …, n_{s}). For n ⩾ N we have I_{n} ⩽ I (since I is the union of the I_{n}) and I ⩽ I_{n} (since I_{n} contains a generating set for I); thus I_{n} = I. Therefore I_{N} = I_{N+1} = I_{N+2} = ⋯, and no strictly infinite ascending chain of ideals exists.