Sets of integers represented by degree zero rational functions - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T07:57:17Z http://mathoverflow.net/feeds/question/120172 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120172/sets-of-integers-represented-by-degree-zero-rational-functions Sets of integers represented by degree zero rational functions Gjergji Zaimi 2013-01-29T02:54:13Z 2013-01-29T08:31:03Z <p>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.</p> <p>Which sets $S\subset \mathbb Z$ can be written as $S(f)$ for some $f$ as above?</p> <p>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$. </p> <p>This question is just a musing from playing around with variations to <a href="http://en.wikipedia.org/wiki/Hilbert%27s_tenth_problem" rel="nofollow">Hilbert's tenth problem</a>. A more direct question would be: Is every <a href="http://en.wikipedia.org/wiki/Diophantine_set" rel="nofollow">Diophantine set</a> representable as some $S(f)$?</p> http://mathoverflow.net/questions/120172/sets-of-integers-represented-by-degree-zero-rational-functions/120179#120179 Answer by SJR for Sets of integers represented by degree zero rational functions SJR 2013-01-29T06:45:20Z 2013-01-29T08:31:03Z <p>A set $T \subseteq \mathbb{Z}$ can be written as $S(f)$ if and only if $T$ is effectively enumerable.</p> <p>Proof: As in zeb's comment, the restriction to degree zero doesn't matter, and we consider rational functions of arbitrary degree.</p> <p>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)$.</p> <p>Conversely, it is intuitively clear that every set of the form $S(r)$, with $r$ a rational function, is effectively enumerable.</p>