Funciones primitivo-recursivas y ecuaciones polinomiales

Question

Estoy buscando ejemplos de funciones primitivas recursivas $f:\mathbb{N}\rightarrow\mathbb{N}$ que no se pueden escribir como un par de polinomios, es decir,

$$f(n) = m \Leftrightarrow P(n,m) = Q(n,m)$$

con $P(x,y), Q(x,y) \in \mathbb{Z}_+[x,y]$.

Nota que cuando una función diofantina

$$f(n) = m \Leftrightarrow (\exists k) P(n,m,k) = Q(n,m,k)$$

(que no es de la forma deseada) y $k$ está acotado – es decir, hay una función primitiva recursiva fija $K(n,m)$ con $P(n,m,k) = Q(n,m,k) \Rightarrow k < K(n,m)$ – uno puede escribir equivalentemente

$$f(n) = m \Leftrightarrow \prod_{i=0}^{K(n,m)}(P(n,m,i) - Q(n,m,i)) = 0$$

que es de la forma deseada. (¿Quizás incluso para funciones computables arbitrarias $K(n,m)$?)

Entonces la pregunta es: ¿Hay funciones primitivas recursivas con

$$f(n) = m \Leftrightarrow (\exists k) P(n,m,k) = Q(n,m,k)$$

donde la variable $k$ no está acotada?

Answer 1

Sea $f(n)=2^n$. Y supongamos que existe $R(x,y)=P(x,y)-Q(x,y)\in\mathbb Z[x,y]$ no nulo con $R(n,2^n)=0$ para todo $n\in\mathbb N$. Escribimos $R(x,y)=\sum_{k=0}^K R_k(x)y^k$ con $R_k\in\mathbb Z[x]$ y $R_K\ne 0$. Entonces existen $C, x_0$ con $|R_k(x)|x_0$ y todo $k$. Entonces para $x>x_0$, $y>1$, $$\left|\frac{R(x,y)-R_K(x)y^K}{y^K}\right|