Integer valued polynomials and polynomials with integer coefficients It is well known that the subring $S$ of integer valued polynomials ${\mathbb Q}[x]$ is generated by the binomial functions $P_n={x \choose n}$. One can ask a dual question: how to characterize the polynomial functions ${\mathbb Z} \to {\mathbb Z}$ which come from an element in ${\mathbb Z}[x]$.
I understand one can write down derivative as a (terminating) series of difference derivatives and thus express each coefficients in terms of values of the polynomial but does this (or another) procedure lead to a neat answer?
There is a necessary condition for a polynomial function $f:{\mathbb Z} \to {\mathbb Z}$ to come from an element in ${\mathbb Z}[x]$, namely for every $n$ the residue of $f(x) \mod n$ depends only on the residue of $x \mod n$. This necessary condition is not sufficient but I am interested in the subring of elements in $S$ satisfying that necessary condition. Is there a nice set of generators and/or a basis?
 A: In the second paragraph of the post you ask about those integer-valued polynomials $f(x)$ for which $\frac{f(x)-f(y)}{x-y}$ is an integer for integers $x\ne y$. The basis in this $\mathbb{Z}$-module $M$ may be described as follows. For each $n=1,2,\ldots$ define the minimal positive rational $\alpha_n$ such that $\alpha_nx(x-1)\ldots(x-n+1)\in M$. I claim that

*

*$\alpha_n={\rm lcm}(1,2,\ldots,n)/n!$


*The polynomials $1,\alpha_1x,\alpha_2x(x-1),\ldots$ form a basis of $M$.
You may read the proof here (Problem 4, solution 1).

Now about characterizing those polynomials which have integer coefficients via the values. This may be done if we generalize the necessary condition $$\frac{f(x)-f(y)}{x-y}\in \mathbb{Z}\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,\,\,(1)$$ as follows:
$$
\sum_{i=0}^k \frac{f(x_i)}{\prod_{j:j\ne i} (x_i-x_j)}\in \mathbb{Z} \quad\quad\quad\quad\quad(2)
$$
for all distinct integers $x_0,x_1,\ldots,x_k$ ((2) reduces to (1) when $k=1$). By Lagrange interpolation formula, the expression in (2) is the coefficient of $x^k$ in the polynomial $g(x)$ which has degree at most $k$ and takes the same values as $f$ at points $x_0,\ldots,x_k$. In other words, $g$ is the remainder of
$f$ modulo $(x-x_0)(x-x_1)\ldots (x-x_k)$. So, if $f(x)\in \mathbb{Z}[x]$, we have $g(x)\in \mathbb{Z}[x]$ and in particular (2) holds. On the other hand, if (2) holds for $k=\deg f+1$, we see that the leading coefficient of $f$ is integer, so we may subtract the leading term from $f$ and induct, proving that $f(x)\in \mathbb{Z}[x]$.
