Une propriété de divisibilité

Bonjour,

je viens par hasard de découvrir dans une feuille de TD la propriété suivante.

Soit $n\in\N$ avec $n\geq 2$. Si $x_1,\ldots, x_n$ sont des entiers naturels, alors $\displaystyle{\prod_{1\leq i<j\leq n} (j-i)}$ divise $\displaystyle{\prod_{1\leq i<j\leq n} (x_j-x_i)}$.

La démonstration proposée utilise le calcul du déterminant d’une matrice à coefficients entiers (complètement parachuté). Je me demandais s’il n’y aurait pas une autre démonstration plus « directe » de ce résultat.

Je vous remercie pour votre aide et vos suggestions.

Réponses

  • Bonjour,

    j'imagine que "directe" signifie "purement arithmétique".
    Oui, c'est possible, mais au regard de ce qui suit, je comprends tout à fait que les professeurs exposent plutôt la solution par les déterminants de Vandermonde...

    Soit $p$ un nombre premier.
    On note respectivement $v_p(\displaystyle{\prod_{1\leq i<j\leq n} (j-i)})$ et $v_p(\displaystyle{\prod_{1\leq i<j\leq n}(x_j-x_i)})$ l'exposant de $p$ dans la décomposition de $\displaystyle{\prod_{1\leq i<j\leq n} (j-i)}$ et dans celle de $\displaystyle{\prod_{1\leq i<j\leq n}(x_j-x_i)}$.

    Alors $v_p(\displaystyle{\prod_{1\leq i<j\leq n}(x_j-x_i))= \sum_{k \geq 1} n_k}$, où $n_k$ est le nombre de facteurs $x_i-x_j$ divisibles par $p^k$.
    De même, $v_p(\displaystyle{\prod_{1\leq i<j\leq n} (j-i) )= \sum_{k \geq 1} m_k}$, où $m_k$ est le nombre de facteurs $i-j$ divisibles par $p^k$.

    On va prouver que, pour tout $k \geq 1$ ($p$ étant fixé depuis le début), on a $n_k \geq m_k$, ce qui donnera directement la conclusion.

    On fixe donc un entier $k \geq 1$.

    Pour $i \in \{0,1, \cdots, p^k-1\}$, on note $b_i$ le nombre d'indices $j$ pour lesquels $a_j = i \mod {(p^k)}$.
    Alors $n_k = \displaystyle{\sum_{i=0}^{p^k-1} \dbinom{b_i}{2}}$.

    D'autre part, le nombre d'indices $j \in \{1, \cdots \}$ tels que $j = 0 \mod (p^k)$ est $\lfloor \dfrac{n}{p^k} \rfloor$,

    et pour $i \in \{1, \cdots, p^k-1\}$, on a $j = i \mod(p^k)$ ssi $j= rp^k+i \leq n$ avec $0 \leq r \leq \lfloor \dfrac{n-i}{p^k} \rfloor$. Le nombre de tels indices $j$ vaut donc $\lfloor \dfrac{n-i+p^k}{p^k} \rfloor$.

    Ainsi, après réindexation $j= p^k-i$, on a $m_k = \displaystyle{\sum_{j=0}^{p^k-1} \dbinom{\lfloor \frac{n+j}{p^k} \rfloor}{2}}$.

    On est amené à chercher la valeur minimale de $\displaystyle{S(x_0,\cdots ,x_{p^k-1}) = \sum_{i=0}^{p^k-1} \dbinom{x_i}{2}}$ où $x_0,x_1,\cdots, x_{p^k-1}$ sont des entiers naturels vérifiant $x_0+x_1+\cdots +x_{p^k-1} = n$.

    Notons que l'on travaille sur un ensemble fini de $p^k$-uplets possibles et donc qu'un tel minimum existe.
    Sans perte de généralité, on peut supposer que $x_0 \leq x_1 \leq \cdots \leq x_{p^k-1}$.

    Il est facile de vérifier que si $a$ et $b$ sont des entiers naturels vérifiant $a+1<b$ alors $\displaystyle{\dbinom{a}{2} + \dbinom{b}{2} > \dbinom{a+1}{2} + \dbinom{b-1}{2}}$.

    Par conséquent, dans le cas d'un minimum, on doit avoir $x_i = x_0$ ou $x_i = x_0+1$ pour tout $i$.
    Notre ordonnancement assure de l'existence d'un entier $j$ tel que $x_0=x_1 = \cdots = x_j$ et $x_{j+1} = \cdots = x_{p^k-1} = x_0+1$.

    De plus, puisque $x_0+x_1+\cdots +x_{p^k-1} = n$, il vient $p^k(x_0+1) -j-1= n$.

    On a donc $n_k \geq (j+1) \dbinom{x_0}{2} + (p^k-j-1)\dbinom{x_0+1}{2}$.

    Mais, pour $i \in \{0, \cdots, p^k-1\}$, on a $\dfrac{n+i}{p^k} = \dfrac{p^k(x_0+1)-j-1+i}{p^k}$

    d'où $\lfloor \dfrac{n+i}{p^k} \rfloor = x_0+1 + \lfloor \dfrac{i-j-1}{p^k} \rfloor$.

    Par suite, pour $i \geq j+1$, on a $\lfloor \dfrac{n+i}{p^k} \rfloor = x_0+1$
    tandis que pour $i \leq j$, on a $\lfloor \dfrac{n+i}{p^k} \rfloor = x_0$.

    L'expression ci-dessus de $m_k$ montre alors que
    $m_k = \displaystyle{\sum_{i=0}^{p^k-1} \dbinom{\lfloor \frac{n+i}{p^k} \rfloor}{2}=(j+1) \dbinom{x_0}{2} + (p^k-j-1)\dbinom{x_0+1}{2}}$,

    et ainsi $m_k \leq n_k$, comme annoncé.

    Pierre.
  • Il n'est pas surprenant que les démonstrations de cette propriété fassent intervenir les déterminants puisqu'on reconnait dans ces deux produits la forme factorisée d'un déterminant de Vandermonde.

    Je ne connaissais pas la démonstration purement arithmétique de PierreB mais je connais une autre démonstration (qui n'est pas de moi) n'utilisant pas les déterminants mais des polynômes. Elle utilise le lemme :
    si $P\in\R_{n-1}[X]$ alors pour tout $x\in\Z$ on peut écrire $P(x)=\displaystyle\sum_{k=1}^nL_k(x)P(k)$ où les $L_k(x)$ sont des entiers.
    Les $L_k$ sont les polynômes de Lagrange associés à $1,2,...,n$ mais ce lemme se démontre sans connaître les polynômes de Lagrange, avec simplement une récurrence. Si $n=1$ alors $P(x)=1\times P(1)$.
    Supposons la propriété vraie pour $P\in\R_{n-1}[X]$ et soit $P\in\R_n[X]$.
    $Q(X)=P(X+1)-P(X)$ est dans $\R_{n-1}[X]$ donc pour $x\in\Z$, $Q(x)=\displaystyle\sum_{k=1}^nL_k(x)(P(k+1)-P(k)$ avec les $L_k(x)$ entiers.
    Pour un entier $x\geq n+2$ , $P(x)=P(n+1)+Q(n+1)+\dots+Q(x-1)$ est combinaison linéaire à coefficients dans $\Z$ des $P(1),\dots,P(n+1)$.
    De même pour un entier $x\leq 0$ , $P(x)=P(1)-Q(0)-\dots-Q(x)$ est combinaison linéaire à coefficients dans $\Z$ des $P(1),\dots,P(n+1)$.
    Cela achève la démonstration par récurrence.

    Utilisons ce lemme pour démontrer la propriété de divisibilité. Soit $P(x_1,\dots,x_n)=\displaystyle{\prod_{1\leq i<j\leq n} (x_j-x_i)}$.
    C'est un polynôme en $x_n$ de degré au plus $n-1$ donc c'est une combinaison linéaire à coefficients dans $\Z$ des $P(x_1,\dots,x_{n-1},k_n)$ pour $1\leq k_n\leq n$.
    On continue avec $P(x_1,\dots,x_{n-1},k_n)$ jusqu'à obtenir $P(x_1,\dots,x_n)$ comme combinaison linéaire à coefficients dans $\Z$ des $P(k_1,\dots,k_n)$ avec $k_1,\dots,k_n$ entiers entre $1$ et $n$. Comme permuter $k_i$ et $k_j$ change éventuellement le signe et que $P(k_1,\dots,k_n)$ est nul si deux des entiers sont égaux, on obtient que $P(x_1,\dots,x_n)$ est un entier multiple de $P(1,\dots,n)$
  • Je vous remercie tout les deux pour vos démonstrations. Je dois encore les étudier en détail, mais je comprends aussi du coup pourquoi on utilise plutôt l’astuce du déterminant en général.
Connectez-vous ou Inscrivez-vous pour répondre.