Manuel Kauers Hagenberg, January 13, 2003 RISC-Linz

Computer Algebra Exercises

Solution 7

Ex. (31) Let

a(x, y) = xy^{2} − x^{3}y − 2x^{2}y + xy + 2x^{4} − 2x^{2}
= xy^{2} + (−x^{3} − 2x^{2} + x)y + (2x^{4} − 2x^{2})
b(x, y) = 2x^{2}y^{2} − 4x^{3}y + 4x^{3}.

We are about to compute the resultant of a and b with respect to y. Writing

m = n = deg_{y}(a) = deg_{y}(b) = 2.

and

d = max_{0≤i≤m} ||a_{i}|| = 4, e = max_{0≤i≤n} ||b_{i}|| = 4,

we get the coefficient bound

B = 2(m + n)!d^{n}e^{m} = 2 · 4! · 4^{2} · 4^{2} = 12 288.

We compute the resultant by the algorithm RES MOD. The following table shows the intermediate results.

P  p  c_{p}  c
1  2  FAIL  0
1  3  FAIL  0
1  5  FAIL  0
1  7  FAIL  0
1  11  FAIL  0
1  17  FAIL  0
1  19 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8}  8x^{12} + 3x^{11} − 3x^{9} + 8x^{8}
19  23 8x^{12} + 7x^{11} + 16x^{9} + 8x^{8} 8x^{12} − 16x^{11} + 16x^{9} + 8x^{8}
437 29 8x^{12} + 13x^{11} + 16x^{9} + 8x^{8} 8x^{12} − 16x^{11} + 16x^{9} + 8x^{8}
12 673 Stop: P = 12 673 > 12 288 = B

We get the result

Res_{y}(a, b) = 8x^{12} − 16x^{11} + 16x^{9} + 8x^{8}.

For the computation of the c_{p}, we show the intermediate results for p = 19 only.^{1} For failing primes, the computation is not interesting, the failure is just due to the fact that there are to few evaluation points. For the other contributing primes, the table of intermediate results looks similar.

For the shown p = 19, the degree bound amounts to B = 17.

1The author wishes to thank Tobias Beck for finding a subtle bug in the code which generated the data in the table on the following page.

\begin{matrix}β & a_{p}(β, y) & b_{p}(β, y) & c_{β} & c_{p} \\ 0 & 0 & 0 & FAIL & 0 \\ 1 & y^{2} + 17y & 2y^{2} + 15y + 4 & 16 & 16 \\ 2 & 2y^{2} + 5y + 5 & 8y^{2} + 6y + 7 & 18 & 2x + 14 \\ 3 & 3y^{2} + 15y + 11 & 18y^{2} + 6y + 1 & 17 & 8x^{2} + 16x + 11 \\ 4 & 4y^{2} + 3y + 5 & 13y^{2} + 10y + 17 & 8 & 15x^{3} + 13x^{2} + 10x + 15 \\ 5 & 5y^{2} + y + 3 & 12y^{2} + 13y + 11 & 2 & 7x^{4} + 2x^{3} + 11x^{2} + 2x + 13 \\ 6 & 6y^{2} + 3y + 12 & 15y^{2} + 10y + 16 & 4 & 9x^{5} + 5x^{4} + 7x^{3} + 17x + 16 \\ 7 & 7y^{2} + 3y + 11 & 3y^{2} + 15y + 9 & 12 & 18x^{6} + 11x^{5} + x^{4} + x^{3} + 10x^{2} + 14x + 18 \\ 8 & 8y^{2} + 14y + 8 & 14y^{2} + 4y + 6 & 8 & 17x^{7} + 17x^{6} + 13x^{5} + 7x^{4} + 10x^{3} + 16x^{2} + 3x + 9 \\ 9 & 9y^{2} + 11y + 2 & 10y^{2} + 10y + 5 & 14 & 13x^{8} + 5x^{7} + 9x^{6} + 2x^{5} + 4x^{4} + 2x^{3} + 10x^{2} + 12x + 16 \\ 10 & 10y^{2} + 7y + 2 & 10y^{2} + 9y + 5 & 9 & 18x^{9} + x^{8} + 9x^{7} + 16x^{6} + 18x^{5} + 4x^{4} + 13x^{3} + 11x^{2} + 6x + 15 \\ 11 & 11y^{2} + 15y + 8 & 14y^{2} + 15y + 6 & 6 & 18x^{9} + x^{8} + 9x^{7} + 16x^{6} + 18x^{5} + 4x^{4} + 13x^{3} + 11x^{2} + 6x + 15 \\ 12 & 12y^{2} + 10y + 11 & 3y^{2} + 4y + 9 & 9 & 18x^{9} + x^{8} + 9x^{7} + 16x^{6} + 18x^{5} + 4x^{4} + 13x^{3} + 11x^{2} + 6x + 15 \\ 13 & 13y^{2} + 5y + 12 & 15y^{2} + 9y + 16 & 3 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \\ 14 & 14y^{2} + 13y + 3 & 12y^{2} + 6y + 11 & 10 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \\ 15 & 15y^{2} + 9y + 5 & 13y^{2} + 9y + 17 & 13 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \\ 16 & 16y^{2} + 6y + 11 & 18y^{2} + 13y + 1 & 8 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \\ 17 & 17x^{2} + 17y + 5 & 8y^{2} + 13y + 7 & 17 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \\ 18 & 18y^{2} + 17y & 2y^{2} + 4y + 4 & 16 & 8x^{12} + 3x^{11} + 16x^{9} + 8x^{8} \end{matrix}

