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?
 A: 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.
A: 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.
