$$ \def\CC{\bf C} \def\QQ{\bf Q} \def\RR{\bf R} \def\ZZ{\bf Z} \def\NN{\bf N} $$

Option Algèbre et Calcul Formel de l'Agrégation de Mathématiques: Groupe Symétrique et groupes de permutations

Ce document dans d'autres formats: feuille de travail, source RST.

Groupe symétrique

Définition

Soit $E$ un ensemble.

On appelle groupe symétrique de $E$ l’ensemble des applications bijectives de $E$ sur $E$ muni de la composition d’applications.

On le note $S_E$.

Exemple:

In [ ]:
G = SymmetricGroup(['a', 'b', 'c'])
G.list()
Out[ ]:
[(), ('b','c'), ('a','b'), ('a','b','c'), ('a','c','b'), ('a','c')]

Pour voir ses éléments comme des fonctions:

In [ ]:
F = FiniteSetMaps(['a','b','c'])
for sigma in G: print F(sigma)
Out[ ]:
map: a -> a, b -> b, c -> c
map: a -> a, b -> c, c -> b
map: a -> b, b -> a, c -> c
map: a -> b, b -> c, c -> a
map: a -> c, b -> a, c -> b
map: a -> c, b -> b, c -> a

Un cas particulier courant est le cas où $E$ est l’ensemble fini $\left\{ 1,\dots,n\right\}$, $n$ étant un entier naturel strictement positif. On note alors $S_n$ le groupe symétrique de cet ensemble. Les éléments de $S_n$ sont appelés permutations et $S_n$ est appelé groupe des permutations d’ordre $n$, ou groupe symétrique d’ordre $n$.

Exemple:

In [ ]:
S3 = SymmetricGroup(3)

Maintenant, si $E$ est un ensemble à $n$ éléments, alors on sait que $S_E$ est isomorphe à $S_n$ :

In [ ]:
G.is_isomorphic(S3)
Out[ ]:
True

En conséquence, il suffit de connaître les propriétés du groupe $S_n$ pour en déduire celles du groupe $S_E$.

Proposition

Le groupe $S_n$ est d’ordre $n!$ .

Exemple:

In [ ]:
SymmetricGroup(3).cardinality()
Out[ ]:
6
In [ ]:
SymmetricGroup(100).cardinality()
Out[ ]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

Permutations

Quelques permutations particulières

  • Une transposition $(i,j)$ est une permutation qui échange $i$ et $j$ et laisse les autres éléments inchangés.
  • Une transposition élémentaire est une transposition de la forme $(i,i+1)$.
  • Un cycle $(c_{1},c_{2},\dots,c_{k})$ est une permutation qui envoie $c_{1}$ sur $c_{2}$, $c_{2}$ sur $c_{3}$, et $c_{k}$ sur $c_{1}$.

Représentation des permutations

In [ ]:
G = SymmetricGroup(8)
sigma = G.random_element()
  • Mot:
In [ ]:
    [sigma(i) for i in range(1,9)]
Out[ ]:
[7, 8, 3, 2, 5, 4, 1, 6]
In [ ]:
    sigma.domain()                            # raccourci mal nommé!
Out[ ]:
[7, 8, 3, 2, 5, 4, 1, 6]
  • Bimot:
In [ ]:
    [(i,sigma(i)) for i in range(1,9)]
Out[ ]:
[(1, 7), (2, 8), (3, 3), (4, 2), (5, 5), (6, 4), (7, 1), (8, 6)]
  • Graphe:
In [ ]:
    DiGraph([(i,sigma(i)) for i in range(1,9)], loops=True).plot()
In [ ]:
    DiGraph([(i,sigma(i)) for i in range(1,9)], loops=True).plot(talk=True)
  • Matrice:
In [ ]:
    sigma.matrix()
Out[ ]:
[0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 1]
[0 0 1 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 1 0 0 0 0]
[1 0 0 0 0 0 0 0]
[0 0 0 0 0 1 0 0]
  • Produit de cycles (voir ci-dessous):