2 Ex. (32) Let

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.

Then, by Maple,

r_{zy}(x) = Res_{z}(Res_{y}(f_{1}, f_{2}), Res_{y}(f_{1}, f_{3}))
= −8x^{7} + 32x^{6} + 64x^{5} + 16x^{4} − 56x^{3} + 16x^{2},
r_{zx}(y) = Res_{z}(Res_{x}(f_{1}, f_{2}), Res_{x}(f_{1}, f_{3}))
= 16y^{8} − 128y^{6} + 320y^{5} − 576y^{4} + 512y^{3} − 256y^{2},
r_{yx}(z) = Res_{y}(Res_{x}(f_{1}, f_{2}), Res_{x}(f_{1}, f_{3}))
= −64z^{8} + 672z^{7} − 1 792z^{6} + 2 304z^{5} − 1 024z^{4} + 512z^{3}.

Now, by Winker, each root of the first system is also a root of the latter. We can therefore go through all roots of the latter system and check if they satisfy the first.

But what are the roots of the latter system? First, we can factor r_{zy} by Maple and find

r_{zy}(x) = −8x^{2}(x^{5} − 8x^{3} − 4x^{4} + 7x − 2x^{2} − 2).

This has the roots x = 0 and x = α where α is an algebraic extension such that

ℚ(α) = ℚ[x]/⟨x^{5} − 8x^{3} − 4x^{4} + 7x − 2x^{2} − 2⟩.

Now, we can factor the second polynomial in ℚ(α). This yields

r_{zx}(y) = 4(y − 2)y^{2}(2y + (−2α^{4} + 7α^{3} + 20α^{2} + 13α − 10))u_{1}(y)

where u_{1} ∈ ℚ(α)[y] is an ugly irreducible factor. Hence, r_{zx} has the roots y = 0, y = 2,

y = α^{4} − \frac{7}{2}α^{3} − 10α^{2} − \frac{13}{2}α + 5,

and y = β, where β is a new algebraic extension of ℚ(α) such that

ℚ(α, β) = ℚ(α)[y]/⟨u_{1}(y)⟩.

Finally, for the factorization of r_{yx} over ℚ(α, β) brings

r_{yx}(z) = \frac{1}{8}z^{3} · (2z + α^{4} − 4α^{3} − 8α^{2} − 4α + 3) · u_{2}(z)

where u_{2}(z) ∈ ℚ(α, β) is again an irreducible factor. Let γ be an algebraic number which vanishes on u_{2}(y), i.e. let γ be such that

ℚ(α, β, γ) = ℚ(α, β)[z]/⟨u_{2}(z)⟩.

