Produit des éléments de $\mathfrak S(3)$

etanche
etanche
dans Algèbre
Bonjour

Quels sont les éléments du groupe symétrique $\mathfrak S_3$ qui s’écrivent comme produit de tous les éléments de $\mathfrak S_3$ dans un ordre quelconque , chaque élément apparaissant une fois.
Merci.

Réponses

  • Calli
    Calli
    Bonjour,
    Ce sont les transpositions. Et on n'a besoin de faire aucun calcul pour le savoir.
  • nicolas.patrois
    nicolas.patrois
    Un petit script bien bourrin en Python donne la même réponse. :-D
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Calli
    Calli
    message privé d'etanche a écrit:
    Comment tu démontres ?

    Je ne sais pas pourquoi tu le demandes en privé. Je préfère répondre en public.

    Le raisonnement a deux étapes : ces produits sont des transpositions (à toi de trouver pourquoi) puis, par indiscernabilité de 1,2 et 3, si on obtient une transposition alors on obtient aussi toutes les autres (à toi de formaliser ce point).
  • etanche
    etanche
    Ok même question dans $\mathfrak S_n$ avec $n\geq 4$
  • nicolas.patrois
    nicolas.patrois
    Compte le nombre de transpositions.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • ev
    ev
    @ Nicolas

    Et pas les 4-cycles ?

    e.v.
    Personne n'a raison contre un enfant qui pleure.


  • nicolas.patrois
    nicolas.patrois
    Oui, aussi.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Borelline
    Borelline
    Bonjour !
    Est-ce possible d'avoir une indication supplémentaire pour $n \geq 4$ svp (:P), j'avoue que pour l'instant, après avoir compté les transpositions et les $4$-cycles, je demeure tout de même perplexe ! 8-)
  • nicolas.patrois
    nicolas.patrois
    Connais-tu la signature d’une permutation ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Borelline
    Borelline
    Oui ?
  • Calli
    Calli
    etanche a écrit:
    Ok même question dans $\mathfrak S_n$ avec $n\geq 4$

    "Merci" c'est trop demandé ?
  • Calli
    Calli
    Moi non plus je ne vois pas où tu veux en venir Nicolas. Pour $n=4$ : il y a un nombre pair de transpositions et de 4-cycles dans $\mathfrak S_4$, donc les produits dont on parle sont de signature paire... et ensuite ?
  • raoul.S
    raoul.S
    Je pense qu'on devrait obtenir $\mathfrak{A}_n$ (le groupe alterné) pour $n\geq 4$, car je ne vois pas pourquoi on pourrait exprimer une permutation paire comme produit de tous les éléments mais pas une autre.

    C'est peut-être facile mais je ne vois pas comment le montrer...
  • Calli
    Calli
    Appelons l'ensemble recherché $E_n$. On sait que : $\forall n\geqslant 4, \,E_n\subset \mathfrak A_n$ (le groupe alterné, chacun sa notation :-D).

    Pour $n=4$, on peut montrer que $E_4$ contient un 3-cycle en formant le produit dans l'ordre suivant :
    $$\begin{align*}
    &\text{produit des bitranspositions, qui fait id car }\{{\rm id}, \text{bitranspositions}\}\cong (\Bbb Z/2\Bbb Z)^2 \\
    \times &\text{produits deux par deux des 4-cycles avec leur inverse, qui fait id}\\
    \times &\text{produits deux par deux des 3-cycles contenant 4 avec leur inverse, qui fait id}\\
    \times & \text{produit des transpositions contenant 4, qui fait un 4-cycle}\\
    \times & \text{produit des éléments de $\mathfrak S_3$ dans un ordre quelconque, qui fait une transposition}
    \end{align*}$$
    Donc $E_4$ contient tous les 3-cycles. Peut-être contient-il aussi l'identité (édit : et les bitranspositions, je les avais oublié). Mais ça n'est plus l'heure d'y réfléchir ; je vais dormir.
  • raoul.S
    raoul.S
    Il y a 9 éléments d'ordre 2 :

    $$\tau_{12},\tau_{13},\tau_{14},\tau_{23},\tau_{24},\tau_{34},\tau_{12}\cdot \tau_{34},\tau_{13}\cdot \tau_{24},\tau_{14}\cdot \tau_{23}$$

    Ce sont les uniques éléments égaux à leur propre inverse.

    Pour l'identité il suffit de multiplier chaque élément qui n'est pas d'ordre deux avec son inverse, puis les 9 éléments d'ordre deux dans le bon ordre (facile à trouver) et on obtient $id$.

    Pour les bitranspositions on remarque encore une fois qu'en multipliant judicieusement les 9 éléments ci-dessus on en obtient une et donc on les a toutes.

    Donc $E_4=\mathfrak A_4$ (je m'adapte B-)-)
  • Borelline
    Borelline
    Bon, contrairement au cas $\mathfrak{S}_3$ qui était facile, il faut mettre les mains dans le cambouis j'ai l'impression !
  • nicolas.patrois
    nicolas.patrois
    J’ai étendu mon script en Python (fait sans sage) pour qu’il calcule un produit aléatoire de toutes les permutations de $\mathfrak{S}_n$ : 
    #!/usr/bin/python3

from random import shuffle

# itérateur qui sort les permutations
def liste(l):
 if len(l)==1:
  yield l
 for i in range(len(l)):
  for ll in liste(l[:i]+l[i+1:]):
   yield [l[i]]+ll

# transforme une permutation sous la forme [1,3,2] en "(2 3)"
def l2p(l):
  e=set(range(len(l)))
  p="("
  while e:
    p+=")("
    c=e.pop()
    cc=c
    if l[c]==c+1:
      continue
    while True:
      c=l[c]-1
      e-={c}
      p+=" %d"%(c+1)
      if c==cc:
        break
  p+=")"
  while "()" in p:
    p=p.replace("()","")
  while "( " in p:
    p=p.replace("( ","(")
  if p:
    return perm(p)
  return "()"

# calcule le produit de permutations sous la forme "(1 5 6)(2 3)"
def perm(pe):
  p=pe.replace("()","")[1:-1].split(")(")
  p=[[int(i) for i in l.split()] for l in p][::-1]
  p=[l+[l[0]] for l in p]
  m=max(max(l) for l in p)
  d={i:i for i in range(1,m+1)}

  for e in range(1,m+1):
    ee=e
    for l in p:
        if ee in l:
            ee=l[l.index(ee)+1]
    d[e]=ee

  s=set(range(1,m+1))
  r=[]
  while s:
    n=[]
    e=min(s)
    while e not in n:
        s-={e}
        n.append(e)
        e=d[e]
    if len(n)>1:
        r.append(str(tuple(n)).replace(",",""))

  if r:
    return "".join(r)
  return "()"

n=5
sn=[]

for l in liste(list(range(1,n+1))):
  sn.append(l2p(l))
sn=sn[1:]

for _ in range(20):
  shuffle(sn)
#  print("".join(sn))
  print(perm("".join(sn)))
    Sortie : 
    (2 4 3)
(1 4 5 2 3)
(2 5)(3 4)
(2 3 4)
(1 5 2)
(1 2)(3 5)
(1 4 3)
(1 4)(3 5)
(3 4 5)
()
(1 5)(3 4)
(2 5)(3 4)
(1 5 3)
(1 4 2 3 5)
(1 2)(3 4)
(1 4 5 2 3)
(1 5 3 2 4)
(1 2 5 3 4)
(1 5 3 4 2)
(1 3 2 5 4)
    Manifestement, on peut avoir toutes les permutations paires possibles, c’est-à-dire $\mathfrak{A}_n$ tout entier.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Borelline
    Borelline
    Rien que le fait que $E_n$ soit un groupe semble compliqué à montrer, non ?

    Si on avait $E_n$ groupe, je pense qu'un schéma de preuve similaire nous donnerait sa simplicité et on pourrait ensuite y insérer les $3$-cycles, en faisant des manipulations analogues à ce que Calli et Raoul.S proposaient et ainsi on pourrait conclure.
  • raoul.S
    raoul.S
    Oui même utiliser une récurrence ne semble pas évident.

    Deux remarques simples mais qui peuvent peut-être être utiles pour une éventuelle récurrence :

    1) $\mathfrak{S}_n$ est engendré par les $n-1$ transpositions $\tau_{n,k}$ où $k$ parcourt $[\![1,n-1]\!]$
    2) si $\sigma$ est une permutation qui ne fixe pas $n$ alors $\sigma = \tau_{n,\sigma(n)}\cdot ( \tau_{n,\sigma(n)}\cdot \sigma)$. Donc toute permutation qui ne fixe pas $n$ est produit d'une transposition du même type que 1) et d'une permutation qui fixe $n$ appartenant donc à $\mathfrak{S}_{n-1}$.

    Si avec ces deux points et l'hypothèse de récurrence on arrive à montrer que les produits pairs de transpositions du type $\tau_{n,k}$ sont dans $E_n$ alors c'est bon.

    yakafokon...
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 39

AlegBen314159BibixJLTLirone93Matricule_63Rescassolcadiougerard0igrec27jelobreuil +28 Invités