Integer-valued polynomials July 21, 2009Posted by Akhil Mathew in algebra, Problem-solving.
Tags: integers, 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 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.
It turns out that we can always express any polynomial in terms of the binomial coefficients:
Definition 1 We 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. .
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, with integral 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.