Intro: This question has been inspired by the question If $P(P(x)-1) = 1 + x^{36}$ then $P(2)=$ . Here, we will consider (what was not explicitly mentioned in the original question) that $P$ is a polynomial, and we will consider different fields of coefficients.
With an easy substitution $Q(x)=P(x)-1$, in the original question we get that $Q(Q(x))=x^{36}$ and so the "easy" solution is $Q(x)=x^6$ and $P(x)=x^6+1$. The question here is: are there other solutions for $Q$, and thereby for $P$? In particular, over $\mathbb C$ the solutions are also $P(x)=\epsilon^i x^6+1$ where $\epsilon$ is a primitive $7$th root of unity, and $i=0,1,\ldots, 6$.
With that as an introduction, I am asking the:
Question: Suppose $K$ is a field and $P\in K[x]$ is a polynomial such that $P(P(x))=x^{n^2}$ for some natural number $n\ge 1$. What can be said about solutions for $P$ other than $P(x)=x^n$?
In particular, I am interested if $P(x)=x^n$ is the unique solution over $K=\mathbb R$, and whether $P(x)=\epsilon^i x^n$ are all the solutions over $\mathbb C$, where $\epsilon$ is a primitive $(n+1)$th root of unity, $i=0,1,\ldots,n$. As a cherry on the cake, it would be interesting to see if anything can be said over other fields of characteristic $0$, or, more generally, over other fields.
My work: I only looked at a field of characteristic $0$ for now, and if necessary I can always assume WLOG that $K$ is algebraically closed.
One obvious conclusion is that degree of $P$ is $n$.
It seems that $P(P(x))-x=x^{n^2}-x=x\prod_{i=0}^{n^2-1}(x-\eta^i)$ where $\eta$ is a primitive $(n^2-1)$st root of unity. Let $Z=\{0, 1,\eta,\eta^2,\ldots,\eta^{n^2-2}\}$ be the set of the zeros of $x^{n^2}-x$. Turns out, $x\in Z$ is equivalent to $P(P(x))=x$. Now, let $x\in Z$ and $y=P(x)$. This implies $P(P(y))=P(P(P(x))=P(x)=y$ so $y\in Z$. Also, $P(y)=P(P(x))=x$. Thus, $P$ is an involution on the set $Z$. This would of course make it a finite problem for any particular $n$: just look at all the (polynomial) involutions on $Z$ (e.g. Lagrange interpolation polynomials) and dismiss those that don't satisfy $P(P(x))=x^{n^2}$, but even for small numbers (like $n=6$ in the original problem) it would be a lot of work.
One outtake here is that we can do the whole work in the algebraic closure $A$ of $\mathbb Q$ because all the candidate polynomials will end up being in $A[x]$, even if the field is a bigger field of characteristic $0$. However, this also means that we can work in $\mathbb C\supset A$ all the time.
Now, let's see what we can say about zeros of $P$. If $z$ is a zero of $P$, then $P(z)=0\in Z$ and $z^{n^2}=P(P(z))=P(0)=z'\in Z$. Thus, all zeros of $P$ are either $0$, or they are on the unit circle and $n^2$th power of them is an element of $Z$ which itself is one of $(n^2-1)$st roots of unity. Thus, all zeros of $P$ must be either $0$ or they are $n^2(n^2-1)$st roots of unity. So we have two cases:
- $z'=P(0)=0$, in which case $z^{n^2}=0$ i.e. $z=0$. Thus all the zeros of $P$ are equal to $0$, so $P(x)=\alpha x^n$ and one can easily show that $\alpha^{n+1}=1$.
- $z'=P(0)\ne 0$, so $z^{n^2}\ne 0$ and so none of the zeros of $P$ are $0$, exactly one of them (namely $z'$) is an $(n^2-1)$st root of unity, and the rest are $n^2$th roots of $z'$ and also $n^2(n^2-1)$st roots of unity and not in $Z$.
I think my plan from here would be to try to prove that the second case cannot happen. And this is where I am stuck at the moment.
Below I prove that if $n$ is not divisible by the characteristic of a field $K$, then the only $P(x)\in K[x]$ with $P(P(x))=x^{n^2}$ is $P(x)=ax^n$ where $a^{n+1}=1$. In particular, for $K\in \{\mathbb{R},\mathbb{C}\}$, the characteristic is zero, and we get your solutions, plus when $K=\mathbb{R}$ and $n$ odd, $P(x)=-x^n$.
Here is the proof:
$$P(x)=ax^n+bx^{n-1}+O(x^{n-2})$$ $$P(x)^n=a^nx^{n^2}+na^{n-1}bx^{n^2-1}+O(x^{n^2-2})$$ $P(x)^{n-1}=O(x^{n^2-n})$ so we only need to include $P(P(x))=aP(x)^n+O(x^{n^2-n})$ $$P(P(x))=a^{n+1}x^{n^2}+na^nbx^{n^2-1}+O(x^{n^2-2})$$
If we require $P(P(x))=x^{n^2}$, then $a^{n+1}=1$ and $na^nb=0$. If the characteristic of $K$ does not divide $n$, then we find $b=0$. So, $P(x)=ax^n+cx^{n-2}+O(x^{n-3})$. We would like to show that $c=0$ and repeat the argument until $P(x)=ax^n$.
Let $m<n$ and suppose $P(x)=ax^n+cx^m+O(x^{m-1})$. We get
$$P(x)^n=a^nx^{n^2}+na^{n-1}cx^{n(n-1)+m}+O(x^{n(n-2)+2m})$$
So, as $P(x)^m=O(x^{mn})$ and $mn\le n(n-1)$, we get $$P(P(x))=a^{n+1}x^{n^2}+na^ncx^{n(n-1)+m}+O(x^{n(n-2)+2m})$$
So, if $P(P(x))=x^{n^2}$, $a^{n+1}=1$ and $na^nc=0$. Again, if the characteristic of $K$ does not divide $n$, then $c=0$ follows. We can repeat the argument with $m-1$, and keep going until we find that $P(x)=ax^n$ where $a$ is an $(n+1)^\text{th}$ root of unity in $K$.