In [ ]:
    sigma
Out[ ]:
(1,7)(2,8,6,4)

Produit de deux permutations

Le produit dans le groupe symétrique est donné par la composition de fonctions: $\sigma\tau = \sigma\circ\tau$. Parfois on préfère l'ordre inverse et on définit: $\sigma \tau = \tau \circ \sigma$.

Exercice

Calculer le produit des permutations suivantes:

In [ ]:
G = SymmetricGroup(3)
sigma = G([2,3,1])
tau   = G([2,1,3])

Correction:

In [ ]:
(sigma * tau).domain()
Out[ ]:
[1, 3, 2]
In [ ]:
(tau * sigma).domain()
Out[ ]:
[3, 2, 1]

Note

Dans Sage, le produit sigma * tau désigne la composée $\tau \circ \sigma$. Sage suit en cela la convention utilisée par le logiciel GAP, inclus dans Sage et à qui Sage délègue de nombreux calculs sur les groupes.

Propositions

  1. Dans le produit $\sigma\tau$, on peut considérer que $\tau$ permute les positions de $\sigma$, tandis que dans le produit $\tau\sigma$, $\tau$ permute les valeurs de $\sigma$ :
In [ ]:
    G = SymmetricGroup(8)
    tau   = G([(3,5)])
    sigma = G([1,5,4,6,8,2,7,3])
    sigma
Out[ ]:
[1, 5, 4, 6, 8, 2, 7, 3]
In [ ]:
    (sigma * tau).domain()
Out[ ]:
[1, 3, 4, 6, 8, 2, 7, 5]
In [ ]:
    (tau * sigma).domain()
Out[ ]:
[1, 5, 8, 6, 4, 2, 7, 3]
  1. Deux cycles disjoints commutent.
  2. Toute permutation se décompose de manière unique comme un produit de cycles (à l’ordre près).

Exercice

  1. Comment calculer l’inverse d’une permutation? Complexité?
  2. Calcul de la décomposition en cycles? Complexité?

Type cyclique

Le type cyclique d’une permutation est la partition de $n$ donnée par les longueurs de ses cycles.

Exemple

In [ ]:
sigma = G.random_element(); sigma
sigma.cycle_type()

Exercices

  1. Que se passe-t-il lorsque l’on conjugue une permutation $\tau$ donnée sous forme de décomposition en cycles par une permutation $\sigma$ (avec pour résultat $\sigma\tau\sigma^{-1}$)? Exemple: prendre $\sigma = (1,2,3,4,5,6,7,8,9)$ et $\tau=(2,5,3)$.
In [ ]:
    sigma = G([(1,2,3,4,5,6,7,8,9)])
    tau   = G([(2,5,3)])
    ~sigma * tau * sigma
  1. Quelles sont les classes de conjugaisons du groupe symétrique?
Conséquence: les représentations du groupe symétrique sont indexées par les partitions.

Générateurs du groupe symétrique

Proposition

  1. $S_n$ est engendré par les cycles.
  2. $S_n$ est engendré par les transpositions.
  3. $S_n$ est engendré par les transpositions élémentaires.
  4. $S_n$ est engendré par la transposition $(1,2)$ et le cycle $(1,\dots,n)$.

Présentation par générateurs et relations

Générateurs: $\tau_{i}=(i,i+1)$.

Relations:

  • $\tau_{i}^{2}=1$,
  • $\tau_{i}\tau_{i+1}\tau_{i}=\tau_{i+1}\tau_{i}\tau_{i+1}$,
  • $\tau_{i}\tau_{j}=\tau_{j}\tau_{i}$ si $\left|i-j\right|>1$.

Le permutoèdre pour $S_3$

Le permutoèdre pour $S_4$

Exemple de lien combinatoire/algèbre: comptage des permutations par niveau et $q$-factorielle

