How to remove duplicate roots from a polynomial?

Given a polynomial equation (with real coefficients of any degree with any number of repeating roots), let say

$x^5 + 6x^4 - 18x^3 - 10x^2 + 45x - 24 = 0$, ... (A)

it can be written as

$(x-1)^2 (x+8) (x^2-3) = 0$.

As you can see, it has a repeating root $x = 1$.

Forming a new polynomial by removing the duplicate root (i.e, taking repeating roots only once), we will get

$(x-1) (x+8) (x^2-3) = 0$.

Then expanding it, we get

$x^4+7 x^3-11 x^2-21 x+24 = 0$. ... (B)

Is it possible to get a polynomial having all of the roots of the given polynomial but taking the repeating roots only once, i.e, getting (B) from (A), directly without finding any roots? If possible, how to do the same?

Solution 1:

The square free kernel (or radical) of a polynomial, i.e. the product of all prime = irreducible factors (up to a constant factor) can be computed efficiently via a gcd calculation, namely

$$ {\rm rad}(f(x))\, =\, \frac{f(x)}{\gcd(f(x),f'(x))}\qquad$$

This works because taking the dervative decrements the multiplicity of each prime factor, thus taking the above quotient has the effect of cancelling out repeated factors from $\,f.\,$ (Beware that this need not work over fields of characteristic $\neq 0).$

A typical example is Hermite's method for integrating rational functions.

Contrast this with the number (integer) case. Lacking an analog of the derivative for numbers we cannot use the same idea. It is trivial to to compute the radical and square/squarefree parts if we are given the prime factorization. Currently we do not know any better way, and it is widely suspected that there is none, i.e computing the squarefree part of an integer may prove to be equivalent to factorization.

This problem is important because one of the main tasks of computational algebraic number theory reduces to it (in deterministic polynomial time). Namely the problem of computing the ring of integers of an algebraic number field depends upon the square-free decomposition of the polynomial discriminant (when computing an integral basis).