4
$\begingroup$

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?

$\endgroup$
11
  • $\begingroup$ How does one know that there is a repeated root without knowledge of any root? $\endgroup$
    – Mark Viola
    Apr 10 '15 at 17:11
  • $\begingroup$ It is a polynomial condition on the coefficients of the polynomial, also known as $Res(f,f')=0$. @Dr.MV cfr Resultant $\endgroup$
    – user228113
    Apr 10 '15 at 17:16
  • $\begingroup$ @Dr.MV : I don't know. This question came to my mind but I could not think of a way to do it. I am expecting that the algorithm/solution should return the same polynomial if it has no repeating roots. $\endgroup$
    – Bhaskar
    Apr 10 '15 at 17:20
  • 3
    $\begingroup$ The squarefree part is $\, f/\gcd(f,f')\,$ over a field of characteristic 0 $\endgroup$ Apr 10 '15 at 17:25
  • $\begingroup$ @G.Sassatelli Does that tell one whether the original polynomial of interest has multiple roots? And how does one proceed to find the "resultant" without any knowledge of any root? $\endgroup$
    – Mark Viola
    Apr 10 '15 at 17:26
6
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.