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

Solution 1:

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.

Solution 2:

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.