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]