# How to find the recurrence polynomial?

Problem:

If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion):

$$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in \mathbb{N})$$

How to find $g$, such the roots of $g$ is just $x_1,x_2,\ldots,x_b$?

Details:

Looks like the main problem is solve

$g(x){(-1)}^bg(-x)=f(x)$. But I don't know if this is suficient to force $g$ be of the form $\prod_{i=1}^{b}(x-x_i)$. Looks like using this way, we get a indeterminated system, but if we can express all solutions there's no problem.

Using mathematica an easy problem couldn't be solved, see:

f[x_]:=(x-1)(x+1), RSolve[-g[x]g[-x]==f[x],g[x],x]. The software calculate and calculate...I didn't get answer.

So, using the definition of $f$ above ($f(x)=\sum_{a=0}^{2b}f_ax^a$) how to find the polynomial $g$ with roots $x_1,x_2,\ldots,x_b$?

How can we solve this recursion ($g(x){(-1)}^bg(-x)=f(x)$) and find all $g$ to satisfies it?

If someone knows a computable way to do it, I'd like to know too. If is using Mathematica is more interesting to me.

• Quite unclear. How can a degree $b$ polynomial have $2b$ roots in $\pm$ pairs? Dec 14 '11 at 0:40
• The question is underspecified since you have given no way to distinguish $x_j$ from $-x_j$. E.g., given the polynomial $x^2+1$, $x+i$ is an answer, but so is $x-i$; in higher degrees, it gets worse. Dec 14 '11 at 0:40
• @J.M. In the sum is 2b. Edited. Dec 14 '11 at 0:46
• Anyway, this should be interesting to you: With[{n = 6}, {#, x /. Solve[# == 0, x]} &[Collect[Expand[Apply[Times, Sqrt[x] + (C /@ Range[n])] Apply[Times, Sqrt[x] - (C /@ Range[n])]], x, Simplify]]] Change the value of n to something higher or lower; you should see a pattern. Dec 14 '11 at 0:48

Since $$f(x)=x^{2b}+a_{2b-1}x^{2b-1}+\cdots +a_1x+a_0$$ is a polynomial with roots $$x_1, -x_1, ..., x_b, -x_b$$ (For the sake of simplicity, let us assume that $$x_1, ..., x_b$$ are positive real numbers). So $$f$$ must be of the form$$f(x)=(x-x_1)(x+x_1) \cdots (x-x_b)(x+x_b)=\prod_{i=1}^b(x^2-x_i^2).$$As we know, the coefficients of a polynomial $$p$$ of degree $$n$$ with roots $$r_1, r_2, ..., r_n$$ are elementary symmetric polynomials in the roots of $$p$$; that is,$$p(x)=\prod_{i=1}^n(x-r_i)=\sum_{k=0}^n\sum_{1 \le j_1 \lt ... \lt j_k \le n}(-1)^kr_{j_1} ... r_{j_k}x^{n-k}.^{\, \dagger}$$ So, the coefficient of $$x^{2b-2}$$ in $$f(x)$$ equals $$a_{2b-2}=-\sum_{i=1}^bx_i^2.$$Suppose that there is a general algebraic way (By "algebraic way" I mean a way involving a finite number of the operations of addition, multiplication, and exponentiation with constant rational exponents) to find a polynomial $$g$$ with roots $$x_1, ..., x_b$$,$$g(x)=\prod_{i=1}^b(x-x_i)=\sum_{k=0}^b\sum_{1 \le j_1 \lt ... \lt j_k \le b}(-1)^kx_{j_1} ... x_{j_k}x^{b-k},$$ from knowing $$f$$. So, this implies that we can find the coefficient of $$x^{b-1}$$ in $$g(x)$$, that is, $$\sum_{i=1}^bx_b$$, which implies the fact that there is a general algebraic way to find the sum of the square roots of an arbitrary polynomial $$f$$ in terms of the coefficients of $$f$$, which is a contradiction (In brief, if such a way exists, then one can algebraically find a root of a polynomial which is non-solvable by radicals, which is impossible). $$\ddagger$$
Thus, there is no general algebraic way to find a polynomial $$g$$ with roots $$x_1, ..., x_b$$.
$$\dagger$$ For the proof, please see this answer.
$$\ddagger$$ For the proof, please see this answer.