Let $a_1,a_2,\ldots,a_n$ be $n$ distinct integers. Show that the product of all the fractions of the form $\dfrac{a_k-a_l}{k-l}$, where $n \geq k > l$, is an integer.

I thought about first determining how many differences $a_k-a_l$ are divisible by $b$.

Assume that $n_0$ of the integers $a_1,a_2,\ldots,a_n$ are divisible by $b$, that $n_1$ of them yield the remainder $1$ upon division by $b$, that $n_2$ of them yield the remainder $2$, and so on up to $n_{b-1}$ integers the yield a remainder of $b-1$ when divided by $n$. It then follows that $$n_0+n_1+n_2+\cdots+n_{b-1} = n.$$ The difference $a_k-a_l$ is divisible by $b$ if and only if $a_k \equiv a_l \pmod{b}$. Now note that the number of differences $a_k-a_l$ divisible by $b$ such that $a_k \equiv a_l \equiv r \pmod{b}$ is $C^2_{n_r} = \dfrac{n_r(n_r-1)}{2}$. It follows that the number of differences divisible by $b$ is exactly \begin{align*}N &= \dfrac{n_0(n_0-1)}{2}+\dfrac{n_1(n_1-1)}{2}+\cdots+\dfrac{n_{b-1}(n_{b-1}-1)}{2}\\&= \dfrac{n_0^2+n_1^2+n_2^2+\cdots+n_{b-1}^2}{2}-\dfrac{n_0+n_1+n_2+\cdots+n_{b-1}}{2}\\&= \dfrac{n_0^2+n_1^2+n_2^2+\cdots+n_{b-1}^2}{2}-\dfrac{n}{2}.\end{align*}


The following lemma solves the problem:

Lemma: Let $n$ be a positive integer and $p$ a prime. Given positive integers $a_1<a_2<\dots < a_n$ let $f_p(a_1,a_2,\dots a_n)=v_p(\prod\limits_{1\leq i < j\leq n} a_i-a_j)$. Then $f_p(a_1,a_2,\dots,a_n)\geq f_p(1,2,\dots,n)$.

Proof: We can calculate $v_p(a_1,a_2,\dots a_n)$ in the following way:

For every positive integer $k$ and $0\leq j < p^k$ we let $b^j_k$ be the number of terms among $a_1,a_2,\dots,a_n$ that are congruent to $j\bmod p^k$.

Let $c_k=\sum\limits_{j=0}^{p^k}\binom{b_k^j}{2}$.

Then we have $f(a_1,a_2,\dots a_n)=\sum\limits_{k=0}^\infty c_k$.

Notice that by Jensen's inequality for binomial coefficients we have that $c_k$ is minimized if and only if for every $j\neq j'$ we have that $|b_k^j-b_k^{j'}|\leq1$. Since this is clearly the case when $a_1,a_2,\dots,a_n=1,2,3,\dots,n$ the lemma follows.

  • $\begingroup$ The idea to the formula is a bit similar to de Polignac's formula. If you are having trouble seeing why the formula holds I can give some help. $\endgroup$
    – Yorch
    Dec 10 '16 at 3:47
  • $\begingroup$ Can you explain the Jensen's Inequality part? $\endgroup$ Dec 10 '16 at 3:55
  • $\begingroup$ Sure, the theorem is as follows: Let $x_1,x_2,\dots x_n$ be non-negative integers that add up to a constant $A$. Then the sum $\binom{x_1}{2}+\binom {x_2}{2}+\dots + \binom{x_n}{2}$ is minimized when $|x_i-x_j|\leq 1|$ for all $1|\leq i < j\leq n$. The proof is easy by contradiction. If $x_i<x_j-1$ then the sum becomes even smaller after changing $x_i$ for $x_i+1$ and $x_j$ for $x_j-1$. $\endgroup$
    – Yorch
    Dec 10 '16 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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