Lemme de Dickson
En mathématiques, le lemme de Dickson stipule que tout ensemble de -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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Dickson_hyperbola9.svg/220px-Dickson_hyperbola9.svg.png)
Soit un entier fixé, et soit l'ensemble des couples de nombres dont le produit est au moins . Lorsqu'il est défini sur les nombres réels positifs et muni de l'ordre produit, a une infinité d'éléments minimaux de la forme , un pour chaque nombre positif ; 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 d'entiers naturels vérifie et , car si x était strictement supérieur à K alors (x − 1, y) appartiendrait aussi à S. Donc admet au plus éléments minimaux, un nombre fini[note 1].
Énoncé général
Soit l'ensemble des entiers naturels, soit n une constante fixe quelconque. On munit de l'ordre partiel produit, pour lequel si et seulement si, pour tout , . L'ensemble des n-uplets supérieurs ou égaux à un n-uplet particulier forme un orthant positif, de sommet .
Avec cette notation, le lemme de Dickson peut être énoncé sous plusieurs formes équivalentes :
- pour toute partie non vide de , l'ensemble des éléments minimaux de est fini et non nul[1] ;
- est un bel ordre ;
- toute partie non vide de peut être couverte par un ensemble fini d'orthants positifs, dont les sommets appartiennent tous à .
Généralisations et applications
Dickson a utilisé son lemme pour prouver que, pour tout nombre donné , il ne peut exister qu'un nombre fini de nombres parfaits impairs qui ont au plus 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 à . 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 dans sont en bijection avec les monômes sur un ensemble de variables . 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
Notes
- ↑ Il est en fait possible de montrer que ou est inférieur ou égal à et qu'il y a au plus un couple minimal pour chaque choix de l'une des coordonnées. Il y a donc au plus éléments minimaux.
Références
- ↑ (en) Joseph B. Kruskal, « The theory of well-quasi-ordering: A frequently discovered concept », J. Combin. Theory, series A, vol. 13, no 3, , p. 298 (DOI 10.1016/0097-3165(72)90063-5)
Article connexe
- Lemme de Gordan (en)
Portail des mathématiques