# Is there an example of a rational polynomial that has integer output for all integer inputs that are sufficiently large?

Is there an example of a rational polynomial $f(n)\in \mathbb{Q}[t]$ that has integer output for all integer inputs that are sufficiently large, but not for, say, inputs $n=1,2,3,\dots,n$?

-

No. If $f$ has degree $d$, you can reconstruct $f(n-1)$ from $f(n), \ldots, f(n+d)$ by taking repeated differences and adding again.

-
So a rational polynomial that has integer outputs for sufficiently high integer inputs must in fact have integer outputs for ALL integer inputs? –  Helmut Oct 16 '12 at 13:33
Yes. For example a quadratic polynomial with $f(10)=a$, $f(11)=b$, $f(12)=c$ integers will have first differences $b-a, c-b$ and second difference $c-2b+a$; hence the first differences continue to the left with $b-a-(c-2b+a)=-2a+3b-c$, thus $f(9)=a-(-2a+3b-c)=3a-3b+c$. –  Hagen von Eitzen Oct 16 '12 at 22:19

Any $P\in\mathbb Q[X]$ whose evaluations at all $n \in\Bbb N$ are in $\Bbb Z$ are integer linear combinations of the rational polynomials $\binom Xd$ with $d \in\Bbb N$: the coefficient of $\tbinom X0=1$ is the evaluation $P$ at $0$; subtracting off that (constant) term, the coefficient of $\tbinom X1=X$ is the evaluation at $1$ of the remainder; subtracting off that (linear) term, the coefficient of $\tbinom X2=\frac{X^2-X}2$ is the evaluation at $2$ of the remainder; and so forth. The remainder ultimately becomes $0$ when the coefficient of $\binom Xd$ is taken into account where $d=\deg P$, as we have subtracted off a polynomial $Q$ of degree $d$ whose evaluations in $0,1,\ldots,d$ coincide with those of $P$, which forces $P=Q$.

Now the rational polynomials $\tbinom Xd$ take integer values at all $n\in\Bbb Z$, and therefore so will $P$. If for some $P'\in\mathbb Q[X]$ the evaluations at all integers${}\geq n_0$ are in $\Bbb Z$, then consider $P=P'[X:=X+n_0]$ (substitute $X+n_0$ for $X$), now $P$ has integer evaluations at all $n \in\Bbb N$, and the above applies, so $P'$ has integer evaluations at all $n \in\Bbb Z$.

To make the link with answer by Hagen von Eitzen, this argument only needs the integrality at $\deg P+1$ successive values, which forces all evaluations to be integer.

-

No.

Suppose $f$ is a polynomial in $\mathbb{Q}[x]$ outputting integers for sufficiently large integer inputs. Then I claim $f$ can be written $$\sum_{i = 0}^n a_i {x \choose i}$$ where $${x \choose i} = \frac{x(x-1)\ldots(x-i+1)}{i!}$$ and the $a_i$ are integers; note that this expression is $1$ when $i = 0$ (because the numerator is the empty product). This claim then proves your result, since clearly anything that can be written this way has your property.

The proof: Clearly we can write $f$ this way for some rational numbers $a_i$. We will recover the $a_i$ and then argue that they must be integers. If $g$ is a polynomial, set $$\Delta g = g(x+1) - g(x).$$ We compute (just by writing it out) that $$\Delta {x \choose i} = {x \choose i -1}$$ for $i > 0$ and clearly $\Delta {x \choose 0} = 0$.

Since $\Delta$ is linear, it follows that \begin{align*} a_0 =& f(0) & \\ a_1 =& (\Delta f)(0)\\ a_2 =& (\Delta^{(2)} f)(0)\\ \ldots \\ a_n =& (\Delta^{(n)}f)(0)\\ \end{align*}

With these formulas and induction on the degree of $f$, we have that all of the coefficients but $a_0$ must be integers (because the polynomials $\Delta^{(i)}(f)$ have smaller degree, they must evaluate to integers on all integers). But then $a_0$ must be an integer as well, since when you plug in a large number you will get an integer plus $a_0$.

-
I don't see how you argue that $a_1=(\Delta f)(0)=f(1)-f(0)$ must be integer. –  Marc van Leeuwen Oct 16 '12 at 14:19
$\Delta(f)$ is a polynomial of strictly smaller degree than $f$ which takes integer values for all sufficiently large integers, so it follows from the inductive hypothesis on the degree. –  user29743 Oct 16 '12 at 17:38