Polynomials taking integer values

This is not a hot new result, just part of general mathematical culture.

If a polynomial f(x) has integer coefficients, then its values at integer arguments are clearly integers. The converse is false; the simplest example is the polynomial x(x−1)/2.

Also, if a polynomial vanishes at infinitely many different arguments, then it vanishes everywhere. But it is not true that a polynomial which has integer values at infinitely many integer arguments takes integer values at all integer arguments. The simplest counterexample is x/2.

On the other hand, we might often be in the situation where we know that a polynomial takes integer values at all positive integers (for example, because it counts something). Does it follow that it takes integer values at all integers?

This is on my mind as a result of thinking about reciprocal polynomials, as described in a recent post. The cycle polynomial of a permutation group, divided by the group order, takes integer values at positive integers, since it counts something; if a reciprocal polynomial is to have the same property, then the original polynomial should take integer values at negative integers as well.

The answer is yes. If you haven’t thought about this before, please do so now before reading on.

Here is the outline of a simple argument for a more general fact:

If a polynomial of degree n takes integer values at n+1 consecutive integer arguments, then it takes integer values at all integer arguments.

Clearly by translation we may assume that f(0), f(1), …, f(n) are integers. Our proof is by induction on n; starting the induction at n = 0 is immediate. If f has degree n and satisfies the hypothesis, let g be the difference polynomial defined by g(x) = f(x+1)−g(x). Then g has degree n−1 and takes integer values at 0, 1, … n−1; so it takes integer values at all integer arguments, from which we see that the same is true for f.

Richard Stanley, in his celebrated book, gives the very nice representation theorem for such polynomials. The polynomial g in the preceding proof is the first difference polynomial of f; inductively one can define the ith difference polynomial for any i. Now the result is:

Let f be a polynomial of degree n taking integer values at all integers. Then f(x) is an integer linear combination of the “binomial coefficient” polynomials {x choose k}, for k = 0,…n; the coefficient is the kth difference polynomial evaluated at 0.

Of course, this theorem, lovely though it is, is not the most efficient representation in all situations. For example, if n is even, say n = 2m, then (x^2m+x^m)/2 is the cycle polynomial of the group consisting of the identity and a fixed-point-free involution (divided by the group order); I don’t know how to write it in terms of binomial coefficients.