TD5 : Équations de mots, Groupe symétrique

EX 1

a) Initialisation : immédiat, si $u=v=𝜀$

b) Hérédité :

Sans perte de généralité : $\vert u\vert ≤\vert v\vert$ :

  • Si $u=𝜀$ : immédiat
  • Sinon :

$v ≝ u v’$, et \(uuv' = uv'u\)

d’où

\(uv' = v'u\) et par hypothèse de réc, il vient que : il existe un mot $w$ tq :

  • $u = w^n$
  • $v’ = w^m$

donc $v = w^{n+m}$, et le résultat est acquis.

EX 2

On remarque que si $\vert u\vert =\vert v\vert$, $n=m$, et $u=v$.

( Par réc sur $\vert u\vert +\vert v\vert$ : il existe un mot $w$ tel que

a) Initialisation : immédiat, si $u=v=𝜀$

b)

  • Si $u=𝜀$ : immédiat
  • Sinon :

Sans perte de généralité : $\vert u\vert <\vert v\vert$, donc $m > n$.

De plus, on peut supposer que $\vert u\vert ∧\vert v\vert = 1$, car sinon : \(u^{m} = v^{n}\) et il vient que \(u^{n'} = v^{m'}\) ) _____

  • Sans perte de généralité : $\vert u\vert <\vert v\vert$, donc $m > n$.

  • Supposons que $\vert u\vert ∧\vert v\vert = 1$

Bézout ⟶ $∃a,b ∈ ℕ; a\vert v\vert - b\vert u\vert = 1$, avec

  • $a < \vert u\vert$
  • $b < \vert v\vert$

Pour toute lettre $w_i$ ($i < \vert v\vert$ )

$w_i = w_{i+a\vert v\vert } = w_{i+a\vert v\vert -b\vert u\vert } = w_{i+1}$

NB : $w_{i+a\vert v\vert -b\vert u\vert }$ reste une lettre, car :

\(i+a\vert u\vert ≤ (a+1)\vert u\vert ≤ \vert u\vert \vert v\vert ≤\vert w\vert\) car $\vert u\vert ,\vert v\vert /\vert w\vert$ et $\vert u\vert ∧\vert v\vert = 1$

donc $∃a ∈ 𝛴; u,v,w ∈ a^*$

Puis, dans le cas général, on trvaille sur l’alphabet : on pose $A_{a_1 ⋯ a_d} ≝ a_1 ⋯ a_d, …$

on ne s’écrit qu’avec une seule lettre sur cet alphabet, d’où :

\[∃ 𝛼_1, ⋯, 𝛼_d ∈ 𝛴; u,v,w ∈ (a_1 ⋯ a_d)^*\]

EX 3

⟹ : $z=x$

⟸ :

  • Si $\vert u\vert ≥\vert z\vert$ : $u=zx$ et $v=xz$ (par l’identité dont on dispose)

  • Si $\vert z\vert >\vert u\vert$ : Par réc sur la taille de $z$ :

$z=ux$ et $z=xv$ ⟶ HR : $u$ et $v$ conjugués, car $\vert x\vert < \vert z\vert$

EX 5

Soit $M$ un monoïde fini.

C’est le quotient du monoïde $M^*$ par la relation d’équivalence “$u$ et $v$ ont la même image par le morphisme de monoïde qui envoie les lettres sur les lettres”

EX 6

1) Principe des tiroirs.

2)

a) évident, sinon $x^{j-i}$ contredit la minimalité de $l$ (où $0 ≤ i < j ≤l-1$ vérifient $x^i = x^j$)

b) évident, par division euclidienne des exposants par $l$

c) $x^p x^r = x^{p+r} = x^{p+l-k} = x^{l}x^{p-k} = x^{k}x^{p-k} = x^p$

\[\begin{cases} \{x^k, ⋯, x^{l-1}\} ⟶ ℤ/(l-k)ℤ \\ x^p \mapsto p-r \end{cases}\]

est un homomorphisme de $Ker$ trivial : isomorphisme.

d) $x^r$ est idempotent, et c’est le seul car c’est un groupe (un seul idempotent : le neutre).

EX 11

1)

Existence :

On considère les orbites de l’action définie précédemment :

\[⟦1,n⟧ = \bigcup\limits_{O \text{ orbite}} O\]

et :

\[𝜎 = \prod\limits_{O \text{ orbite}} 𝜎_{\vert O}\]

Unicité :

Si $𝜎 = \prod\limits_{i} 𝛾_i = \prod\limits_{i} 𝜎_i$ sont des décompositions en cycles à support disjoints,

alors pour toute orbite $O$, il existe $i, j$ tq $𝛾_i = O = 𝜎_j$

2) C’est le ppcm des ordres des cycles.

3) C’est le max des ppcm des toutes les décompositions de l’entier 6 :

  • 1, 2, 3
  • 2, 2, 2
  • 6

$or_{max, 𝕾_6} = 6$

4) On dessine le graphe de $𝜎$ : les cycles du graphe sont les cycles de la décomposition de $𝜎$.

a) b) 8

EX 12

1)

M1 :

Tout cycle s’écrit en produit de transpositions.

2) M2 :

Par réc sur $n$

  • Initialisation : immédiate pour $n=2$

  • Hérédité :

    • Si $𝜎(n+1) = n+1$ : on se ramène au cas précédent
    • Sinon, on multiplie $𝜎$ par $(𝜎(n+1),n+1)$ et on se ramène au point précédent.

$(1,n) = ()

3)

Leave a comment