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.
0 votos
¿Cuál es el origen de este problema?
3 votos
@StevenStadnicki Mi cerebro ;)
0 votos
¿Qué tiene de interesante esta pregunta?
0 votos
Para que quede claro, ¿estás preguntando si una función que satisfaga estas propiedades será siempre polinómica, o simplemente estás buscando un polinomio que satisfaga estas propiedades?
0 votos
@cosmo5 Quizás el hecho de que no sea obvio probar...
2 votos
@A.E.Rosas Claramente, preguntando por si el único $f$ son polinómicas.
0 votos
@ThomasAndrews gracias por la aclaración.