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) is a generalization of the usual n = 2 case, due to Macaulay. It is, along with Gröbner bases, one of the main tools of elimination theory.
Notation The resultant of two univariate polynomials and is commonly denoted or
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: or
The degrees of the polynomials are used in the definition of the resultant. However, a polynomial of degree 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 or
Definition
The resultant of two univariate polynomials with coefficients in a field (or a commutative ring) is the determinant of their Sylvester matrix. More precisely, let
and
be nonzero polynomials of degrees and respectively. Let denote the -dimensional vector space (or free module) of polynomials with degree at most . The map is a linear map between two spaces of dimension . With respect to the descending monomial bases and the matrix of is the Sylvester matrix: having columns of and columns of . Its determinant is the resultant .
For and , the resultant is:Assuming the coefficient ring is a field (or an integral domain, which can be extended to a field), let and be respectively the roots (listed with multiplicities) of and in an algebraically closed field extension of . (For integer coefficients, the roots may be considered as complex numbers.) Then the resultant can be written as: This is a straightforward consequence of the characterizing properties below.
Properties Again let and be polynomials in of respective degrees and with resultant
Characterizing properties The following properties hold for polynomials with coefficients in a commutative ring . If 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 is a subring of another ring , then That is and have the same resultant when considered as polynomials over or . If (that is if is a nonzero constant) then ; and if , then
Zeros The resultant of two polynomials with coefficients in an integral domain is zero if and only if they have a common divisor of positive degree over the field of fractions of . 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 of degree less than and a polynomial of degree less than such that 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 and be two polynomials of respective degrees and with coefficients in a commutative ring , and a ring homomorphism of into another commutative ring . Applying to the coefficients of a polynomial extends to a homomorphism of polynomial rings , which is also denoted With this notation, we have: If preserves the degrees of and (that is if and ), then If and then If and and the leading coefficient of is then If and and the leading coefficient of is then
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 is a polynomial ring in other indeterminates, and is the ring obtained by specializing to numerical values some or all indeterminates of , 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
If and are the reciprocal polynomials of and , respectively, then
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 and are nonzero constants (that is they are independent of the indeterminate ), and and are as above, then If and are as above, and is another polynomial such that the degree of is , then
It is only when and have the same degree that cannot be deduced from the degrees of the given polynomials. If either is monic, or , then If , then
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. Keeping track of successive factors allows one to compute 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 the resultant is non-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 requires only arithmetic operations, while the computation of the determinant of the Sylvester matrix with standard algorithms requires arithmetic operations.
Generic properties In this section, we consider two polynomials
and
whose coefficients are distinct indeterminates. Let
be the polynomial ring over the integers defined by these indeterminates. The resultant is the generic resultant for degrees and . It has the following properties.
is an absolutely irreducible polynomial. If is the ideal of generated by and , then is the principal ideal of generated by .
Homogeneity The generic resultant for the degrees and is homogeneous in various ways. More precisely: It is homogeneous of degree in It is homogeneous of degree in It is homogeneous of degree in all the variables and If and are given the weight (that is, the weight of each coefficient is its degree as elementary symmetric polynomial), then it is quasi-homogeneous of total weight . If and are homogeneous multivariate polynomials of respective degrees and , then their resultant in degrees and with respect to an indeterminate , denoted in , is homogeneous of degree in the other indeterminates.
Elimination property Let be the ideal generated by two polynomials and in a polynomial ring where is itself a polynomial ring over a field. If at least one of and is monic in , then:
The ideals and define the same algebraic set. That is, a tuple of elements of an algebraically closed field is a common zero of the elements of if and only it is a zero of The ideal has the same radical as the principal ideal That is, each element of has a power that is a multiple of All irreducible factors of divide every element of
The first assertion is a basic property of the resultant. The other assertions are immediate corollaries of the second one, which can be proved as follows.
As at least one of and is monic, a tuple is a zero of if and only if there exists such that is a common zero of and . Such a common zero is also a zero of all elements of Conversely, if is a common zero of the elements of it is a zero of the resultant, and there exists such that is a common zero of and . So and have exactly the same zeros.
Computation
Naively, the resultant could be computed by using the formula expressing it as a product of root differences (with roots computed via Newton's method), but such an algorithm would be inefficient and numerically unstable. As the resultant is a symmetric function of the roots of each polynomial, it could also be expressed in terms of the coefficients of by using the fundamental theorem of symmetric polynomials, but this would be highly inefficient. As the resultant is the determinant of the Sylvester matrix (and of the Bézout matrix), it may be computed using any algorithm for computing determinants. This needs arithmetic operations, where , but the more efficient methods below are preferred in practice.
Using the described above, the computation of a resultant can be done by a small augmentation of the Euclidean algorithm for polynomials, using only arithmetic operations in the field of coefficients. However, when the coefficients are integers, rational numbers or polynomials, these arithmetic operations imply a number of GCD computations of coefficients which make the algorithm inefficient. The subresultant pseudo-remainder sequences were introduced to solve this problem and avoid any fraction or GCD computations with coefficients.
A more efficient algorithm is obtained by using the good behavior of the resultant under a ring homomorphism on the coefficients: to compute a resultant of two polynomials with integer coefficients, one computes their resultants modulo sufficiently many prime numbers and then reconstructs the integer value with the Chinese remainder theorem.
The use of fast multiplication of integers and polynomials allows algorithms for resultants and greatest common divisors that have a better time complexity, which is of the order of the complexity of the multiplication, multiplied by the logarithm of the size of the input ( where is an upper bound of the number of digits of the input polynomials).
Application to polynomial systems
Resultants were introduced for solving systems of polynomial equations and provide the oldest proof that there exist algorithms for solving such systems. These are primarily intended for systems of two equations in two unknowns, but also allow solving general systems.
Case of two equations in two unknowns
Consider the system of two polynomial equations
where and are polynomials of respective total degrees and . Then is a polynomial in , which is generically of degree (by properties of ). A value of is a root of if and only if either:
have a common root at in an algebraically closed field containing the coefficients, meaning ; or have a common root at , meaning and .
Therefore, solutions to the system are obtained by computing the roots of , and for each root , computing the common roots of and .