By some intuition (called Maple), we know that the solutions of the system can be expressed in ℚ(α), and we allow ourselves to ignore root candidates that involve β or γ.

The set of solution candidates hence amounts to

\{0, α\} × \{0, 2, α^{4} − \frac{7}{2}α^{3} − 10α^{2} − \frac{13}{2}α + 5\} × \{0, −\frac{1}{2}α^{4} + 2α^{3} + 4α^{2} + 2α − \frac{3}{2}\}.

We have to check all of them now.

First, if x = 0, then

f_{1}(0, y, z) = −yz
f_{2}(0, y, z) = yz − 1
f_{3}(0, y, z) = yz.

The third equation requires yz = 0 in contradiction to the second equation which requires yz = 1. Hence, x ≠ 0 and it only remains x = α.

For y = 0, we get

f_{1}(α, 0, z) = 2z
f_{2}(α, 0, z) = α^{2} − 1
f_{3}(α, 0, z) = αz − 2α.

The first equation requires z = 0, and with this the third equation would imply α = 0 which is impossible. Hence, y ≠ 0. For y = 2, we get

f_{1}(α, 2, z) = 4α
f_{2}(α, 2, z) = α^{2} + 2z − 1
f_{3}(α, 2, z) = αz + 2z − 2α.

This time, the first equation would imply α = 0 which still cannot be. It remains the possibility

y = y_{0} := α^{4} − \frac{7}{2}α^{3} − 10α^{2} − \frac{13}{2}α + 5.

We now turn to z. First, for z = 0, we receive

f_{1}(α, y_{0}, z) = 2αy_{0}
f_{2}(α, y_{0}, z) = α^{2} − 1
f_{3}(α, y_{0}, z) = −2α

The first and the last equation lead to contradicitions. It only remains the possibility

z = z_{0} := −\frac{1}{2}α^{4} + 2α^{3} + 4α^{2} + 2α − \frac{3}{2}.

Finally, we get

f_{1}(x_{0}, y_{0}, z_{0}) = 2x_{0}y_{0} − y_{0}z_{0} + 2z_{0}

= \frac{1}{8}α^{8} − \frac{15}{4}α^{7} − 2α^{6} + \frac{123}{4}α^{5} + 56α^{4} + \frac{59}{4}α^{3} − 27α^{2} − \frac{23}{4} + \frac{9}{2} = 0,

f_{2}(x_{0}, y_{0}, z_{0}) = x_{0}^{2} + y_{0}z_{0} − 1

= − \frac{1}{2}α^{8} + \frac{15}{4}α^{7} + 2α^{6} − \frac{115}{4}α^{5} − 64α^{4} − \frac{123}{4}α^{3} + 23α^{2} + \frac{79}{4}α − \frac{17}{2} = 0,

f_{3}(x_{0}, y_{0}, z_{0}) = x_{0}z_{0} + y_{0}z_{0} − 2x_{0}

= − \frac{1}{2}α^{8} + \frac{15}{4}α^{7} + 2α^{6} − \frac{117}{4}α^{5} − 62α^{4} − \frac{107}{4}α^{3} + 24α^{2} + \frac{65}{4}α − \frac{15}{2} = 0,

which proves that (x_{0}, y_{0}, z_{0}) actually describes the solution set of the system under consideration.

By Maple, we can verify that there are no other solutions of the system, and using numerics it can be found that α actually corresponds to five complex values, i.e. the the system has five solutions.

Ex. (33) We consider the system given by the polynomials

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.

Any value of z which is part of a solution of the system, must be a root of both

r_{xy}(z) = ( − \frac{5}{64}z^{5} − \frac{1}{8}z^{4} − \frac{3}{64}z^{3} + \frac{13}{32}z^{2} + \frac{51}{32}z − \frac{15}{16})^{4}

and

r_{yx}(z) = ( − 10z^{11} − \frac{89}{4}z^{10} − \frac{163}{8}z^{9} + \frac{385}{16}z^{8} + \frac{9679}{32}z^{7} + \frac{1201}{4}z^{6} +
\frac{11641}{32}z^{5} − \frac{1005}{8}z^{4} − \frac{45195}{16}z^{3} − \frac{5715}{4}z^{2} + \frac{6075}{4}z)^{2}

