Showing $\prod\limits_{i<j} \frac{x_i-x_j}{i-j}$ is an integer

Let $x_1,...,x_n$ be distinct integers. Prove that

$$\prod_{i<j} \frac{x_i-x_j}{i-j}\in \mathbb Z$$

I know there is a solution using determinant of a matrix, but I can't remember it now. Any help will be appreciated.

-
Please avoid titles that are entirely in $\LaTeX$. –  Ｊ. Ｍ. Feb 3 '12 at 16:25
Without the $i-j$, this is the determinant of a Vandermonde Matrix: en.wikipedia.org/wiki/Vandermonde_matrix –  Eric Naslund Feb 3 '12 at 16:35
Your expression (up to a negative sign) is the determinant of the exponential vandermonde matrix: $$\left[\begin{array}{ccccc} 1 & \frac{x_{1}}{1!} & \cdots & \frac{x_{1}^{n-2}}{(n-2)!} & \frac{x_{1}^{n-1}}{(n-1)!}\\ 1 & \frac{x_{2}}{1!} & \cdots & \frac{x_{2}^{n-2}}{(n-2)!} & \frac{x_{2}^{n-1}}{(n-1)!}\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 1 & \frac{x_{n-1}}{1!} & \cdots & \frac{x_{n}^{n-2}}{(n-2)!} & \frac{x_{n}^{n-1}}{(n-1)!}\\ 1 & \frac{x_{n}}{1!} & \cdots & \frac{x_{n}^{n-2}}{(n-2)!} & \frac{x_{n}^{n-1}}{(n-1)!} \end{array}\right].$$ –  Eric Naslund Feb 3 '12 at 17:29
Argh. I used to know a very nice proof of this, but I've completely forgotten it. It's somewhere on AoPS. –  Qiaochu Yuan Feb 3 '12 at 22:04
@Qiaochu: It must have been similar to David Moews answer. I doubt much nicer will appear. –  robjohn Feb 4 '12 at 0:11

If $x_1$, $\ldots$, $x_n$ are integers, then $\prod_{1\le i<j\le n} \frac{x_i-x_j}{i-j}$ is integral because it is the determinant of the integral matrix $$\left(x_i \choose j-1\right)_{i,j=1,\ldots,n}.$$

You can see this by starting with the formula for the determinant of the Vandermonde matrix, $$\det\left( (x_i^{j-1})_{i,j=1,\ldots,n}\right) = \prod_{1\le i<j\le n} (x_j-x_i);$$ then, divide column $j$ of the Vandermonde matrix by $(j-1)!$ to get the matrix $$\left(\frac{x_i^{j-1}}{(j-1)!}\right)_{i,j=1,\ldots,n}$$ given by Eric Naslund above. Its determinant equals $\prod_{1\le i<j\le n} \frac{x_j-x_i}{j-i}=\prod_{1\le i<j\le n} \frac{x_i-x_j}{i-j}$. Finally, taking $j=n$, $n-1$, $\ldots$, $1$ in succession, add in rational multiples of columns $1$, $\ldots$, $j-1$ to column $j$ to change each $\frac{x_i^{j-1}}{(j-1)!}$ to $x_i \choose j-1$; this does not change the determinant of the matrix.

-

Here's a very direct approach. For each prime up to $n-1$, we just need to check that $$\text{val}_p\left( \prod_{i<j}(i-j)\right) \leq \text{val}_p\left( \prod_{i<j}(x_i-x_j) \right)$$ for any choice of integers $x_i$. (Here, the $p$-adic valuation $\text{val}_p(x)$ simply counts the powers of $p$ that divide $x$.) That is, we need to show that choosing $x_1, x_2, \ldots, x_n$ to be $1, 2, \ldots, n$ gives the smallest $p$-adic valuation possible.

To do this, notice that setting $x_i=i$ gives the minimum possible number of pairs $(i,j)$ such that $x_i-x_j$ is divisible by $p$ (or divisible by $p^2$, or by $p^3$, or any $p^k<n$ ). This is because the numbers $1, 2, \ldots, n$ are as evenly spread out among the residue classes modulo $p^k$ as possible. By the Pigeonhole principle, any other choice of integers $x_1, x_2, \ldots, x_n$ will have at least as many repeated residue classes, and an uneven distribution leads to a greater total number of pairs $(x_i,x_j)$ from the same residue class. (Because of the inequality of triangular numbers $T_{n+i}+T_{n-i} \geq 2T_{n}$.)

Thus, $\displaystyle \prod_{i<j} \frac{x_i-x_j}{i-j}$ is an integer, because there are at least as many powers of $p$ on top as there are on the bottom for each prime $p$.

-