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 which takes integer values at all sufficiently large . What can we say about ?*

Denote the set of such by . Then clearly . But the converse is false.

Take for instance

which is always integral, since and always have the same parity.

**Binomial Coefficients **

It turns out that we can always express *any* polynomial in terms of the binomial coefficients:

Definition 1We define the-th binomial coefficient:

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

We see that since the ordinary binomial coefficients are integers.

The binomial coefficients have many interesting properties. First, we define the **difference operator** mapping . The key idea to this problem is that *preserves *, i.e. .

We have:

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

Finally, the polynomials form a basis for . Given a polynomial of degree and leading coefficient , take the difference

and get a polynomial of degree . Then induct on the degree of to see that the span ; 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. In other words, every polynomial is a linear combination, withintegral coefficients, of binomial coefficients.

*Proof:* Induction on . If we are working with a constant function which must be an integer, and by definition. Otherwise, if and the theorem is proved for smaller degrees, we can write

where , but not necessarily . Then

since , we see that necessarily the by the inductive hypothesis.

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

July 22, 2009 at 1:02 pm

The difference operator you want is actually the forward one, .

Anyway, there’s a rather clever way to do this proof “constructively” analogous to the Taylor series expansion: just check the identity . A polynomial takes integer values if and only if its finite difference table consists of integers. But even better, the coefficients 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 to satisfy for some sequence of integers . The “local” obstruction to this polynomial having integer coefficients is that the integers may not satisfy , which must be true of any polynomial with integer coefficients. Is this the only obstruction? In other words, given that the condition holds does have integer coefficients?

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 (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.

July 27, 2009 at 6:00 am

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

takes values and , so we have for this range of arguments, but the leading coefficient of is 1/2.

July 27, 2009 at 6:24 pm

Argh. The correct condition I want is stronger, then: if is the unique polynomial with rational coefficients of minimal degree satisfying and in addition for all , 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 is the unique polynomial with rational coefficients of minimal degree such that . Does there exist such that if then ?