Minimum degree of $P(P(x)) - Q(Q(x))$ Let $P$ and $Q$ be distinct polynomials of degree $n$, with real coefficients. What is the minimum possible degree of $P(P(x)) - Q(Q(x))$?
(Treat conventionally the degree of the zero polynomial to be $0$.)
For $n$ odd because of $P(x) = x^n$ and $Q(x) = -x^n$ the answer is $0$. By bashing (i.e. writing $P(x) = ax^2 + bx + c$, $Q(x) = mx^2 + nx + p$ and expanding $P(P(x)) - Q(Q(x))$) we see that the degree must be at least $2$. Any idea for an approach for general $n = 2k$, possibly without too much expanding (but more like considering complex roots or something else clever)?
Any help appreciated!
 A: (This is too long for a comment so I submitted an answer instead)
Note 1:
For even $n$:
Let $P(x)=\sum^{n}_{i=0}a_ix^i$ and $Q(x)=\sum^{n}_{i=0}b_ix^i$. Then by Multinomial Theorem:
$$P(P(x))=\sum^{n}_{i=0}a_i\left(\sum^{n}_{j=0}a_jx^j\right)^i=\sum^{n}_{i=0}a_i\sum_{k_1+k_2+\cdots+k_n=i}\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}\left(a_jx^j\right)^{k_j}=\sum^{n}_{i=0}a_i\sum_{k_1+k_2+\cdots+k_n=i}\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}a_j^{k_j}x^{j\cdot k_j}=\sum^{n}_{i=0}a_i\sum_{k_1+k_2+\cdots+k_n=i}\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}\left(a_jx^j\right)^{k_j}=\sum^{n}_{i=0}\sum_{k_1+k_2+\cdots+k_n=i}a_i\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}a_j^{k_j}\cdot x^{\sum^{n}_{j=1}j\cdot k_j}$$
Similarly,
$$Q(Q(x))=\sum^{n}_{i=0}\sum_{k_1+k_2+\cdots+k_n=i}b_i\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}b_j^{k_j}\cdot x^{\sum^{n}_{j=1}j\cdot k_j}$$
Thus:
$$P(P(x))-Q(Q(x))=\sum^{n}_{i=0}\sum_{k_1+k_2+\cdots+k_n=i}a_i\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}a_j^{k_j}\cdot x^{\sum^{n}_{j=1}j\cdot k_j}-\sum^{n}_{i=0}\sum_{k_1+k_2+\cdots+k_n=i}b_i\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}b_j^{k_j}\cdot x^{\sum^{n}_{j=1}j\cdot k_j}$$
Consider the coefficient for $x^{n^2}$ of $P(P(x))-Q(Q(x))$. To first find that, we need to find a combination of nonnegative integers $k_1, k_2,\cdots,k_n$ such that $\sum^{n}_{j=1}j\cdot k_j=n^2$ and $\sum^{n}_{j=1}k_j\leq n$. The only case when this happens is when $k_1=k_2=k_3=\cdots=k_{n-1}=0, k_n=n$. Then $\sum^{n}_{j=1}j\cdot k_j=n^2$, $i=n$ and $a_i\binom n{k_1,k_2,\cdots,k_n}\prod^n_{j=1}a_j^{k_j}\cdot x^{\sum^{n}_{j=1}j\cdot k_j}=a_n\binom n{0,0,\cdots,n}a_n^nx^{n^2}=a_n^{n+1}x^{n^2}$, so the coefficient for $x^{n^2}$ of $P(P(x))$ is $a_n^{n+1}$. Similarly, the coefficient for $x^{n^2}$ of $-Q(Q(x))$ is $-b_n^{n+1}$, so the coefficient for $x^{n^2}$ of $P(P(x))-Q(Q(x))$ is $a_n^{n+1}-b_n^{n+1}$. We want this to be $0$ (which would imply that $P(P(x))-Q(Q(x))$ has degree less than or equal to $n^2-1$), so we want $a_n^{n+1}-b_n^{n+1}=0$. (Presumably) the coefficients of the polynomials must be real, so we have $a_n=b_n$.

Note 2:
Suppose $Q(x)=P(x)+c$ and $P(x)=\sum^{n}_{i=0}a_ix^i$. Then:
$$Q(Q(x))=P(P(x)+c)+c=c+\sum^{n}_{i=0}a_i(P(x)+c)^i=c+\sum^{n}_{i=0}\sum^{i}_{j=0}a_i\binom ijc^jP^{n-j}(x)=c+\sum^{n}_{i=0}P^i(x)c^{n-i}\sum^{i}_{j=0}a_{n-j}\binom {n-j}{n-i}$$
So:
$$P(P(x))-Q(Q(x))=\sum^{n}_{i=0}a_iP^i(x)-c-\sum^{n}_{i=0}P^i(x)c^{n-i}\sum^{i}_{j=0}a_{n-j}\binom {n-j}{n-i}=\sum^{n}_{i=0}\left(a_i-c^{n-i}\sum^{i}_{j=0}a_{n-j}\binom {n-j}{n-i}\right)P^i(x)-c$$
Note that $P^i(x)$ has degree $in$.
Presumably we can find $c$ and $a_1,a_2,\cdots,a_n$ such that $a_i-c^{n-i}\sum^{i}_{j=0}a_{n-j}\binom {n-j}{n-i}=0$ for as many values of $i$ as possible, but I'm not sure.
