Permutations, prétraitement

Entrée: permutations g_{1}, g_{2}, …, g_{r} de {1, 2, …, n} Sortie: tableau T [i, j], 1 ≤ i ≤ j ≤ n.

T ← partout la permutation Ident pour k ← 1 jusqu’à r

tamiser(g_{k})

tantque il reste dans T un couple g, h de permutations non considéré

tamiser(g ⋆ h)

où tamiser(p) consiste à effectuer:

π ← p

tantque π ≠ Ident faire

i ← plus petit point non fixé par π j ← image de i selon π si T [i, j] = Ident alors T [i, j] ← π π ← π ⋆ (T [i, j])^{−1}

On obtient du tableau T

Test d’appartenance : Donnée: permutations h et g_{1}, g_{2}, …, g_{r} Déterminer: si h ∈ ⟨g_{1}, g_{2}, …, g_{r}⟩.

former T en prétraitant g_{1}, g_{2}, …, g_{r} si tamiser(h) ajouteà T alors retourner faux

sinon retourner vrai .

Ordre du groupe engendré : Donnée: permutations g_{1}, g_{2}, …, g_{r} Déterminer: |⟨g_{1}, g_{2}, …, g_{r}⟩|.

former T en prétraitant g_{1}, g_{2}, …, g_{r}

ordre ← 1
pour i ← 1 jusqu'à n faire

m ← 1 + |{j | j > i et T [i, j] ≠ Ident }|

     ordre ← ordre × m
retourner ordre.

Principale propriété de tamiser(p), p ≠ Ident

Soit:

• s = plus petit point non fixé par p

• T [t, j] = dernière entrée examinée lors du tamisage de p.

Alors:

• s ≤ t

• après tamiser(p), p s’exprime sous la forme

T [t, j] ⋆ T [t − 1, j_{t−1}] ⋆ ⋯ ⋆ T [s + 1, j_{s+1} ] ⋆ T [s, j_{s}].

PREUVE: induction sur le nombre de tours de la boucle tantque lors du tamisage.

PREUVE: détails

Par inspection, notons d’abord que pour tout 1 ≤ i < j ≤ n, T [i, i] contiendra toujours Ident et T [i, j] contiendra toujours une permutation qui fixe 1, 2, …, i − 1 et qui envoie i à j.

Base de l’induction. Soit n = 1. Si p fut tamisée en un seul tour de boucle, alors

Cas 1: T_{avant}[s, s^{p}] = Ident. Dans ce cas

T [s, s^{p}] ← p

fut effectuée, d’où T [s, s^{p}] = p à la fin du tour.

Cas 2: T_{avant}[s, s^{p}] ≠ Ident. Puisqu’un seul tour a suffi, p ⋆ T_{avant}[s, s^{p}]^{−1} = Ident. Donc p = T_{avant}[s, s^{p}], et le tamisage de p laisse T inchangé.

Pas de l’induction: Soit n − 1 ≥ 1, et soit p tamisée en n tours de boucle. Après le premier tour, π avait la valeur p⋆T [s, s^{p}]^{−1}. Puisque p ⋆ T [s, s^{p}]^{−1} fut tamisée en n − 1 tours, l’hypothèse d’induction permet d’écrire

p ⋆ T [s, s^{p}]^{−1} = T [t, j] ⋆ a_{t−1} ⋆ ⋯ ⋆ a_{σ},

où le plus petit point non fixé par p⋆T [s, s^{p}]^{−1} est σ, où chaque a_{k} provient de la ligne k, et où T [t, j] fut la dernière entrée considérée lors du tamisage de p ⋆ T [s, s^{p}]^{−1} (donc du tamisage de p). Notons que T [s, s^{p}], du fait qu’elle provient de la ligne s, fixe 1, 2, …, s− 1 et envoie s à s^{p}. Ainsi p ⋆ T [s, s^{p}]^{−1} fixe 1, 2, …, s. Donc σ > s. Puisque

p = T [t, j] ⋆ a_{t−1} ⋆ ⋯ ⋆ a_{σ} ⋆ T [s, s^{p}],

on conclut en insérant au besoin des T [i, i] entre a_{σ} et T [s, s^{p}].

Fin de la PREUVE.