For real univariate polynomials $f, g$, $f \circ f \circ f = g \circ g \circ g \implies f = g$? Firstly $f \circ f = g \circ g$ has many counterexamples such as involutions. Also in case of  $f \circ f \circ f = g \circ g \circ g$ with $f, g \in \mathbb{C}[x]$ there is an evident counterexample: $f(x) = x, g(x) = \omega x$ where $\omega$ is any complex cube root of unity. I made the following observations:


*

*$\deg f = \deg g$

*The leading term of $f$ and $g$ must be equal.

*The term before the leading term has same coefficient. Let $\deg f = \deg g = n$. The $(n^3 - 1)$-degree terms of $f \circ f \circ f$ and $g \circ g \circ g$ can only be produced by multiplying $(n - 1)$ $n^2$-degree terms and one $n^2 - 1$ terms of $f \circ f$ and $g \circ g$, respectively, where the $(n^2 - 1)$-degree terms of $f \circ f$ and $g \circ g$ can be only produced by multiplying $n - 1$ $n$-degree terms and one $(n - 1)$-degree term of $f$ and $g$, respectively. Since the $n^2$-degree terms and $n$-degree terms are equal by 2, $(n - 1)$-degree terms of $f$ and $g$ must be also equal. Namely, let $f(x) = a_nx^n + a_{n - 1}x^{n - 1} + \ldots$ then $f(f(x)) = a_n^{n + 1}x^{n^2} + na_n^na_{n - 1}x^{n^2 - 1} + \ldots$, finally $f(f(f(x))) = a_n^{n^2 + n + 1}x^{n^3} + n^2a_n^{n^2 + n}a_{n - 1}x^{n^3 - 1} + \ldots$ Induction like this may lead to the solution for the problem.

*If $a$ is a fixed point, possibly complex, of $f$, then $a$ is a fixed point of $g \circ g \circ g$. Thus the orbit of $a$ with respect to $g$ has a period of $1$ or $3$. Proving that the period is always $1$ will ensure that $f(x) - x$ and $g(x) - x$ have the same roots up to multiplicity of roots.

*Since $f'(x)f'(f(x))f'(f(f(x))) = g'(x)g'(g(x))g'(g(g(x)))$ there are some relations between the critical points of $f$ and $g$.

*For arbitrary affine polynomials $\lambda$ the conjugates $\lambda \circ f \circ \lambda^{-1}, \lambda \circ g \circ \lambda^{-1}$ also satisfies the condition.

