jump to navigation

Integer-valued polynomials July 21, 2009

Posted by Akhil Mathew in algebra, Problem-solving.
Tags: ,

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]



1. Qiaochu Yuan - July 22, 2009

The difference operator you want is actually the forward one, \Delta P(x) = P(x + 1) - P(x).

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

2. Akhil Mathew - July 22, 2009

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 f: \mathbb{Z}_p \to \mathbb{Z}_p (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.

3. Qiaochu Yuan - July 22, 2009

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

4. Todd Trimble - July 27, 2009

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

\displaystyle P(x) = 12\binom{x}{4}

takes values P(0) = P(1) = P(2) = P(3) = 0 and P(4) = 12, so we have (m-n) | (P(m)-P(n) for this range of arguments, but the leading coefficient of P(x) is 1/2.

5. Qiaochu Yuan - July 27, 2009

Argh. The correct condition I want is stronger, then: if P is the unique polynomial with rational coefficients of minimal degree satisfying P(k) = a_k and in addition m - n | P(m) - P(n) for all m, n, 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 P is the unique polynomial with rational coefficients of minimal degree such that P(k) = a_k. Does there exist N such that if m - n | P(m) - P(n), 0 \le m, n \le N then P \in \mathbb{Z}[x]?

6. polynomial rings « Information Flow - November 22, 2009

[…] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: