Q:

Root finding in [0,1]

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]$?

A:

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

A:

Not sure if this is the right SE forum for it, but the answer is yes.
I'll give the reduction in two steps:

$f(x)$ has a root iff $h(x)$ has a root in [-1,1] (scaling, i.e. $h(x)=f(\alpha \cdot x)$).
$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.

