Nombre pair de transpositions pour faire Id

http://www.les-mathematiques.net/phorum/read.php?3,515809,516402#msg-516402

Ce post résume je crois

Parce que $\tau'_m=\tau'_1\cdots\tau'_{m-1}$.

Tu peux expliquer ta remarque ?
Même après édition, je ne comprends toujours pas la remarque.
J'essaie de répondre à une interprétation de ladite remarque, interprétation qui n'est peut-être pas la bonne.
On suppose $n$ impair parce qu'on fait un raisonnement par l'absurde. Ce $n$ n'a rien à voir avec le nombre d'éléments de l'ensemble sur lequel agissent les permutations.
Les manips faites avec le 1 (un élément de l'ensemble) ont pour but de montrer qu'on peut alors écrire l'identité comme produit d'un nombre impair de transpositions où le 1 n'intervient pas (donc dans le groupe de permutations d'un ensemble avec un élément de moins). En continuant comme ça à éliminer un élément après l'autre, on aboutit à l'absurde.

Il est difficile de cerner ce qui te pose problème.

Soit le plus petit ensemble fini possible E tel qu'il existe un produit p d'un nombre impair de transpositions de E qui
donne l'identité.

Soit x un élément de E

On peut modifier p en un produit d'un nombre impair de transpositions de E-{x} (ce sont des transpositions de E qui laissent toutes x fixe ) qui donne l'identité. Cela est une contradiction puisque E a été choisi le plus petit possible

Tu poses la question de pourquoi si abc....xyz=Id et a,b,c...y laissent toutes fixes l'élément Toto alors z laisse aussi fixe l'élément Toto?

Je te réponds "c'est presque évident" et donc cherche un peu

As-tu relu mon dernier message ?

Je pense que tu ne lis pas assez doucement et précisément ce qu'on t'ecrit. Tu as répondu "non" au (2) de mon dernier post donc j'aimerais bien mais je ne vois plus comment t'aider. Lire le pdf en anglais de ccandide risque de ne pas t'aider non plus

christophe c écrivait:

---

> Lire le
> pdf en anglais de ccandide risque de ne pas
> t'aider non plus

C'est possible en effet s'il ne sait pas répondre à tes deux questions. Toutefois, je l'invite quand même à examiner les deux exemples proposés dans le pdf §7.3.1 et à prendre en considération la dernière phrase de la preuve toujours au même paragraphe (jusque là, je voyais pas encore pourquoi ça marchait mais après c'est limpide).

Très franchement, une fois la transformation comprise le résultat devrait vu comme trivial et je trouve la démonstration ci-dessus assez peu claire Sur la base du document référencé plus haut, j'ai rédigé une démonstration complète et détaillée.



Proposition : Soient $N\geq 3$ et $t_1,\dots, t_N\in\mathcal{S}_n$ des transpositions telles que
$$\mathrm{Id}=t_1\dots t_N $$
alors il existe des transpositions $u_1,\dots, u_{N-2}\in\mathcal{S}_n$ telles que
$$\mathrm{Id}=u_1\dots u_{N-2} $$

Corollaire : Soient $N\geq 1$ et $t_1,\dots, t_N\in\mathcal{S}_n$ des transpositions telles que
$$\mathrm{Id}=t_1\dots t_N $$
alors $N$ est pair.

Preuve Si $N=2p+1$ alors, en appliquant la proposition $p$ fois, on se ramène au cas $N=1$ : l'identité serait une transposition, ce qui est absurde.

Reste à prouver la Proposition. Ce qui passe par la réduction suivante.

Lemme : Soient $u$ et $t=(a \quad b)$ deux transpositions distintes de $\mathcal{S}_n$. Alors il existe une transposition $v\in\mathcal{S}_n$ et $x\neq a$ tels que $ut=(a \quad x)v$ et $v(a)= a$.


Preuve
Puisque $t$ et $(a \quad b)$ sont distinctes, il y a 3 cas à envisager :
1er cas : $(a \quad c)(a \quad b)=(a \quad b)(b \quad c)$
2ème cas : $(b \quad c)(a \quad b)=(a \quad c)(b \quad c)$
3ème cas : $(c \quad d)(a \quad b)=(a \quad b)(c \quad d)$.

Preuve de la Proposition

Partons d'une décomposition en $N$ transpositions :

$$\mathrm{Id}=t_{N-1}\dots t_1 (a \quad b)$$

et supposons la conclusion fausse ie que $\mathrm{Id}$ ne soit pas le produit de $N-2$ transpositions.

Montrons alors par récurrence limitée sur $k\in\{1,\dots, N\}$ qu'il existe $x\neq a$ et des transpositions $u_1,\dots, u_{k-1}$ tels $u_1(a)=\dots=u_{k-1}(a)=a$ et

$$\mathrm{Id}=t_{N-1}\dots t_k (a \quad x) u_{k-1}\dots u_1 \quad(\star)$$

L'assertion est vraie pour $k=1$. Supposons que $(\star)$ soit vrai pour $k< N$ fixé.
On sait que $t_k\neq (a \quad x)$ car sinon $t_k (a \quad x)=\mathrm{Id}$ et donc, après simplication dans $(\star)$, on aurait $\mathrm{Id}$ qui serait produit de $N-2$ transpositions, ce qui a été exclu. Par suite, le lemme s'applique et donc $t_k (a \quad x)=(a \quad y)u_k$ avec $u_k(a)=a$ en sorte que
$$\mathrm{Id}=t_{N-1}\dots (a \quad y)u_k u_{k-1}\dots u_1$$
ce qui termine la récurrence.

En appliquant le résultat pour $k=N$ on obtient que

$$\mathrm{Id}=(a \quad x)u_{N-1}\dots u_1 $$

avec $u_k(a)=a$ en sorte que $\mathrm{Id}(a)=x$ ce qui est absurde.

christophe c
Pas vraiment d'accord, c'est fondamentalement la même preuve basée sur l'algorithme de réduction que je démontre en détail (la récurrence) et ce que ne démontre pas L2_maths. Hors la réduction, l'essentiel de la preuve tient en 2 lignes (l'énoncé de la proposition et le corollaire qui en résulte).

[Inutile de recopier le message précédent. AD]