Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Please avoid titles that are entirely in $\LaTeX$. –  J. M. Feb 3 '12 at 16:25
2  
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
8  
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
1  
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
1  
@Qiaochu: It must have been similar to David Moews answer. I doubt much nicer will appear. –  robjohn Feb 4 '12 at 0:11

2 Answers 2

up vote 16 down vote accepted

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.

share|improve this answer

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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.