MAS400: Solutions 5

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

1. Fix a monomial order on R = F [x_{1}, …, x_{n}] and let f, f_{1}, …, f_{m} ∈ R with f_{1}, …, f_{m} ≠ 0. Suppose that f rem (f_{1}, …, f_{s}) = 0 for some s ⩽ m. Show that f rem (f_{1}, …, f_{m}) = 0.

In the solution to Exercises 4, Question 2, we saw that if the remainder is zero after applying multivariate division then the else-part of the while-loop is never executed. So when dividing by (f_{1}, …, f_{s}) we always have lt f_{i} | lt p (notation p as in algorithm MultivariateDivision). We now claim that on division by (f_{1}, …, f_{s}) and (f_{1}, …, f_{m}) the values of p are the same after j executions of the while-loop (for j = 0, 1, 2, … t where t is the number of times the while-loop operates on division by (f_{1}, …, f_{s})), which we show by induction. Certainly this is true for j = 0, as p = f then. If it is true after j executions (and p ≠ 0) then there exists j ∈ {1, …, s} such that lt f_{j} | lt p, whence there exists j ∈ {1, …, m} such that lt f_{j} | lt p. Thus the value of i chosen by MultivariateDivision such that lt f_{i} | lt p satisfies 1 ⩽ i ⩽ m, and is the same for both divisions. Therefore the values of p are identical after j + 1 executions, and therefore identical always. Therefore division by (f_{1}, …, f_{m}) terminates after t executions of the while-loop and yields remainder 0.

2. Let F be your favourite field, and choose your favourite monomial order. State your choices clearly. With respect to your choices find a Gröbner basis for I in each of the following cases.

(a) Ideal I = ⟨xy − 1, y^{2} − 1⟩ in F [x, y].

(b) Ideal I = ⟨xy − 1, xz − 1⟩ in F [x, y, z].

(c) Ideal I = ⟨xy − 1, yz − 1, zx − 1⟩ in F [x, y, z].

(d) Ideal I = ⟨xy^{2} − 1, xz^{2} − 1⟩ in F [x, y, z].

(e) Ideal I = ⟨x^{2}y − 1, x^{2}z − 1⟩ in F [x, y, z].

(f) Ideal I = ⟨x^{2}y − 1, y^{2}z − 1, z^{2}x − 1⟩ in F [x, y, z].

Also find a reduced Gröbner basis for each of the above ideals. NB: Some of these questions may take a long time.

I shall take F = ℚ, and the ⩽_{lex} monomial order with x > y > z. Sample solutions are as follows. The multivariate division is left as an exercise for the reader.

(a) Take g_{1} = xy − 1, g_{2} = y^{2} − 1. S(g_{1}, g_{2}) = yg_{1} − xg_{2} = x − y and S(g_{1}, g_{2}) rem (g_{1}, g_{2}) = x − y. So set g_{3} = x − y. Then S(g_{1}, g_{2}) = x − y, S(g_{1}, g_{3}) = g_{1} − yg_{3} = y^{2} − 1 and S(g_{2}, g_{3}) = xg_{2}−y^{2}g_{3} = y^{3}−x all have zero remainder on division by (g_{1}, g_{2}, g_{3}) (the latter division requires two steps). Therefore {g_{1}, g_{2}, g_{3}} = {xy − 1, y^{2} − 1, x − y} is a Gröbner basis for I = ⟨xy − 1, y^{2} − 1⟩.

(b) Take g_{1} = xy − 1, g_{2} = xz − 1. S(g_{1}, g_{2}) = zg_{1} − yg_{2} = y − z and S(g_{1}, g_{2}) rem (g_{1}, g_{2}) = y − z. So set g_{3} = y − z. Then S(g_{1}, g_{2}) = y−z, S(g_{1}, g_{3}) = g_{1}−xg_{3} = xz−1 and S(g_{2}, g_{3}) = yg_{2}− xzg_{3} = xz^{2} − y all have zero remainder on division by (g_{1}, g_{2}, g_{3}) (the latter division requires two steps). Therefore {g_{1}, g_{2}, g_{3}} = {xy − 1, xz − 1, y − z} is a Gröbner basis for I = ⟨xy − 1, xz − 1⟩.

