2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The usual name is "sub-resultant algorithm". Wikipedia has an extensive description. $\endgroup$ – Dr. Lutz Lehmann Mar 2 '14 at 17:42
  • $\begingroup$ Hi, Lutz - Thank you for your comment. However, the subresultant algorithm is far more complicated than what I'm looking for. I'm looking for a simple modification of Euclid's algorithm which correctly computes the resultant of two univariate polynomials. Of course, subresultant-based methods will be far more efficient than such a simple modification of Euclid's algorithm. But, efficiency is not my concern at the moment. $\endgroup$ – drawingpad Mar 2 '14 at 17:47
  • $\begingroup$ Yes, sorry, I saw too late that you stated that your computation is in $\Bbb Q[X]$. $\endgroup$ – Dr. Lutz Lehmann Mar 2 '14 at 17:56
  • $\begingroup$ Euclidean algorithm based computation of resultants is discussed in detail in Subresultants Revisited by Gathen and Lücking. They appear to be Schost's source (Schost is the author of the linked notes). It is a shame that most texts only discuss Sylvester's (occasionally also Bezout's) giant determinants for computing them. $\endgroup$ – Conifold Jan 6 '17 at 5:14
2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Hi, Lutz. Thank you for this helpful answer. Will you please explain how you get (-2)^{2-0} in the second line of the sequence of equations? Here, I compute (-2)^{2-1), as the algorithm calls for (-2)^(d_{i-1} - d_i}), which in this case (with i=3) we have F_2 = x^2 - 3 and F_3 = -2x + 2. Thank you for your help. $\endgroup$ – drawingpad Mar 2 '14 at 18:25
  • $\begingroup$ Yes, there seems to be a discrepancy between the corollary where $\deg F-\deg R$ would translate into $\deg F_{i-1}-\deg F_{i+1}=d_{i+1}-d_{i-1}$ and the algorithm. I'll withdraw the last sentence of the answer. $\endgroup$ – Dr. Lutz Lehmann Mar 2 '14 at 18:52
  • $\begingroup$ Excellent - Now I understand. Thank you very much! $\endgroup$ – drawingpad Mar 2 '14 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.