Integer-valued polynomials

So, in a break from the earlier series I was doing on Lie algebras, I want to discuss a very elementary question about polynomials. The answer is well-known but is interesting. It would make a good competition type problem (indeed, it’s an exercise in Serge Lang’s Algebra). Moreover, ironically, it’s useful in algebra: At some point one of us will probably discuss Hilbert polynomials, which take integer values, so this result tells us something about them.

We have a polynomial ${P(X) \in \mathbb{Q}[X]}$ which takes integer values at all sufficiently large ${n \in \mathbb{N}}$ . What can we say about ${P}$ ?

Denote the set of such ${P}$ by ${\mathfrak{I}}$ . Then clearly ${\mathbb{Z}[X] \subset \mathfrak{I}}$ . But the converse is false.

Take for instance

$\displaystyle P(X) = \frac{ X^2 - X}{2},$

which is always integral, since ${X^2}$ and ${X}$ always have the same parity.

Binomial Coefficients

It turns out that we can always express any polynomial ${P}$ in terms of the binomial coefficients:

Definition 1 We define the ${n}$ -th binomial coefficient:

$\displaystyle C_n(X) := \binom{X}{n} = \frac{X(X-1) \dots (X-(n-1))}{n!}.$

This is of course a generalization of the normal definition of the binomial coefficients.

We see that ${C_n(X) \in \mathfrak{I}}$ since the ordinary binomial coefficients are integers.

The binomial coefficients have many interesting properties. First, we define the difference operator ${\Delta: \mathbb{Q}[X] \rightarrow \mathbb{Q}[X]}$ mapping ${P(X) \rightarrow P(X+1) - P(X)}$ . The key idea to this problem is that ${\Delta}$ preserves ${\mathfrak{I}}$ , i.e. ${\Delta(\mathfrak{I}) \subset \mathfrak{I}}$ .

We have:

$\displaystyle \Delta C_n(X) = C_{n-1}(X),$

which is checked directly from the definition and a little bit of algebra.

Finally, the polynomials ${C_n(X)}$ form a basis for ${\mathbb{Q}[X]}$ . Given a polynomial ${P(X)}$ of degree ${d}$ and leading coefficient ${a X^d}$ , take the difference

$\displaystyle P(X) - n! a C_d(X)$

and get a polynomial of degree ${\leq d-1}$ . Then induct on the degree of ${P}$ to see that the ${C_n(X)}$ span ${\mathbb{Q}[X]}$ ; since the degrees are different, they are linearly independent. (This is basically the proof that a triangular matrix with nonzero elements on the diagonal is invertible.)

Solution of the problem

Theorem 2 ${\mathfrak{I} = \bigoplus_n \mathbb{Z} C_n(X)}$ . In other words, every polynomial ${P(X) \in \mathfrak{I}}$ is a linear combination, with integral coefficients, of binomial coefficients.

Proof: Induction on ${\deg P}$ . If ${\deg P = 0}$ we are working with a constant function which must be an integer, and ${C_0(X) = 1}$ by definition. Otherwise, if ${\deg P = d}$ and the theorem is proved for smaller degrees, we can write

$\displaystyle P(X) = \sum_{i=0}^d a_i C_i(X),$

where ${a_i \in \mathbb{Q}}$ , but not necessarily ${\mathbb{Z}}$ . Then

$\displaystyle \Delta P(X) = \sum_i a_i C_{i-1}(X) \in \mathfrak{I};$

since ${\deg \Delta P < \deg P}$ , we see that necessarily the ${a_i \in \mathbb{Z}}$ by the inductive hypothesis. $\Box$

[Edit, 6/22- this material is also covered, with some additional results as well, in this post. See also here. AM]

Qiaochu Yuan Says:

July 22, 2009 at 1:02 pm

The difference operator you want is actually the forward one, $\Delta P(x) = P(x + 1) - P(x)$ .

Anyway, there’s a rather clever way to do this proof “constructively” analogous to the Taylor series expansion: just check the identity $a_k = \Delta^k P(0)$ . A polynomial takes integer values if and only if its finite difference table consists of integers. But even better, the coefficients $a_i$ are precisely the entries in its first row!

This turns out to be extremely convenient for polynomial interpolation; see my old posts here and here.

Anyway, here’s a problem along these lines. Suppose we want a polynomial of degree $n$ to satisfy $P(k) = a_k, k = 0, 1, ... n$ for some sequence of integers $a_k$ . The “local” obstruction to this polynomial having integer coefficients is that the integers $a_k$ may not satisfy $m - n | a_m - a_n$ , which must be true of any polynomial with integer coefficients. Is this the only obstruction? In other words, given that the condition holds does $P(x)$ have integer coefficients?

Akhil Mathew Says:

July 22, 2009 at 1:59 pm

Thanks for the correction!

Your method of finding the explicit coefficients is also how one finds the coefficients in the infinite binomial expansion of a continous function $f: \mathbb{Z}_p \to \mathbb{Z}_p$ (and shows their uniqueness); the existence of an infinite binomial expansion (Mahler’s theorem), may become a future post. If someone else doesn’t do it, I probably will eventually, since I like the result.

I looked at your posts, and they cover everything I mentioned here quite well, so I will add a link to them. I will think about your problem as well, but I don’t have an immediate answer.

July 22, 2009 at 7:24 pm

There’s some additional discussion of finite differences at Palmer Mebane’s blog here.

Todd Trimble Says:

July 27, 2009 at 6:00 am

Qiaochu, if I understand the problem, the answer is no. The polynomial

$\displaystyle P(x) = 12\binom{x}{4}$

takes values $P(0) = P(1) = P(2) = P(3) = 0$ and $P(4) = 12$ , so we have $(m-n) | (P(m)-P(n)$ for this range of arguments, but the leading coefficient of $P(x)$ is 1/2.

July 27, 2009 at 6:24 pm

Argh. The correct condition I want is stronger, then: if $P$ is the unique polynomial with rational coefficients of minimal degree satisfying $P(k) = a_k$ and in addition $m - n | P(m) - P(n)$ for all $m, n$ , then the conclusion holds. This is a corollary of a problem on USAMO 1995, but I’m curious how much we can weaken its hypotheses.

More specifically, suppose $P$ is the unique polynomial with rational coefficients of minimal degree such that $P(k) = a_k$ . Does there exist $N$ such that if $m - n | P(m) - P(n), 0 \le m, n \le N$ then $P \in \mathbb{Z}[x]$ ?

Climbing Mount Bourbaki