Let $P(x)$ and $Q(x)$ be polynomials with positive leading coefficients. If $P(P(x)) = P(x)^5+x^{15}+Q(x)$, minimum value of the degree of $Q(x)$? My steps:
Since for two polynomial expressions to be equal, their degrees have to be equal, I decided to compare the degrees of the RHS and LHS. I figured out that the degree of $P(P(x))$ is ${deg(P(x))}^{deg(P(x))}$ And the degree of the LHS can only be 15, $5 \cdot deg(P(x))$ or $deg(Q(x))$. However, I wasn't able to produce a solution from here. Any help would be appreciated.
 A: Let $P(x)= ax^n+...$ and $Q(x) =bx^m+...$ where $a,b>0$. Then $$a(ax^n+...)^n+... = a^5x^{5n} +...x^{15} +bx^m+...$$ so $n^2 = \max\{5n,15,m\}\geq 5n\implies n\geq 5$. If $n\geq 6$ then $n^2 > 5n>15$ so $n^2 =\max \{5n,15,m\} =m $ and thus $m\geq 36$.
So let $n=5$, then $P(x)= ax^5+cx^4+dx^3+...$ and $m\leq 25$.
$$Q(x) = a(ax^5+...)^5 -(a^5x^{25}+...)-x^{15}$$

*

*If $a\neq 1$ then $m= 25$.


*If $a=1$ then $$Q(x) = cP(x)^4+...-x^{15}$$ If $c\neq 0$ then degree of RHS is 20 so we put $c=0$, then the degree of RHS is $15$ or less. So let $c=0$ Now we have $$Q(x) = dP(x)^3+...-x^{15}$$
If $d=0 $ then RHS has degree 15 and negative leading coefficient, so $d\neq 0$. If we put $d=1$ we get $$Q(x) = P(x)^3+...-x^{15}$$ and now RHS has degree $<15$.
So if we set $P(x) = x^5+x^3$ we get $Q(x) =3x^{13} + 3x^{11}+x^9 $, so $m_{\min} =13$.
A: One possible solution is
$$P(x)=x^5+x^3\text{ and }Q(x)=3x^{13}+3x^{11}+x^9$$
We will prove that this gives the smallest degree $Q$. First, we will show that $d(P)=5$. Suppose not, then
$$P(x)=\sum_{n=0}^k a_n x^n$$
for some $a_k>0$ and $k>5$. Then
$$Q(x)=P(P(x))-P(x)^5-x^{15}$$
We also have that
$$d(P(P))=k^2>5k>15$$
$$d(P^5)=5k>15$$
$$d(x^{15})=15$$
which implies $d(Q)=k^2>15$. Thus, the degree of $P(x)$ is at most $5$. Now, consider a general
$$P(x)=a x^5+ b x^4+c x^3+dx^2+ex+f$$
Using this formula for $P(x)$ it is obvious that $d(Q)\leq 25$. We can write $Q(x)$ as
$$Q(x)=P(P(x))-P(x)^5-x^{15}=\sum_{n=0}^{25} r_n x^n$$
It's a little tedious, but one can check that
$$r_{25}=a^6-a^5$$
Since we want to minimize the degree of $Q$, we want this to be $0$ so $a=1$. Continuing in this fashion, we find that setting $a=1$ gives
$$r_{25}=r_{24}=...=r_{21}=0$$
$$r_{20}=b$$
So $b=0$. In the same manner, setting $b=0$ gives
$$r_{20}=r_{19}=...=r_{16}=0$$
$$r_{15}=c-1$$
So $c=1$. Setting $c=1$ gives us
$$r_{15}=r_{14}=0$$
$$r_{13}=3$$
At this point, we can't lower the degree using $d,e,$ or $f$ (which are essentially free variables at this point) and we conclude the minimum degree of $Q(x)$ is $13$.
