<s>[INST] Find all polynomials $P$ such that $P(P(x))=P(x^n)+P(x)-1$ 
Find all polynomials $P$ of degree $n$ such that $P(P(x))=P(x^n)+P(x)-1$.

I stumbled upon this problem while solving functional equations in polynomials. However, even after trying most of the methods I know, I'm still yet to solve it. Here's what I tried:

*

*Obviously, solutions exist, since the constant polynomial $P(x)=1$ satisfies the given equation.

*Considering the highest degree of both sides didn't give any results (they have the same degree).

*Taking the derivative of both sides just further complicated the equation.

*Substituting $x\mapsto P(x)$ didn't seem to help either.

*I tried to prove that $P$ is injective, but it just gave $P(x)=P(y) \Longrightarrow P(x^n)=P(y^n)$.

*Substituting $x\mapsto x^n$ and combining the result with the original equation yields $P(P(x^n))-P(P(x))=P(x^{n^2})-P(x)$. I tried to define some new polynomial from this equation to simplify it, but it didn't work.

*Trying for specific values of n, I found $P(x)=1$ and $P(x)=2x-1$ work when $n=1$, but no such polynomial of degree $2$ exists.

What should I do to solve this problem?
Also, I've noticed that the second-highest degree of RHS is $nm$, where $m$ is the second-highest degree of $P$. Is it  possible to prove that LHS has a different second-highest degree?
 [/INST] $\bullet\ $ If $n=0$, then $P=a$ for a constant $a$. Replacing in the equation, you get $a=a+a-1$, so $a=1$, so you get thet solution
$$P(X)=1$$
$\bullet\ $ If $n=1$, then $P(X)=aX+b$ for some constants $a\neq 0$ and $b$. Replacing in the equation, you get
$$a(aX+b)+b=aX+b+aX+b-1$$
so $a^2=2a$ and $ab+b=2b-1$. You get that $a=2$ and $b=-1$, so you get the solution
$$P(X)=2X-1$$
$\bullet\ $ If $n=2$, then $P(X)=aX^2+bX+c$ for some constants $a \neq 0$, $b$ and $c$. Replacing in the equation, you get that
$$a(aX^2+bX+c)^2 + b(aX^2+bX+c)+c=aX^4+bX^2+c + aX^2+bX+c - 1$$
i.e.
$$a^3X^4 + 2a^2bX^3+ (ab^2+2a^2c+ab)X^2 +(2abc+b^2)X + ac^2+bc+c$$ $$= aX^4+(a+b)X^2+ bX+2c - 1$$
Identifying the $X^4$ coefficient, you get $a^3=a$, so $a=\pm 1$.
Identifying the $X^3$ coefficient, you get then that $2b=0$, so $b=0$.
Identifying the $X^2$ coefficient, you get then that $2c=a$.
Identifying the constant coeffcient, you get that $ac^2 = c-1$, so $a(2c)^2=4c-4$, so $a^3 = 2a-4$, so $a=2a-4$, so $a=4$, contradiction.
So there is no solution for $n=2$.
$\bullet\ $ If $n\geq 3$ :
First, there is no solution of the form $P(X)=aX^n$. Indeed, for such a polynomial, you have $P(0)=0$, which contradicts the fact that $P(P(X))=P(X^n)+P(X)-1$ (just evaluate at $X=0$).
So if $P$ is solution, then you have $P(X)=aX^n + bX^m + Q(X)$, with $a,b \neq 0$, $m<n$ and $\deg(Q)<m$. For such a polynomial, one has
\begin{align*} &P(P(X)) \\
&=a(aX^n + bX^m + Q(X))^n + b(aX^n + bX^m + Q(X))^m + Q(aX^n + bX^m + Q(X))\\
& =a^{n+1}X^{n^2} + a^{n}bnX^{n(n-1)+m} + R(X)
\end{align*}
where $R$ has degree strictly less than $n(n-1)+m$. But one has also
$$P(X^n)+P(X)-1 = aX^{n^2} +S(X)$$
where $S$ has degree less than $\max(m,nm)$. But since $n \geq 3$, then $\max(m,nm) < n(n-1)+m$, so you got a contradiction.
Finally, the only solutions are
$$\boxed{P(X)=1 \quad \quad \text{and} \quad \quad P(X)=2X-1}$$
</s>