Is $f(x)$ necessarily a polynomial if $f(f(x))$ is?

If $g(x)$ is a polynomial, and $$g(x) = f(f(x))\ \forall x\in \mathbb{R}$$

is $f(x)$ necessarily a polynomial, given that $f$ is infinitely differentiable? Reading this question I noticed that the answer fails if we consider the domain to be the whole real line. I'm wondering whether removing the increasing condition allows for solutions that work across the whole real line, without allowing for "weird" functions like

$$f(x) = \left|x\right|^{\sqrt{2}}$$

hence the infinitely differentiable condition.

The only progress I've mad on this is as follows:

Assume $g(x)$ has degree $d$ and leading coefficient $a$. Thus

$$\lim_{x\to\infty} \frac{g(x)}{ax^d} = 1$$

$$\lim_{x\to\infty} \frac{f(f(x))}{ax^d} = 1$$

If

$$x^{k-\epsilon} << f(x) << x^{k+\epsilon}\ \forall\ \epsilon>0$$

for some $k$ (which I think has to hold), then

$$x^{k^2-\epsilon} << f(f(x)) << x^{k^2+\epsilon}$$

and thus $d=k^2$. I don't think this does much though. Does anyone have any ideas?

• @vadim123 That's not infinitely differentiable, it is? Commented Oct 12, 2016 at 2:35
• Also, if $g(x) = a x^d + \cdots + a_0$, then your first limit should be 1, not zero. Commented Oct 12, 2016 at 2:35
• @erfink Thanks - I just fixed it. Commented Oct 12, 2016 at 2:37
• Can you give what you're trying to show as an if -> then statement? Unclear what is supposed to be infinitely differentiable. Commented Oct 12, 2016 at 2:37
• @erfink Sorry - $f$ is supposed to be infinitely differentiable. I'm trying to prove that, given that $f$ is differentiable, then $f$ is a polynomial. Is it clearer now? Commented Oct 12, 2016 at 2:43

The answer is negative. Let $f$ be any involution on $\mathbb{R}$ i.e. any function whose graph is symmetric with respect to the line $y=x$. Then $g(x)=f(f(x)) = x$ is a polynomial, but not all involutions $f$ are polynomials.

• Can you please give an example or a proof that one exists? All you do is state that one exists without justifying it. Commented Oct 12, 2016 at 2:52
• The graph of $y=cos(x)$ is symmetric wrt $x=0$. Rotate it $\frac{\pi}{4}$ clockwise and it's straightforward to verify that the graph you get is that of a function $f$ which is symmetric wrt $y=x$ and obviously not a polynomial.
– dxiv
Commented Oct 12, 2016 at 2:56
• Thanks for giving an example! This makes a lot of sense now. Commented Oct 12, 2016 at 3:07
• That example doesn't quite work, since it will have vertical slope at some points and thus not be smooth. But it works if you use $y=\cos(x)/2$ instead. Commented Oct 12, 2016 at 3:09
• @EricWofsey Point taken, thanks. You are right of course.
– dxiv
Commented Oct 12, 2016 at 3:11

It is possible for $f(x)$ to not be a polynomial. For instance, let $\alpha:\mathbb{R}\to\mathbb{R}$ be a diffeomorphism, and define $f_\alpha=\alpha^{-1}\circ h\circ\alpha$ where $h(x)=-x$. These functions all satisfy $f_\alpha(f_\alpha(x))=x$, but they cannot be polynomials for every possible choice of $\alpha$. Indeed, notice that if $\alpha'=\alpha$ on both an interval $(a,b)$ and on the interval $\alpha^{-1}(h(\alpha(a)),h(\alpha(b)))$, then $f_\alpha=f_{\alpha'}$ on $(a,b)$. You can easily have two diffeomorphisms $\alpha$ and $\alpha'$ which agree in this way on two intervals, but which disagree elsewhere such that $f_\alpha$ and $f_{\alpha'}$ are not the same everywhere (since using bump functions, you can freely vary a diffeomorphism locally). It follows that $f_\alpha$ and $f_{\alpha'}$ cannot both be polynomials, since a polynomial is determined by its values on an interval.

To be more explicit, you could take $\alpha(x)=x$ and let $\alpha'(x)=x+\varphi(x)$ where $\varphi$ is a nonzero smooth function on $\mathbb{R}$ with compact support such that the derivative of $\varphi$ is always strictly between $-1$ and $1$. Then $f_\alpha(x)=-x$ for all $x$, and $f_{\alpha'}(x)=-x$ if $x$ and $-x$ are both not in the support of $\varphi$. But if $x$ is such that $\varphi(x)\neq 0$ then $f_{\alpha'}(x)=-x-\varphi(x)\neq -x$. Thus $f_{\alpha'}$ is not a polynomial.