In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients that is equal to zero if and only if the polynomials have a common root (possibly in a field extension), or, equivalently, a common factor (possibly in a field extension as well). In some older texts, the resultant is also called the eliminant. The resultant is widely used in number theory, either directly or through the discriminant, which is essentially the resultant of a polynomial and its derivative. The resultant of two polynomials with rational or polynomial coefficients may be computed efficiently on a computer. It is a basic tool of computer algebra, and is a built-in function of most computer algebra systems. It is used, among others, for cylindrical algebraic decomposition, integration of rational functions and drawing of curves defined by a bivariate polynomial equation. The resultant of n homogeneous polynomials in n variables (also called multivariate resultant, or Macaulay's resultant for distinguishing it from the usual resultant) is a generalization, introduced by Macaulay, of the usual resultant. It is, with Gröbner bases, one of the main tools of elimination theory.
Notation The resultant of two univariate polynomials A and B is commonly denoted res ( A , B ) {\displaystyle \operatorname {res} (A,B)} or Res ( A , B ) . {\displaystyle \operatorname {Res} (A,B).}
In many applications of the resultant, the polynomials depend on several indeterminates and may be considered as univariate polynomials in one of their indeterminates, with polynomials in the other indeterminates as coefficients. In this case, the indeterminate that is selected for defining and computing the resultant is indicated as a subscript: res x ( A , B ) {\displaystyle \operatorname {res} _{x}(A,B)} or Res x ( A , B ) . {\displaystyle \operatorname {Res} _{x}(A,B).}
The degrees of the polynomials are used in the definition of the resultant. However, a polynomial of degree d may also be considered as a polynomial of higher degree where the leading coefficients are zero. If such a higher degree is used for the resultant, it is usually indicated as a subscript or a superscript, such as res d , e ( A , B ) {\displaystyle \operatorname {res} _{d,e}(A,B)} or res x d , e ( A , B ) . {\displaystyle \operatorname {res} _{x}^{d,e}(A,B).}
Definition The resultant of two univariate polynomials over a field or over a commutative ring is commonly defined as the determinant of their Sylvester matrix. More precisely, let
A = a 0 x d + a 1 x d − 1 + ⋯ + a d {\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}
and
B = b 0 x e + b 1 x e − 1 + ⋯ + b e {\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}
be nonzero polynomials of degrees d and e respectively. Let us denote by P i {\displaystyle {\mathcal {P}}_{i}} the vector space (or free module if the coefficients belong to a commutative ring) of dimension i whose elements are the polynomials of degree strictly less than i. The map
φ : P e × P d → P d + e {\displaystyle \varphi :{\mathcal {P}}_{e}\times {\mathcal {P}}_{d}\rightarrow {\mathcal {P}}_{d+e}} such that
φ ( P , Q ) = A P + B Q {\displaystyle \varphi (P,Q)=AP+BQ}
is a linear map between two spaces of the same dimension. The matrix of this map is
( a 0 0 ⋯ 0 b 0 0 ⋯ 0 a 1 a 0 ⋯ 0 b 1 b 0 ⋯ 0 a 2 a 1 ⋱ 0 b 2 b 1 ⋱ 0 ⋮ ⋮ ⋱ a 0 ⋮ ⋮ ⋱ b 0 a d a d − 1 ⋯ ⋮ b e b e − 1 ⋯ ⋮ 0 a d ⋱ ⋮ 0 b e ⋱ ⋮ ⋮ ⋮ ⋱ a d − 1 ⋮ ⋮ ⋱ b e − 1 0 0 ⋯ a d 0 0 ⋯ b e ) {\displaystyle {\begin{pmatrix}a_{0}&0&\cdots &0&b_{0}&0&\cdots &0\\a_{1}&a_{0}&\cdots &0&b_{1}&b_{0}&\cdots &0\\a_{2}&a_{1}&\ddots &0&b_{2}&b_{1}&\ddots &0\\\vdots &\vdots &\ddots &a_{0}&\vdots &\vdots &\ddots &b_{0}\\a_{d}&a_{d-1}&\cdots &\vdots &b_{e}&b_{e-1}&\cdots &\vdots \\0&a_{d}&\ddots &\vdots &0&b_{e}&\ddots &\vdots \\\vdots &\vdots &\ddots &a_{d-1}&\vdots &\vdots &\ddots &b_{e-1}\\0&0&\cdots &a_{d}&0&0&\cdots &b_{e}\end{pmatrix}}} on the descending monomial bases { ( x e − 1 , 0 ) , ( x e − 2 , 0 ) , … , ( 1 , 0 ) , ( 0 , x d − 1 ) , ( 0 , x d − 2 ) , … , ( 0 , 1 ) } ⊂ P e × P d {\displaystyle \{(x^{e-1},0),(x^{e-2},0),\ldots ,(1,0),(0,x^{d-1}),(0,x^{d-2}),\ldots ,(0,1)\}\subset {\mathcal {P}}_{e}\times {\mathcal {P}}_{d}} and
{ x d + e − 1 , x d + e − 2 , … , 1 } ⊂ P d + e . {\displaystyle \{x^{d+e-1},x^{d+e-2},\ldots ,1\}\subset {\mathcal {P}}_{d+e}.}
This matrix is often called the Sylvester matrix of φ {\displaystyle \varphi } and the resultant of A {\displaystyle A} and B {\displaystyle B} . The matrix has e columns of ai and d columns of bj. For instance, taking d = 3 and e = 2 gives:
| a 0 0 b 0 0 0 a 1 a 0 b 1 b 0 0 a 2 a 1 b 2 b 1 b 0 a 3 a 2 0 b 2 b 1 0 a 3 0 0 b 2 | {\displaystyle {\begin{vmatrix}a_{0}&0&b_{0}&0&0\\a_{1}&a_{0}&b_{1}&b_{0}&0\\a_{2}&a_{1}&b_{2}&b_{1}&b_{0}\\a_{3}&a_{2}&0&b_{2}&b_{1}\\0&a_{3}&0&0&b_{2}\end{vmatrix}}} If the coefficients of the polynomials belong to an integral domain, then
res ( A , B ) = a 0 e b 0 d ∏ 1 ≤ i ≤ d 1 ≤ j ≤ e ( λ i − μ j ) = a 0 e ∏ i = 1 d B ( λ i ) = ( − 1 ) d e b 0 d ∏ j = 1 e A ( μ j ) , {\displaystyle \operatorname {res} (A,B)=a_{0}^{e}b_{0}^{d}\prod _{\begin{array}{c}1\leq i\leq d\\1\leq j\leq e\end{array}}(\lambda _{i}-\mu _{j})=a_{0}^{e}\prod _{i=1}^{d}B(\lambda _{i})=(-1)^{de}b_{0}^{d}\prod _{j=1}^{e}A(\mu _{j}),}
where λ 1 , … , λ d {\displaystyle \lambda _{1},\dots ,\lambda _{d}} and μ 1 , … , μ e {\displaystyle \mu _{1},\dots ,\mu _{e}} are respectively the roots, listed with multiplicities, of A and B in any algebraically closed field containing the integral domain. This is a straightforward consequence of the characterizing properties of the resultant that appear below. In the common case of integer coefficients, the algebraically closed field is generally chosen as the field of complex numbers.
Properties In this section and its subsections, A and B are two polynomials in x of respective degrees d and e, and their resultant is denoted
res ( A , B ) . {\displaystyle \operatorname {res} (A,B).}
Characterizing properties The following properties hold for the resultant of two polynomials with coefficients in a commutative ring R. If R is a field or more generally an integral domain, the resultant is the unique function of the coefficients of two polynomials that satisfies these properties.
If R is a subring of another ring S, then res R ( A , B ) = res S ( A , B ) . {\displaystyle \operatorname {res} _{R}(A,B)=\operatorname {res} _{S}(A,B).} That is A and B have the same resultant when considered as polynomials over R or S. If d = 0 (that is if A = a 0 {\displaystyle A=a_{0}} is a nonzero constant) then res ( A , B ) = a 0 e . {\displaystyle \operatorname {res} (A,B)=a_{0}^{e}.} Similarly, if e = 0, then res ( A , B ) = b 0 d . {\displaystyle \operatorname {res} (A,B)=b_{0}^{d}.}
res ( x + a 1 , x + b 1 ) = b 1 − a 1 {\displaystyle \operatorname {res} (x+a_{1},x+b_{1})=b_{1}-a_{1}}
res ( B , A ) = ( − 1 ) d e res ( A , B ) {\displaystyle \operatorname {res} (B,A)=(-1)^{de}\operatorname {res} (A,B)}
res ( A B , C ) = res ( A , C ) res ( B , C ) {\displaystyle \operatorname {res} (AB,C)=\operatorname {res} (A,C)\operatorname {res} (B,C)}
Zeros The resultant of two polynomials with coefficients in an integral domain D is zero if and only if they have a common divisor of positive degree over the field of fractions of D. The resultant of two polynomials with coefficients in an integral domain is zero if and only if they have a common root in an algebraically closed field containing the coefficients. There exists a polynomial P of degree less than e and a polynomial Q of degree less than d such that res ( A , B ) = A P + B Q . {\displaystyle \operatorname {res} (A,B)=AP+BQ.} This is a generalization of Bézout's identity to polynomials over an arbitrary commutative ring. In other words, the resultant of two polynomials belongs to the ideal generated by these polynomials.
Invariance by ring homomorphisms Let A and B be two polynomials of respective degrees d and e with coefficients in a commutative ring R, and φ : R → S {\displaystyle \varphi \colon R\to S} a ring homomorphism of R into another commutative ring S. Applying φ {\displaystyle \varphi } to the coefficients of a polynomial extends φ {\displaystyle \varphi } to a homomorphism of polynomial rings R [ x ] → S [ x ] {\displaystyle R[x]\to S[x]} , which is also denoted φ . {\displaystyle \varphi .} With this notation, we have:
If φ {\displaystyle \varphi } preserves the degrees of A and B (that is if deg ( φ ( A ) ) = d {\displaystyle \deg(\varphi (A))=d} and deg ( φ ( B ) ) = e {\displaystyle \deg(\varphi (B))=e} ), then φ ( res ( A , B ) ) = res ( φ ( A ) , φ ( B ) ) . {\displaystyle \varphi (\operatorname {res} (A,B))=\operatorname {res} (\varphi (A),\varphi (B)).}
If deg ( φ ( A ) ) < d {\displaystyle \deg(\varphi (A))<d} and deg ( φ ( B ) ) < e , {\displaystyle \deg(\varphi (B))<e,} then φ ( res ( A , B ) ) = 0. {\displaystyle \varphi (\operatorname {res} (A,B))=0.}
If deg ( φ ( A ) ) = d {\displaystyle \deg(\varphi (A))=d} and deg ( φ ( B ) ) = f < e , {\displaystyle \deg(\varphi (B))=f<e,} and the leading coefficient of A is a 0 {\displaystyle a_{0}} then φ ( res ( A , B ) ) = φ ( a 0 ) e − f res ( φ ( A ) , φ ( B ) ) . {\displaystyle \varphi (\operatorname {res} (A,B))=\varphi (a_{0})^{e-f}\operatorname {res} (\varphi (A),\varphi (B)).}
If deg ( φ ( A ) ) = f < d {\displaystyle \deg(\varphi (A))=f<d} and deg ( φ ( B ) ) = e , {\displaystyle \deg(\varphi (B))=e,} and the leading coefficient of B is b 0 {\displaystyle b_{0}} then φ ( res ( A , B ) ) = ( − 1 ) e ( d − f ) φ ( b 0 ) d − f res ( φ ( A ) , φ ( B ) ) . {\displaystyle \varphi (\operatorname {res} (A,B))=(-1)^{e(d-f)}\varphi (b_{0})^{d-f}\operatorname {res} (\varphi (A),\varphi (B)).}
These properties are easily deduced from the definition of the resultant as a determinant. They are mainly used in two situations. For computing a resultant of polynomials with integer coefficients, it is generally faster to compute it modulo several primes and to retrieve the desired resultant with Chinese remainder theorem. When R is a polynomial ring in other indeterminates, and S is the ring obtained by specializing to numerical values some or all indeterminates of R, these properties may be restated as if the degrees are preserved by the specialization, the resultant of the specialization of two polynomials is the specialization of the resultant. This property is fundamental, for example, for cylindrical algebraic decomposition.
Invariance under change of variable
res ( A ( x + a ) , B ( x + a ) ) = res ( A ( x ) , B ( x ) ) {\displaystyle \operatorname {res} (A(x+a),B(x+a))=\operatorname {res} (A(x),B(x))}
res ( A ( a x ) , B ( a x ) ) = a d e res ( A ( x ) , B ( x ) ) {\displaystyle \operatorname {res} (A(ax),B(ax))=a^{de}\operatorname {res} (A(x),B(x))}
If A r ( x ) = x d A ( 1 / x ) {\displaystyle A_{r}(x)=x^{d}A(1/x)} and B r ( x ) = x e B ( 1 / x ) {\displaystyle B_{r}(x)=x^{e}B(1/x)} are the reciprocal polynomials of A and B, respectively, then res ( A r , B r ) = ( − 1 ) d e res ( A , B ) {\displaystyle \operatorname {res} (A_{r},B_{r})=(-1)^{de}\operatorname {res} (A,B)}
This means that the property of the resultant being zero is invariant under linear and projective changes of the variable.
Invariance under change of polynomials If a and b are nonzero constants (that is they are independent of the indeterminate x), and A and B are as above, then res ( a A , b B ) = a e b d res ( A , B ) . {\displaystyle \operatorname {res} (aA,bB)=a^{e}b^{d}\operatorname {res} (A,B).}
If A and B are as above, and C is another polynomial such that the degree of A – CB is δ, then res ( B , A − C B ) = b 0 δ − d res ( B , A ) . {\displaystyle \operatorname {res} (B,A-CB)=b_{0}^{\delta -d}\operatorname {res} (B,A).}
It is only when B C {\displaystyle BC} and A {\displaystyle A} have the same degree that δ {\displaystyle \delta } cannot be deduced from the degrees of the given polynomials. If either B is monic, or deg C < deg A – deg B, then res ( B , A − C B ) = res ( B , A ) , {\displaystyle \operatorname {res} (B,A-CB)=\operatorname {res} (B,A),} If f = deg C > deg A – deg B = d – e, then res ( B , A − C B ) = b 0 e + f − d res ( B , A ) . {\displaystyle \operatorname {res} (B,A-CB)=b_{0}^{e+f-d}\operatorname {res} (B,A).}
These properties imply that in the Euclidean algorithm for polynomials, and all its variants (pseudo-remainder sequences), the resultant of two successive remainders (or pseudo-remainders) differs from the resultant of the initial polynomials by a factor which is easy to compute. Conversely, this allows one to deduce the resultant of the initial polynomials from the value of the last remainder or pseudo-remainder. This is the starting idea of the subresultant-pseudo-remainder-sequence algorithm, which uses the above formulae for getting subresultant polynomials as pseudo-remainders, and the resultant as the last nonzero pseudo-remainder (provided that the resultant is not zero). This algorithm works for polynomials over the integers or, more generally, over an integral domain, without any division other than exact divisions (that is, without involving fractions). It involves O ( d e ) {\displaystyle O(de)} arithmetic operations, while the computation of the determinant of the Sylvester matrix with standard algorithms requires O ( ( d + e ) 3 ) {\displaystyle O((d+e)^{3})} arithmetic operations.
Generic properties In this section, we consider two polynomials
A = a 0 x d + a 1 x d − 1 + ⋯ + a d {\displaystyle A=a_{0}x^{d}+a_{1}x^{d-1}+\cdots +a_{d}}
and
B = b 0 x e + b 1 x e − 1 + ⋯ + b e {\displaystyle B=b_{0}x^{e}+b_{1}x^{e-1}+\cdots +b_{e}}
whose d + e + 2 coefficients are distinct indeterminates. Let
R = Z [ a 0 , … , a d , b 0 , … , b e ] {\displaystyle R=\mathbb {Z} [a_{0},\ldots ,a_{d},b_{0},\ldots ,b_{e}]}
be the polynomial ring over the integers defined by these indeterminates. The resultant res ( A , B ) {\displaystyle \operatorname {res} (A,B)} is often called the generic resultant for the degrees d and e. It has the following properties.
res ( A , B ) {\displaystyle \operatorname {res} (A,B)} is an absolutely irreducible polynomial. If I {\displaystyle I} is the ideal of R [ x ] {\displaystyle R[x]} generated by A and B, then I ∩ R {\displaystyle I\cap R} is the principal ideal generated by res ( A , B ) {\displaystyle \operatorname {res} (A,B)} .
Homogeneity The generic resultant for the degrees d and e is homogeneous in various ways. More precisely:
It is homogeneous of degree e in a 0 , … , a d . {\displaystyle a_{0},\ldots ,a_{d}.}
It is homogeneous of degree d in b 0 , … , b e . {\displays