MAS400: Solutions 3

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

1. Perform multivariate division in F [x, y] for the following cases. For critical cases, one may assume that F = ℚ. Do them also with f_{1} and f_{2} interchanged, and for the monomial orders ⩽_{lex} and ⩽_{grlex} in which x > y. (You can also see what happens if x < y if you like.)

(a) f = xy^{3} − xy^{2}, f_{1} = xy − x, f_{2} = y^{3}.

(b) f = x^{2} + xy^{3}, f_{1} = xy + 1, f_{2} = y^{2}.

This working shows what you should have at each stage of the algorithm. Note that just one of q_{1}, q_{2}, r changes at each step, and then only by a term; p also changes at each step, but more then one term may be altered. The final line of table gives the output. In this working (but not in the question) all polynomials have been arranged so that the orders of their terms respect the monomial order in force, with the largest term being first. The leading coefficients of f_{1} and f_{2} are always 1, so this working applies in all fields. Mv-Div: ⩽_{lex}, ⩽_{grlex} (x > y); f = xy^{3} − xy^{2}, f_{1} = xy − x, f_{2} = y^{3}.

Step  p  q_{1} q_{2} r
0 (initial) xy^{3} − xy^{2} 0 0 0
1 (final)  0  y^{2} 0 0

Mv-Div: ⩽_{lex}, ⩽_{grlex} (x > y); f = xy^{3} − xy^{2}, f_{1} = y^{3}, f_{2} = xy − x.

Step  p  q_{1} q_{2}  r
0 (initial) xy^{3} − xy^{2} 0  0  0
1  −xy^{2} x  0  0
2  −xy  x −y  0
3  −x  x −y − 1 0
4 (final)  0  x −y − 1 −x

Mv-Div: ⩽_{lex} (x > y); f = x^{2} + xy^{3}, f_{1} = xy + 1, f_{2} = y^{2}.

Step  p  q_{1} q_{2} r
0 (initial) x^{2} + xy^{3} 0 0 0
1 xy^{3} 0 0 x^{2}
2  −y^{2} y^{2} 0 x^{2}
3 (final)  0  y^{2} −1 x^{2}

Mv-Div: ⩽_{lex} (x > y); f = x^{2} + xy^{3}, f_{1} = y^{2}, f_{2} = xy + 1.

Step  p  q_{1} q_{2} r
0 (initial) x^{2} + xy^{3} 0 0 0
1  xy^{3}  0 0 x^{2}
2 (final)  0  xy 0 x^{2}

Mv-Div: ⩽_{grlex} (x > y); f = xy^{3} + x^{2}, f_{1} = xy + 1, f_{2} = y^{2}.

Step  p  q_{1} q_{2} r
0 (initial) xy^{3} + x^{2} 0 0 0
1  x^{2} − y^{2} y^{2} 0 0
2  x^{2}  y^{2} −1 0
3 (final)  0  y^{2} −1 x^{2}

Mv-Div: ⩽_{grlex} (x > y); f = xy^{3} + x^{2}, f_{1} = y^{2}, f_{2} = xy + 1.

Step  p  q_{1} q_{2} r
0 (initial) xy^{3} + x^{2} 0 0 0
1  x^{2}  xy 0 0
2 (final)  0  xy 0 x^{2}

2. Perform multivariate division in F [x] when f ∈ {x^{4}, x^{4} − 1}, f_{1} = x^{3} + 1, f_{2} = x^{2} + 1, and also with f_{1} and f_{2} interchanged. Note that there is a unique monomial order in this case. Although F [x] is univariate, we cannot use univariate division as we are trying to simultaneously divide by two polynomials. What is the ideal I = ⟨f_{1}, f_{2}⟩ anyway?

The multivariate division proceeds in the same manner, regardless of field. We shall let f = x^{4} + λ, where λ is an arbitrary element of F. Mv-Div: f = x^{4} + λ, f_{1} = x^{3} + 1, f_{2} = x^{2} + 1.

Step  p  q_{1} q_{2}  r
0 (initial) x^{4} + λ 0 0  0
1  −x + λ x 0  0
2  λ  x 0 −x
3 (final)  0  x 0 −x + λ

Mv-Div: f = x^{4} + λ, f_{1} = x^{2} + 1, f_{2} = x^{3} + 1.

Step  p  q_{1} q_{2} r
0 (initial) x^{4} + λ  0  0 0
1  −x^{2} + λ x^{2} 0 0
2  1 + λ x^{2} − 1 0 0
3 (final)  0  x^{2} − 1 0 1 + λ

If 2 ≠ 0 (the general case) then 1 = \frac{x+1}{2}f_{1} + \frac{−x^{2}−x+1}{2}f_{2} ∈ I, and so I = F [x]. If char F = 2 (that is 2 = 0), for example when F = 𝔽_{2}, then x + 1 | f_{1} and x + 1 | f_{2} giving I ⩽ ⟨x + 1⟩. On the other hand we have x − 1 = x + 1 = f_{1} + xf_{2} ∈ I so that I = ⟨x + 1⟩. One obtains the ideal generators using the Euclidean Algorithm. In this case multivariate division is useless for membership testing in I.

3. Let I = ⟨\underline{x}^{α_{1}}, \underline{x}^{α_{2}}, …, \underline{x}^{α_{s}}⟩ be a (finitely generated) monomial ideal of F [x_{1}, …, x_{n}], and f ∈ F [x_{1}, …, x_{n}]. Show that if we apply multivariate division to divide f by (\underline{x}^{α_{1}}, \underline{x}^{α_{2}}, …, \underline{x}^{α_{s}}) then we get remainder r = 0 if and only if f ∈ I (regardless of the fixed monomial order used).

Let f = ∑_{α∈A} a_{α}\underline{x}^{α}, where a_{α} ∈ F \ \{0\} for all α ∈ A. Suppose that f ∈ I. By Lemma E of notes a_{α}\underline{x}^{α} ∈ I for all α ∈ A, and by Lemma D of notes get, for all α ∈ A, \underline{x}^{α_{i}} | \underline{x}^{α} for some i = i(α) depending on α. (This implication obviously reverses.)

Now if f ∉ I then multivariate division by the f_{i} = \underline{x}^{α_{i}} gives a nonzero remainder, so we now consider what happens when f ∈ I. Referring to notation from MultivariateDivision throughout we claim that the terms of p are always a subset of the terms of f (this would not be true in general). Also, the else part of while-loop is never invoked; therefore r remains 0 throughout. Certainly these are both true on entry to the while-loop, so suppose they both hold before an application of the loop (note that we would apply the loop again only when p ≠ 0). Let a_{α}\underline{x}^{α} = lt(p). Since a_{α}\underline{x}^{α} is a term of f there exists i such that f_{i} = \underline{x}^{α_{i}} | a_{α}\underline{x}^{α}. Now when t = lt(p)/ lt(f_{i}) (as per algorithm) we obtain tf_{i} = t lt(f_{i}) = lt(p), so the new p is a sum of terms of f (with one fewer terms than the old p). The else part of the while-loop was not invoked so r remains 0. Therefore r = 0 on exiting the while-loop, and we are done.