MAS400: Solutions 6

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

1. Show that for a given monomial order ⩽ on R ⩽ F [x_{1}, …, x_{n}] the reduced Gröbner basis of any ideal I ⩽ R is unique with respect to ⩽. (The reduced Gröbner basis of I can depend on the monomial order chosen.)

Let G = {g_{1}, …, g_{s}} be a reduced Gröbner basis for I. Then lt g_{i} ≠ lt g_{j} whenever i ≠ j (by the definition of a reduced Gröbner basis), and also lt g_{i} | lt g_{j} whenever i ≠ j. So order G so that lt g_{1} < lt g_{2} < ⋯ < lt g_{s}. Now let J := ⟨lt G⟩ = ⟨lt I⟩, so that J is a monomial ideal. By Lemma D, if f is a monomial in J then lt g_{i} | f for some i. Thus for all k, lt g_{k} ∉ ⟨lt g_{1}, …, lt g_{k−1}⟩. Let m_{1} be the minimum monomial in J. Then lt g_{i} | m_{1} for some i, and thus lt g_{1} ⩽ lt g_{i} ⩽ m_{1}. But lt g_{k} ∈ J for all k and so m_{1} ⩽ lt g_{1}, and thus lt g_{1} = m_{1} (and i = 1). Now define m_{2} to be the least monomial in J not belonging to ⟨m_{1}⟩, and for all k let m_{k} be the least monomial in J not belonging to ⟨m_{1}, …, m_{k−1}⟩ (if such exists). Evidently lt g_{2} ∈ J \ ⟨m_{1}⟩ and so m_{2} ⩽ lt g_{2}. Since m_{2} is divisible by some lt g_{i} for i ≠ 1 we get lt g_{2} ⩽ lt g_{i} ⩽ m_{2} and so m_{2} = lt g_{2}. Similarly, using induction, we get that m_{k} = lt g_{k} for all k. (Note that m_{i} will be defined for 1 ⩽ i ⩽ s, but that m_{s+1} will not be since J = ⟨lt G⟩.) Therefore lt G is uniquely determined, even as a multiset. Let G′ = {h_{1}, …, h_{s}} be ‘another’ reduced Gröbner basis for I where lt g_{i} = lt h_{i} for all i. The terms of g_{i} − h_{i} are not divisible by any of the lt g_{j} (resp. lt h_{j}). (The only terms of g_{i} or h_{i} divisible by any lt g_{j} or lt h_{j} is lt g_{i} = lt h_{i}, in the case i = j.)

2. Find an algorithm for reducing a Gröbner basis (for an ideal I of F = [x_{1}, …, x_{n}] w.r.t. some monomial order ⩽) to a reduced Gröbner basis. Write the algorithm in pseudo-code.

Given a Gröbner basis G = {g_{1}, …, g_{m}} of I we first perform the obvious first steps:

• Replace g_{i} by g_{i}/ lc g_{i} for all i.

• Order G so that lt g_{1} ⩽ lt g_{2} ⩽ ⋯ ⩽ lt g_{m}.

• For 1 ⩽ j ⩽ m if there is i < j such that lt g_{i} | lt g_{j} then remove g_{j} (there will always be an ‘unremovable’ g_{i} with this property, for g_{i} is removed only if lt g_{k} | lt g_{i} for some k < i, but then lt g_{k} | lt g_{j}).

So now we have a Gröbner basis G = {g_{1}, …, g_{m}} such that lt g_{1} < lt g_{2} < ⋯ < lt g_{m} and lc g_{i} = 1 for all i. Evidently lt g_{j} does not divide any term of g_{i} whenever i < j. We now produce a reduced Gröbner basis G = {g′_{1}, …, g′_{m}} for I, where lt g_{i} = lt g′_{i} for all i. This is done recursively as follows. Let g′_{1} = g_{1}. Initially, we assign g′_{2} = g_{2}. Now let t be the largest term of g′_{2} divisible by lt g_{1} and define (new) g′_{2} := g′_{2} − (t/ lt g_{1})g_{1}, and continue until no such term exists. This does not alter lt g_{i} for any i. Similarly once we have assigned g′_{1}, …, g′_{k−1} we initially let g′_{k} = g_{k}, and let t be the largest term of g′_{k} divisible by a lt g_{i} (where necessarily i < k) and define (new) g′_{k} := g′_{k} − (t/ lt g_{i})g_{i}, and continue until no such term exists. (I’ll leave it to you to show that this process terminates for each k.) The final {g′_{1}, …, g′_{m}} is a reduced Gröbner basis for I.)

