Looking for an elementary demonstration

[Kees]

are integers, all different. It is possible to prove that
.
Either by using some techniques with Vandermonde Determinants or by proving a stronger result on polynomials

and applying l'Hôpital's rule on P(1).
I am looking for a more elementary approach, does anyone know any ?

[R.D. Silverman]

Originally Posted by Kees

are integers, all different. It is possible to prove that
.
Either by using some techniques with Vandermonde Determinants or by proving a stronger result on polynomials

and applying l'Hôpital's rule on P(1).
I am looking for a more elementary approach, does anyone know any ?

Perhaps a pigeonhole approach. The product of (i-j) will contain
all of the primes less than j. Now consider the product of (a_i - a_j).
If the former does not divide the latter then there must be some prime
that appears as a factor of (i-j) [perhaps with multiplicity] that does
not appear in the latter product. But if we have j *different* integers
and a prime p LESS THAN j, then some pair of those integers must
be in the same congruence class mod p. (i.e. there are not j different
congruence classes mod p for p < j)

This is just a sketch.

[Kees]

Obviously, we can write

I used the pigeonhole approach to prove the result for small n. But even for small n, you cannot use this method in a straightforward way.
For n=4 you need to prove divisibility by 12.
The factor 3 easily pops up because of the fact that there are only 3 residues modulo 3 and we have four numbers, so at least two of them (a,b) must be equal modulo 3 and therefore 3|(a-b).
For 2 you need to do a little more work.
Several approaches work, you can for instance suppose that the 4 numbers have 4 different residues modulo 4 (if not you have a factor 4 instantly), but in that case there are two even and two odd numbers, which both contribute a factor 2.
Another way would be to simply look at the numbers modulo 2.
There are 5 distributions possible (all even, 3 even 1 odd, etc) and each of these possibilities gives at least two factors 2.
For small n you can continue this approach, but I have my doubts whether this extends very nicely.

[akruppa]

I mentioned the problem during coffee break in our group, and Jérémie Detrey came up with this solution:

Originally Posted by Jérémie Detrey

Okay guys, I think I have the proof. Maybe a bit ugly, but I think it's
correct. Here we go.

Let n be an integer, and take the distinct integers a_1, ..., a_n.

Let P_n := \prod_{1 \le i < j \le n}(j-i)
and Q_n := \prod_{1 \le i < j \le n}(a_j-a_i).

We want to prove that P_n | Q_n.

For that, let's first rewrite P_n = \prod_{1 \le i \le n} i^{n-i}. This
is seen simply by looking at the terms we multiply together:

j
.
:
6 o o o o o .
5 o o o o . .
4 o o o . . .
3 o o . . . .
2 o . . . . .
1 . . . . . .
1 2 3 4 5 6 ... i

The difference j-i is constant on each diagonal. Therefore we have n-1
terms of difference 1, n-2 terms of difference 2, and so on until 1 term
of difference n-1.

If we now look at the number N_{n,l} of terms of difference divisible by
an integer l, we have: n-l terms of difference l, n-2l terms of
difference 2l, ..., n-i.l terms of difference i.l, ..., n-[n/l].l terms
of difference [n/l].l, where [.] denotes the floor function. Therefore:
N_{n,l} = \sum_{1 \le i \le [n/l]}(n - i.l)
= n.[n/l] - l.\sum_{1 \le i \le [n/l]}(i)
= n.[n/l] - l.[n/l].([n/l]+1)/2

Now let's focus a bit on Q_n: for the difference a_j-a_i to be divisible
by an integer l, we need that a_j and a_i belong to the same equivalence
class modulo l. Since we have n numbers a_i, we have to put each of them
into one of the l equivalence classes modulo l, and then compute the sum
for each equivalence class of the number of edges in the complete graph
formed by all the points in each of this equivalence class. Let's write
this sum as M_{n,l}.

A clique of k vertices has k.(k-1)/2 edges, so if an equivalence class
modulo l has k numbers a_i in it, this accounts for k.(k-1)/2 in the sum
M_{n,l}. We can see that the lower bound for M_{n,l} is attained when
all equivalence classes have exactly [n/l] or [n/l]+1 numbers.

Indeed, if two classes are unbalanced (with k and k' numbers
respectively, where k-1 > k'), we can decrease the value of M_{n,l} by
taking a number from the first class (this will decrease M_{n,l} by k-1)
and put it into the second class, which will in turn increase M_{n,l} by
k', yielding a global decrease of M_{n,l} by k-1-k'.

So, by pigeon-holing everything, we have exactly l equivalence classes,
among which n mod l contain exactly [n/l]+1 numbers, the other ones
containing exactly [n/l] numbers. Rewriting n mod l as n - l.[n/l], we
have:
* n-l.[n/l] classes accounting for ([n/l]+1).[n/l]/2
= ([n/l]-1).[n/l]/2 + [n/l] edges
* l-n+l.[n/l] classes accounting for ([n/l]-1).[n/l]/2 edges

This gives:
M_{n,l} = l.([n/l]-1).[n/l]/2 + (n-l.[n/l]).[n/l]
= n.[n/l] - l.[n/l].([n/l]+1)/2
= N_{n,l}

So for every l < n, we have that l^{N_{n,l}} = l^{M_{n,l}} | Q_n. Since
no prime \ge n can divide P_n by definition, we have the result P_n |
Q_n. QED \o/

J.

PS: Guillaume dropped by my office 3 minutes ago. I showed him the
problem. He had a more elegant solution using polynomial discriminants
in less than 30 seconds... I'm gonna hang myself

We haven't figured out how Guillaume's proof with discriminants might work yet... ideas, anyone?

Alex