How to find $p\in \Bbb C[X]$ given $p(p(X))$ 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$.
 A: 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.
