Ce document dans d'autres formats: feuille de travail, source RST.
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:
G = SymmetricGroup(['a', 'b', 'c'])
G.list()
Pour voir ses éléments comme des fonctions:
F = FiniteSetMaps(['a','b','c'])
for sigma in G: print F(sigma)
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:
S3 = SymmetricGroup(3)
Maintenant, si $E$ est un ensemble à $n$ éléments, alors on sait que $S_E$ est isomorphe à $S_n$ :
G.is_isomorphic(S3)
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:
SymmetricGroup(3).cardinality()
SymmetricGroup(100).cardinality()
G = SymmetricGroup(8)
sigma = G.random_element()
[sigma(i) for i in range(1,9)]
sigma.domain() # raccourci mal nommé!
[(i,sigma(i)) for i in range(1,9)]
DiGraph([(i,sigma(i)) for i in range(1,9)], loops=True).plot()
DiGraph([(i,sigma(i)) for i in range(1,9)], loops=True).plot(talk=True)
sigma.matrix()
sigma
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:
G = SymmetricGroup(3)
sigma = G([2,3,1])
tau = G([2,1,3])
Correction:
(sigma * tau).domain()
(tau * sigma).domain()
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
G = SymmetricGroup(8)
tau = G([(3,5)])
sigma = G([1,5,4,6,8,2,7,3])
sigma
(sigma * tau).domain()
(tau * sigma).domain()
Exercice
Le type cyclique d’une permutation est la partition de $n$ donnée par les longueurs de ses cycles.
Exemple
sigma = G.random_element(); sigma
sigma.cycle_type()
Exercices
sigma = G([(1,2,3,4,5,6,7,8,9)])
tau = G([(2,5,3)])
~sigma * tau * sigma
Conséquence: les représentations du groupe symétrique sont indexées par les partitions.
Proposition
Générateurs: $\tau_{i}=(i,i+1)$.
Relations:
q = QQ['q'].gen()
1 * (1+q) * (1+q+q^2)
expand( 1 * (1+q) * (1+q+q^2) )
expand( 1 * (1+q) * (1+q+q^2) * (1+q+q^2+q^3) )
sage.combinat.q_analogues.q_factorial(4)
Les $q$-factorielles apparaissent aussi naturellement dans le comptage de sous-espaces vectoriels ou d'applications inversibles sur un corps fini $\mathbb F_q$.
Un groupe de permutations est un groupe donné comme sous-groupe d'un groupe symétrique.
C5 = CyclicPermutationGroup(5); C5
C5.group_generators()
D5 = DihedralGroup(5); D5
D5.group_generators()
A5 = AlternatingGroup(5); A5
A5.group_generators()
A5.is_simple()
Exercice
Construire le groupe des symétries du cube:
G = PermutationGroup([...])
Problème: Soit $G\subset S_n$ un groupe de permutation; $G$ est typiquement très gros.
Exercice
Soit $H$ le sous groupe des éléments de $G$ qui fixent $n$.
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:
Exercices
Correction
PermutationGroup([], domain=[1,2,3,4]).strong_generating_system(base_of_group=[4,3,2,1])
CyclicPermutationGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
AlternatingGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
DihedralGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
SymmetricGroup(4).strong_generating_system(base_of_group=[4,3,2,1])
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
Comment calculer un système générateur fort?
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:
S3 = SymmetricGroup(3)
S3.subgroups()
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:
On veut pouvoir calculer avec ses sous-structures $I$ (idéaux, sous-espaces vectoriels, groupes de permutations):
Pour cela, on se donne:
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:
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.
p(k,poids)
qui calcule $p_{k}$ à partir de la liste des poids des éléments de $F$.sigma.cycle_type()
et passer directement à la suite.type_cyclique(sigma)
qui calcule le type cyclique d’une permutation sigma
à partir de la méthode cycle_tuples des permutations. G = DihedralGroup(10)
g = G.an_element(); g
g.parent().domain()
et utiliser un ensemble (set) pour noter les éléments du domaine déjà croisés.
Polya(G, poids)
implantant la formule ci-dessus pour un groupe $G$ et des poids quelconques.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.
Compter le nombre de cubes que l’on peut obtenir en peignant leurs faces en au plus trois couleurs.
Indications:
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:
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}}$.
C'est l'un de vos prédécesseurs qui l'a implantée!
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:
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:
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$.