Assume you're given $p(p(X))$ in the form
$$p(p(X))= \sum_{i≥0} a_i X^i$$
Is there any quick algorithm to retrieve $p$?
What can be said about the degree of $p(p)$ I think it's twice the degree of $p$.
Asked
Active
Viewed 71 times
2
-
If $p$ has degree $1$, then so does $p\circ p$. – hmakholm left over Monica Aug 02 '15 at 00:25
-
3If $p(x)$ has degree $n$, then $p(p(x))$ has degree $n^2$, not $2n$. For an easy example: let $p(x) = x^3$, then $p(p(x)) = (x^3)^3 = x^9$. This is far from being a linear map so I'm not certain that a fast algorithm exists. – Cameron Williams Aug 02 '15 at 00:26
-
1There might be several $p$ leading to the same $p(p(X))$. For example $p = X$, and $p = a-X$ (for any $a \in \mathbb{C}$) lead to the same polynomial $p \circ p$. – Joel Cohen Aug 02 '15 at 01:43
-
I see what you mean, Joel. Even if that's the case, is there an algorithm to find a $p$ that works? – YoTengoUnLCD Aug 02 '15 at 02:24
-
If deg(p)>1<deg(q) – DanielWainfleet Aug 02 '15 at 05:45
-
Do you know the maximal degree of p(x) or can it be arbitrarily large? – Atnas Aug 02 '15 at 21:11
-
It can be arbitrarily large. – YoTengoUnLCD Aug 02 '15 at 22:53
1 Answers
0
I've thought about this quite a lot and come up with part of a solution.
We call the coefficients of the original polynomial $c_i$ and have it of degree $n$, s.t. $$p(p(X))=\sum\limits_{i=0}^{n^2} a_iX^i$$ $$p(X)=\sum\limits_{i=0}^n c_iX^i$$
The first five coefficients of $p(x)$ are given by $$c_{n} = a_{n^2}^{-n-1}$$ $$c_{n-1} = F(1)$$ $$c_{n-2} = F(2)-H_2(2)$$ $$c_{n-3} = F(3)-H_2(3)-H_3(3)$$ $$c_{n-4} = F(4)-H_2(4)-H_3(4)-H_4(4)$$ The formulas do not hold if $c_i$ has $i<0$, as that coefficient does not exist.
The additional functions are given below $$ F(i) = \frac{1}{n}\frac{a_{n^2-i}}{c_n^n} + \begin{cases} \frac{1}{4}\frac{c_{n-1}}{c_{n}} & i=n\\ 0 & otherwise \end{cases} $$ $$ H_2(i) = c_{n-1}^i\prod\limits_{j=1}^{i-1}\frac{n-j}{j+1}\frac{1}{c_n} $$ $$ H_3(i) = c_{n-2}\prod\limits_{j=1}^{i-2}\frac{n-j}{j} \frac{c_{n-1}}{c_n}$$ $$ H_4(i) = \frac{(c_{n-1}c_{n-3}+\frac{3i}{2}c_{n-2}^2)}{c_{n-1}} \prod\limits_{j=1}^{i-2}\frac{n-j}{j} \frac{c_{n-1}}{c_n} $$
Sadly this is not the complete solution, since I can't find a general formula for $H_j(i)$
It only something I've found by looking at the solutions generated by CAS software for specific values of $n$, and then chosen functions that work for all tested values, so technically I haven't proved that it's correct, but I find it unlikely that it will break down, if it works for all values of $n$ between 1 and 20.
I hope it can help someone.
Atnas
- 211