Pseudo-code is given on a separate sheet. (The reduced Gröbner bases given below satisfy lt g_{1} > lt g_{2} > · · ·.)

3. Let G be a Gröbner basis for the non-zero ideal I ⩽ F [x]. Show that there exists f ∈ F [x] such that f ∈ G and I = ⟨f⟩.

If f ≠ 0 then lt f ∈ {1, x, x^{2}, …}, and if g ∈ I \ {0} and lt g = x^{i} then for all j ⩾ 0 we have gx^{j} ∈ I and lt(gx^{j}) = x^{i+j}. Therefore ⟨lt G⟩ = ⟨lt I⟩ = {x^{m}, x^{m+1}, x^{m+2}, …} for some m ∈ ℕ. So pick g ∈ G such that lt g = x^{m}, so that ⟨lt G⟩ = ⟨lt g⟩, and so {g} is a Gröbner basis for I, in particular I = ⟨g⟩ and {g} ⊆ G. (The reader may like to ponder the proof where I showed that all non-zero ideals I of F [x] are generated by any element g ∈ I where deg g is minimal among non-zero elements of I.)

4. Use elimination ideals to determine the following affine varieties.

(a) 𝕍(xy − 1, y^{2} − 1) ⊆ ℂ^{2}.

(b) 𝕍(xy − 1, xz − 1) ⊆ ℂ^{3}.

(c) 𝕍(xy − 1, yz − 1, zx − 1) ⊆ ℂ^{3}.

(d) 𝕍(xy^{2} − 1, xz^{2} − 1) ⊆ ℂ^{3}.

(e) 𝕍(x^{2}y − 1, x^{2}z − 1) ⊆ ℂ^{3}.

(f) 𝕍(x^{2}y − 1, y^{2}z − 1, z^{2}x − 1) ⊆ ℂ^{3}.

(g) 𝕍(x^{3}y − 1, xy^{3} − 1) ⊆ ℂ^{2}.

Recall that ⩽_{lex} (with x > y > z) is a j-elimination order for all relevant j. Except for the last one we calculated reduced Gröbner bases of the corresponding ideals in ℚ[x, y] or ℚ[x, y, z] w.r.t. ⩽_{lex} with x > y > z on the last exercise sheet. Answers are as follows.

(a) {x − y, y^{2} − 1}.

(b) {xz − 1, y − z}.

(c) {x − z, y − z, z^{2} − 1}.

(d) {xz^{2} − 1, y^{2} − z^{2}}.

(e) {x^{2}z − 1, y − z}.

(f) {x − z^{7}, y − z^{4}, z^{9} − 1}.

(g) {x − y^{5}, y^{8} − 1}. It was remarked in lectures that calculations for things like Multivariate Division and Gröbner Basis are unaltered when passing to field extensions. So the above are also reduced Gröbner bases for the appropriate ideals of ℂ[x, y] or ℂ[x, y, z] (depending on case). (The affine varieties will vary subtlely on field extension.) Using the notation ℂ^{×} := ℂ\{0}, ζ = exp(2πi/9), ω = exp(2πi/8) the solutions are as follows.

(a) 𝕍(xy − 1, y^{2} − 1) = { (a, a) : a ∈ {1, −1} }.

(b) 𝕍(xy − 1, xz − 1) = { (a^{−1}, a, a) : a ∈ ℂ^{×} }.

(c) 𝕍(xy − 1, yz − 1, zx − 1) = { (a, a, a) : a ∈ {1, −1} }.

(d) 𝕍(xy^{2} − 1, xz^{2} − 1) = { (a^{−2}, ±a, a) : a ∈ ℂ^{×} }.

(e) 𝕍(x^{2}y−1, x^{2}z−1) = \{ (±/\sqrt{a^{−1}}, a, a) : a ∈ ℂ^{×} \} = \{ (a, a^{−2}, a^{−2}) : a ∈ ℂ^{×} }.

