Si $f: \mathbb{N} \to \mathbb{N}$ y $\forall x \in \mathbb{N},\,(f \circ f )(x) = x^{4}$ es $f$ ¿polinomio?

Question

Si $f: \mathbb{N} \to \mathbb{N}$ y $\forall x \in \mathbb{N},\,(f \circ f )(x) = x^{4}$ es $f$ ¿polinomio?

Por supuesto, si nos olvidamos de la primera hipótesis y tomamos $f$ como $\forall x \in \mathbb{R^*}, \, f(x)=\frac{1}{x}$ tenemos $\forall x \in \mathbb{R^*}, \, f(f(x))=x$ y $f$ no es polinómico. Pero no veo cómo esto podría ayudar.

Answer 1

La respuesta es no, existen tales $f.$

Déjalo, $f(2^m)=3^{2m}$ y $f(3^{m})=2^{2m}$ y en caso contrario $f(n)=n^2.$

Esto no es un polinomio porque $f(n)-n^2$ tiene infinitos ceros pero no es idénticamente cero.

En términos más generales, si $\sigma:P\to P$ es una involución sobre el conjunto $P$ de primos, es decir, tal que $\sigma\circ\sigma$ es la identidad - entonces podemos definir:

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

Este $f$ satisface $f(ab)=f(a)f(b)$ para todos $a,b.$

De hecho, puede definirse unívocamente definiendo $f(0)=0,f(1)=1,$ $f(p)=\sigma(p)^2$ para $p$ primo y $f(ah)=f(a)f(b)$ para todos $a,b.$

No es 100% obvio que este $f$ no es un polinomio, pero si $\sigma(p)=p$ para algún primo $p$ entonces $f(n)-n^2$ es cero para infinitos $n,$ a saber $n=p^k.$

Hay muchísimos $\sigma,$ y así incontables $f.$

---

Overkill

En términos más generales, si $h:\mathbb N\to \mathbb N$ es una función estrictamente creciente tal que $h(n)\geq n$ y hay un $a_1, a_2$ no a imagen de $h$ tal que $a_1<a_2<h(a_1)-1$

Defina $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}$$

Hay infinitos $n$ no en $(a_k)_k$ empezando por $n_1=h(a_1)-1$ entonces $n_{k+1}=h(n_k).$

Si $h(n)=n^2+1$ entonces podemos tomar $a_1=6, a_2=7, n_0=8.$ En términos más generales, si $h$ es un polinomio con coeficientes enteros positivos y grado $2$ o mayor, siempre podemos encontrar $a_1,a_2,n_0.$

También podemos encontrar no polinomios con ejemplos lineales, en determinadas circunstancias. Por ejemplo, si $h(n)=2n$ podemos elegir $a_1=1, a_3=3.$ Entonces $g(2^k)=3\cdot 2^{k+1},g(3\cdot 2^k)=2^{k+1}$ y $g(n)=2n$ de lo contrario. Entonces $g(g(n))=4n$ para todos $n.$

$h(n)=n+3$ también puede resolverse con $a_1=1,a_2=2.$ Entonces:

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

Entonces $g(g(n))=n+6$ para todos $n.$

$h(n)=n+2$ también puede resolverse con $g(n)=n+2+(-1)^n.$

Incluso podemos resolver $h(n)=n+1.$ Sea $g(2n+1)=2n, g(2n)=2n+3.$ Si $\mathbb N$ no incluye $0$ en su lugar lo hacemos $g(2n-1)=2n+2$ y $g(2n)=2n-1.$ No es un polinomio porque $g(n)-2n$ está acotada y es distinta de cero.

Answer 2

I cree la respuesta es no, porque hay "demasiado espacio" entre los valores proscritos. Imagina que tomas la siguiente función: $$\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*}$$

Así, por ejemplo, $f(2)=3$ (porque es el primer valor $\gt 2$ que $f()$ no ha asumido), $f(3)=16$ (ya que "tiene que ser"), $f(4)=5$ , $f(5)=64$ etc; tendremos que tomar $f(16)=81$ ya que eso también "tiene que ser", pero entonces podemos tomar fácilmente $f(81)=16^4=65536$ , $f(65536)=81^4$ etc. Como hay suficientes valores no prescritos para todos, hay debe ser siempre un $y$ suficientemente pequeño" en el segundo caso.

Esto no es una prueba formal de ninguna de estas afirmaciones, pero es la dirección en la que yo empezaría a buscar.