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

Solution 1:

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.

Solution 2:

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 \dbinom{x}{0}$, 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\limits_{i=0}^{m-1} (a_i/b_i) x^i$. Since the polynomial $b_m f(x) - a_m m! \dbinom{x}{m}$ 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! \dbinom{x}{m} = \sum_{j=0}^{m-1} c_j \dbinom{x}{j}, \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! \dbinom{x}{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! \dbinom{x}{m} + \frac{1}{b_m} \sum\limits_{j=0}^{m-1} c_j \dbinom{x}{j}, \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} \dbinom{k}{j} $$ and since the first $k$ terms of the sum are integers, $c_k/b_m$ must also be an integer and 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,

Solution 3:

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.