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.

About Peter Cameron

I count all the things that need to be counted.

View all posts by Peter Cameron →

4 Responses to Polynomials taking integer values

Shahrooz Janbaz says:

31/01/2017 at 13:44

Nice note and argument…

Robin Chapman says:

31/01/2017 at 19:24

To write a polynomial like $(x^{2m}+x^m)/2$ in terms of binomial coefficients: ${x choose k}$ it suffices to write a monomial $x^n$ in such a way. The (well-known) formula for this involves Stirling numbers of the second kind, which I’ll write as $S(n,k)$ , and is
$x^n=\sum_{k=0}^n k! S(n,k){x choose k}$ .

There’s some nice combinatorics in this; when $A$ is a finite set of $x$ elements then both sides count the number of maps from $\{1,\ldots,n\}$ to $A$ , the right side splitting up these maps according to the size of their images.

Frank Cornelius says:

01/02/2017 at 11:38

Integer-valued polynomials are studied in “Polynomial Points”, J Integer Sequences, Vol 10 (2007). Article 07.3.6, in which the object is to determine which sequences of integers can be generated by integer-valued polynomials. See “Multinomial Points”, Houston J Math, Vol 34, No 3, 2008, for higher dimensions.

Robin Chapman says:

03/02/2017 at 09:25

Here’s a different argument to prove that a polynomial F taking integer values on N takes integer values on Z.

For each prime number p, F is a continuous function on the p-adic numbers Q_p. As N is dense in the p-adic integers Z_p, which are closed in Q_p, then F maps Z_p to Z_p, and a fortiori, Z to Z_p.

This holds for any p, and the only rationals which are in Z_p for all p are integers, so F maps Z to Z.

This argument applies to prove that a polynomial mapping a set S to Z maps Z to Z, provided that S is dense in Z_p for all primes p. This is the same as saying that for any integer a and prime power p^k there is some element of S that is congruent to a modulo p^k.

This may seem a “mathematics-made-difficult” style argument, but the idea of using p-adic continuity of polynomials over Q is used in number theory to prove things such as the Clausen-von Staudt congruences for Bernoulli numbers, and that again is the start of the theory of p-adic L-functions.

(Sorry, after my last effort I am giving up using the WordPress latex mode. It is just too frustrating. )