(f) 𝕍(x^{2}y−1, y^{2}z−1, z^{2}x−1) = { (a^{7}, a^{4}, a) : a ∈ {1, ζ, ζ^{2}, ζ^{3}, ζ^{4}, ζ^{5}, ζ^{6}, ζ^{7}, ζ^{8}} }.

(g) 𝕍(x^{3}y − 1, xy^{3} − 1) = { (a^{5}, a) : a ∈ {1, ω, ω^{2}, ω^{3}, ω^{4}, ω^{5}, ω^{6}, ω^{7}} }. We did Part (b) in lectures. We’ll do Part (d) as a sample solution. Here we have G_{2} = G ∪ ℂ[z] = ∅, G_{1} = G ∪ ℂ[y, z] = {y^{2} − z^{2}} and G_{2} = G ∪ ℂ[x, y, z] = G = {xz^{2} − 1, y^{2} − z^{2}}. Thus I_{2} = 0 ⊆ ℂ[z], I_{1} = ⟨y^{2} − z^{2}⟩ ⊆ ℂ[y, z] and I_{0} = I = ⟨xz^{2} − 1, y^{2} − z^{2}⟩ ⊆ ℂ[x, y, z]. Therefore 𝕍I_{2} = { (a) : a ∈ ℂ }. Fix a ∈ ℂ. We get

{ b : b ∈ ℂ | (b, a) ∈ 𝕍I_{1} } = 𝕍(y^{2} − a^{2}) = {a, −a}

and so 𝕍I_{1} = { (±a, a) : a ∈ ℂ }. Fix a ∈ ℂ and ε ∈ {1, −1}. Then

{ b : b ∈ ℂ | (b, εa, a) ∈ 𝕍I_{0} } = 𝕍(xa^{2} − 1, (εa)^{2} − a^{2}) = 𝕍(xa^{2} − 1).

If a = 0 we get 𝕍(xa^{2} − 1) = ∅, otherwise 𝕍(xa^{2} − 1) = a^{−2}. Therefore 𝕍I = 𝕍I_{0} = { (a^{−2}, ±a, a) : a ∈ ℂ^{×} }.

It should be noted that these particular examples are more easily solved not using Gröbner bases and elimination ideals. In this question, we are being asked to solve systems of equations of the form x^{i}y^{j}z^{k} = 1, i, j, k ∈ ℕ, where in each case, and for each relevant variable, there is at least one equation involving that variable. Moreover, generally there are enough equations involving a variable to allow substitution to take place. For example in Part (f) we are trying to solve x^{2}y − 1 = y^{2}z − 1 = z^{2}x − 1 or x^{2}y = y^{2}z = z^{2}x = 1, whence 0 ∉ {x, y, z}. Now z^{2}x = 1 gives x = z^{−2}, whence we obtain the system of equations z^{−4}y = y^{2}z = 1. Thus y = z^{4} and y^{2}z = 1 gives z^{9} = 1. So we get the same answer as above.

For the system of equations x^{m}y − 1 = xy^{m} − 1 = 0 for m ⩾ 2 (generalisation of Part (g)) the equation xy^{m} − 1 = 0 gives y ≠ 0 and x = y^{−m}, and substituting into x^{m}y − 1 = 0 gives y^{−m^{2}}y − 1 = 0, or y^{m^{2}−1} = 1. So (x, y) = (λ^{−mi}, λ^{i}) for some i ∈ {0, …, m^{2} − 2} where λ = exp(2πi/(m^{2} − 1)). (I’ll leave it is an exercise for you to see this works.) Therefore

𝕍(x^{m}y − 1, xy^{m} − 1) = { (λ^{−mi}, λ^{i}) : 0 ⩽ i ⩽ m^{2} − 2 (i ∈ ℤ) } ⊆ ℂ.

Note that if m ⩾ 2 then the reduced Gröbner basis for ⟨x^{m}y−1, xy^{m}−1⟩ is {x − y^{m^{2}−m−1}, y^{m^{2}−1}}. Exceptional behaviour occurs when m = 1 (or −1).