If $f: \mathbb{N} \to \mathbb{N}$ and $\forall x \in \mathbb{N},\,(f \circ f )(x) = x^{4}$, is $f$ polynomial? 
If $f: \mathbb{N} \to \mathbb{N}$ and $\forall x \in \mathbb{N},\,(f \circ f )(x) = x^{4}$, is $f$ polynomial?

Of course if we forget about the first hypothesis and we take $f$ such as $\forall x \in \mathbb{R^*}, \, f(x)=\frac{1}{x}$ we have $\forall x \in \mathbb{R^*}, \, f(f(x))=x$ and $f$ isn't polynomial. But I don't see how this could help.
 A: The answer is no, there exist non-polynomial such $f.$
Let, $f(2^m)=3^{2m}$ and $f(3^{m})=2^{2m}$ and otherwise $f(n)=n^2.$
This is not a polynomials because $f(n)-n^2$ has infinitely many zeros but is not identically zero.
More generally, if $\sigma:P\to  P$ is an involution on the set $P$ of primes - that is, such that $\sigma\circ\sigma$ is the identity - then we can define:
$$f\left(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}
\right)=\sigma(p_1)^{2a_1}\cdots\sigma(p_k)^{2a_k}$$
This $f$ satisfies $f(ab)=f(a)f(b)$ for all $a,b.$
Indeed, it can be defined uniquely by defining $f(0)=0,f(1)=1,$ $f(p)=\sigma(p)^2$ for $p$ prime and $f(ah)=f(a)f(b)$ for all $a,b.$
It's not 100% obvious that this $f$ is not a polynomial, but if $\sigma(p)=p$ for some prime $p$ then $f(n)-n^2$ is zero for infinitely many $n,$ namely $n=p^k.$
There are uncountably many $\sigma,$ and thus uncountably many $f.$

Overkill
More generally, if $h:\mathbb N\to \mathbb N$ is a strictly increasing function such that $h(n)\geq n$ and there is an $a_1, a_2$ not in the image of $h$ such that $a_1<a_2<h(a_1)-1$
Define $a_{n+2}=h(h(a_n)).$
Define:
$$g(n)=\begin{cases}a_{k+1}&n=a_k\\
h(a_{k+1})&n=h(a_k)\\
h(n)&\text{otherwise}\end{cases}$$
There are infinitely many $n$ not in $(a_k)_k$ starting with $n_1=h(a_1)-1$ then $n_{k+1}=h(n_k).$
If $h(n)=n^2+1$ then we can take $a_1=6, a_2=7, n_0=8.$ More generally, if $h$ is a polynomial with positive integer coefficients and degree $2$ or greater, we can always find $a_1,a_2,n_0.$
We can also find non-polynomials with linear examples, under circumstances. For example, if $h(n)=2n$ we can choose $a_1=1, a_3=3.$ Then $g(2^k)=3\cdot 2^{k+1},g(3\cdot 2^k)=2^{k+1}$ and $g(n)=2n$ otherwise. Then $g(g(n))=4n$ for all $n.$
$h(n)=n+3$ can also be solved with $a_1=1,a_2=2.$ Then:
$$g(n)=\begin{cases}
n+4&n\equiv 1\pmod 3\\
n+2&n\equiv 2\pmod 3\\
n+3&n\equiv 0\pmod 3
\end{cases}$$
Then $g(g(n))=n+6$ for all $n.$
$h(n)=n+2$ can also be solved with $g(n)=n+2+(-1)^n.$
We can even solve $h(n)=n+1.$ Let $g(2n+1)=2n, g(2n)=2n+3.$ If $\mathbb N$ does not include $0$ we instead make it $g(2n-1)=2n+2$ and $g(2n)=2n-1.$ This is not a polynomial because $g(n)-2n$ is bounded and non-zero.
A: I believe the answer is no, because there's 'too much room' between proscribed values. Imagine taking the following function:
$$
\begin{equation*}
f(x)=\begin{cases}
y^4 & \exists y f(y)=x \\
\min(y: y\gt x \land \not\exists z\leq x: f(z)=y) & \text{otherwise}
\end{cases}
\end{equation*}
$$
So, for instance, $f(2)=3$ (because it's the first value $\gt 2$ that $f()$ hasn't taken on), $f(3)=16$ (since it 'has to be'), $f(4)=5$, $f(5)=64$, etc; we'll need to take $f(16)=81$ since that also 'has to be', but then we can easily take $f(81)=16^4=65536$, $f(65536)=81^4$ and so on. Because there are enough non-proscribed values to go around, there should always be a $y$ 'small enough' in the second case.
This isn't a formal proof of any of these assertions, but this is the direction I'd start looking.