In [ ]:
q = QQ['q'].gen()
1 * (1+q) * (1+q+q^2)
expand( 1 * (1+q) * (1+q+q^2) )
Out[ ]:
q^3 + 2*q^2 + 2*q + 1
In [ ]:
expand( 1 * (1+q) * (1+q+q^2) * (1+q+q^2+q^3) )
Out[ ]:
q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1
In [ ]:
sage.combinat.q_analogues.q_factorial(4)
Out[ ]:
q^6 + 3*q^5 + 5*q^4 + 6*q^3 + 5*q^2 + 3*q + 1

Les $q$-factorielles apparaissent aussi naturellement dans le comptage de sous-espaces vectoriels ou d'applications inversibles sur un corps fini $\mathbb F_q$.

Groupes de permutations

Un groupe de permutations est un groupe donné comme sous-groupe d'un groupe symétrique.

Exemples

  • Groupe trivial.
  • Groupe cyclique $C_n$ :
In [ ]:
    C5 = CyclicPermutationGroup(5); C5
Out[ ]:
Cyclic group of order 4 as a permutation group
In [ ]:
    C5.group_generators()
Out[ ]:
Family ((1,2,3,4,5),)
  • Groupe diédral $D_n$ :
In [ ]:
    D5 = DihedralGroup(5); D5
Out[ ]:
Dihedral group of order 10 as a permutation group
In [ ]:
    D5.group_generators()
Out[ ]:
Family ((1,2,3,4,5), (1,5)(2,4))
  • Groupe alterné $A_n$ :
In [ ]:
    A5 = AlternatingGroup(5); A5
Out[ ]:
Alternating group of order 5!/2 as a permutation group
In [ ]:
    A5.group_generators()
Out[ ]:
Family ((3,4,5), (1,2,3,4,5))
In [ ]:
    A5.is_simple()
  • Tout groupe fini! (théorème de Cayley)

Exercice

Construire le groupe des symétries du cube:

In [ ]:
G = PermutationGroup([...])

Applications:

  • Groupes de symétries d’objets discrets.
  • Comptage d’objets à isomorphie près (Énumération de Pólya; voir TP).
  • Étude des groupes finis.
  • Étude du groupe des permutations des racines d’un polynôme. C'est l’origine du concept de groupe par Évariste Galois.

Systèmes générateurs forts

Problème: Soit $G\subset S_n$ un groupe de permutation; $G$ est typiquement très gros.

  1. Comment le représenter? Le manipuler?
  2. Calculer son nombre d'éléments?
  3. Tester si un élément est dedans?
  4. Exprimer un élément en fonction des générateurs?
  5. Déterminer ses sous-groupes?
  6. Est-il abélien, simple, résoluble, ... ?

Exercice

Soit $H$ le sous groupe des éléments de $G$ qui fixent $n$.

  1. Supposons $|H|$ connu. Comment en déduire $|G|$?
  2. Comment obtenir des représentants des classes de $G/H$?
  3. Supposons que l'on sache tester si une permutation est dans $H$. Comment tester si une permutation est dans $G$?

Définition

On considère la tour de groupes

$$\{ id\}=G_{0}\subset G_{1}\subset\cdots\subset G_n=G,$$

où $G_{i}$ est le sous-groupe des éléments de $G$ qui fixent $\left\{i+1,\dots,n\right\}$.

Pour décrire $G$, il suffit de décrire chacune des inclusions.

Un système générateur fort est composé des représentants des cosets (classes) de $G_{i}/G_{i-1}$ pour chaque $i$.

On abrège système générateur fort en SGS (pour strong generating system).

Exemple

$S_n$ engendré par (toutes) les transpositions.

Proposition

La connaissance d’un système générateur fort permet de résoudre tous les problèmes ci-dessus:

  1. Calcul du nombre d'éléments
  2. Tester si un élément est dedans
  3. ...

