Manuel Kauers Hagenberg, January 18, 2003 RISC-Linz

Computer Algebra Exercises

Solution 8

Ex. (36) Let ≤_{1}, ≤_{2} be admissible orderings. We have to show that also ≤ := prod(≤_{1}, ≤_{2}) is admissible. This means that 1 is its minimum and a ≤ b implies ac ≤ bc for all a, b, c.

1 is the minimum of ≤: Let t_{1} ∈ [x_{1}, …, x_{i}] and t_{2} ∈ [x_{i+1}, …, x_{n}]. Then

1 ≤ t_{1}t_{2} ⟺ 1 <_{1} t_{1} ∨ (1 =_{1} t_{1} ∧ 1 ≤_{2} t_{2})

Since ≤_{1} is an admissible order, 1 <_{1} t_{1} or 1 =_{1} t_{1} must be true. In the first case, we are done, and in the second case, we have 1 ≤_{2} t_{2} which is asserted by the admissibility of ≤_{2}.

≤ is monotonous: Let a = a_{1}a_{2}, b = b_{1}b_{2} and c = c_{1}c_{2} be such that a ≤ b. Then, by definition,

a_{1} <_{1} b_{1} ∨ (a_{1} =_{1} b_{1} ∧ a_{2} ≤_{2} b_{2})

which by the admissibility of ≤_{1} and ≤_{2} and some other trivial properties (“monotonicity” of =_{1} and ≠_{1}) also implies

a_{1}c_{1} <_{1} b_{1}c_{1} ∨ (a_{1}c_{1} =_{1} b_{1}c_{1} ∧ a_{2}c_{2} ≤_{2} b_{2}c_{2}),

i.e. ac ≤ bc.

This completes the proof.

Ex. (37) To prove: Any admissible ordering on [X] = [x_{1}, …, x_{n}] is noetherian, i.e. any strictly descending sequence is finite.

Assume that s_{1}, s_{2}, … is in strictly descending sequence. The admisibility of the order asserts that none of the s_{i} can lie in the intersection of the cones spanned by the s_{j} (j < 1), because the elements of the cone with corner s_{i} are of the form s = s_{i} · t and hence s ≥ s_{i}.

In order to be outside the the cone of s_{1}, the term s_{2} must have a strictly lower exponent in at least one variable. It is clear by inspection that there are only finitely many terms in the square spanned by gcd(s_{1}, s_{2}), s_{1} and s_{2}. We can ignore them and find that the next term, say s_{3}, has to be strictly less than gcd(s_{1}, s_{2}), i.e. it cannot lie in its cone, i.e. it must have at least one variable with strictly smaller exponent.

We see that a strictly decreasing sequence of terms induces strictly decreasing sequences on the exponents. But the exponents live in the natural numbers, so each of them finally has to be finite. Since there are only finitely many variables, all of the exponent sequences have to be finished at some point. This completes the “proof.”

Ex. (38) Let f_{1} = x^{2}y + xy + 1, f_{2} = y^{2} + x + y ∈ ℤ_{3}[x, y]. We compute a Grö bner basis of ⟨f_{1}, f_{2}⟩ wrt. graduated lexicographical ordering where x > y by Bruno’s algorithm.

f_{1} = x^{2}y + xy + 1
f_{2} = y^{2} + x + y
S(f_{1}, f_{2}) = xy^{2} + y − x^{3} − x^{2}y
⟶^{−xf_{2}} −xy^{2} − x^{2} − xy

⟶^{+f_{1}} −x^{3} + y − x^{2} + 1 =: f_{3}

S(f_{1}, f_{3}) = x + y^{2} − y

⟶^{−f_{2}} 0

S(f_{2}, f_{3}) = −x^{4} − x^{3}y + y^{2}x^{2} − y^{3} − y^{2}
⟶^{−xf_{3}} −x^{3}y + y^{2}x^{2} − y^{3} − y^{2} + x^{3} − xy − x
⟶^{−yf_{3}} −2x^{3}y + y^{2}x^{2} − y^{3} + x^{3} − xy − x − x^{2}y + y

⟶^{−2yf_{3}} y^{2}x^{2} − y^{3} + x^{3} − xy − x + x^{2}y − y − 2y^{2}

⟶^{−x^{2}f_{2}} −y^{3} − xy − x − y − 2y^{2}
⟶^{+yf_{2}} −x − y^{2} − y

⟶^{+f_{2}} 0.

Hence,

{x^{2}y + xy + 1, y^{2} + x + y, −x^{3} + y − x^{2} + 1}

is a Gröbner basis of ⟨f_{1}, f_{2}⟩.

Ex. (39) We use Gröbner basis computations to find solutions of the system

f_{1}(x, y, z) = 2xy − yz + 2z
f_{2}(x, y, z) = x^{2} + yz − 1
f_{3}(x, y, z) = xz + yz − 2x

Using a lexicographic ordering with x > y > z, Maple gives us the following (reduced) Gröbner basis:

{56z^{3} − 72z^{2} + 32z − 16 + 2z^{5} − 21z^{4},
−96 − 194z^{2} − 6z^{4} + 67z^{3} + 56y + 224z,
112x + 10z^{4} − 93z^{3} + 146z^{2} − 84z − 8}

A factorisation shows that the first polynomial is irreducible in ℚ. Let α be an algebraic number that is a root of this polynomial. We know that every solution of the system must have z = α. We plug z = α into the second equation and get

y = \frac{3}{28}α^{4} − \frac{67}{56}α^{3} + \frac{97}{28}α^{2} − 4α + \frac{12}{7}.

We can do the same with the last polynomial and get

x = \frac{3}{4}α − \frac{5}{56}α^{4} + \frac{93}{112}α^{3} − \frac{73}{56}α^{2} + \frac{1}{14}.

Summarizing, we got the point

(x, y, z) = (\frac{3}{4}α − \frac{5}{56}α^{4} + \frac{93}{112}α^{3} − \frac{73}{56}α^{2} + \frac{1}{14}, \frac{3}{28}α^{4} − \frac{67}{56}α^{3} + \frac{97}{28}α^{2} − 4α + \frac{12}{7}, α)

as solution to the original system. This was pretty easy!

Ex. (40) Now consider the system

f_{1}(x, y, z) = xz − xy^{2} − 4x^{2} − \frac{1}{4}
f_{2}(x, y, z) = y^{2}z + 2x + \frac{1}{2}
f_{3}(x, y, z) = x^{2}z + y^{2} + \frac{1}{2}x.

We compute a Gröbner basis wrt. lexicographic ordering with x > y > z. This gives us

G := {5z^{5} + 8z^{4} + 3z^{3} − 26z^{2} − 102z + 60,
33 134 + 1 388y^{2} + 6 295z − 2 405z^{2} − 3 017z^{3} − 1 445z^{4},
2 776x + 705z^{4} + 1 538z^{3} + 1 219z^{2} − 3 656z − 16 646}

The first polynomial is again irreducible over ℚ, let α be a root of it, and solve the second polynomial over ℚ(α). This leads to another algebraic number β, and the last polynomial is linear in ℚ(α, β)[x].

Hence, the solution is

(x, y, z) = (−\frac{5}{56}α^{4} + \frac{93}{112}α^{3} − \frac{73}{56}α^{2} + \frac{3}{4}α + \frac{1}{14}, β, α),

as it was on the previous sheet.