# Polynomial in $\mathbb{Q}[x]$ sending integers to integers?

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the coefficients of $f$ are integers with respect to the basis $\{\binom{x}{k}\mid k\in\mathbb{N}\}$?

The reverse direction seems clear, so I wonder why the opposite implication is also true. I did notice that all the roots of $\binom{x}{k}$ are just $0,\dots,k-1$. Can we factor the polynomial is some nice way to reveal the opposite conclusion? Thanks.

-
possible duplicate of [Property of a polynomial $f\in\mathbb{Q}$X$$ such that $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$?](math.stackexchange.com/questions/91625/…) –  lhf Feb 12 '12 at 1:56
The key word here is finite differences. See Newton series. –  lhf Feb 12 '12 at 1:58

This is a special case of a classical result of Polya and Ostrowski (1920): $f(x) \in \mathbb Q[x]$ is an integer valued polynomial, i.e. $f(\mathbb Z)\subset \mathbb Z\:,\:$ iff $f(x)$ is an integral linear combination of binomial coefficients ${x\choose k},\:$ for $\: k\le \deg f$. For a proof see e.g. Polya And Szego, Problems and theorems in analysis, vol II, Problem 85 p. 129 and its solution on p. 320.

For example

$$\rm\displaystyle\ \ \frac{n^3+5\:n}6\ =\ \frac{n^3-n + 6\:n}6\ =\ \frac{(n+1)\:n\:(n-1)}6 + \:n\ =\ {n+1\choose 3} + {n\choose 1}$$

This has been extended to much more general rings (e.g. Dedekind domains) by Cahen at al.

-
Thanks for the reference! –  Jakucha Feb 11 '12 at 23:02
This result also appears in LeVeque's Fundamentals of Number Theory, section 3.4, exercise 14. –  lhf Feb 12 '12 at 23:35

The idea is simple ; given a polynomial $f \in \mathbb Q[x]$ of degree $m$, we can reduce the degree of $f$ and use induction as in the following :

If a polynomial of degree $0$ is integer-valued, then we can write it as $f(x) = a \in \mathbb Z$ and thus $f(x) = a \begin{pmatrix} x \\\ 0 \end{pmatrix}$ so for $m=0$ we are doing just fine.

Assuming all polynomials of degree $<m$ can be written as such combinations of binomial coefficients, let $f(x) \in \mathbb Q[x]$ be such a polynomial of degree $m$. Then $f(x) = (a_m/b_m) x^m + \sum_{i=0}^{m-1} (a_i/b_i) x^i$. Since $b_m f(x) - a_m m! \begin{pmatrix} x \\\ m \end{pmatrix}$ is also integer valued by assumption, and its degree is at most $m-1$, it can be expressed as $$b_m f(x) - a_m m! \begin{pmatrix} x \\\ m \end{pmatrix} = \sum_{j=0}^{m-1} c_j \begin{pmatrix} x \\\ j \end{pmatrix}, \qquad c_j \in \mathbb Z$$ without excluding the case where $c_j = 0$ for $0 \le j \le m-1$ (in this case the degree of $b_m f(x) - a_m m!$ is either not defined or $-\infty$ depending on which convention you like, but either way things work out nicely), which means $$f(x) = \frac{a_m}{b_m} m! \begin{pmatrix} x \\\ m \end{pmatrix} + \frac{\sum_{j=0}^{m-1} c_j \begin{pmatrix} x \\\ j \end{pmatrix}}{b_m}, \qquad c_j \in \mathbb Z$$ Here by computing $f(0)$, $f(1)$, $\dots$, $f(m)$, one can see that this expression is an integer-linear-combination of the binomial coefficients. For instance, $f(0) = c_0 / b_m$, hence $b_m$ divides $c_0$. Then $f(1) = c_1/ b_m + c_0/b_m$, so that $c_1 /b_m$ is an integer, hence $b_m$ divides $c_1$. Going on like this, $$f(k) = \sum_{j=0}^k \frac {c_j}{b_m} \begin{pmatrix} k \\\ j \end{pmatrix}$$ and since the first $k$ terms of the sum are integers, $c_k/b_m$ must also be an integer thus $b_m$ divides $c_k$. By computing $f(m)$ this process stops. In other words, $f(x)$ is expressible as desired. The result follows by induction.

Hope that helps,

-
The idea between the lines is that the integer-valued coefficients form a $\mathbb Z$-module for which the binomial coefficient polynomials form a basis. I implicitly used the basis part to expect unicity and thus reducing the degree by removing one component allowed me to use induction. –  Patrick Da Silva Feb 11 '12 at 23:43
Since you already know that the $\binom Xn$ for $n\in\Bbb N$ form a $\Bbb Q$-basis of $\Bbb Q[X]$ (and indeed this is easy to see), the rest of the argument is trivial. Let $P=\sum_nc_n\binom Xn\in\Bbb Q[X]$ be arbitrary, then the value of $P$ at $m\in\Bbb N$ is $c_m+\sum_{i<n}c_i\binom mi$, which must be an integer. Now by immediate induction on $m$, all the coefficients $c_m$ are integer.