Exercices

  1. Construire à la main un système générateur fort pour:
    • le groupe trivial $Id_n$
    • le groupe cyclique $C_{4}$
    • le groupe alterné $A_{4}$
    • le groupe symétrique $S_n$
    • le groupe dihédral $D_{8}$
    • le groupe des symétries du cube agissant sur les sommets.
  2. Donner une borne sur la taille d’un système générateur fort. Comparer avec la taille du groupe.

Correction

In [ ]:
PermutationGroup([], domain=[1,2,3,4]).strong_generating_system(base_of_group=[4,3,2,1])
Out[ ]:
[[()], [()], [()], [()]]
In [ ]:
CyclicPermutationGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
Out[ ]:
[[(1,2,3,4), (1,4,3,2), (), (1,3)(2,4)], [()], [()], [()]]
In [ ]:
AlternatingGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
Out[ ]:
[[(), (1,4,2), (1,4,3), (1,2,4)], [(), (1,2,3), (1,3,2)], [()], [()]]
In [ ]:
DihedralGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
Out[ ]:
[[(1,2,3,4), (1,4,3,2), (), (1,3)(2,4)], [(), (1,3)], [()], [()]]
In [ ]:
SymmetricGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
Out[ ]:
[[(), (1,4), (2,4), (3,4)], [(), (1,2,3), (1,3,2)], [(), (1,2)], [()]]

Définition

Un sous-ensemble $B$ est une base de $G$ si tout élément $g$ dans le groupe est caractérisé par $g(b)$ pour $b$ dans $B$.

Ci-dessus, on a utilisé $B:=\{n,\dots,1\}$, mais la définition de système générateur fort se généralise relativement à n'importe quelle base $B$.

Exercices

  1. Vérifier que $\left\{5,4,3\right\}$ est une base pour $A_{5}$.

Algorithme de Schreier-Sims

Comment calculer un système générateur fort?

  1. Calculer l'orbite $G.n$ de $n$ (comment on fait?)
  2. Les permutations qui envoient $n$ sur $i$, $i$ dans $G.n$ donnent des représentants des cosets de $G/G_n$
  3. Calculer les générateurs de $G_n$ (avec le lemme de Schreier)
  4. Réitérer

Exercice:

Utiliser l’algorithme de Schreier-Sims pour retrouver un SGS pour le groupe des symétries du cube, sachant qu’il est engendré par $\left(0,1,3,7,6,4\right)\left(2,5\right)$ et $\left(0,1,3,2\right)\left(4,5,7,6\right)$.

On peut calculer incrémentalement et efficacement un système générateur fort à partir d’un système générateur quelconque.

Algorithmes dérivés de petite complexité (typiquement $O(n\log(|G|))$). On peut manipuler des groupes de permutations d'ordre plusieurs centaines de milliers.

Exemple:

In [ ]:
S3 = SymmetricGroup(3)
S3.subgroups()
Out[ ]:
[Permutation Group with generators [()], Permutation Group with generators [(2,3)], Permutation Group with generators [(1,2)], Permutation Group with generators [(1,3)], Permutation Group with generators [(1,2,3)], Permutation Group with generators [(1,2), (1,3,2)]]

Synthèse: méthodes d'éliminations

Ce que l'on vient de voir est une idée très générale en calcul algébrique:

On a une structure algébrique:

  • une algèbre de polynômes (univariée/multivariée),
  • un espace vectoriel,
  • un groupe symétrique...

On veut pouvoir calculer avec ses sous-structures $I$ (idéaux, sous-espaces vectoriels, groupes de permutations):

  1. Test d'appartenance d'un élément à $I$,
  2. Test d'égalité de $I$ et de $J$,
  3. Calcul de «taille» de $I$,
  4. ...

Pour cela, on se donne:

  1. Un ordre,
  2. Un drapeau de sous-structures .. TODO:: développer
  3. Un procédé de division: Euclide, ...
  4. Une notion de système générateur fort: PGCD, base de Gröbner, forme échelon, système fort de générateurs,
  5. Un algorithme de calcul d'un tel système: algorithme d'Euclide, de Buchberger, de Gauss, de Schreier-Sims, ...