and hence of its greatest common divisor

gcd(r_{xy}, r_{yx}) = \frac{1}{25}(−5z^{5} − 8z^{4} − 3z^{3} + 26z^{2} + 102z − 60)^{2};

This representation is already a factorisation, so let α be an algebraic number such that

ℚ(α) = ℚ[z]/⟨−5z^{5} − 8z^{4} − 3z^{3} + 26z^{2} + 102z − 60⟩.

We know that any solution (x, y, z) to the system will have z = α.

Now consider the variable x. The resultant hacking leads to

r_{zy}(x) = ( − \frac{5}{16}x^{3} − 2x^{4} + \frac{21}{8}x^{5} − 4x^{6} + \frac{27}{2}x^{7} − 2x^{8})^{4}
r_{yz}(x) = \frac{1}{4096}x^{4}(−864x^{5} + 128x^{6} − 168x^{3} + 256x^{4} + 20x + 128x^{2})^{2}
gcd(r_{zy}, r_{yz}) = u_{1}(x) · (x − \frac{8323}{1388} − \frac{457}{347}α + \frac{1219}{2776}α^{2} + \frac{769}{1388}α^{3} + \frac{705}{2776}α^{4})^{2}x^{6}

where u_{1}(x) ∈ ℚ(α)[x] is an ugly irreducible polynomial of degree 4. We denote by β an algebraic number which is root of this polynomial, i.e.

ℚ(α, β) = ℚ(α)[x]/⟨u_{1}(x)⟩.

As possible values for x, we now have the candidates x = 0, x = β, and

x = \frac{8323}{1388} + \frac{457}{347}α − \frac{1219}{2776}α^{2} − \frac{769}{1388}α^{3} − \frac{705}{2776}α^{4}.

Finally, consider the candidates for the coordinate y. We have

r_{xz}(y) = \frac{1}{4}y^{2}(2y^{12} + 54y^{10} + \frac{335}{4}y^{8} + \frac{169}{4}y^{7} + \frac{109}{16}y^{4} − \frac{5}{4}y^{2})
r_{zx}(y) = −432y^{22} − 11680y^{20} − 18516y^{18} − \frac{19317}{2}y^{16} − \frac{4431}{2}y^{14}
− \frac{9119}{16}y^{12} − \frac{10757}{32}y^{10} − \frac{2515}{64}y^{8} + \frac{1109}{128}y^{6} − \frac{97}{16}y^{4} + \frac{5}{8}y^{2}
gcd(r_{xz}, r_{zx}) = y^{2}(y^{2} + \frac{16567}{694} + \frac{6295}{1388}α − \frac{2405}{1388}α^{2} − \frac{3017}{1388}α^{3} − \frac{1445}{1388}α^{4})u_{2}(y)

where u_{2}(y) is again an ugly irreducible factor which we don’t want to get to close to. For the candidates of y, we get y = 0, y = γ_{1} and y = γ_{2} where γ_{1}, γ_{2} are new algebraic numbers defined by

ℚ(α, β, γ_{1}) = ℚ(α, β)[y]/⟨y^{2} + \frac{16567}{694} + \frac{6295}{1388}α − \frac{2405}{1388}α^{2} − \frac{3017}{1388}α^{3} − \frac{1445}{1388}α^{4}⟩
ℚ(α, β, γ_{1}, γ_{2}) = ℚ(α, β, γ_{1})[y]/⟨u_{2}(y)⟩.

Again, by some strange intuition, we know that β and γ_{2} don’t appear in the final solution of the original system, so the candidate set is

\{0, \frac{8323}{1388} + \frac{457}{347}α − \frac{1219}{2776}α^{2} − \frac{769}{1388}α^{3} − \frac{705}{2776}α^{4}\} × \{0, γ_{1}\} × \{α\}.

Plugging x = 0 into the system, we get

