Groupe symétrique

jp59

Bonjour,
voici quelques résultats sur le groupe symétrique.
voici la démonstration du théorème 5

Dans la partie "existence", l'auteur considère la restriction d'une permutation quelconque (différente de l'identité) à chacune de ces orbites. Il définit r restrictions de sigma réduites à leurs orbites et affirment que ce sont r cycles grâce à la proposition 4 ci-dessus.
1) Restriction ici, au sens précis de "restriction de permutation", a-t-il le même sens que pour une restriction de fonction "classique" ? Rien ne semble indiquer le contraire en faisant une rapide recherche Google.
2) En admettant qu'il s'agit de la même chose, comment peut-on définir les ci comme des cycles ? Un cycle est défini sur (1,n) entier. Or ici les ci sont des restrictions sur des orbites (ceux au cardinal au moins égal à 2), donc, par définition d'une restriction, ne sont pas définis au delà de ces orbites qui ne couvrent pas tout (1,n). Or, par définition, un cycle est une permutation qui fixe les points exclus de son support. Pourquoi les ci fixent les points hors de leurs orbites ?
Merci d'avance pour vos éclaircissements sur ce point sur lequel j'ai l'impression de passer complétement à côté.

Heuristique

$\newcommand{\S}{\mathfrak{S}}$Bonjour,

L'auteur fait ici un abus très courant sur les restrictions d'une permutation : tout le monde le fait, c'est normal quand on est habitué mais je t'accorde que ça peut faire bizarre au premier abord !

Soit $\sigma \in \S_n$ une permutation et $I$ un ensemble stable par $\sigma$ (typiquement, une orbite). On peut alors considérer  la restriction de $\sigma$ à $I$ que l'on note $\sigma_I$.

