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

<p>I'll give the reduction in two steps:</p>

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

<p>Let's prove 1:</p>

<p>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$.</p>

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

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

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

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

CC BY-SA 3.0
2014-04-29T17:16:37.613Z
I think you want $h(x)=f(x / \alpha)$.
Thomas Steinke
CC BY-SA 3.0
2014-05-01T19:17:53.217Z
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...
Steven Stadnicki
CC BY-SA 3.0
2014-04-29T14:36:53.607Z
2014-05-01T10:30:00.747Z
2014-05-01T10:30:00.747Z
R B
<p>Here is an alternative to the answer by R B ; It is somewhat simpler, but has the disadvantage of an increase in degree.</p>

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

CC BY-SA 3.0
2014-05-01T12:04:06.200Z
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})$.
R B
CC BY-SA 3.0
2014-05-01T13:42:28.637Z
I think you meant $g(x) = (2x-1)^n f(2x-1) f(1/(2x-1))$, but yes.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-05-01T11:07:59.013Z
2014-05-01T11:07:59.013Z
Kristoffer Arnsfelt Hansen
<p>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]$?</p>

<reductions><polynomials>
Root finding in [0,1]
user22166
# Root finding in [0,1]

(Asked by: username_0 on 2014-04-29)

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

**Tags:** reductions, polynomials

---

## 2 answers

### Answer by username_1 on 2014-04-29. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_2**: I think you want $h(x)=f(x / \alpha)$.  
> **username_3**: 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...  

---

### Answer by username_4 on 2014-05-01. Score: 5

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

> **Comments:**
> **username_1**: 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})$.  
> **username_4**: I think you meant $g(x) = (2x-1)^n f(2x-1) f(1/(2x-1))$, but yes.  

---

