10
$\begingroup$

We can view the binomial coefficient $\binom{x}{k}$ has a polynomial in $x$ with degree $k$. So taking some $f\in\mathbb{Q}[x]$, why is $f(n)\in\mathbb{Z}$ for all $n\in\mathbb{Z}$, precisely when the coefficients of $f$ are integers with respect to the basis $\{\binom{x}{k}\mid k\in\mathbb{N}\}$?

The reverse direction seems clear, so I wonder why the opposite implication is also true. I did notice that all the roots of $\binom{x}{k}$ are just $0,\dots,k-1$. Can we factor the polynomial is some nice way to reveal the opposite conclusion? Thanks.

  • 0
    The key word here is *finite differences*. See [Newton series](http://en.wikipedia.org/wiki/Finite_difference#Newton_series).2012-02-12

3 Answers 3

14

This is a special case of a classical result of Polya and Ostrowski (1920): $f(x) \in \mathbb Q[x]$ is an integer valued polynomial, i.e. $f(\mathbb Z)\subset \mathbb Z\:,\:$ iff $f(x)$ is an integral linear combination of binomial coefficients ${x\choose k},\:$ for $\: k\le \deg f$. For a proof see e.g. Polya And Szego, Problems and theorems in analysis, vol II, Problem 85 p. 129 and its solution on p. 320.

For example

$\rm\displaystyle\ \ \frac{n^3+5\:n}6\ =\ \frac{n^3-n + 6\:n}6\ =\ \frac{(n+1)\:n\:(n-1)}6 + \:n\ =\ {n+1\choose 3} + {n\choose 1}$

This has been extended to much more general rings (e.g. Dedekind domains) by Cahen at al.

  • 1
    This result also appears in LeVeque's [Fundamentals of Number Theory](http://store.doverpublications.com/0486689069.html), section 3.4, exercise 14.2012-02-12
5

The idea is simple ; given a polynomial $f \in \mathbb Q[x]$ of degree $m$, we can reduce the degree of $f$ and use induction as in the following :

If a polynomial of degree $0$ is integer-valued, then we can write it as $f(x) = a \in \mathbb Z$ and thus $f(x) = a \dbinom{x}{0}$, so for $m=0$ we are doing just fine.

Assuming all polynomials of degree $ can be written as such combinations of binomial coefficients, let $f(x) \in \mathbb Q[x]$ be such a polynomial of degree $m$. Then $f(x) = (a_m/b_m) x^m + \sum\limits_{i=0}^{m-1} (a_i/b_i) x^i$. Since the polynomial $b_m f(x) - a_m m! \dbinom{x}{m}$ is also integer-valued by assumption, and its degree is at most $m-1$, it can be expressed as $ b_m f(x) - a_m m! \dbinom{x}{m} = \sum_{j=0}^{m-1} c_j \dbinom{x}{j}, \qquad c_j \in \mathbb Z $ without excluding the case where $c_j = 0$ for $0 \le j \le m-1$ (in this case the degree of $b_m f(x) - a_m m! \dbinom{x}{m}$ is either not defined or $-\infty$ depending on which convention you like, but either way things work out nicely), which means $$ f(x) = \frac{a_m}{b_m} m! \dbinom{x}{m} + \frac{1}{b_m} \sum\limits_{j=0}^{m-1} c_j \dbinom{x}{j}, \qquad c_j \in \mathbb Z $$ Here by computing $f(0)$, $f(1)$, $\dots$, $f(m)$, one can see that this expression is an integer-linear-combination of the binomial coefficients. For instance, $f(0) = c_0 / b_m$, hence $b_m$ divides $c_0$. Then $f(1) = c_1/ b_m + c_0/b_m$, so that $c_1 /b_m$ is an integer, hence $b_m$ divides $c_1$. Going on like this, $ f(k) = \sum_{j=0}^k \frac {c_j}{b_m} \dbinom{k}{j} $ and since the first $k$ terms of the sum are integers, $c_k/b_m$ must also be an integer and thus $b_m$ divides $c_k$. By computing $f(m)$ this process stops. In other words, $f(x)$ is expressible as desired. The result follows by induction.

Hope that helps,

  • 0
    The idea between the lines is that the integer-valued coefficients form a $\mathbb Z$-module for which the binomial coefficient polynomials form a basis. I implicitly used the basis part to expect unicity and thus reducing the degree by removing one component allowed me to use induction.2012-02-11
1

Since you already know that the $\binom Xn$ for $n\in\Bbb N$ form a $\Bbb Q$-basis of $\Bbb Q[X]$ (and indeed this is easy to see), the rest of the argument is trivial. Let $P=\sum_nc_n\binom Xn\in\Bbb Q[X]$ be arbitrary, then the value of $P$ at $m\in\Bbb N$ is $c_m+\sum_{i, which must be an integer. Now by immediate induction on $m$, all the coefficients $c_m$ are integer.