(c) Take g_{1} = xy − 1, g_{2} = yz − 1 and g_{3} = xz − 1. Then S(g_{1}, g_{2}) = zg_{1} − xg_{2} = x − z, S(g_{1}, g_{3}) = zg_{1} − yg_{3} = y − z and S(g_{2}, g_{3}) = xg_{2} − yg_{3} = −x + y. We get S(g_{1}, g_{2}) rem (g_{1}, g_{2}, g_{3}) = x − z, S(g_{1}, g_{3}) rem (g_{1}, g_{2}, g_{3}) = y − z, S(g_{2}, g_{3}) rem (g_{1}, g_{2}, g_{3}) = −x + y. Therefore we set g_{4} = x − z, g_{5} = y − z and g_{6} = −x + y. S(g_{1}, g_{4}) = g_{1} − yg_{4} = yz − 1, S(g_{1}, g_{5}) = xz − 1, S(g_{1}, g_{6}) = y^{2} − 1, S(g_{2}, g_{4}) = −x + yz^{2}, S(g_{2}, g_{5}) = z^{2} − 1, S(g_{2}, g_{6}) = −x+y^{2}z, S(g_{3}, g_{4}) = z^{2}−1, S(g_{3}, g_{5}) = xz^{2}−y, S(g_{3}, g_{6}) = yz−1, S(g_{4}, g_{5}) = xz − yz, S(g_{4}, g_{6}) = y − z, S(g_{5}, g_{6}) = −xz + y^{2} [with leading term written first]. We have S(g_{i}, g_{j}) rem (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}) = 0 for 1 ⩽ i < j ⩽ 6 except for (i, j) ∈ {(2, 5), (3, 4)}, when the remainder is z^{2} − 1. (The calculation that S(g_{2}, g_{3}) rem (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}) = 0 requires two steps of MV-Div, despite the fact that S(g_{2}, g_{3}) = g_{6}. The most difficult calculations require three steps of MV-Div; these were required to calculate the remainder after dividing S(g_{2}, g_{6}) and S(g_{5}, g_{6}) by (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}).) Anyway, we set g_{7} = z^{2} − 1, and calculate S(g_{1}, g_{7}) = xy − z^{2}, S(g_{2}, g_{7}) = y − z, S(g_{3}, g_{7}) = x − z, S(g_{4}, g_{7}) = x − z^{3}, S(g_{5}, g_{7}) = y − z^{3}, S(g_{6}, g_{7}) = x − yz^{2}. We have S(g_{i}, g_{j}) rem (g_{1}, g_{2}, g_{3}, g_{4}, g_{5}, g_{6}, g_{7}) = 0 for 1 ⩽ i < j ⩽ 7. By Question 1, we ‘only’ have to perform these MV-Divs if j = 7 or (i, j) ∈ {(2, 5), (3, 4)}. We are now done, and a Gröbner basis for ⟨xy − 1, yz − 1, xz − 1⟩ is {g_{1}, …, g_{7}} = {xy −1, yz −1, xz −1, x−z, y −z, −x+y, z^{2} −1}.

GröbnerBasis takes quite a long time here. To speed up the process, we observe that if r = f rem (f_{1}, …, f_{s}) then the ideals ⟨f, f_{1}, …, f_{s}⟩ and ⟨r, f_{1}, …, f_{s}⟩ coincide [Proof: Exercise]. With the notation of this question, observe that g_{6} = g_{5} − g_{4}, and that g_{4}, g_{5}, g_{6} have total degree 1, while g_{1}, g_{2}, g_{3} have total degree 2. We calculate that g_{1} rem (g_{4}, g_{5}) = g_{2} rem (g_{4}, g_{5}) = g_{3} rem (g_{4}, g_{5}) = z^{2} − 1. Thus I = ⟨f_{1}, f_{2}, f_{3}⟩ = ⟨g_{1}, g_{2}, g_{3}⟩ = ⟨g_{1}, g_{2}, g_{3}, g_{4}, g_{5}⟩ = ⟨g_{4}, g_{5}, g_{7}⟩, where g_{7} = z^{2} − 1. By considering just three S-polynomials we find that {x − z, y − z, z^{2} − 1} = {g_{4}, g_{5}, g_{7}} is a [reduced] Gröbner basis for I.

(d) Take g_{1} = xy^{2} − 1, g_{2} = xz^{2} − 1. S(g_{1}, g_{2}) = z^{2}g_{1} − y^{2}g_{2} = y^{2} − z^{2} and S(g_{1}, g_{2}) rem (g_{1}, g_{2}) = y^{2} − z^{2}. So set g_{3} = y^{2} − z^{2}. Then S(g_{1}, g_{2}) = y^{2} − z^{2}, S(g_{1}, g_{3}) = g_{1} − xg_{3} = xz^{2} − 1 and S(g_{2}, g_{3}) = y^{2}g_{3} − xz^{2}g_{3} = xz^{4} − y^{2} all have zero remainder on division by (g_{1}, g_{2}, g_{3}) (the latter division requires two steps). Therefore {g_{1}, g_{2}, g_{3}} = {xy^{2} − 1, xz^{2} − 1, y^{2} − z^{2}} is a Gröbner basis for I = ⟨xy^{2} − 1, xz^{2} − 1⟩.

(e) Take g_{1} = x^{2}y − 1, g_{2} = x^{2}z − 1. S(g_{1}, g_{2}) = zg_{1} − yg_{2} = y − z and S(g_{1}, g_{2}) rem (g_{1}, g_{2}) = y − z. So set g_{3} = y − z. Then S(g_{1}, g_{2}) = y − z, S(g_{1}, g_{3}) = g_{1} − x^{2}g_{3} = x^{2}z − 1 and S(g_{2}, g_{3}) = yg_{2} − x^{2}zg_{3} = x^{2}z^{2} − y all have zero remainder on division by (g_{1}, g_{2}, g_{3}) (the latter division requires two steps). Therefore {g_{1}, g_{2}, g_{3}} = {x^{2}y−1, x^{2}z−1, y−z} is a Gröbner basis for I = ⟨x^{2}y−1, x^{2}z−1⟩.

(f) Not done yet, as GröbnerBasis takes too long.

Reduced Gröbner bases 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}.

The major step is just to eliminate elements in the Gröbner bases given above whose leading term is divisible by the leading term of another element in the Gröbener basis (eliminate the terms one by one). One also normalises the terms of the Gröbner basis so that their leading coefficients are 1. One might have to make other adjustments to the Gröbner basis before it is in reduced form (see Question 2 on next sheet).

Changing the monomial order will change the reduced Gröbner basis. For example if we have ⩽_{lex} monomial order with y > x > z then the answer to Part (a) is {y−x, x^{2}−1}, while the answers to the other parts remain the same [with some reordering if we insist that the elements in a Gröbner basis be ordered by their leading terms].

If the monomial order is ⩽_{grlex} with x > y > z then the answers to Parts (a)–(e) remain the same [up to reordering] and the answer to Part (f) is {yz^{3} − x, z^{4} − y, y^{3} − z^{3}, y^{2}z − 1, x^{2} − yz, xy − z^{2}, xz − y^{2}}.