##
Integer-valued polynomials *July 21, 2009*

*Posted by Akhil Mathew in algebra, Problem-solving.*

Tags: integers, polynomials

trackback

Tags: integers, polynomials

trackback

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]*

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?

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.

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

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.

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 ?

[…] been playing with polynomial rings. So perhaps it’s good to recall what has been said about such things in the past by others. (Let’s call this a sort of literature review!) In algebra […]