TP: Énumération de Pólya

Le fichier GroupeSymetrique.py vous donne un point de départ pour les différentes fonctions que vous aurez à implanter dans ce TP. Le fichier GroupeSymetrique-correction.py contient une correction partielle.

La formule d'énumération de Pólya permet de dénombrer des objets discrets considérés modulo certaines symétries. Un des cas les plus simples concerne le dénombrement des colliers à $n$ perles rouges ou bleues, considérés à une rotation près. Par exemple, voilà trois colliers à $n=8$ perles. Les deux premiers sont identiques, mais pas le troisième (on pourrait autoriser le retournement, mais on ne le fera pas dans un premier temps pour simplifier).

Pour refabriquer un de ces dessins, on peut utiliser:

In [ ]:
G = graphs.CycleGraph(8)
G.plot(vertex_colors={"red": [0,2,3,4,5], "blue": [1,6,7]})

Nous allons énoncer cette formule dans le cas général, en l’illustrant au fur et à mesure sur cet exemple.

Exercice préliminaire

Vérifier, en les dessinant tous à la main, qu’il y a $8$ colliers à $n=5$ perles rouges ou bleues. Préciser combien d'entre eux ont $0,1,2,\dots$ perles rouges.

Soit $E$ un ensemble fini (ici $E:=\left\{ 1,\dots,5\right\}$), et $F$ un autre ensemble (ici $F:=\left\{ Rouge,Bleu\right\}$), typiquement fini ou dénombrable. Les objets discrets qui nous intéressent sont les fonctions de $E$ dans $F$ (ici les colliers où on a fixé la première perle). Pour modéliser des symétries sur $E$ (ici on veut considérer que deux colliers qui sont identiques à rotation près sont identiques), on introduit un sous-groupe $G$ du groupe symétrique $S_E$ (ici le groupe cyclique $G:=C_{5}=\left\langle (1,\dots,5)\right\rangle$). Ce groupe agit sur l’ensemble des fonctions $F^{E}$ par $\sigma\cdot f:=f\circ\sigma^{-1}$, où $\sigma\in G$ et $f\in F^{E}$. Deux fonctions $f$ et $g$ sont dites isomorphes s’il existe une permutation $\sigma$ dans $G$ telle que $f=\sigma.g$ (ici, deux colliers sont isomorphes s’ils sont identiques à rotation près).

Notre objectif est de compter le nombres de classes d’isomorphie. Cela peut être fait via le Lemme de Burnside. Nous allons directement énoncer une version raffinée de cette formule, due à Pólya, afin de compter les colliers selon leur nombre de perles rouges. Pour cela, nous allons associer à chaque élément $c$ de $F$ un poids $w(c)$ multiplicatif, et associer à chaque fonction $f$ dans $F^{E}$ le poids $w\left(f\right)=\prod_{e\in E}w(f(e))$. Ce poids est constant sur une classe d’isomorphie $\overline{f}$, ce qui permet de définir $w\left(\overline{f}\right)$. Considérons maintenant la somme $\sum_{\overline{f}}w\left(\overline{f}\right)$ des poids de toutes les classes d’isomorphie. Si $w\left(c\right)=1$ pour tout $c$ dans $F$, cette somme donne le nombre de classes d’isomorphies, c’est-à-dire $8$ dans notre exemple. Si $w(Rouge)=1$ et $w(Bleu)=q$, on obtient:

$$\sum_{\overline{f}}w\left(\overline{f}\right) = 1+q+2q^{2}+2q^{3}+q^{4}+q^{5},$$

qui indique en particulier qu’il y a deux colliers avec respectivement deux ou trois perles rouges, et un collier avec respectivement une, deux, quatre, ou cinq perles rouges. On notera que le rôle joué par les éléments de $F$ (ici les couleurs rouges et bleues) sont parfaitement symétriques; cela rend relativement naturelle l'introduction des polynômes symétriques suivantes:

