$P,Q$ are polynomials with real coefficients and for every real $x$ satisfy $P(P(P(x)))=Q(Q(Q(x)))$. Prove that $P=Q$

Question

$P,Q$ are polynomials with real coefficients and for every real $x$ satisfy $P(P(P(x)))=Q(Q(Q(x)))$. Prove that $P=Q$.

I see only that these polynomials are same degree

Answer 1

It is easy to see that $P$ and $Q$ have the same leading term. Without loss of generality, assume that both are monic. Note that $P$ and $Q$ also have the same constant term. (Note: as zhw has pointed out, this part is not so obvious. I'll try to update with an argument shortly.)

Suppose that $P\neq Q$. Since $P-Q$ is not a constant, it is unbounded. Without loss of generality, there is some $t$ such that $P$ and $Q$ are strictly increasing on $[t,\infty)$, and, for all $a\geq t$, we have $P(a)>Q(a)\geq a$.

Then we have $P(P(P(t))) > P(P(Q(t)) > P(Q(Q(t))) > Q(Q(Q(t)))$, a contradiction.

Answer 2

Since one easily messes things up when starting from highest coefficients downward (as I did in my first revision of this answer), we shall consider the function $f(z)=\frac1{P(z^{-1})}$, which allows us nicer acccess to the high coefficients of $P$. As a matter of notation, write $$f^{\circ k}:=\underbrace{f\circ\ldots\circ f}_{k}$$ for function iteration.

Lemma. Let $n,m,k\in\mathbb N$, $m> k\ge 2$. Let $f$ be holomorphic around $0$ with $f(0)\ne0$. Then there exist $M$ with $k^n<M<k^n(m-k+1)$ and $\alpha\in\mathbb C$ with $\alpha\ne 0$ such that for any $h$ holomorphic around $0$, we have $$(z^kf+z^mh)^{\circ n}=(z^kf)^{\circ n}+\alpha h(0)z^M+O(z^{M+1}).$$ Proof. First observe (e.g., by induction on $n$) that $(z^kf)^{\circ n}$ has a root of order exactly $k^n$ at $z=0$, and $((z^kf)^{\circ n})^r$ has a root of order exactly $ k^nr$ at $z=0$, say $$\tag1((z^kf)^{\circ n})^r=c_{n,r}z^{k^nr}+O(z^{k^nr})$$ with $c_{n,r}\ne0$ depending only on $f,k,n,r$ (but we consider $f,k$ fixed).

Now we show the claim of the lemma by induction on $n$. The claim is clear for $n=1$ with $\alpha=1$ and $M=m$ (which is $<k^1(m-k+1)$!). Assume that the claim holds for $n$. For any $r\ge 1$, we have $$\tag1\begin{align}\left( (z^kf+z^mh)^{\circ n}\right)^r&=\left((z^kf)^{\circ n}+\alpha h(0)z^M+O(z^{M+1})\right)^r\\ &=((z^kf)^{\circ n})^r+r\cdot ((z^kf)^{\circ n})^{r-1}\alpha h(0)z^M+O(z^{k^n(r-1)+M+1}).\end{align}$$ Let $f(z)=a_0+a_1z+a_2z^2+\ldots$. Then summing $(1)$ using these coefficients we get $$\begin{align}((z^kf+z^mh)^{\circ n}) &=(z^kf+z^mh)\circ ((z^kf+z^mh)^{\circ n}) \\&=\sum_r a_r(z^kf^{\circ n})^{r+k}+\sum_r a_r(r+k)((z^kf)^{\circ n})^{r+k-1}\alpha h(0)z^M\\ &\quad+h(0)((z^kf)^{\circ n})^m+h(0)m((z^kf)^{\circ n})^{m-1}\alpha h(0)z^M\\&\quad+O(z^{k^n(\min\{m,k\}-1)+M+1})\end{align}$$ Now the first sum is just $(z^kf)^{\circ(n+1)}$. The second sum is $$a_0kc_{n,k-1}\alpha h(0)z^{k^n(k-1)+M}+O(z^{k^n(k-1)+M+1}).$$ The third summand is $$h(0)z^{k^nm}+O(z^{k^nm+1})=O(z^{k^n(k-1)+M+1}) $$ because $M<k^n(m-k+1) $. The fourth summand is $$h(0)^2m\alpha z^{k^n(m-1)+M}+O(z^{k^n(m-1)+M+1}) =O(z^{k^n(k-1)+M+1})$$ because $m>k$. Thus with $M':=k^n(k-1)+M$ (which is $>k^n(k-1)+k^n=k^{n+1}$ and $<k^n(k-1)+k^n(m-k+1)=k^nm\le k^{n+1}(m-k+1)$) we have $$(z^kf+z^mh)^{\circ (n+1)}=(z^kf)^{\circ(n+1)}+\alpha'h(0)z^{M'}+O(z^{M'+1}) $$ where $\alpha'=a_0kc_{n,k-1}\alpha\ne 0$. This shows that the claim also holds for $n+1$. $_\square$

Corollary. Let $n,k\in\mathbb N$, $k\ge2$. Let $f,g$ be holomorphic around $0$ with a root of order exactly $k$ at $z=0$. Then $f^{\circ n}=g^{\circ n}$ implies $f=g$.

Proof. Note that we can write $f(z)=z^kf_0(z)$ and $g(z)=z^kf_0(z)+z^mh(z)$ with $m>k\ge 2$. $_\square$

Proposition. Let $P,Q$ be polynomials such that $P(P(P(x)))=Q(Q(Q(x)))$ for all $x\in\mathbb R$. Then $P=Q$.

Proof. By the condition, the polynomials $P^{\circ 3}$ and $Q^{\circ 3}$ are the same. If $P(x)=a_nx^n+\ldots$, then $P^{\circ 3}(x) = a_n^{n^2+n+1}x^{n^3}+\ldots$. We conclude that we can read $\deg P$ from $P^{\circ 3}$, namely $\deg P=\sqrt[3]{\deg P^{\circ 3}}$, and we also obtain $a_n$ because $n^2+n+1$ is odd and odd powers are bijective maps $\mathbb R\to\mathbb R$. Hence $P,Q$ have the same degree and the same leading coefficient.

In the case $n=0$, we are already done.

In the case $n=1$, say $P(x)=ax+b$, $Q(x)=ax+c$, we have $P(P(P(x)))=a^3x+(a^2+a+1)b$ and $Q(Q(Q(x)))=a^3x+(a^2+a+1)c$. Since for $a\in\mathbb R$ we have $a^2+a+1=(a+\frac12)^2+\frac34>0$, we conclude $b=c$, i.e., $P=Q$ also in this case.

In the case $n\ge 2$, we can consider $f(z)=\frac1{P(z^{-1})}$ and $g(z)=\frac1{Q(z^{-1})}$, which match the conditions of the corollary as both are $\frac1{a_n}z^n+O(z^{n+1})$. $_\square$

Answer 3

Slade, I had the same approach but I'm not sure how you got the constant terms equal so quickly. But if the degree is $1$ that part is easy and you're done. Otherwise, if $p\ne q,$ then $|p_2(x)-q_2(x)|$ blasts off to $\infty$ as $x\to \infty.$ Because the leading coefficients of $p$ and $q$ agree, this would imply $|p_3(x)-q_3(x)|\to \infty,$ contradiction.