Travaux pratiques
2. Écrire des fonctions OrbiteSn et OrbiteAn renvoyant respectivement, en fonction de n, les orbites pour l’action naturelle de S n et A n sur X n = {1, . . . , n}.
Vérifier que l’action est transitive pour 3 n 8.
Quel est le temps de calcul pour S 8 ? Comparer en calculant l’orbite de 1 avec
la commande Maple orbit.
3. La lenteur de la procédure orbite provient du fait que l’on calcule au préalable
tous les éléments du groupe. On peut s’en passer, en travaillant intelligemment
avec le système S de générateurs du groupe G. Ainsi, pour calculer l’orbite de i,
on procède comme suit :
(a) Initialisation : O := {i}.
(b) On fait agir les éléments de S : s’il n’en résulte aucun nouvel élément,
c’est terminé ; sinon, soit N l’ensemble de ces nouveaux éléments.
(c) On met à jour O := O ∪ N .
(d) On fait agir les éléments de S sur N (plutôt que sur O tout entier) : s’il
n’en résulte aucun nouvel élément, c’est terminé. Sinon, on met à jour N
comme l’ensemble de ces nouveaux éléments qui ne sont pas déjà dans O,
puis on applique (c).
Implémenter cet algorithme au sein d’une procédure
orbite_i:=proc(G,i,action)
renvoyant l’orbite de i pour l’action de G définie par action, puis modifier
la procédure orbite afin qu’elle utilise orbite_i. Enfin, récolter les fruits en
testant, sur S 8 par exemple, l’amélioration du temps de calcul.
4. Écrire une fonction OrbiteG renvoyant, en fonction du groupe de permutations
G (qui sera toujours introduit comme un permgroup), la liste des orbites pour
l’action naturelle de G. Comme application, déterminer tous les groupes de
permutations transitifs de degré 3 (i.e. les sous-groupes de S 3 agissant transitivement sur X 3 ). Vérifier également la transitivité de l’action pour les groupes
suivants :
L[1]:=permgroup(4,{[[1,2,3,4]]}):
L[2]:=permgroup(4,{[[1,2,3,4]],[[1,2]]}):
L[3]:=permgroup(4,{[[1,2,3,4]],[[1,3]]}):
L[4]:=permgroup(4,{[[1,2],[3,4]],[[1,3],[2,4]]}):
L[5]:=permgroup(4,{[[1,2,3]],[[1,2],[3,4]]}):\vspace*{-1mm}
On peut démontrer qu’il s’agit là de tous les groupes transitifs de degré 4 (à
conjugaison près).
109
2. Écrire des fonctions OrbiteSn et OrbiteAn renvoyant respectivement, en fonction de n, les orbites pour l’action naturelle de S n et A n sur X n = {1, . . . , n}.
Vérifier que l’action est transitive pour 3 n 8.
Quel est le temps de calcul pour S 8 ? Comparer en calculant l’orbite de 1 avec
la commande Maple orbit.
3. La lenteur de la procédure orbite provient du fait que l’on calcule au préalable
tous les éléments du groupe. On peut s’en passer, en travaillant intelligemment
avec le système S de générateurs du groupe G. Ainsi, pour calculer l’orbite de i,
on procède comme suit :
(a) Initialisation : O := {i}.
(b) On fait agir les éléments de S : s’il n’en résulte aucun nouvel élément,
c’est terminé ; sinon, soit N l’ensemble de ces nouveaux éléments.
(c) On met à jour O := O ∪ N .
(d) On fait agir les éléments de S sur N (plutôt que sur O tout entier) : s’il
n’en résulte aucun nouvel élément, c’est terminé. Sinon, on met à jour N
comme l’ensemble de ces nouveaux éléments qui ne sont pas déjà dans O,
puis on applique (c).
Implémenter cet algorithme au sein d’une procédure
orbite_i:=proc(G,i,action)
renvoyant l’orbite de i pour l’action de G définie par action, puis modifier
la procédure orbite afin qu’elle utilise orbite_i. Enfin, récolter les fruits en
testant, sur S 8 par exemple, l’amélioration du temps de calcul.
4. Écrire une fonction OrbiteG renvoyant, en fonction du groupe de permutations
G (qui sera toujours introduit comme un permgroup), la liste des orbites pour
l’action naturelle de G. Comme application, déterminer tous les groupes de
permutations transitifs de degré 3 (i.e. les sous-groupes de S 3 agissant transitivement sur X 3 ). Vérifier également la transitivité de l’action pour les groupes
suivants :
L[1]:=permgroup(4,{[[1,2,3,4]]}):
L[2]:=permgroup(4,{[[1,2,3,4]],[[1,2]]}):
L[3]:=permgroup(4,{[[1,2,3,4]],[[1,3]]}):
L[4]:=permgroup(4,{[[1,2],[3,4]],[[1,3],[2,4]]}):
L[5]:=permgroup(4,{[[1,2,3]],[[1,2],[3,4]]}):\vspace*{-1mm}
On peut démontrer qu’il s’agit là de tous les groupes transitifs de degré 4 (à
conjugaison près).
109