$$p_{k} := \sum_{c\in F} w(c)^{k}$$

qui énumèrent les objets de $F$ répétés $k$ fois.

Nous pouvons maintenant énoncer la fameuse formule de Pólya. La seule information dont l’on a besoin sur le groupe est en fait le type cyclique $l(c)$ de chacun de ses éléments:

$$\sum_{\overline{f}}w\left(\overline{f}\right) = \frac{1}{\left|G\right|}\sum_{\sigma\in G}\; \prod_{k\in l(\sigma)}p_{k}$$

Précision: dans le produit $\prod_{k\in l(\sigma)} p_k$, on tient compte des répétitions; si $\sigma$ a trois cycles de longueur $k$, alors $p_k$ est élevé à la puissance trois.

Indication pour l'ensemble des exercices: Sage (comme MuPAD ou Maple) contiennent un certain nombre de fonctions prédéfinies pour manipuler les groupes de permutations (voir PermutationGroup), dont la formule de Pólya; à vous de choisir ce que vous réimplantez ou pas selon ce que vous avez le plus besoin de comprendre.

Exercice: comptage de colliers

  1. Écrire une fonction p(k,poids) qui calcule $p_{k}$ à partir de la liste des poids des éléments de $F$.
  2. La formule de Pólya requiers de calculer le type cyclique d'une permutation.
    • Option 1: (Sage >= 7.5) utilisez directement la méthode sigma.cycle_type() et passer directement à la suite.
    • Option 2: Implanter une fonction type_cyclique(sigma) qui calcule le type cyclique d’une permutation sigma à partir de la méthode cycle_tuples des permutations.
    • Option 3: Implanter l'algorithme de recherche des cycles, mais en stockant uniquement leur taille. Indications:
In [ ]:
        G = DihedralGroup(10)
        g = G.an_element(); g
Out[ ]:
(1,2,3,4,5,6,7,8,9,10)
In [ ]:
        g.parent().domain()
Out[ ]:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
    et utiliser un ensemble (set) pour noter les éléments du domaine déjà croisés.
  1. Lister les permutations de $C_{5}$.
  2. Écrire la formule ci-dessus pour $poids=[1,1]$.
  3. Écrire une fonction Polya(G, poids) implantant la formule ci-dessus pour un groupe $G$ et des poids quelconques.
  4. Compter le nombre de colliers bicolores à dix perles selon leur nombre de perles rouges.
  5. Compter le nombre de colliers à dix perles de trois couleurs.

Exercice: comptage de colliers (suite)

Variante sur l’exercice précédent: on veut maintenant aussi considérer comme identiques deux colliers qui ne diffèrent que d’un retournement. Compter le nombre de tels colliers à trois perles bleues et deux perles rouges.

Indication: considérer le groupe diédral $D_{5}$ des symétries du pentagone.

Exercice: colorations du cube

Compter le nombre de cubes que l’on peut obtenir en peignant leurs faces en au plus trois couleurs.

Indications:

  1. Numéroter les faces, considérer le groupe des isométries positives du cube, comme groupe de permutations de ses faces.
  2. Déterminer les générateurs de ce groupe (par exemple sous forme de produit de cycles).
  3. Construire le groupe dans Sage en utilisant PermutationGroup.
  4. Poursuivre comme ci-dessus.

Exercice: énumération des graphes (plus avancé)

Construire à la main les $11$ graphes simples non orientés sur $4$ sommets non étiquetés. Puis recalculer leur nombre grâce à la formule de Pólya. Compter le nombre de graphes simples à $5,6,7,8,9,10,\ldots$ sommets.