*The case when $f, g$ is constant or affine is trivial. For $f, g$ quadratic, it is enough to consider when $f$ and $g$ is monic by 2 and 6. Let
$$p = \arg \min f(x), q = \arg \min g(x), r = \min f(x), s = \min g(x)$$
If $p \ne q$ and $r \ne s$, WLOG $r < s$, with conjugation by $\lambda = x \mapsto x - r$ we can assume that $r = 0$. Assume that $p < 0$. Since $g'(q) = 0$ $f'(q)f'(f(q))f'(f(f(q)) = 0$. Then $p = q$ or $f(q) = p$ or $f(f(q)) = p$ but $p \ne q$ so $p \in \operatorname{ran} f$, which is a contradiction. Thus $p \ge 0$. Then $[p, \infty) \subset \operatorname{ran} f$, so $\operatorname{ran} f \supset f(\operatorname{ran} f) \supset f([p, \infty)) = \operatorname{ran} f$. Thus $\operatorname{ran} f \circ f \circ f = f(f(\operatorname{ran} f)) = f(\operatorname{ran} f) = \operatorname{ran} f \supsetneq \operatorname{ran} g \supset \operatorname{ran} g \circ g \circ g$ which is a contradiction. Thus $p = q$ or $r = s$.


*

*If $p = q$, with conjugation by $\lambda = x \mapsto x - p$ we only have to consider when $f(x) = x^2 + a$ and $g(x) = x^2 + b$. But in $((x^2 + a)^2 + a)^2 + a$ the sextic term is $4ax^6$ thus $f = g$.

*If $r = s$, $f(x) = (x - p)^2$ and $g(x) = (x - q)^2$. But in $(((x - p)^2 - p)^2 - p)^2$ the septic term is $-8px^7$ thus $f = g$.



Are there any ideas to solve this problem? Or if there is a counterexample, how strong should be the restrictions to $f, g$ so that the statement holds?
 A: Proposition 1. Let $n,m\ge1$.
Let $$\begin{align}p(x)&=x^n+a_1x^{n-1}+\ldots+a_n,\\\tilde p(x)&=x^n+\tilde a_1x^{n-1}+\ldots+\tilde a_n,\\ q(x)&=x^m+b_1x^{m-1}+\ldots +b_m,\\\tilde q(x)&=x^m+\tilde b_1x^{m-1}+\ldots +\tilde b_m\end{align}$$ be polonomials with $p\circ q=\tilde p\circ \tilde q$. Then  $q-\tilde q$ is constant.
Proof. The behaviour near $\infty$ tells us about the higher coefficients of $q$.
More precisely,  we have
$$\tag1p(q(z))=q(z)^n+ O(z^{nm-m})$$
so that we can read off the highest coefficients of 
$$q(z)^n=z^{nm}+c_1z^{nm-1}+c_2z^{nm-2}+\ldots$$
where
$$c_k=nb_k+(\text{polynomial in }b_1,\ldots, b_{k-1}).$$
Now from $c_1,\ldots, c_{m-1}$, we can determine one by one the coefficients $b_1,\ldots, b_{m-1}$, and of course obtain the same result when we use the same method to obtain $\tilde b_1,\ldots,\tilde b_{m-1}$. $\square$
Note that we cannot expect more since in we can always replace $q(x)$ with $q(x)+\delta$ and $p(x)$ with $p(x-\delta)$.
Proposition 2. In the situation of proposition 1, assume additionally $a_1=\tilde a_1$. Then $q=\tilde q$.
Proof.
We can strengthen $(1)$ to
$$\tag2
p(q(z))=q(z)^n+a_1q(z)^{n-1}+O(z^{nm-2m}). $$
The coefficient of $z^{nm-m}$ is
$$ a_1+nb_m+(\text{polynomial in }b_1,\ldots, b_{m-1})$$
and allows us to also determine $b_m$. $\square$.

Now assume that $f,g$ are univariate polynomials with $(f^{\circ r}=g^{\circ r}$ for some $r\ge 2$. 
Then from $\deg(f^{\circ r})=(\deg f)^r$ and same for $g$, we conclude $\deg f=\deg g=:m$. 
If $m=1$, we have $(x+c)^{\circ r}=x+rc$ and so $f=g$ is immediate. Assume therefore that $m\ge2$.
Apply  proposition 1 to $n:=m^{r-1}$, $p=f^{\circ (r-1)}$, $q=f$, $\tilde   p=g^{\circ (r-1)}$, $\tilde q=g$, to find that $f-g=\text{const}$. In particular, we know enough of $f$ to use proposition 2 and conclude $f=g$.
A: I don't have a solution (yet), but I can show that the derivatives $f'$ and $g'$ have the same sign.
Suppose $f$ is strictly monotone on an interval $[a, b]$. Then $f \circ f \circ f = g \circ g \circ g$ is also strictly monotone on $[a, b]$. This implies $g \circ g \circ g$ is injective, which in turn implies $g$ must be injective (if $h$ is a left-inverse of $g \circ g \circ g$, then $h \circ h \circ h \circ g \circ g$ is a left-inverse of $g$). Since $g$ is injective, $g$ too must be strictly monotone.
Moreover, it's not difficult to verify that $g$ is monotone increasing if and only if $g \circ g \circ g$ is monotone increasing, i.e. $g$ and $g \circ g \circ g$ have the same monotonicity. The same can therefore be said of $g$ and $f$.
This means that
$$f'(x) > 0 \iff g'(x) > 0 \text{ and } f'(x) < 0 \iff g'(x) < 0.$$
EDIT: Actually, this is not quite true. I'm implicitly assuming that the derivative has no repeated roots, and so each root of the derivative is accompanied by a sign change.
