# 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?

• If you know the degree $d$ of your polynomial function, you can determine the coefficients from $f(0), f(1), \ldots, f(d)$ by taking successive differences. If you don't know the degree, you can't come to a positive conclusion by looking at finitely many values because you can't distinguish between polynomials that happen to be equal at all the points you tested. – Robert Israel Mar 22 at 22:27

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

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

2. 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]$$.

• I’m not sure how this answers the original question. I believe the OP was asking which polynomial functions from $\mathbb Z$ to $\mathbb Z$ are given by polynomials in $\mathbb Z[X]$? I think we know what the polynomials are: they’re integer combinations of $X(X-1)...(X-k)$. I believe the question is how can we tell by looking at $f(X)$ whether it has this property. Clearly your condition is not sufficient as you explain there are polynomials with non-integer coefficients satisfying your condition. – Anthony Quas Mar 23 at 8:04
• @AnthonyQuas this answers the question in the second paragraph of OP. – Fedor Petrov Mar 23 at 8:44
• @AnthonyQuas I added something about the first part of the question too. But I am not sure that this is what Roman actually needs. – Fedor Petrov Mar 23 at 9:00
• @FedorPetrov your updated posting fully answers both of my questions, many thanks! – Roman Mar 23 at 13:33
• @FedorPetrov, by the way, the proofs look clear but it would be nice to have a textbook or paper reference, do you know any? – Roman Mar 23 at 15:32