How does one compute a resultant by using Euclidean algorithm?

Question

In an answer to the question Resultant of Two Univariate Polynomials, a PDF of course slides was linked which describes a modification of Euclid's algorithm for computing univariate polynomial resultants (reference: http://www.csd.uwo.ca/~eschost/publications/CS829-lecture3.pdf - slide 53).

The algorithm is as follows (with F, G the input polynomials, d_i the degree of F_i, and LC(p) the leading coefficient of p):

F_1 := F
F_2 := G
i := 2
R_1 := 1

while deg(F_i) > 0:
   F_{i+1} := F_{i-1} mod F_i
   R_i := (-1)^{d_i * d_{i-1}} * LC(F_i)^{d_{i-1} - d_i} * R_{i-1}
   i++

if F_i != 0 then return R_{i-1} * LC(F_i)^{d_{i-1}}
   else return 0

However, this algorithm is incorrect, though I am not sure `where' the bug is.

To see that it is incorrect, consider the following two polynomials in Q[x]:

f(x) = x^2 - 2x - 1,
g(x) = x^2 - 3.

Then, the algorithm given above computes that

Resultant(f,g) = 4

whereas the correct result is

Resultant(f,g) = -8.

This correct result is easily verified e.g. via Sage:

sage: x, = QQ['x'].gens()
sage: f = x^2 - 2*x - 1
sage: g = x^2 - 3
sage: f.resultant(g)
-8

Where is the bug in the resultant algorithm given in those slides? Or, alternatively, what is a correct modification of Euclid's algorithm sufficient for computing the resultant of two univariate polynomials in Q[x]? Please note that I am not looking for methods based on subresultant PRS's, but rather for a `simple' modification of Euclid's algorithm sufficient for computing the resultant of two univariate polynomials. (Of course, the resulting method will be far less efficient than subresultant-based methods. On the other hand, it should be much easier to understand, implement and teach.)

Thank you.

Answer 1

Slide 49 bottom has the basis of the algorithm

Corollary: For $F$, $G$ with coefficients in a field, $$\text{res}(F, G) = (−1)^{\deg(F ) \deg(G)}\text{ LeadCoeff}(G)^{\deg(F )−\deg(R)}\,\text{res}(G, R),$$ for $R$ such that $F = QG + R$.

---

Following that theorem and the algorithm, the example computes as \begin{align} \text{res}(x^2 - 2x - 1, x^2 - 3) &=(-1)^{2\cdot 2}\,1^{2-1}\,\text{res}(x^2 - 3, -2x+2)\\ &=(-1)^{2\cdot 1}\,(-2)^{2-0}\,\text{res}(-2x+2, -2)\\ &=4\cdot(-2)=-8 \end{align}

which you found as the correct result. So there is nothing wrong with the algorithm. The difference $\deg(F )−\deg(R)$ is not correctly translated into the terms of the algorithm, it should be $d_{i-1}-d_{i+1}$.

---

To get a feeling for the reduction formula, let's recompute it (under the simplifying assumption that $G$ has simple roots). \begin{align} \operatorname{Res}(F,G) &=(-1)^{\deg F⋅\deg G}⋅\operatorname{Res}(G,F)\\ &=(-1)^{\deg F⋅\deg G}⋅\operatorname{LC}(G)^{\deg F}⋅\prod_{z:G(z)=0}F(z)\\ &=(-1)^{\deg F⋅\deg G}⋅\operatorname{LC}(G)^{\deg F}⋅\prod_{z:G(z)=0}(Q(z)G(z)+R(z))\\ &=(-1)^{\deg F⋅\deg G}⋅\operatorname{LC}(G)^{\deg F-\deg R}⋅\operatorname{LC}(G)^{\deg R}⋅\prod_{z:G(z)=0}R(z)\\ &=(-1)^{\deg F⋅\deg G}⋅\operatorname{LC}(G)^{\deg F-\deg R}⋅\operatorname{Res}(G,R) \end{align}