Relation de Divisibilité, Treillis et Hypercubes
Durant trois jours, les élèves de la première S de Madame Larras du lycée Pasquet((Site du Lycée Pasquet)) (Arles) ont travaillé, huit par salles et quatre par groupes, autour des treillis et diagrammes de Hasse. Ce groupe s'est intéressé en particulier à la relation de divisibilité représentée dans un diagramme de Hasse, ce qui l'a conduit à étudier les cubes dans différentes dimensions, et ce jusque dans la dimension n.
Déroulement du Stage et Résultats
L'objectif était d'étudier la relation de divisibilité dans les entiers naturels. Cette relation est représentable au moyen d'un Treillis, comme celui-ci :<BR> Stages/2011-05-30/w2ak.principe.treillisex.jpg?300
La simplicité du treillis obtenu résidant dans le nombre des diviseurs premiers du nombre étudié, ainsi que dans la puissance à laquelle chacun est élevé, il fallait donc commencer progressivement :
Stages/2011-05-30/w2ak.principe.simplicitetreillis.jpg
On Commence avec les Bases
Nous avons donc étudié plusieurs cas de nombres, en fonction de leur nombre de diviseurs premiers distincts, ainsi de la puissance à laquelle ils sont élevés.
Diviseurs Premiers Distincts tous à la Puissance 1
1 Diviseur premier : Le treillis le plus simple de cette relation
Prenons donc un nombre ayant un unique diviseur premier (étant donc lui-même un nombre premier) et dressons le diagramme de Hasse de la relation de divisibilité : <BR> [w2ak.treillis.11] <BR> On obtient donc le treillis le plus simple possible, qui est aussi une algèbre de boole.
2 Diviseurs premiers Distincts
Si l'on rajoute un diviseur premier, distinct du précédent, la forme du treillis change : alors que l'on n'aurait qu'une ligne pour 3, on translate cette ligne en ajoutant le diviseur premier 2, pour former 6 = 2 x 3 : <BR> [w2ak.treillis.6]
On remarque que l'on effectue exactement la même opération que pour passer d'une dimension à l'autre : un élément (ligne) translaté selon un nouveau vecteur de base, puis les points similaires reliés entre eux, donnant un nouvel élément (carré) ; c'est le passage de la dimension 1 (comme 1 diviseur premier) à la dimension 2. Ceci se confirmera en effet dans les parties suivantes.
3 Diviseurs premiers Distincts
Etape sur laquelle le groupe est passé plutôt rapidement : un nombre ayant 3 diviseurs premiers distincts, tous à la puissance 1. On obtiendrait d'après, la supposition précédemment énoncée, une représentation d'un cube (dimension 3). <BR> Les diviseurs de 30 = 2 x 3 x 5 sont en effets représentables dans un treillis ayant la forme d'un cube : <BR> [w2ak.treillis.30]
Diviseurs premiers distincts à des puissances supérieures
Graphiquement, l'ajout d'une puissance à un diviseur premier se fait par un « ajout » à une algèbre de Boole, tout en restant dans la même dimension :
Quelques exemples <BR> Diviseurs de 12 = 2² x 3 à partir de 6 = 2 x 3 <BR> [w2ak.treillis.12]
Diviseurs de 90 = 2 x 3² x 5 à partir de 30 = 2 x 3 x 5 <BR> [w2ak.treillis.90]
Diviseurs de 180 = 2² x 3² x 5 à partir de 30 = 2 x 3 x 5 <BR> [w2ak.treillis.180]
Un diviseur premier supplémentaire ... La dimension 4
Les diviseurs d'un nombre ayant quatre diviseurs premiers distincts, tous à la puissance 1, sont réprésentables dans un cube de dimension 4, l'Hypercube.
Un exemple avec les diviseurs de 210:
- 210 = 2 * 3 * 5 * 7 a en effet 4 diviseurs premiers distincts à la puissance 1.
Comprendre la représentation de la 4D de différentes façon : distinguez les deux cubes, chaques sommets correspondants reliés entre eux.
Stages/2011-05-30/w2ak.hypercube_4d-pourtoutlemonde.gif
Représentation de l'hypercube 5D, un grand pas vers la dimension N
Après une translation supplémentaire de l'hypercube, une représentation de l'hypercube 5D a pu être obtenue, de manière tout d'abord légèrement "floue" ...
les premières esquisses de la 5D
...puis plus distincte.
représentations plus claires mais plus compactes
cette avancée a donné envie au groupe d'étudier les caractéristiques (du moins certaines) qu'aurait un cube de dimension N, puis, au delà, un treillis d'un nombre ayant N diviseurs premiers distincts, pas forcément à la puissance 1.
Etude des caractéristiques dans la dimension N
Admettons dans un treillis des diviseurs d'un nombre plusieurs caractéristiques :
On nomme sommet chacun des nombres présents dans le treillis, qui sont aussi les sommets des cubes.
On nomme arrêtes toutes les liaisons existant entre deux nombres (distance de Hamming égale à 1 entre deux nombres).
On nomme rangs r_i ((le symbole "_" permettra de désigner un caractère en indice)) chaque groupe de nombre ayant i diviseurs premiers distincts.
- Exemple: dans le treillis des diviseurs de 30, r_2 représente le groupe de tous les diviseurs de 30 ayant eux même 2 diviseurs premiers distincts, soient 6, 10 et 15. r_0 représente donc "1"
Stages/2011-05-30/w2ak.termes.nd.jpg
Cherchons donc à définir les caractéristiques des treillis dans la dimension N
N diviseurs premiers distincts à la puissance 1
Pour un nombre N ayant n diviseurs premiers distincts à la puissance 1 :
nombre de rangs r_i : n+1 car il faut compter le rang r_0
nombre de sommets total : 2n. Il a été établi qu'en passant d'une dimension à la suivante, on translate la figure. On multiplie par deux le nombre de sommets, à partir de 1 = 20 pour la dimension 0.
nombre de sommets dans chaque rang r_i : c'est le nombre de diviseurs de N ayant tous i diviseurs premiers distincts, soit la combinaison de i diviseurs premiers parmi n (nombre de diviseurs premiers de N) <BR> Stages/2011-05-30/w2ak.dn.f1.jpg
- alignl n(r_i) = C rsup i rsub n newline alignl n(r_i) = left ( {alignc stack { n # i }} right ) newline alignl n(r_i) = {alignc n!} over {alignc i! (n-i)!}
<BR> formule OpenOffice
nombre d'arrêtes, ou de liaisons entre les sommets : n arrêtes partent de chaque sommet. n x 2^n correspond donc au double des arrêtes totale (chaque arrête est en effet comptée deux fois, pour chacune de ses extrémités). On a donc : <BR> Stages/2011-05-30/w2ak.dn.f2.jpg
alignl n(S) = {alignc n times 2n} over {alignc 2} = n times 2{n-1} newline alignl "ou " n(S) = sum from {i=0} to {n} n times left( {alignc stack { i # n }} right)
cette seconde formule a été trouvée de manière différente : pour chaque rang, on ne regarde que les arrêtes partant vers le bas (vers des diviseurs et non des multiples, donc), de sorte que l'on ne compte chaque arrête qu'une seule fois. Les nombres d'un rang r_i ayant i diviseurs premiers distincts, on a i arrêtes partant vers le bas pour chaque sommet du rang, qui comporte n(r_i) sommets. <BR> On multiplie donc le nombre d'arrêtes partant vers le bas pour chaque sommet d'un rang r_i (donc ce nombre est i) par le nombre de sommets du rang (combinaison de i parmi n), puis on effectue la somme pour chaque rang.
Plus loin : puissances supérieures à 1
Nous avons tenté de définir le nombre de sommets d'un treillis qui représenterait les diviseurs d'un nombre N ayant n diviseurs premiers distincts nommés p_i, respectivement à la puissance α_i. <BR> Nous avons donc établi que : Stages/2011-05-30/w2ak.dn.f3.jpg
Explication
Attribuons dans le treillis des diviseurs de 180 = 2²x3²x5 des coordonnées pour chaque point. <BR> On aura donc pour chaque point trois coordonnées pour chaque axe de la dimension 3.
On obtient trois coordonnées pour chaque point, celle de droite correspondant au diviseur premier 2, celle de gauche au diviseur premier 5: <BR> Stages/2011-05-30/w2ak.treillis.coord.gif
Le nombre de sommets dans le treillis correspond au nombre de possibilités de groupe de trois coordonnées, c'est à dire au produit des possibilités pour chaque coordonnée. <BR> Nombre de possibilités pour chaque coordonnée : α_i + 1 (car il faut compter la possibilité du 0). <BR> On obtient donc bien le nombre de sommets en réalisant le produit des (α_i + 1).
