Evaristette, septembre 2018

Chères amies, chers amis de Galois, voici l'evaristette de septembre:

Galois est considéré comme l'initiateur de la théorie des groupes. En
tout cas, le groupe des permutations des racines d'une équation est au
cœur de sa théorie. Soit G le groupe de toutes les permutations des
entiers de 1 à n. On sait qu'il peut être engendré par n-1
transpositions, .... c'est dans tous les livres mais sauriez-vous
montrer qu'il ne peut être engendré par n-2 transpositions. Supplément :
trouver une condition nécessaire et suffisante pour qu'un ensemble de
n-1 transpositions engendre G.


A vos plumes (d'oie)! Ce 26 septembre, un "ami de Galois" [https://www.evaristegalois.org/]

Réponses

  • Bonjour,

    on peut procéder en prouvant que dans $S_n$, il existe toujours un élément qui ne peut être écrit comme produit de $n-2$ transpositions: ce sont les $n-$cycles, c'est-à-dire les cycles dont le support est de cardinal $n$.
    On peut le démontrer par l'absurde.
    Cordialement
    ...
  • Une manière de voir est d'associer à toute permutation $\sigma$, le nombre $C_{\sigma}$ de cycles que contient sa décomposition en cycles à supports disjoints (en incluant les points fixes).

    En composant cette permutation avec n'importe quelle transposition $(i,j)$, on constate que ce cardinal augmente ou diminue de $1$ selon que $i$ et $j$ sont dans le même cycle ou dans des cycles différents.

    Si on compose $\sigma$ avec $k$ transposition,$C_{\sigma}$ augmente ou diminue d'au plus $k$.
    Sachant que le cardinal de la permutation "Identité" est $n$ et que celui d'un cycle d'ordre $n$ est $1$, on voit que le nombre de transpositions nécessaires pour transformer un $n$-cycle en $n$ cycles d'ordre $1$ ne peut-être inférieur à $n-1$.
    ...
  • Merci pour cette jolie démo df. (tu)
  • Bonjour,

    Il me semble que l'affirmation initiale est exacte. Par contre la démonstration ne me suffit pas : le groupe engendré par $n-2$ transpositions peut contenir des éléments qui sont composés de plus de ces $n-2$ transpositions, il suffit de faire des répétitions...
  • Salut Norbert: En représentant fidèlement le groupe de permutation comme un groupe de symétries hyperplanes tu as (n-2) symétries hyperplanes dans $R^{n-1}$. Les vecteur orthogonaux à tes hyperplans engendrent un sev V de dimension au plus n-2 et donc laisse fixe l'orthogonal soit D (en général une droite). Or le groupe opère transitivement donc il ne peut être engendré par tes $(n-2)$ symétries ;-)
  • Merci pour cette démonstration efficace. Je propose une autre approche : à un ensemble $E$ de transpositions, on peut associer un graphe, les sommets sont les entiers de $1$ à $n$ (qui doivent tous apparaître si on veut engendrer $\mathcal{S}n$), les sommets $i$ et $j$ sont joints par une arête si $(i,j)$ est dans $E$. Pour que $E$ engendre $\mathcal{S}_n$, il faut et suffit que ce graphe soit connexe : si $i$ et $k$ sont reliés par un chemin, il est facile de trouver un produit de tranpositions de $E$ qui donne la transposition $(i,k)$. Or un graphe connexe à $n$ sommets à au moins $n-1$ arêtes. (démonstration par récurrence, par exemple). En prime, si $E$ contient $n-1$ tranpositions, on a une condition pour qu'il engendre $\mathcal{S}_n$. Et si je ne me trompe pas, le graphe devrait être un arbre.
  • Il y a aussi une interprétation en terme de graphes.
    On considère un enemble fini $E$ et un ensemble $\mathcal T$ de transpositions de $E$. On représente les éléments de $E$ par des points, et l'on joint deux de ces points si la transposition qui les échange est élément de $\mathcal T$. On obtient ainsi un graphe non orienté. L'ensemble $\mathcal T$ engendre le groupe de toutes les permutations de $E$ si et seulement si l'on peut se rendre de n'importe quel point à n'importe quel autre en suivant les arêtes du graphe, autrement dit si le graphe est connexe. Il n'est pas difficile de démontrer qu'un graphe connexe à $n$ sommets a au moins $n-1$ arêtes.
    Si le graphe n'est pas connexe, ses composantes connexes donnent le groupe de permutations engendré par $\mathcal T$.
    Qu'on ne se méprenne pas : j'avais vu ça il y a longtemps et je ne connais presque plus rien à la théorie des graphes : encore une chose que je regrette... mais cette vision imagée extraite de ma mémoire me semble très parlante.
    Bonne soirée.
    Fr. Ch.
  • Joli, mais ce que vous écrivez est la même chose non?
    M
  • Oui, je n'avais pas lu le précédent message, mais j'ai dit un chouïa de plus.
    Un graphe à $n$ sommets et $n-1$ arêtes n'est pas forcément un arbre.
  • On a deux exemples classiques de générateurs du groupe $\mathcal{S}_n$ par $n-1$ transpositions, qui font généralement l'objet d'un exercice.
    Il y a les transpositions $(1,i)$, $2 \le i \le n$, ce qui correspond effectivement à un arbre.
    Il y a aussi les transpositions $(i,i+1)$, $1 \le i \le n-1$, ce qui correspond à une « chaîne » pour ainsi dire, je ne sais si ça a un nom en théorie des graphes.
    Mais il y a une foule d'autres ensembles de $n-1$ transpositions qui engendrent le groupe symétrique.
    Bonne soirée.
    Fr. Ch.
  • Oups ! J'ai écrit une bêtise. Un graphe connexe à $n$ sommets ayant $n-1$ arêtes est un arbre. Comme j'ai dit, je suis pas mal rouillé en théorie des graphes.
    Bonne journée.
    Fr. Ch.
  • L'interprétation en terme de graphes permet de montrer qu'il y a $n^{n-2}$ ensembles de $n-1$ transpositions qui engendrent le groupe symétrique $\mathcal{S}_n$.

    C'est aussi le nombre de façons d'exprimer un $n$-cycle comme un produit de $n-1$ transpositions (suite A000272 de l'OEIS).
Connectez-vous ou Inscrivez-vous pour répondre.