Indications:

  1. Un graphe simple non orienté sur $n$ sommets peut être considéré comme une fonction allant de l’ensemble des paires $\{i,j\}$ de $\{1,\dots,n\}$ dans $\{0,1\}$ ($1$ s’il y a une arête entre $i$ et $j$, et $0$ sinon).
  2. On numérote les paires $\{i,j\}$ de $1$ à $\binom{n}{2}$. Le groupe $G$ est le groupe des permutation des paires induites par les $n!$ permutations des sommets dans $S_n$. On peut donc rechercher quelles permutations des paires sont induites par l’échange des sommets $1$ et $2$ et par la permutation cyclique $(1,2,3,\dots,n)$ des sommets; le groupe $G$ est alors engendré par ces deux permutations, et l’on peut poursuivre comme dans l’exercice précédent.
  3. Au delà de $n=7$ le calcul devient long à cause de la somme sur le groupe. Pour aller plus loin, on peut regrouper dans la formule de Pólya les permutations ayant le même type cyclique. Pour cela, il faut pouvoir compter le nombre de permutations dans $S_n$ ayant un type cyclique donné, et pouvoir calculer le type cyclique d’une permutation des arêtes dans $G$, connaissant le type cyclique de la permutation des sommets correspondant dans $S_n$.

Exercice: énumération des multigraphes (plus avancé)

Un multigraphe est un graphe dans lequel il peut y avoir un nombre quelconque d’arêtes entre deux sommets. Calculer la série génératrice par nombre d’arêtes des graphes sur 4,5,6 sommets. Indication: ici, $F$ est composé des entiers $\left\{0,1,2,\dots\right\}$ auxquels on peut attribuer les poids $\left\{ 1,q,q^{2},\dots\right\}$; on peut alors mettre $p_{k}:=1^{k}+q^{k}+q^{2k}+\cdots$ sous la forme $p_{k}=\frac{1}{1-q^{k}}$.

Exercice (plus avancé)

  1. Consulter la documentation et le code de la méthode cycle_index des groupes de permutations
C'est l'un de vos prédécesseurs qui l'a implantée!
  1. Utilisez-la pour recalculer les exemples précédents.
  2. Est-elle plus ou moins performante que votre implantation?
  3. Comment fonctionne-t-elle?

TP: Systèmes générateurs forts

On supposera pour simplifier que l'on travaille avec un groupe de permutations $G$ de $\{1,\dots,n\}$ et que la base est $n,n-1,\dots,1$.

On représentera un système générateur fort de $G$ sous la forme d'une liste $l$ telle que $l[i-1]$ contient des représentants des cosets de $G_i/G_{i-1}$. Ces représentants seront représenté sous la forme d'un dictionnaire associant à chaque élément $y$ de l'orbite de $i$ sous $G_i$ une permutation $\sigma_{i,y}$ de $G_i$ telle que $\sigma_{i,y}(i)=y$.

Pour le groupe symétrique $S_3$, cela donnerait:

In [ ]:
S = SymmetricGroup(3)
sgf = [ {1: S.one()},
        {1: S([(1,2)]), 2: S.one()},
        {1: S([(1,3)]), 2: S([(2,3)]), 3: S.one()} ]

Exercice

Construisez dans Sage les systèmes générateurs forts des groupes $C_4$, $D_4$, $A_4$, et du groupe des symétries du cube.

Comparez avec le système générateur fort calculé par Sage (en fait GAP).

Exercice: Utilisation des systèmes générateurs forts

Implanter des procédures qui, étant donné un système générateur fort d’un groupe $G$, permettent de:

  1. Calculer la taille du groupe,
  2. Calculer la liste des éléments du groupe,
    • Indication: récursion
    • Variante (avancé): implanter un itérateur
  3. Tester si une permutation donnée appartient au groupe.

Exercice: Calcul des systèmes générateurs forts

Implanter l’algorithme de Schreier-Sims pour calculer un système générateur fort d’un groupe de permutations donné par des générateurs.

Indication: Implanter d'abord une méthode transversal(generateurs, i) qui calcule l'orbite de $i$ sous l'action des générateurs avec, pour chaque élément $i$ de l'orbite, une permutation envoyant $i$ sur $y$.

Quelques références