Sets of integers represented by degree zero rational functions

2013-01-29T02:54:13Z

Suppose $f(x_1,x_2,\dots)=\frac{P}{Q}$, where $P,Q$ are polynomials in several variables with integer coefficients that have the same degree. Let's denote by $S(f)$ the set of integers $n$ for which $f(x_1,x_2,\dots)=n$ is solvable in integers.

Which sets $S\subset \mathbb Z$ can be written as $S(f)$ for some $f$ as above?

For example we have, $S(\frac{x_1^2+x_2^2}{x_1x_2+1})=\lbrace -5,0,1,4,\dots,k^2,\dots\rbrace$.

This question is just a musing from playing around with variations to Hilbert's tenth problem. A more direct question would be: Is every Diophantine set representable as some $S(f)$?

Answer by SJR for Sets of integers represented by degree zero rational functions

2013-01-29T06:45:20Z

A set $T \subseteq \mathbb{Z}$ can be written as $S(f)$ if and only if $T$ is effectively enumerable.

Proof: As in zeb's comment, the restriction to degree zero doesn't matter, and we consider rational functions of arbitrary degree.

Suppose $T$ is effectively enumerable. By the MRDP theorem choose a polynomial $f(\bar{z},x)$ such that $T$ is precisely all $x$ for which the equation $f(\bar{z},x)=0$ is solvable in integers $\bar{z}$. Then the rational function \begin{equation*} r(\bar{z},x):=x+\dfrac{f(\bar{z},x)^2}{1+f(\bar{z},x)^2} \end{equation*} has the value $x$ if $f(\bar{z},x)=0$, and otherwise is not an integer. Therefore $T=S(r)$.

Conversely, it is intuitively clear that every set of the form $S(r)$, with $r$ a rational function, is effectively enumerable.

Sets of integers represented by degree zero rational functions - MathOverflow

Sets of integers represented by degree zero rational functions

Answer by SJR for Sets of integers represented by degree zero rational functions