Lemme de Dickson

En mathématiques, le lemme de Dickson stipule que tout ensemble de $n$-uplets d'entiers naturels a un nombre fini d'éléments minimaux. Ce fait combinatoire simple est attribué à l'algébriste américain L. E. Dickson, qui l'a utilisé pour prouver un résultat en théorie des nombres sur les nombres parfaits. Cependant, le lemme était certainement connu plus tôt, par exemple de Paul Gordan dans ses recherches sur la théorie des invariants.

Exemple

Une infinité de couples réels minimaux (x, y) (l'hyperbole noire) mais seulement cinq couples minimaux d'entiers positifs (rouge) vérifient xy ≥ 9.

Soit $K$ un entier fixé, et soit $S=\{(x,y)\mid xy\geq K\}$ l'ensemble des couples de nombres dont le produit est au moins $K$. Lorsqu'il est défini sur les nombres réels positifs et muni de l'ordre produit, $S$ a une infinité d'éléments minimaux de la forme $(x,K/x)$, un pour chaque nombre positif $x$ ; cet ensemble de points est l'une des branches d'une hyperbole. Cependant, le lemme de Dickson ne concerne que les n-uplet d'entiers naturels, et sur les nombres naturels il n'y a qu'un nombre fini de couples minimaux. Chaque couple minimal $(x,y)$ d'entiers naturels vérifie $x\leq K$ et $y\leq K$, car si x était strictement supérieur à K alors (x − 1, y) appartiendrait aussi à S. Donc $S$ admet au plus $K^{2}$ éléments minimaux, un nombre fini.

Énoncé général

Soit $\mathbb {N}$ l'ensemble des entiers naturels, soit n une constante fixe quelconque. On munit $\mathbb {N} ^{n}$ de l'ordre partiel produit, pour lequel $(a_{1},a_{2},\dots ,a_{n})\leq (b_{1},b_{2},\dots b_{n})$ si et seulement si, pour tout $i$, $a_{i}\leq b_{i}$. L'ensemble des n-uplets supérieurs ou égaux à un n-uplet particulier $a=(a_{1},a_{2},\dots ,a_{n})$ forme un orthant positif, de sommet $a$.

Avec cette notation, le lemme de Dickson peut être énoncé sous plusieurs formes équivalentes :

• pour toute partie non vide $S$ de $\mathbb {N} ^{n}$, l'ensemble des éléments minimaux de $S$ est fini et non nul ;
• $(\mathbb {N} ^{n},\leq )$ est un bel ordre ;
• toute partie non vide $S$ de $\mathbb {N} ^{n}$ peut être couverte par un ensemble fini d'orthants positifs, dont les sommets appartiennent tous à $S$.

Généralisations et applications

Dickson a utilisé son lemme pour prouver que, pour tout nombre donné $n$, il ne peut exister qu'un nombre fini de nombres parfaits impairs qui ont au plus $n$ facteurs premiers. Cependant, on ne sait pas s'il existe des nombres parfaits impairs.

La relation de divisibilité entre les entiers P-friables, entiers dont les facteurs premiers appartiennent tous à l'ensemble fini P, donne à ces nombres la structure d'un ensemble partiellement ordonné isomorphe à $(\mathbb {N} ^{|P|},\leq )$ . Ainsi, pour tout ensemble S de nombres P-friables, il existe un sous-ensemble fini de S tel que tout élément de S est divisible par l'un des nombres de ce sous-ensemble. Ce fait a été utilisé, par exemple, pour montrer qu'il existe un algorithme pour classer les coups gagnants et perdants à partir de la position initiale dans le jeu de Sylver (en), même si l'algorithme lui-même reste inconnu.

Les n-uplets $(a_{1},a_{2},\dots ,a_{n})$ dans $\mathbb {N} ^{n}$ sont en bijection avec les monômes $x_{1}^{a_{1}}x_{2}^{a_{2}}\dots x_{n}^{a_{n}}$ sur un ensemble de $n$ variables $x_{1},x_{2},\dots x_{n}$. Le lemme de Dickson peut être vu comme un cas particulier du théorème de la base de Hilbert indiquant que tout idéal polynomial engendré par des monômes est de type fini. En effet, Paul Gordan a utilisé cette reformulation du lemme de Dickson en 1899 dans le cadre d'une preuve du théorème de la base de Hilbert.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Dickson's lemma » (voir la liste des auteurs).

Article connexe

• Lemme de Gordan (en)