f_{1}(0, y, z) = −\frac{1}{4}
f_{2}(0, y, z) = y^{2}z + \frac{1}{2}
f_{3}(0, y, z) = y^{2},

i.e. the first equation cannot be satisfied. It only remains the possibility

x = x_{0} := \frac{8323}{1388} + \frac{457}{347}α − \frac{1219}{2776}α^{2} − \frac{769}{1388}α^{3} − \frac{705}{2776}α^{4}.

Plugging y = 0 into the system leads to

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

The constraint f_{2} would require x = −\frac{1}{4} which is inconsistent with what we know so far about x. It only remains y = γ_{1}.

Finally, plugging (x, y, z) = (x_{0}, γ_{1}, α) into the system leads to

f_{1}(x_{0}, γ_{1}, α) = x_{0}α − αγ_{1}^{2} − 4x_{0}^{2} − \frac{1}{4} = 0
f_{2}(x_{0}, γ_{1}, α) = γ_{1}^{2}α + 2x_{0} + \frac{1}{2} = 0
f_{3}(x_{0}, γ_{1}, α) = x_{0}^{2}α + γ_{1}^{2} + \frac{1}{2}x_{0} = 0,

i.e. this is really a solution.

Ex. (34) [taken from Winkler, page 242f]

By t denote the degree of a, and write a = a_{t} + ⋯ + a_{0} where a_{i} is a homogenous polynomial of degree i. Choose elements c_{1}, …, c_{r} ∈ K with the property that c_{r} ≠ 0 and a_{t}(c_{1}, …, c_{r}) ≠ 0. Such c_{i} exist if K is sufficiently large. Let

â(x_{1}, …, x_{r}) = a(x_{1} + x_{1}c_{r}, …, x_{r−1} + c_{r−1}x_{r}, c_{r}x_{r})
b̂(x_{1}, …, x_{r}) = b(x_{1} + x_{1}c_{r}, …, x_{r−1} + c_{r−1}x_{r}, c_{r}x_{r}).

We claim that (α_{1}, …, α_{r}) ∈ K^{r} is a common root of â and b̂ if and only if (α_{1} + c_{1}α_{r}, …, α_{r−1} + c_{r−1}α_{r}, c_{r}α_{r}) is a common root of a and b.

For the direction from the left to the right, assume that (α_{1}, …, α_{r}) is a common root of â and b̂. We have to show that (α_{1} + c_{1}α_{r}, …, α_{r−1} + c_{r−1}α_{r}, c_{r}α_{r}) is a root of both a and b. This is immediate by the construction of â and b̂:

0 = â(α_{1}, α_{2}, …, α_{r})
= a(α_{1} + α_{1}c_{r}, …, α_{r−1} + c_{r−1}α_{r}, c_{r}α_{r}),
0 = b̂(α_{1}, α_{2}, …, α_{r})
= b(α_{1} + α_{1}c_{r}, …, α_{r−1} + c_{r−1}α_{r}, c_{r}α_{r})

Ex. (35) [taken from Bosch, Corollary 9 on page 173] First, it is immediate from the form of the Sylvester matrix that

Res(αf, βg) = α^{deg g}β^{deg f} Res(f, g)

by usual determinant manipulation rules. Using this, we can assume without loss of generality that f and g be monic.

Now, assume that f(x) = x − α and g(x) = g_{m}x^{m} + ⋯ + g_{0}. Then

Res(f, g) = det (\begin{matrix}1 & 0 & … & 0 & g_{m} \\ −α & 1 & ... & ⋮ & g_{m−1} \\ 0 & ... & ... & 0 & ⋮ \\ ⋮ & ... & ... & 1 & ⋮ \\ 0 & … & 0 & −α & g_{0} \end{matrix}) = g(α).

As for the general case, we conclude from the determinant multiplicity that

Res(ab, c) = Res(a, c) · Res(b, c).

Hence, a successive decomposition of f leads to

Res(f, g) = ∏_{i=1}^{n} g(α_{i}).

Expanding the definition of g, we get the desired form

Res(f, g) = ∏_{i=1}^{n} ∏_{j=1}^{m}(α_{i} − β_{j}).