Resultant


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, or, equivalently, a common factor. 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 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 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 over a field or over a commutative ring is commonly defined as the determinant of their Sylvester matrix. More precisely, let
and
be nonzero polynomials of degrees and respectively. Let us denote by the vector space of dimension whose elements are the polynomials of degree strictly less than. The map
such that
is a linear map between two spaces of the same dimension. Over the basis of the powers of , this map is represented by a square matrix of dimension, which is called the Sylvester matrix of and .
The resultant of and is thus the determinant
which has columns of and columns of .
For instance, taking and we get
If the coefficients of the polynomials belong to an integral domain, then
where and are respectively the roots, counted with their multiplicities, of and 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, and are two polynomials in of respective degrees and, and their resultant is denoted

Characterizing properties

The following properties hold for the resultant of two 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 then Similarly, 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 , 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, 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, the resultant of two successive 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. This algorithm works for polynomials over the integers or, more generally, over an integral domain, without any division other than exact divisions. It involves 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 often called the generic resultant for the degrees and. It has the following properties.
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 , 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

Theoretically, the resultant could be computed by using the formula expressing it as a product of roots differences. However, as the roots may generally not be computed exactly, 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 computed by using the fundamental theorem of symmetric polynomials, but this would be highly inefficient.
As the resultant is the determinant of the Sylvester matrix, it may be computed by using any algorithm for computing determinants. This needs arithmetic operations. As algorithms are known with a better complexity, this method is not used in practice.
It follows from that the computation of a resultant is strongly related to the Euclidean algorithm for polynomials. This shows that the computation of the resultant of two polynomials of degrees and may be done in 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 is of the same order and make the algorithm inefficient.
The subresultant pseudo-remainder sequences were introduced to solve this problem and avoid any fraction and any GCD computation of 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 result 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.