# 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:

1. $$\deg f = \deg g$$
2. The leading term of $$f$$ and $$g$$ must be equal.
3. 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.
4. 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.
5. 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$$.
6. For arbitrary affine polynomials $$\lambda$$ the conjugates $$\lambda \circ f \circ \lambda^{-1}, \lambda \circ g \circ \lambda^{-1}$$ also satisfies the condition.
7. 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$$.
1. 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$$.
2. 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?

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$$.

• Assumption that $f, g$ is monic is just for nice equations. Right? Also based on your proof, I think this can be generalized to any iteration with an additional constraint: the sign of the leading coefficients are equal. – Ris Feb 9 at 11:26

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.

• Why is $f\circ f\circ f$ strictly monotone? Are you assuming that $f$ maps $[a,b]$ into $[a,b]$? – user1551 Feb 9 at 10:19
• @user1551 Ugh, you're right. – user744868 Feb 9 at 10:20