Rational functions from integers to integers

Question

A polynomial with integer coefficients maps integers to integers. A rational function (which is a quotient of two polynomials) tends to map integers to rational numbers. Other than the trivial case where the denominator is a factor of the numerator, are there any rational functions that map all integers to integers? What is known about them and how can they be found?

Answer 1

Let $r(z) = \frac{p(z)}{q(z)}$ such that $r:\mathbb{Z}\rightarrow\mathbb{Z}$ and $p,q$ polynomials. Then $q(z)|p(z)$ for all $z \in \mathbb{Z}$ and $\deg p \geq \deg q$ (check what happens at $\infty$).

You can check here, for example, how the division between polynomials over a commutative ring (like $\mathbb{Z}$) works.

So if $q$ is monic, then you can divide the polynomials, so $p(z)=f(z)q(z)+g(z)$ with $f,g$ polynomials and $\deg g < \deg q$. Then if $g \not \equiv 0$, $r(z)=f(z)+\frac{g(z)}{q(z)}$, so $\frac{g(z)}{q(z)}$ is also an "integer" rational function, which is absurd. So $g\equiv0$ and $r$ is a integer polynomial.

If $q$ is non-monic, you can apply the theorem of the linked answer: call $q_0$ the leading coefficient of $q$, then $q_0^kp(z) = f(z)q(z) + g(z)$. Consider the integer rational function $q_0^kr(z) = \frac{q_0^kp(z)}{q(z)} = f(z)+ \frac{g(z)}{q(z)}$. As above, this implies that $g(z) \equiv 0$. So $r(z)=\frac{p(z)}{q(z)}=\frac{q_0^kp(z)}{q_0^kq(z)}=\frac{f(z)q(z)}{q_0^kq(z)}=\frac{f(z)}{q_0^k}$. Then again $r$ is a polynomial, possibly with rational coefficients ($f$ is a integer polynomial, but might not be divisible by $q_0^k$).

Answer 2

I started writing this up while trying to make sure I understood dcolazin's answer. I might as well post this as a separate complete answer. (I include more details on behaviour at $\infty$, and less on monicity.)

---

Let $r(x)=\frac{p(x)}{q(x)}$ be a rational expression, where $p(x),q(x)\in\mathbb Q[x]$ are polynomials with rational coefficients, and assume $r(n)\in\mathbb Z$ for all $n\in\mathbb Z$.

By polynomial division, write $p(x)=f(x)q(x)+g(x)$ where $f$ and $g$ are polynomials and $\deg g<\deg q$. Then we have $r(x)=f(x)+\frac{g(x)}{q(x)}$. Write $f(x)=\frac{F(x)}{d}$ where $d$ is a common denominator of the coefficients of $f$, so $F$ has integer coefficients. Now

$$\frac{g(x)}{q(x)}=\frac{d\,r(x)-F(x)}{d}$$

where the numerator is integer-valued (when $x$ is an integer), so the whole expression has discrete values, as integer multiples of $\tfrac1d$.

Since $\deg g<\deg q$, the rational expression $\tfrac{g(x)}{q(x)}$ has limit $0$ as $x\to\infty$. In particular, $\left|\tfrac{g(n)}{q(n)}\right|$ is less than $\tfrac1d$ and therefore is exactly $0$, for any large enough $n\in\mathbb Z$.

We have $g(n)=0$ for infinitely many values of $n$, and therefore $g(x)=0$ as a polynomial (since any non-zero polynomial has finitely many roots). Thus $r(x)=f(x)$ is a polynomial.

Much is known about integer-valued polynomials. By considering finite differences, any such polynomial can be written in the form $r(x)=\sum_ka_k\binom xk$ with integer coefficients $a_k$.

---

I would like to extend this to $p(x),q(x)\in\mathbb F[x]$, where $\mathbb F$ is an arbitrary field containing $\mathbb Q$. But then we can't take limits, and we can't get a common denominator for $f$.