23
$\begingroup$

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

$$\prod_{i

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

  • 1
    Please avoid titles that are entirely in $\LaTeX$.2012-02-03
  • 2
    Without the $i-j$, this is the determinant of a Vandermonde Matrix: http://en.wikipedia.org/wiki/Vandermonde_matrix2012-02-03
  • 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].$$2012-02-03
  • 1
    Argh. I used to know a very nice proof of this, but I've completely forgotten it. It's somewhere on AoPS.2012-02-03
  • 1
    @Qiaochu: It must have been similar to David Moews answer. I doubt much nicer will appear.2012-02-04
  • 1
    @robjohn: yes, it was similar: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=590&t=2904052012-02-04

2 Answers 2

18

If $x_1$, $\ldots$, $x_n$ are integers, then $\prod_{1\le i

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

6

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

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

Thus, $\displaystyle \prod_{i

  • 0
    This is the idea behind of one of the existing proofs (cf. the post by Valiowk on http://www.artofproblemsolving.com/community/c6h4858 ), but for it to be complete, the "uneven distribution" argument has to be made precise, and not only primes need to be counted (but also, at least, prime powers).2015-08-19