Resultant

Definition

The resultant ${\displaystyle \mathrm{r}\mathrm{e}\mathrm{s}(A,B)}$ of two univariate polynomials ${\displaystyle A,B}$ with coefficients in a field (or a commutative ring) is the determinant of their Sylvester matrix. More precisely, let $${\displaystyle A=a_0{x}^d+a_1{x}^{d-1}+\cdots +a_d}$$ and $${\displaystyle B=b_0{x}^e+b_1{x}^{e-1}+\cdots +b_e}$$ be nonzero polynomials of degrees ${\displaystyle d}$ and ${\displaystyle e}$ respectively. Let ${\displaystyle {\mathcal{P}}_n}$ denote the ${\displaystyle n}$-dimensional vector space (or free module) of polynomials with degree at most ${\displaystyle n-1}$. The map $${\displaystyle \phi :{\mathcal{P}}_e\times {\mathcal{P}}_d\to {\mathcal{P}}_{d+e},\phi (P,Q)=AP+BQ,}$$ is a linear map between two spaces of dimension ${\displaystyle d+e}$. With respect to the descending monomial bases $${\displaystyle \{(x^{e-1},0),(x^{e-2},0),\dots ,(1,0),(0,x^{d-1}),(0,x^{d-2}),\dots ,(0,1)\}\subset {\mathcal{P}}_e\times {\mathcal{P}}_d}$$ and $${\displaystyle \{x^{d+e-1},x^{d+e-2},\dots ,1\}\subset {\mathcal{P}}_{d+e},}$$the matrix of ${\displaystyle \phi }$ is the Sylvester matrix: $${\displaystyle \left(\begin{array}{cccccccc}{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\\ ⋮& ⋮& \ddots & a_0& ⋮& ⋮& \ddots & b_0\\ a_d& a_{d-1}& \cdots & ⋮& b_e& b_{e-1}& \cdots & ⋮\\ 0& a_d& \ddots & ⋮& 0& b_e& \ddots & ⋮\\ ⋮& ⋮& \ddots & a_{d-1}& ⋮& ⋮& \ddots & b_{e-1}\\ 0& 0& \cdots & a_d& 0& 0& \cdots & b_e\end{array}\right),}$$having ${\displaystyle e}$ columns of ${\displaystyle a_i}$ and ${\displaystyle d}$ columns of ${\displaystyle b_j}$. Its determinant is the resultant ${\displaystyle \mathrm{r}\mathrm{e}\mathrm{s}(A,B)}$.

For ${\displaystyle d=3}$ and ${\displaystyle e=2}$, the resultant is:$${\displaystyle \left|\begin{array}{ccccc}{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{array}\right|=\begin{array}{c}{a}_3^2{b}_0^3-a_2{a}_3{b}_1{b}_0^2+a_2^2{b}_2{b}_0^2-2a_1{a}_3{b}_2{b}_0^2\\ +a_1{a}_3{b}_1^2{b}_0+a_1^2{b}_2^2{b}_0-2a_0{a}_2{b}_2^2{b}_0-a_1{a}_2{b}_1{b}_2{b}_0\\ +3a_0{a}_3{b}_1{b}_2{b}_0-a_0{a}_3{b}_1^3+a_0^2{b}_2^3-a_0{a}_1{b}_1{b}_2^2+a_0{a}_2{b}_1^2{b}_2.\end{array}}$$Assuming the coefficient ring ${\displaystyle F}$ is a field (or an integral domain, which can be extended to a field), let ${\displaystyle {\lambda }_1,\dots ,{\lambda }_d}$ and ${\displaystyle {\mu }_1,\dots ,{\mu }_e}$ be respectively the roots (listed with multiplicities) of ${\displaystyle A}$ and ${\displaystyle B}$ in an algebraically closed field extension of ${\displaystyle F}$. (For integer coefficients, the roots may be considered as complex numbers.) Then the resultant can be written as: $${\displaystyle \mathrm{res}(A,B)=a_0^e{b}_0^d\prod _{\begin{array}{c}1\le i\le d\\ 1\le j\le 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).}$$ This is a straightforward consequence of the characterizing properties below.

Properties

Again let ${\displaystyle A}$ and ${\displaystyle B}$ be polynomials in ${\displaystyle x}$ of respective degrees ${\displaystyle d}$ and ${\displaystyle e}$ with resultant ${\displaystyle \mathrm{res}(A,B).}$

Characterizing properties

The following properties hold for polynomials with coefficients in a commutative ring ${\displaystyle R}$. If ${\displaystyle 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 ${\displaystyle {\mathrm{res}}_R(A,B)={\mathrm{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 ${\displaystyle A=a_0}$ is a nonzero constant) then ${\displaystyle \mathrm{res}(A,B)=a_0^e}$; and if e = 0, then ${\displaystyle \mathrm{res}(A,B)=b_0^d.}$
• ${\displaystyle \mathrm{res}(x+a_1,x+b_1)=b_1-a_1}$
• ${\displaystyle \mathrm{res}(B,A)=(-1{)}^{de}\mathrm{res}(A,B)}$
• ${\displaystyle \mathrm{res}(AB,C)=\mathrm{res}(A,C)\mathrm{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 ${\displaystyle \mathrm{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 ${\displaystyle \phi :R\to S}$ a ring homomorphism of R into another commutative ring S. Applying ${\displaystyle \phi }$ to the coefficients of a polynomial extends ${\displaystyle \phi }$ to a homomorphism of polynomial rings ${\displaystyle R[x]\to S[x]}$, which is also denoted ${\displaystyle \phi .}$ With this notation, we have:

• If ${\displaystyle \phi }$ preserves the degrees of A and B (that is if ${\displaystyle \mathrm{deg}(\phi (A))=d}$ and ${\displaystyle \mathrm{deg}(\phi (B))=e}$), then $${\displaystyle \phi (\mathrm{res}(A,B))=\mathrm{res}(\phi (A),\phi (B)).}$$
• If ${\displaystyle \mathrm{deg}(\phi (A))<d}$ and ${\displaystyle \mathrm{deg}(\phi (B))<e,}$ then $${\displaystyle \phi (\mathrm{res}(A,B))=0.}$$
• If ${\displaystyle \mathrm{deg}(\phi (A))=d}$ and ${\displaystyle \mathrm{deg}(\phi (B))=f<e,}$ and the leading coefficient of A is ${\displaystyle a_0}$ then $${\displaystyle \phi (\mathrm{res}(A,B))=\phi (a_0{)}^{e-f}\mathrm{res}(\phi (A),\phi (B)).}$$
• If ${\displaystyle \mathrm{deg}(\phi (A))=f<d}$ and ${\displaystyle \mathrm{deg}(\phi (B))=e,}$ and the leading coefficient of B is ${\displaystyle b_0}$ then $${\displaystyle \phi (\mathrm{res}(A,B))=(-1{)}^{e(d-f)}\phi (b_0{)}^{d-f}\mathrm{res}(\phi (A),\phi (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

• ${\displaystyle \mathrm{res}(A(x+a),B(x+a))=\mathrm{res}(A(x),B(x))}$
• ${\displaystyle \mathrm{res}(A(ax),B(ax))=a^{de}\mathrm{res}(A(x),B(x))}$
• If ${\displaystyle A_r(x)=x^{d}A(1/x)}$ and ${\displaystyle B_r(x)=x^{e}B(1/x)}$ are the reciprocal polynomials of A and B, respectively, then $${\displaystyle \mathrm{res}(A_r,B_r)=(-1{)}^{de}\mathrm{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 $${\displaystyle \mathrm{res}(aA,bB)=a^e{b}^d\mathrm{res}(A,B).}$$
• If A and B are as above, and C is another polynomial such that the degree of A – CB is δ, then $${\displaystyle \mathrm{res}(B,A-CB)=b_0^{\delta -d}\mathrm{res}(B,A).}$$

It is only when ⁠${\displaystyle CB}$⁠ and ⁠${\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 $${\displaystyle \mathrm{res}(B,A-CB)=\mathrm{res}(B,A),}$$ If f = deg C > deg A – deg B = d – e, then $${\displaystyle \mathrm{res}(B,A-CB)=b_0^{e+f-d}\mathrm{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. 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 ${\displaystyle O(de)}$ arithmetic operations, while the computation of the determinant of the Sylvester matrix with standard algorithms requires ${\displaystyle O((d+e{)}^3)}$ arithmetic operations.

Generic properties

In this section, we consider two polynomials $${\displaystyle A=a_0{x}^d+a_1{x}^{d-1}+\cdots +a_d}$$ and $${\displaystyle B=b_0{x}^e+b_1{x}^{e-1}+\cdots +b_e}$$ whose d + e + 2 coefficients are distinct indeterminates. Let $${\displaystyle R=\mathbb{Z}[a_0,\dots ,a_d,b_0,\dots ,b_e]}$$ be the polynomial ring over the integers defined by these indeterminates. The resultant ${\displaystyle \mathrm{res}(A,B)}$ is the generic resultant for degrees d and e. It has the following properties.

• ${\displaystyle \mathrm{res}(A,B)}$ is an absolutely irreducible polynomial.
• If ${\displaystyle I}$ is the ideal of ${\displaystyle R[x]}$ generated by A and B, then ${\displaystyle I\cap R}$ is the principal ideal of ${\displaystyle R}$ generated by ${\displaystyle \mathrm{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 ${\displaystyle a_0,\dots ,a_d.}$
• It is homogeneous of degree d in ${\displaystyle b_0,\dots ,b_e.}$
• It is homogeneous of degree d + e in all the variables ${\displaystyle a_i}$ and ${\displaystyle b_j.}$
• If ${\displaystyle a_i}$ and ${\displaystyle b_i}$ are given the weight i (that is, the weight of each coefficient is its degree as elementary symmetric polynomial), then it is quasi-homogeneous of total weight de.
• If P and Q are homogeneous multivariate polynomials of respective degrees d and e, then their resultant in degrees d and e with respect to an indeterminate x, denoted ${\displaystyle {\mathrm{res}}_x^{d,e}(P,Q)}$ in § Notation, is homogeneous of degree de in the other indeterminates.

Elimination property

Let ${\displaystyle I=⟨A,B⟩}$ be the ideal generated by two polynomials A and B in a polynomial ring ${\displaystyle R[x],}$ where ${\displaystyle R=k[y_1,\dots ,y_n]}$ is itself a polynomial ring over a field. If at least one of A and B is monic in x, then:

• ${\displaystyle {\mathrm{res}}_x(A,B)\in I\cap R}$
• The ideals ${\displaystyle I\cap R}$ and ${\displaystyle R{\mathrm{res}}_x(A,B)}$ define the same algebraic set. That is, a tuple of n elements of an algebraically closed field is a common zero of the elements of ${\displaystyle I\cap R}$ if and only it is a zero of ${\displaystyle {\mathrm{res}}_x(A,B).}$
• The ideal ${\displaystyle I\cap R}$ has the same radical as the principal ideal ${\displaystyle R{\mathrm{res}}_x(A,B).}$ That is, each element of ${\displaystyle I\cap R}$ has a power that is a multiple of ${\displaystyle {\mathrm{res}}_x(A,B).}$
• All irreducible factors of ${\displaystyle {\mathrm{res}}_x(A,B)}$ divide every element of ${\displaystyle I\cap R.}$

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 A and B is monic, a tuple ${\displaystyle ({\beta }_1,\dots ,{\beta }_n)}$ is a zero of ${\displaystyle {\mathrm{res}}_x(A,B)}$ if and only if there exists ${\displaystyle \alpha }$ such that ${\displaystyle ({\beta }_1,\dots ,{\beta }_n,\alpha )}$ is a common zero of A and B. Such a common zero is also a zero of all elements of ${\displaystyle I\cap R.}$ Conversely, if ${\displaystyle ({\beta }_1,\dots ,{\beta }_n)}$ is a common zero of the elements of ${\displaystyle I\cap R,}$ it is a zero of the resultant, and there exists ${\displaystyle \alpha }$ such that ${\displaystyle ({\beta }_1,\dots ,{\beta }_n,\alpha )}$ is a common zero of A and B. So ${\displaystyle I\cap R}$ and ${\displaystyle R{\mathrm{res}}_x(A,B)}$ 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 ${\displaystyle A(x),B(x)}$ 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 ${\displaystyle O(n^3)}$ arithmetic operations, where ${\displaystyle n=d+e}$, but the more efficient methods below are preferred in practice.

Using the § Invariance under change of polynomials described above, the computation of a resultant can be done by a small augmentation of the Euclidean algorithm for polynomials, using only ${\displaystyle O(de)}$ 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 (${\displaystyle \log (s(d+e)),}$ where s 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 $${\displaystyle \begin{array}{cc}P(x,y)& =0\\ Q(x,y)& =0,\end{array}}$$ where P and Q are polynomials of respective total degrees d and e. Then ${\displaystyle R={\mathrm{res}}_y^{d,e}(P,Q)}$ is a polynomial in x, which is generically of degree de (by properties of § Homogeneity). A value ${\displaystyle \alpha }$ of x is a root of R if and only if either:

• ${\displaystyle P(\alpha ,y),Q(\alpha ,y)}$ have a common root at ${\displaystyle y=\beta }$ in an algebraically closed field containing the coefficients, meaning ${\displaystyle P(\alpha ,\beta )=Q(\alpha ,\beta )=0}$; or
• ${\displaystyle P(\alpha ,y),Q(\alpha ,y)}$ have a common root at ${\displaystyle y=\mathrm{\infty }}$, meaning ${\displaystyle \mathrm{deg}P(\alpha ,y)<d}$ and ${\displaystyle \mathrm{deg}Q(\alpha ,y)<e}$.

Therefore, solutions to the system are obtained by computing the roots of ${\displaystyle R={\mathrm{res}}_y^{d,e}(P,Q)}$, and for each root ${\displaystyle x=\alpha }$, computing the common roots ${\displaystyle y=\beta }$ of ${\displaystyle P(\alpha ,y),}$ ${\displaystyle Q(\alpha ,y),}$ and ${\displaystyle {\mathrm{res}}_x(P,Q)}$.

Bézout's theorem results from the value of ${\displaystyle \mathrm{deg}\left({\mathrm{res}}_y(P,Q)\right)\le de}$, the product of the degrees of P and Q. In fact, after a linear change of variables, one may suppose that, for each root x of the resultant, there is exactly one value of y such that (x, y) is a common zero of P and Q. This shows that the number of common zeros is at most the degree of the resultant, i.e. at most the product of the degrees of P and Q. With some technicalities to count multiplicities and zeros at infinity, this shows that the number of common zeros is exactly the product of the degrees.

General case

At first glance, it seems that resultants may be applied to a general polynomial system of equations $${\displaystyle \begin{array}{cc}{P}_1(x_1,\dots ,x_n)& =0\\ & ⋮\\ P_k(x_1,\dots ,x_n)& =0\end{array}}$$ by computing the resultants of every pair ${\displaystyle (P_i,P_j)}$ with respect to ${\displaystyle x_n}$ for eliminating one unknown, and repeating the process until getting univariate polynomials. Unfortunately, this introduces many spurious solutions, which are difficult to remove.

A method, introduced at the end of the 19th century, works as follows: introduce k − 1 new indeterminates ${\displaystyle U_2,\dots ,U_k}$ and compute $${\displaystyle {\mathrm{res}}_{x_n}(P_1,U_2{P}_2+\cdots +U_k{P}_k).}$$ This is a polynomial in ${\displaystyle U_2,\dots ,U_k}$ whose coefficients are polynomials in ${\displaystyle x_1,\dots ,x_{n-1},}$ which have the property that ${\displaystyle {\alpha }_1,\dots ,{\alpha }_{n-1}}$ is a common zero of these polynomial coefficients, if and only if the univariate polynomials ${\displaystyle P_i({\alpha }_1,\dots ,{\alpha }_{n-1},x_n)}$ have a common zero, possibly at infinity. This process may be iterated until finding univariate polynomials.

To get a correct algorithm two complements have to be added to the method. Firstly, at each step, a linear change of variable may be needed in order that the degrees of the polynomials in the last variable are the same as their total degree. Secondly, if, at any step, the resultant is zero, this means that the polynomials have a common factor and that the solutions split in two components: one where the common factor is zero, and the other which is obtained by factoring out this common factor before continuing.

This algorithm is very complicated and has a huge time complexity. Therefore, its interest is mainly historical.

Other applications

Number theory

The discriminant of a polynomial, which is a fundamental tool in number theory, is ${\displaystyle a_0^{-1}(-1{)}^{n(n-1)/2}{\mathrm{res}}_x(f(x),f^{\prime }(x))}$, where ${\displaystyle a_0}$ is the leading coefficient of ${\displaystyle f(x)}$ and ${\displaystyle n}$ its degree.

If ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ are algebraic numbers such that ${\displaystyle P(\alpha )=Q(\beta )=0}$, then ${\displaystyle \gamma =\alpha +\beta }$ is a root of the resultant ${\displaystyle {\mathrm{res}}_x(P(x),Q(z-x)),}$ and ${\displaystyle \tau =\alpha \beta }$ is a root of ${\displaystyle {\mathrm{res}}_x(P(x),x^{n}Q(z/x))}$, where ${\displaystyle n}$ is the degree of ${\displaystyle Q(y)}$. Combined with the fact that ${\displaystyle 1/\beta }$ is a root of ${\displaystyle y^{n}Q(1/y)=0}$, this shows that the set of algebraic numbers is a field.

Let ${\displaystyle K(\alpha )}$ be an algebraic field extension generated by an element ${\displaystyle \alpha ,}$ which has ${\displaystyle P(x)}$ as minimal polynomial. Every element of ${\displaystyle \beta \in K(\alpha )}$ may be written as ${\displaystyle \beta =Q(\alpha ),}$ where ${\displaystyle Q}$ is a polynomial. Then ${\displaystyle \beta }$ is a root of ${\displaystyle {\mathrm{res}}_x(P(x),z-Q(x)),}$ and this resultant is a power of the minimal polynomial of ${\displaystyle \beta .}$

Algebraic geometry

Given two plane algebraic curves defined as the zeros of the polynomials P(x, y) and Q(x, y), the resultant allows the computation of their intersection. More precisely, the roots of ${\displaystyle {\mathrm{res}}_y(P,Q)}$ are the x-coordinates of the intersection points and of the common vertical asymptotes, and the roots of ${\displaystyle {\mathrm{res}}_x(P,Q)}$ are the y-coordinates of the intersection points and of the common horizontal asymptotes.

A rational plane curve may be defined by a parametric equation $${\displaystyle x=\frac{P(t)}{R(t)},y=\frac{Q(t)}{R(t)},}$$ where P, Q and R are polynomials. An implicit equation of the curve is given by $${\displaystyle {\mathrm{res}}_t(xR-P,yR-Q).}$$ The degree of this curve is the highest degree of P, Q and R, which is equal to the total degree of the resultant.

Symbolic integration

In symbolic integration, for computing the antiderivative of a rational fraction, one uses partial fraction decomposition for decomposing the integral into a "rational part", which is a sum of rational fractions whose antiprimitives are rational fractions, and a "logarithmic part" which is a sum of rational fractions of the form $${\displaystyle \frac{P(x)}{Q(x)},}$$ where Q is a square-free polynomial and P is a polynomial of lower degree than Q. The antiderivative of such a function involves necessarily logarithms, and generally algebraic numbers (the roots of Q). In fact, the antiderivative is $${\displaystyle \int \frac{P(x)}{Q(x)}dx=\sum _{Q(\alpha )=0}\frac{P(\alpha )}{Q^{\prime }(\alpha )}\log (x-\alpha ),}$$ where the sum runs over all complex roots of Q.

The number of algebraic numbers involved by this expression is generally equal to the degree of Q, but it occurs frequently that an expression with less algebraic numbers may be computed. The Lazard–Rioboo–Trager method produces an expression, where the number of algebraic numbers is minimal, without any computation with algebraic numbers.

Let $${\displaystyle S_1(r)S_2(r{)}^2\cdots S_k(r{)}^k={\mathrm{res}}_r(r{Q}^{\prime }(x)-P(x),Q(x))}$$ be the square-free factorization of the resultant which appears on the right. Trager proved that the antiderivative is $${\displaystyle \int \frac{P(x)}{Q(x)}dx=\sum _{i=1}^k\sum _{S_i(\alpha )=0}\alpha \log (T_i(\alpha ,x)),}$$ where the internal sums run over the roots of the ${\displaystyle S_i}$ (if ${\displaystyle S_i=1}$ the sum is zero, as being the empty sum), and ${\displaystyle T_i(r,x)}$ is a polynomial of degree i in x. The Lazard-Rioboo contribution is the proof that ${\displaystyle T_i(r,x)}$ is the subresultant of degree i of ${\displaystyle r{Q}^{\prime }(x)-P(x)}$ and ${\displaystyle Q(x).}$ It is thus obtained for free if the resultant is computed by the subresultant pseudo-remainder sequence.

Computer algebra

All preceding applications, and many others, show that the resultant is a fundamental tool in computer algebra. In fact most computer algebra systems include an efficient implementation of the computation of resultants.

Homogeneous resultant

The resultant is also defined for two homogeneous polynomial in two indeterminates. Given two homogeneous polynomials P(x, y) and Q(x, y) of respective total degrees p and q, their homogeneous resultant is the determinant of the matrix over the monomial basis of the linear map $${\displaystyle (A,B)\mapsto AP+BQ,}$$ where A runs over the bivariate homogeneous polynomials of degree q − 1, and B runs over the homogeneous polynomials of degree p − 1. In other words, the homogeneous resultant of P and Q is the resultant of P(x, 1) and Q(x, 1) when they are considered as polynomials of degree p and q (their degree in x may be lower than their total degree): $${\displaystyle \mathrm{Res}(P(x,y),Q(x,y))={\mathrm{res}}_{p,q}(P(x,1),Q(x,1)).}$$ (The capitalization of "Res" is used here for distinguishing the two resultants, although there is no standard rule for the capitalization of the abbreviation).

The homogeneous resultant has essentially the same properties as the usual resultant, with essentially two differences: instead of polynomial roots, one considers zeros in the projective line, and the degree of a polynomial may not change under a ring homomorphism. That is:

• The resultant of two homogeneous polynomials over an integral domain is zero if and only if they have a non-zero common zero over an algebraically closed field containing the coefficients.
• If P and Q are two bivariate homogeneous polynomials with coefficients in a commutative ring R, and ${\displaystyle \phi :R\to S}$ a ring homomorphism of R into another commutative ring S, then extending ${\displaystyle \phi }$ to polynomials over R, ones has $${\displaystyle \mathrm{Res}(\phi (P),\phi (Q))=\phi (\mathrm{Res}(P,Q)).}$$
• The property of an homogeneous resultant to be zero is invariant under any projective change of variables.

Any property of the usual resultant may similarly extended to the homogeneous resultant, and the resulting property is either very similar or simpler than the corresponding property of the usual resultant.

Macaulay's resultant

Macaulay's resultant, named after Francis Sowerby Macaulay, also called the multivariate resultant, or the multipolynomial resultant, is a generalization of the homogeneous resultant to n homogeneous polynomials in n indeterminates. Macaulay's resultant is a polynomial in the coefficients of these n homogeneous polynomials that vanishes if and only if the polynomials have a common non-zero solution in an algebraically closed field containing the coefficients, or, equivalently, if the n hyper surfaces defined by the polynomials have a common zero in the n –1 dimensional projective space. The multivariate resultant is, with Gröbner bases, one of the main tools of effective elimination theory (elimination theory on computers).

Like the homogeneous resultant, Macaulay's may be defined with determinants, and thus behaves well under ring homomorphisms. However, it cannot be defined by a single determinant. It follows that it is easier to define it first on generic polynomials.

Resultant of generic homogeneous polynomials

A homogeneous polynomial of degree d in n variables may have up to $${\displaystyle (\genfrac{}{}{0ex}{}{n+d-1}{n-1})=\frac{(n+d-1)!}{(n-1)!d!}}$$ coefficients; it is said to be generic, if these coefficients are distinct indeterminates.

Let ${\displaystyle P_1,\dots ,P_n}$ be n generic homogeneous polynomials in n indeterminates, of respective degrees ${\displaystyle d_1,\dots ,d_n.}$ Together, they involve $${\displaystyle \sum _{i=1}^n(\genfrac{}{}{0ex}{}{n+d_i-1}{n-1})}$$ indeterminate coefficients. Let C be the polynomial ring over the integers, in all these indeterminate coefficients. The polynomials ${\displaystyle P_1,\dots ,P_n}$ belong thus to ${\displaystyle C[x_1,\dots ,x_n],}$ and their resultant (still to be defined) belongs to C.

The Macaulay degree is the integer ${\displaystyle D=d_1+\cdots +d_n-n+1,}$ which is fundamental in Macaulay's theory. For defining the resultant, one considers the Macaulay matrix, which is the matrix over the monomial basis of the C-linear map $${\displaystyle (Q_1,\dots ,Q_n)\mapsto Q_1{P}_1+\cdots +Q_n{P}_n,}$$ in which each ${\displaystyle Q_i}$ runs over the homogeneous polynomials of degree ${\displaystyle D-d_i,}$ and the codomain is the C-module of the homogeneous polynomials of degree D.

If n = 2, the Macaulay matrix is the Sylvester matrix, and is a square matrix, but this is no longer true for n > 2. Thus, instead of considering the determinant, one considers all the maximal minors, that is the determinants of the square submatrices that have as many rows as the Macaulay matrix. Macaulay proved that the C-ideal generated by these principal minors is a principal ideal, which is generated by the greatest common divisor of these minors. As one is working with polynomials with integer coefficients, this greatest common divisor is defined up to its sign. The generic Macaulay resultant is the greatest common divisor which becomes 1, when, for each i, zero is substituted for all coefficients of ${\displaystyle P_i,}$ except the coefficient of ${\displaystyle x_i^{d_i},}$ for which one is substituted.

Properties of the generic Macaulay resultant

• The generic Macaulay resultant is an irreducible polynomial.
• It is homogeneous of degree ${\displaystyle B/d_i}$ in the coefficients of ${\displaystyle P_i,}$ where ${\displaystyle B=d_1\cdots d_n}$ is the Bézout bound.
• The product with the resultant of every monomial of degree D in ${\displaystyle x_1,\dots ,x_n}$ belongs to the ideal of ${\displaystyle C[x_1,\dots ,x_n]}$ generated by ${\displaystyle P_1,\dots ,P_n.}$

Resultant of polynomials over a field

From now on, we consider that the homogeneous polynomials ${\displaystyle P_1,\dots ,P_n}$ of degrees ${\displaystyle d_1,\dots ,d_n}$ have their coefficients in a field k, that is that they belong to ${\displaystyle k[x_1,\dots ,x_n].}$ Their resultant is defined as the element of k obtained by replacing in the generic resultant the indeterminate coefficients by the actual coefficients of the ${\displaystyle P_i.}$

The main property of the resultant is that it is zero if and only if ${\displaystyle P_1,\dots ,P_n}$ have a nonzero common zero in an algebraically closed extension of k.

The "only if" part of this theorem results from the last property of the preceding paragraph, and is an effective version of projective Nullstellensatz: If the resultant is nonzero, then $${\displaystyle ⟨x_1,\dots ,x_n{⟩}^D\subseteq ⟨P_1,\dots ,P_n⟩,}$$ where ${\displaystyle D=d_1+\cdots +d_n-n+1}$ is the Macaulay degree, and ${\displaystyle ⟨x_1,\dots ,x_n⟩}$ is the maximal homogeneous ideal. This implies that ${\displaystyle P_1,\dots ,P_n}$ have no other common zero than the unique common zero, (0, ..., 0), of ${\displaystyle x_1,\dots ,x_n.}$

Computability

As the computation of a resultant may be reduced to computing determinants and polynomial greatest common divisors, there are algorithms for computing resultants in a finite number of steps.

However, the generic resultant is a polynomial of very high degree (exponential in n) depending on a huge number of indeterminates. It follows that, except for very small n and very small degrees of input polynomials, the generic resultant is, in practice, impossible to compute, even with modern computers. Moreover, the number of monomials of the generic resultant is so high, that, if it would be computable, the result could not be stored on available memory devices, even for rather small values of n and of the degrees of the input polynomials.

Therefore, computing the resultant makes sense only for polynomials whose coefficients belong to a field or are polynomials in few indeterminates over a field.

In the case of input polynomials with coefficients in a field, the exact value of the resultant is rarely important, only its equality (or not) to zero matters. As the resultant is zero if and only if the rank of the Macaulay matrix is lower than its number of its rows, this equality to zero may by tested by applying Gaussian elimination to the Macaulay matrix. This provides a computational complexity ${\displaystyle d^{O(n)},}$ where d is the maximum degree of input polynomials.

Another case where the computation of the resultant may provide useful information is when the coefficients of the input polynomials are polynomials in a small number of indeterminates, often called parameters. In this case, the resultant, if not zero, defines a hypersurface in the parameter space. A point belongs to this hyper surface, if and only if there are values of ${\displaystyle x_1,\dots ,x_n}$ which, together with the coordinates of the point are a zero of the input polynomials. In other words, the resultant is the result of the "elimination" of ${\displaystyle x_1,\dots ,x_n}$ from the input polynomials.

U-resultant

Macaulay's resultant provides a method, called "U-resultant" by Macaulay, for solving systems of polynomial equations.

Given n − 1 homogeneous polynomials ${\displaystyle P_1,\dots ,P_{n-1},}$ of degrees ${\displaystyle d_1,\dots ,d_{n-1},}$ in n indeterminates ${\displaystyle x_1,\dots ,x_n,}$ over a field k, their U-resultant is the resultant of the n polynomials ${\displaystyle P_1,\dots ,P_{n-1},P_n,}$ where $${\displaystyle P_n=u_1{x}_1+\cdots +u_n{x}_n}$$ is the generic linear form whose coefficients are new indeterminates ${\displaystyle u_1,\dots ,u_n.}$ Notation ${\displaystyle u_i}$ or ${\displaystyle U_i}$ for these generic coefficients is traditional, and is the origin of the term U-resultant.

The U-resultant is a homogeneous polynomial in ${\displaystyle k[u_1,\dots ,u_n].}$ It is zero if and only if the common zeros of ${\displaystyle P_1,\dots ,P_{n-1}}$ form a projective algebraic set of positive dimension (that is, there are infinitely many projective zeros over an algebraically closed extension of k). If the U-resultant is not zero, its degree is the Bézout bound ${\displaystyle d_1\cdots d_{n-1}.}$ The U-resultant factorizes over an algebraically closed extension of k into a product of linear forms. If ${\displaystyle {\alpha }_1{u}_1+\dots +{\alpha }_n{u}_n}$ is such a linear factor, then ${\displaystyle {\alpha }_1,\dots ,{\alpha }_n}$ are the homogeneous coordinates of a common zero of ${\displaystyle P_1,\dots ,P_{n-1}.}$ Moreover, every common zero may be obtained from one of these linear factors, and the multiplicity as a factor is equal to the intersection multiplicity of the ${\displaystyle P_i}$ at this zero. In other words, the U-resultant provides a completely explicit version of Bézout's theorem.

Extension to more polynomials and computation

The U-resultant as defined by Macaulay requires the number of homogeneous polynomials in the system of equations to be ${\displaystyle n-1}$, where ${\displaystyle n}$ is the number of indeterminates. In 1981, Daniel Lazard extended the notion to the case where the number of polynomials may differ from ${\displaystyle n-1}$, and the resulting computation can be performed via a specialized Gaussian elimination procedure followed by symbolic determinant computation.

Let ${\displaystyle P_1,\dots ,P_k}$ be homogeneous polynomials in ${\displaystyle x_1,\dots ,x_n,}$ of degrees ${\displaystyle d_1,\dots ,d_k,}$ over a field k. Without loss of generality, one may suppose that ${\displaystyle d_1\ge d_2\ge \cdots \ge d_k.}$ Setting ${\displaystyle d_i=1}$ for i > k, the Macaulay bound is ${\displaystyle D=d_1+\cdots +d_n-n+1.}$

Let ${\displaystyle u_1,\dots ,u_n}$ be new indeterminates and define ${\displaystyle P_{k+1}=u_1{x}_1+\cdots +u_n{x}_n.}$ In this case, the Macaulay matrix is defined to be the matrix, over the basis of the monomials in ${\displaystyle x_1,\dots ,x_n,}$ of the linear map $${\displaystyle (Q_1,\dots ,Q_{k+1})\mapsto P_1{Q}_1+\cdots +P_{k+1}{Q}_{k+1},}$$ where, for each i, ${\displaystyle Q_i}$ runs over the linear space consisting of zero and the homogeneous polynomials of degree ${\displaystyle D-d_i}$.

Reducing the Macaulay matrix by a variant of Gaussian elimination, one obtains a square matrix of linear forms in ${\displaystyle u_1,\dots ,u_n.}$ The determinant of this matrix is the U-resultant. As with the original U-resultant, it is zero if and only if ${\displaystyle P_1,\dots ,P_k}$ have infinitely many common projective zeros (that is if the projective algebraic set defined by ${\displaystyle P_1,\dots ,P_k}$ has infinitely many points over an algebraic closure of k). Again as with the original U-resultant, when this U-resultant is not zero, it factorizes into linear factors over any algebraically closed extension of k. The coefficients of these linear factors are the homogeneous coordinates of the common zeros of ${\displaystyle P_1,\dots ,P_k,}$ and the multiplicity of a common zero equals the multiplicity of the corresponding linear factor.

The number of rows of the Macaulay matrix is less than ${\displaystyle (ed{)}^n,}$ where e ~ 2.7182 is the usual mathematical constant, and d is the arithmetic mean of the degrees of the ${\displaystyle P_i.}$ It follows that all solutions of a system of polynomial equations with a finite number of projective zeros can be determined in time ${\displaystyle d^{O(n)}.}$ Although this bound is large, it is nearly optimal in the following sense: if all input degrees are equal, then the time complexity of the procedure is polynomial in the expected number of solutions (Bézout's theorem). This computation may be practically viable when n, k and d are not large.