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]