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
    @robjohn: yes, it was si$m$ilar: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=590&t=2904052012-02-04

2 Answers 2

19

If $x_1$, $\ldots$, $x_n$ are integers, then $\prod_{1\le i 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 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. 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.

7

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

  • 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