On peut, à première vue, voir $\sigma_I$ comme un élément de $\S(I)$ (c'est le sens classique de la restriction).

Comme on travaille dans $\S_n$ plutôt que dans $\S(I)$, on peut aussi voir $\sigma_I$ comme une permutation de $[[1,n]]$ qui agit comme $\sigma$ sur $I$ et comme l'identité sur $[[1,n]] \setminus I$ : si $I$ est une orbite, on est donc bien dans le cas d'un cycle.

Ici, l'auteur utilise le "second sens" du mot "restriction" qui est courant quand on parle de permutations.

PS : au passage, le théorème et sa preuve sont également valables pour l'identité. 

jp59

Bonjour,
Merci pour cette explication limpide!
Petite question supplémentaire : dans la dernière partie de la partie "existence", voici ce qu'écrit l'auteur 
On sait que x n'est pas invariant par sigma. OK ça signifie qu'il appartient au support d'un cycle dont le cardinal du support est supérieur à 2.

Mais comment sait-on que l'évaluation de x par ce cycle (ci0) est égale à l'évaluation de sigma en x ? Autrement dit, la dernière égalité de l'avant dernière ligne n'a rien d'évident pour moi.

Pourriez-vous, svp, éclairer ce point ?

Merci

Positif

Parce que deux classes d'équivalences sont disjointes, sinon elles sont égales. Le $x$ ne laisse donc qu'une seule permutation NON-invariante. Ici il l'appelle le cycle numéro $i_0$, et tous les autres cycles sont invariantes par $x$ dans le sens ou $\mathrm{cycle}(x) = x$ (pour les cycles qui constituent les classes d'équivalences de $\sigma$ par $\mathcal{R}$.

jp59

Merci pour cette réponse.

Je ne suis pas sûr de bien comprendre. Bien entendu, les cycles étant à support disjoints, et les orbites formant une partition de (1;n), par définition (en tant que classse d'équivalence de R), il n'y a qu'un seul cycle par lequel x est invariant.

Cela ne me semble pas signifier pour autant, sauf erreur, qu'il n'y ait qu'une image possible pour l'évaluation par un élément invariant.

Par exemple dans le groupe symétrique indice 3 (désolé pour la notation), si on pose x=2, on a bien 2 images possibles dans l'évaluation par 2, qui ne sont pas 2, en l'occurence 1 et 3.
Or,  ici, lorsqu'on écrit ci0(x)=sigma(x), cela suggère, sauf, erreur, qu'"il n'y a qu'une seule permutation dans le groupe symétrique tout entier qui invarie" x or ciO "invarie" x donc sigma(x)=ci0(x)" mais la première partie (en gras) de la proposition me paraît fausse dans la mesure où pour un x quelconque fixé invariant par une permutation, d'autres permutations évaluées en ce même point peuvent différés de lui-même sans pour autant être égale à l'image de la première par ce fameux point (j'espère que c'est clair).

Merci d'avance !

JLapin

$c_{i_0}$ est précisément défini comme le cycle << restriction de $\sigma$ à l'orbite qui contient $x$ >> donc $c_{i_0}(x)=\sigma(x)$.

jp59

Bien sûr, merci JLapin.
Je reviens à la charge avec une autre question. Voici ce qu'écrit l'auteur, 
Voici le corollaire 8 de la page 1231 :


La proposition 12 est donnée telle quelle sans démonstration plus approfondie. Cela n'a rien d'une évidence pour moi.
Quelqu'un pourrait-il détailler le passage du cas des transpositions à la généralisation pour tout type de permutation (proposition 12) ?
Merci d'avance

JLapin

Essaye de le faire dans le cas où  $\sigma = \tau_1\circ \tau_2$ pour commencer.

jp59

Avec une récurrence sur le nombre de transpositions dans la décomposition de la permutation et en utilisant le fait que la signature est un morphisme dans l'hérédité, on arrive bien à ce résultat.

Merci

JLapin

oui

jp59

Bonjour,
nouvelle question sur la partie "unicité" de la preuve. L'entier x, a, par définition, la même image par sigma et par cj et donc l'orbite de x par ces applications est la même. Mais pourquoi l'auteur peut-il affirmer que cj est bien le cycle (x, sigma(x),...,sigma^pj-1(x)) ? Pourriez-vous détailler ce passage? Cela n'est pas évident pour moi. Pj est l'ordre du cycle cj c'est-à-dire le cardinal de son support, je ne vois pas pour quelle raison pj apparaît ici.
L'enchaînement sur l'unicité du nombre de cycles et le fait qu'il ne s'agit des restrictions de sigma non réduit à un point n'est pas clair non plus.

Pourriez-vous détailler ce passage ?

Merci d'avance

NicoLeProf

Pour répondre à ta première question : par définition, l'orbite de $x$ selon $c_j$ est $\{x,c_j(x),...,c_j^{p_j-1}(x) \}$ car $c_j$ est d'ordre $p_j$ donc $c_j^{p_j}(x)=x$ et pour tout $1 \leq n <p_j$, $c_j^{n}(x) \neq x$ . Mais l'auteur a prouvé avant que $\sigma(x)=c_j(x)$ donc $\sigma^2(x)=c_j^2(x)$ et ainsi de suite. (Les orbites coïncident) donc on peut remplacer tous les $c_j$ par des $\sigma$ et l'orbite de $x$ selon $\sigma$ est $\{x,\sigma(x),...,\sigma^{p_j-1}(x) \}$ . Donc $c_j$ est bien le cycle $(x,\sigma(x),..., \sigma^{p_j-1}(x))$ . En effet, si $\sigma^{p_j}(x) \neq x$ alors on aurait $c_j^{p_j}(x) \neq x$ ce qui contredit le fait que $p_j$ est l'ordre de $c_j$ .

Ce que je comprends ensuite est que comme on a fixé une permutation $\sigma$ dès le début donc entièrement déterminée et que l'on trouve que $c_j$ est le cycle $(x,\sigma(x),..., \sigma^{p_j-1}(x))$ pour tout $j \in \{1,...,r\}$, chaque cycle $c_j$ est entièrement déterminé en fonction du cycle $\sigma$ donc chaque cycle $c_j$ est unique. Autrement dit, si nous faisons exactement le même procédé avec un cycle $c_{j'}$ : si nous supposons qu'il existe un autre cycle $c_{j'}$ tel que $c_{j'}(x) \neq x$, nous allons trouver que $c_{j'}$ est le cycle $(x,\sigma(x),...,\sigma^{p_{j'}-1}(x))$ sauf que les cycles sont à supports $2$ à $2$ disjoints donc nécessairement $c_j=c_{j'}$ et $j=j'$ du coup (c'est comme cela que j'aurais rédigé d'ailleurs)  .

Ceci étant valable pour tout $j$ de $\{1,...,r\}$, à chaque fois que l'on suppose qu'il existe un cycle $c_{j'}$ tel que $c_{j'}(x) \neq x$, on prouve que $j'=j$ . Ceci permet d'avoir l'unicité de $r$ (il y a exactement $r$ cycles ici dans la décomposition de $\sigma$).

C'est, en tout cas, comme cela que je comprends les choses. Je laisse les autres contributeurs et contributrices corriger mes propos si nécessaire. ^^'

OShine

Cette démonstration du théorème 5 n'est pas claire du tout, j'avais ouvert un fil sur cette même preuve car je ne la comprenais pas.
Plusieurs personnes m'avaient dit qu'elle manquait de clarté.
Je te conseille de changer de livre. 

Ce tout en un est une usine à gaz dans certaines preuves, j'ai perdu plusieurs heures à essayer de comprendre des preuves alors qu'en prenant un autre livre je la comprenais en 5 minutes.

jp59

@Nico le prof
merci pour l'explicitation et l'unicité de r. Mais comment l'auteur justifie que les cycles ont pour support les orbites non réduites à un point de sigma ?

@OShine
pour ma part, j'aime beaucoup ce livre car je trouve qu'il permet de constituer des bases solides et qu'il a le souci de ne jamais expliquer une notion A avec une notion B qui elle-même nécessite la notion A comme c'est souvent le cas. J'apprécie beaucoup ce livre. N'étant pas assez calé en maths, j'imagine qu'il est perfectible, quel type de livre conseillerais-tu pour avoir un cours aussi solide ? 
C'est tout de même un livre co-écrit par Claude Deschamps, prof de maths en MP* à LLG et qui a fait entrer 700 étudiants à l'X. J'imagine qu'il ne fait pas des preuves "usine à gaz". Le deuxième auteur est le prof de maths de la MP* de Ginette...c'est compliqué de trouver meilleur j'imagine..

OShine

Il n'est pas adapté à tout le monde, je dirai que c'est un livre pour les personnes très fortes en maths. Les élèves qui visent X-ENS. 

Les exercices de fin de chapitre sont pour 80 % d'entre eux infaisables (pour les personnes qui ont un niveau moyen). C'est décourageant de passer sa vie à lire des corrigés car on arrive à résoudre aucun exercice. 
Certaines exercices difficiles sont corrigés trop succinctement.

Certaines démonstrations manquent de clarté, ou sont trop compliquées. Le cours contient trop de choses, c'est un peu difficile de retenir l'essentiel. 

Les points forts du livre sont qu'il est très complet, tout est démontré et qu'il y a énormément d'exemples.

J'ai mis 1 an et demi pour terminer le livre en essayant de comprendre chaque détail. 

NicoLeProf

@jp59 c'est ce que j'ai écrit plus haut non ? L'orbite de $x$ selon $c_j$ est $\{x,c_j(x),...,c_j^{p_j-1}(x) \}$ et pour tout entier $0 \leq n \leq p_j-1$, les $c_j^n(x)$ sont deux à deux distincts sinon cela contredirait le fait que $p_j$ est l'ordre du cycle $c_j$ . Donc les orbites ne sont pas réduites à un point. Il en de même pour les $\sigma^n(x)$ avec les mêmes conditions sur $n$ vu ce qu'on a prouvé précédemment.

Enfin, je crois comprendre les choses comme ça...

Peut-être qu'une autre personne pourra expliquer les choses plus clairement.

JLapin

@NicoLeProf

Je tente quelque chose.

Prenons une permutation $\sigma$ qui n'est pas l'identité.

Notons $R_\sigma$ la relation d'équivalence sur $[1,n]$ associée et $(\Omega_i)_{i\in I}$ la partition de $[1,n]$ associée à cette relation d'équivalence.

Ensuite, notons $\sigma=c_1...c_p$ une décomposition de $\sigma$ en produit de cycles à supports disjoints.

Vérifions d'abord que le support de $c_1$ est l'un des $\Omega_i$.

Fixons $a$ dans le support de $c_1$.

Alors $a$ appartient à un certain $\Omega_i$ (puisque la famille constitue une partition).

Vérifions donc que le support de $c_1$ est effectivement $\Omega_i$, par double inclusion.

Soit $x$ dans le support de $c_1$. Alors, $x=c_1^k(a)$ pour un certain $k$, puis $x=\sigma^k(a)$ (puisque $\sigma$ et $c_1$ coïncident sur le support de $c_1$), donc $x$ est en relation avec $a$ puis $x\in cl(a)=\Omega_i$.

Réciproquement, soit $x$ dans $\Omega_i$. Alors $x$ est en relation avec $a$, donc $x=\sigma^k(a)$ pour un certain $k$, puis $x=c_1^k(a)$ puis $x$ appartient au support du cycle $c_1$.

Ensuite, pour tout $x\in \Omega_i$, on a $c_1(x)=\sigma(x)$ et donc $c_1$ est nécessairement la restriction de $\sigma$ à $\Omega_i$.

De même, chaque $c_j$ est la restriction de $\sigma$ à un certain $\Omega_{i_j}$ non réduit à un singleton.

Enfin, supposons qu'il existe un $\Omega_i$ non trivial qui ne soit pas "touché" par la construction précédente. Alors un élément $a\in \Omega_i$ n'appartient à aucun des supports des $c_j$, donc $\sigma(a)=a$ : absurde.

Ainsi, à l'ordre près, les $c_1,...,c_p$ sont exactement les restrictions de $\sigma$ aux $\Omega_i$ non triviaux. Fin de la preuve de l'unicité.

GG

Si je puis me permettre, je trouve un peu curieux la manière restrictive dont l'auteur de ce texte introduit les premières définitions, car après tout ce sont des notions générales valables pour toutes les actions de groupe. Si le groupe $G$ agit sur l'ensemble $E$, la relation $\exists g \in G (y = g.x)$ est une relation d'équivalence sur $E$ dont les classes s'appellent les orbites de $E$ (sous l'action de $G$).

Ensuite bien sûr, le groupe de permutations $\mathfrak S_n$ agit canoniquement sur $[1, n]$ par $\sigma .x = \sigma(x)$ et l'on nomme par abus de langage orbites de $\sigma$ les orbites de $[1, n]$ sous l'action du sous-groupe $<\sigma>$ engendré par $\sigma$.

En appelant cycle une permutation possédant exactement une orbite à plus d'un élément, on vérifie que cette définition est équivalente à la définition usuelle d'un $k$-cycle $(c_1 c_2 .. c_k)$, dont le support est précisément cette orbite, composée des éléments $c_i$.

Pour chaque orbite à plus d'un élément d'une permutation $\sigma$, le prolongement à $[1, n]$ de la restriction de $\sigma$ à cette orbite, laissant fixes les points hors de l'orbite, est visiblement un cycle ayant cette orbite pour support et le produit, commutatif, de ces cycles à supports disjoints n'est autre que $\sigma$. En outre, cette décomposition est unique, à l'ordre des facteurs près, puisque deux telles décompositions ont les mêmes orbites, à savoir celles de $\sigma$, et que les deux cycles associés à une orbite à plus d'un élément, l'un facteur de la première décomposition, l'autre de la seconde, sont les mêmes car leurs restrictions à cette orbite coïncident avec celle de $\sigma$.

Barry

jp59 a dit :

@Nico le prof
merci pour l'explicitation et l'unicité de r. Mais comment l'auteur justifie que les cycles ont pour support les orbites non réduites à un point de sigma ?

@OShine
pour ma part, j'aime beaucoup ce livre car je trouve qu'il permet de constituer des bases solides et qu'il a le souci de ne jamais expliquer une notion A avec une notion B qui elle-même nécessite la notion A comme c'est souvent le cas. J'apprécie beaucoup ce livre. N'étant pas assez calé en maths, j'imagine qu'il est perfectible, quel type de livre conseillerais-tu pour avoir un cours aussi solide ? 
C'est tout de même un livre co-écrit par Claude Deschamps, prof de maths en MP* à LLG et qui a fait entrer 700 étudiants à l'X. J'imagine qu'il ne fait pas des preuves "usine à gaz". Le deuxième auteur est le prof de maths de la MP* de Ginette...c'est compliqué de trouver meilleur j'imagine..

C'est vrai ce que tu dis sur ces auteurs, mais regardons ce qui est dit sur le livre : "les notions du programme sont abordées dans le strict respect des textes officiels, à jour des programmes 2021".  Comme si à LLG et Ginette, le cours était enseigné dans le strict respect du programme...

OShine

@GG
Il n'y a pas d'action de groupes au programme de MPSI.

NicoLeProf

@JLapin, je pense avoir compris ta démonstration.

Pour l'auteur, je tente une reformulation complète avec mes mots de l'unicité :

supposons qu'il existe des cycles $c_1,...,c_r$ d'ordres respectifs $p_1,...,p_r$, à supports $2$ à $2$ disjoints et $c'_1,...,c'_p$ d'ordres respectifs $q_1,...,q_p$ à supports deux à deux disjoints tels que $\sigma=\prod\limits_{i=1}^r c_i=\prod\limits_{j=1}^p c'_j$ .

Soit $j \in \{1,...,r\}$ . Considérons $x \in \{1,...n\}$ tel que $c_j(x) \neq x$ . Alors $x \in supp(c_j)$ donc $x$ n'appartient pas aux supports des $c_i$ pour tout $i \in \{1,...,r\}$, $i \neq j$ . Donc pour tout $i \in \{1,...,r\}$, $i \neq j$, $c_i(x)=x$ .
Donc, quitte à réordonner les cycles $c_1,...,c_r$, on a : $\sigma(x)=c_j \left (\prod\limits_{i=1 \\ i \neq j}^{r} c_i(x) \right)=c_j(x) \neq x$ .

D'autre part, $\sigma(x)=\prod\limits_{i=1 }^{p} c'_i(x)=c'_1 \circ c'_2 \circ ... \circ c'_p(x) =c_j(x) \neq x$ .

Si $x$ n'appartient à aucun des supports de $c'_i$ pour tout $i \in \{1,...,p\}$ alors on aurait : $\sigma(x)=x$ ce qui est impossible donc il existe un cycle $c'_k$ tel que $c'_k(x) \neq x$ i.e : $x \in supp(c'_k)$ et $x$ n'appartient pas aux supports des autres cycles $c'_i$ pour tout $i \in \{1,...,p\}$, $i \neq k$ car les cycles $c'_i$ sont à supports $2$ à $2$ disjoints.

Dès lors, on obtient : $\sigma(x)=c'_k(x)=c_j(x)$ puis (par commutativité des cycles à supports $2$ à $2$ disjoints et par récurrence immédiate), pour tout $n \in \mathbb{N}$, $\sigma^n(x)=c'^n_k(x)=c^n_j (x)$ donc les orbites de $x$ selon $c'_k$ et $c_j$ coïncident donc $c'_k=c_j=(x,\sigma(x),...,\sigma^{p_{j}-1}(x))=(x,\sigma(x),...,\sigma^{q_{k}-1}(x))$ (un cycle étant entièrement déterminé par l'orbite d'un des éléments de son support) et les cycles $c'_k$ et $c_j$ ont le même ordre.

Ceci étant valable pour tout $j$ quelconque de $\{1,...,r\}$, on en déduit que chaque cycle $c_j$ coïncide avec un cycle $c'_k$ pour $k \in \{1,...,p\}$ donc que $p=r$ et que la décomposition de $\sigma$ est unique à l'ordre près des facteurs.