I am interested in the problem of finding a real root of a polynomial equation $f(x)=0$ where $f(x)=\sum_{i=0}^n a_ix^i$. Is it possible to give a reduction, i.e, to compute a different polynomial $g$ in polytime such that $f$ has a real root iff $g$ has a real root in [0,1]$?


Not sure if this is the right SE forum for it, but the answer is yes.

I'll give the reduction in two steps:

  1. $f(x)$ has a root iff $h(x)$ has a root in [-1,1] (scaling, i.e. $h(x)=f(\alpha \cdot x)$).
  2. $h(x)$ has a root in [-1,1] iff $g(x)$ has a root in [0,1] (simply define $g(x)=h(\frac{x+1}{2})$).

Let's prove 1:

Let's assume $f(x)$ is of degree $n$ and write it as $f(x) = x^n - a_{n-1} x^{n-1} - ... - a_0$.

If $\alpha \leq 1$, then all of the roots of $f$ in [-1,1] will end up in [-1,1] in $h$.

Let $x$ be a root of $f$ such that $|x|>1$. This means $x^n = a_{n-1} x^{n-1} + ... + a_0$.

since $|x|>1$, $|x^n| > x^{n-1},x^{n-2},...,1$ hence $$|x| \le \text{max}(1, |a_{n-1}| + ... + |a_0|).$$

Define $\alpha = \text{max}(1, |a_{n-1}| + ... + |a_0|)$ and you're done.

  • 1
    $\begingroup$ I think you want $h(x)=f(x / \alpha)$. $\endgroup$
    – Thomas
    Apr 29 '14 at 17:16
  • $\begingroup$ Note that this approach can cause a blowup in the height of the coefficients; it's not clear (to me) whether or not this can be done without a substantial blowup in height or degree, though I suspect you need one or the other... $\endgroup$ May 1 '14 at 19:17

Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree.

Simply take $g(x) = x^{2n}f(x)f(-x)f(1/x)f(-1/x)$.

  • $\begingroup$ Also, you can make a hybrid of the approaches (simple and not-that-much-higher degree) with: $g(x) = (\frac{x+1}{2})^nf(\frac{x+1}{2})f(\frac{2}{x+1})$. $\endgroup$
    – R B
    May 1 '14 at 12:04
  • $\begingroup$ I think you meant $g(x) = (2x-1)^n f(2x-1) f(1/(2x-1))$, but yes. $\endgroup$ May 1 '14 at 13:42

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.