Resultants and discriminants over Z

The resultant of f = a \prod_{i=1}^m (x - \alpha_i) and g = b \prod_{j=1}^n (x - \beta_j) in \mathbb{Z}[x],

is the determinant of the (m + n) \times (m + n) Sylvester matrix, whose first n rows hold shifted copies of the coefficients of f and whose last m rows those of g. It is an integer, it vanishes exactly when f and g have a common root, and it is a polynomial in the coefficients, which makes it the tool of elimination: for example, \operatorname{res}_y(f(y), g(x - y)) is a polynomial whose roots are the sums \alpha_i + \beta_j. The discriminant

vanishes exactly when f has a repeated root, and for a monic irreducible f it is, up to the square of an index, the discriminant of the number field \mathbb{Q}[x]/(f). Over a field the resultant can be computed with the Euclidean or half-GCD algorithm (Half-GCD); over \mathbb{Z} the questions are again how to avoid coefficient growth, and how many primes a modular method needs.

The size of the resultant#

Removing contents first gives a better bound, since \operatorname{res}(cf, dg) = c^n d^m \operatorname{res}(f, g) for integers c, d.

The subresultant algorithm#

The subresultant pseudo-remainder sequence of The subresultant algorithm also gives the resultant: if f and g have no common factor, the sequence ends in a constant, and the resultant is that constant times known powers of g and h and a sign, by the multiplicativity of resultants and \operatorname{res}(f, g) = (-1)^{mn} \operatorname{res}(g, f) (Algorithm 3.3.7 of [Coh1996]). _fmpz_poly_resultant_euclidean implements it after removing the contents, which it multiplies back at the end. The intermediate polynomials have coefficients of the size of subresultants, at most that of the resultant itself, so the algorithm performs O(mn) operations on integers of O((m + n)(b + \log(m + n))) bits. It is the fastest method for short polynomials with small coefficients. The generic _gr_poly_resultant_subresultant is adapted from it and works over any integral domain.

The multimodular algorithm#

_fmpz_poly_resultant_modular [Col1971] removes the contents, computes the bound of Theorem 1 for the primitive parts, and takes enough primes p > 2^{63} not dividing the product of the leading coefficients for their product to exceed twice the bound. For each prime it reduces the polynomials and computes the resultant with _nmod_poly_resultant, which uses the half-GCD algorithm for long polynomials, and it combines the residues with one multi-CRT (fmpz_multi_CRT_ui) into the symmetric range. Unlike the GCD, the resultant has no unlucky primes, and the number of primes is fixed in advance; Hadamard's bound is usually close to the actual size for random input.

When a factor d of the resultant and a bound for the quotient are known, _fmpz_poly_resultant_modular_div computes \operatorname{res}(f, g) / d modulo primes that do not divide d (dividing by d modulo each prime) with \lceil (\mathit{nbits} + 1)/63 \rceil primes on 64-bit machines, where nbits is the bit bound passed for the quotient; the extra bit is needed by the reconstruction in the symmetric range. It also splits the powers of the contents between the known divisor and the remaining factor. This is useful when the resultant is known to be divisible by a large number, for example in discriminant computations for number fields.

Use in FLINT#

• fmpz_poly_resultant uses fmpz_poly_resultant_euclidean when the shorter polynomial has length \ell_2 \le 144 and \ell_2^3 (b_1 + b_2) \le 6 \cdot 10^6 for coefficient sizes b_1, b_2 bits, and fmpz_poly_resultant_modular otherwise.
• fmpz_poly_discriminant computes \operatorname{res}(f, f') with _fmpz_poly_resultant, adjusts the sign and divides by the leading coefficient.
• fmpz_poly_xgcd_modular starts with the resultant (Extended GCD and cofactors).
• fmpq_poly_resultant, fmpq_poly_discriminant and fmpq_poly_resultant_modular_div clear denominators and call the fmpz_poly functions.