Word (théorie des groupes) - Word (group theory)

Dans la théorie des groupes , un mot est tout produit écrit d' éléments de groupe et de leurs inverses. Par exemple, si x , y et z sont des éléments d'un groupe G , alors xy , z ⁻¹ xzz et y ⁻¹ zxx ⁻¹ yz ⁻¹ sont des mots de l'ensemble { x ,  y ,  z }. Deux mots différents peuvent avoir la même valeur dans G , ou même dans chaque groupe. Les mots jouent un rôle important dans la théorie des groupes libres et des présentations , et sont des objets d'étude centraux dans la théorie combinatoire des groupes .

Définition

Que G soit un groupe, et que S être un sous - ensemble de G . Un mot en S est une expression de la forme

${\ displaystyle s_ {1} ^ {\ varepsilon _ {1}} s_ {2} ^ {\ varepsilon _ {2}} \ cdots s_ {n} ^ {\ varepsilon _ {n}}}$

où s ₁ , ..., s _n sont des éléments de S et chaque ε _i est ± 1. Le nombre n est connu comme la longueur du mot.

Chaque mot de S représente un élément de G , à savoir le produit de l'expression. Par convention, l' élément d' identité (unique) peut être représenté par le mot vide , qui est le mot unique de longueur zéro.

Notation

Lors de l'écriture de mots, il est courant d'utiliser la notation exponentielle comme abréviation. Par exemple, le mot

${\ displaystyle xxy ^ {- 1} zyzzzx ^ {- 1} x ^ {- 1} \,}$

pourrait être écrit comme

${\ displaystyle x ^ {2} y ^ {- 1} zyz ^ {3} x ^ {- 2}. \,}$

Cette dernière expression n'est pas un mot en soi - c'est simplement une notation plus courte pour l'original.

Lorsque vous traitez avec de longs mots, il peut être utile d'utiliser un surlignage pour désigner des éléments de inverses S . En utilisant la notation surlignée, le mot ci-dessus s'écrirait comme suit:

${\ displaystyle x ^ {2} {\ overline {y}} zyz ^ {3} {\ overline {x}} ^ {2}. \,}$

Mots et présentations

Un sous - ensemble S d'un groupe G est appelé un groupe électrogène si chaque élément de G peut être représenté par un mot dans S . Si S est un ensemble de génération, une relation est une paire de mots S qui représentent le même élément de G . Celles-ci sont généralement écrites sous forme d'équations, par exemple Un ensemble de relations définit G si chaque relation de G suit logiquement de celles de , en utilisant les axiomes pour un groupe . Une présentation pour G est une paire , où S est un groupe électrogène pour G et est un ensemble définissant de relations. ${\ displaystyle x ^ {- 1} yx = y ^ {2}. \,}$${\ displaystyle {\ mathcal {R}}}$${\ displaystyle {\ mathcal {R}}}$${\ displaystyle \ langle S \ mid {\ mathcal {R}} \ rangle}$${\ displaystyle {\ mathcal {R}}}$

Par exemple, le groupe de quatre Klein peut être défini par la présentation

${\ displaystyle \ langle i, j \ mid i ^ {2} = 1, \, j ^ {2} = 1, \, ij = ji \ rangle.}$

Ici, 1 désigne le mot vide, qui représente l'élément d'identité.

Lorsque S est pas un ensemble de génération de G , l'ensemble des éléments représentés par des mots de S est un sous - groupe de G . Ceci est connu comme le sous - groupe de G généré par S , et est généralement désigné . Il est le plus petit sous - groupe de G qui contient les éléments de S . ${\ displaystyle \ langle S \ rangle}$

Mots réduits

Tout mot dans lequel un générateur apparaît à côté de son propre inverse ( xx ⁻¹ ou x ⁻¹ x ) peut être simplifié en omettant la paire redondante:

${\ displaystyle y ^ {- 1} zxx ^ {- 1} y \; \; \ longrightarrow \; \; y ^ {- 1} zy.}$

Cette opération est connue sous le nom de réduction et ne modifie pas l'élément de groupe représenté par le mot. (Les réductions peuvent être considérées comme des relations qui découlent des axiomes de groupe.)

Un mot réduit est un mot qui ne contient aucune paire redondante. Tout mot peut être simplifié en mot réduit en effectuant une séquence de réductions:

${\ displaystyle xzy ^ {- 1} xx ^ {- 1} yz ^ {- 1} zz ^ {- 1} yz \; \; \ longrightarrow \; \; xyz.}$

Le résultat ne dépend pas de l'ordre dans lequel les réductions sont effectuées.

Si S est un ensemble, le groupe libre sur S est le groupe avec présentation . Autrement dit, le groupe libre sur S est le groupe généré par les éléments de S , sans relations supplémentaires. Chaque élément du groupe libre peut être écrit de manière unique en tant que mot réduit en S . ${\ displaystyle \ langle S \ mid \; \ rangle}$

Un mot est réduit cycliquement si et seulement si chaque permutation cyclique du mot est réduite.

Formes normales

Une forme normale pour un groupe G avec groupe S est un choix d'un mot réduit en S pour chaque élément de G . Par exemple:

• Les mots 1, i , j , ij sont une forme normale pour les quatre groupes de Klein .
• Les mots 1, r , r ² , ..., r ^n-1 , s , sr , ..., sr ^n-1 sont une forme normale pour le groupe dièdre Dih _n .
• L'ensemble des mots réduits en S sont une forme normale pour le groupe libre sur S .
• L'ensemble des mots de la forme x ^m y ⁿ pour m, n  ∈  Z sont une forme normale pour le produit direct des groupes cycliques < x > et < de y >.

Opérations sur les mots

Le produit de deux mots est obtenu par concaténation:

${\ displaystyle \ left (xzyz ^ {- 1} \ right) \ left (zy ^ {- 1} x ^ {- 1} y \ right) = xzyz ^ {- 1} zy ^ {- 1} x ^ { -1} y.}$

Même si les deux mots sont réduits, le produit peut ne pas l'être.

L' inverse d'un mot est obtenu en inversant chaque générateur, et en changeant l'ordre des éléments:

${\ displaystyle \ left (zy ^ {- 1} x ^ {- 1} y \ right) ^ {- 1} = y ^ {- 1} xyz ^ {- 1}.}$

Le produit d'un mot par son inverse peut être réduit au mot vide:

${\ displaystyle zy ^ {- 1} x ^ {- 1} y \; y ^ {- 1} xyz ^ {- 1} = 1.}$

Vous pouvez déplacer un générateur du début à la fin d'un mot par conjugaison :

${\ Displaystyle x ^ {- 1} \ left (xy ^ {- 1} z ^ {- 1} yz \ right) x = y ^ {- 1} z ^ {- 1} yzx.}$

Le mot problème

Étant donné une présentation pour un groupe G , le problème de mot est le problème algorithmique de décider, donné en entrée deux mots S , si elles représentent le même élément de G . Le mot problème est l'un des trois problèmes algorithmiques pour les groupes proposés par Max Dehn en 1911. Pyotr Novikov a montré en 1955 qu'il existe un groupe G de présentation finie tel que le mot problème pour G est indécidable ( Novikov 1955 ). ${\ displaystyle \ langle S \ mid {\ mathcal {R}} \ rangle}$

Remarques

Références

• Epstein, David ; Cannon, JW ; Holt, DF; Levy, SVF; Paterson, MS ; Thurston, WP (1992). Traitement de texte en groupes . AK Peters. ISBN   0-86720-244-0 . .
• Novikov, PS (1955). "Sur l'insolvabilité algorithmique du mot problème dans la théorie des groupes". Trudy Mat. Inst. Steklov (en russe). 44 : 1–143.
• Robinson, Derek John Scott (1996). Un cours de théorie des groupes . Berlin: Springer-Verlag. ISBN   0-387-94461-3 .
• Rotman, Joseph J. (1995). Une introduction à la théorie des groupes . Berlin: Springer-Verlag. ISBN   0-387-94285-8 .
• Schupp, Paul E ; Lyndon, Roger C. (2001). Théorie des groupes combinatoires . Berlin: Springer. ISBN   3-540-41158-5 .
• Solitar, Donald ; Magnus, Wilhelm ; Karrass, Abraham (2004). Théorie des groupes combinatoires: présentations de groupes en termes de générateurs et de relations . New York: Douvres. ISBN   0-486-43830-9 .
• Stillwell, John (1993). Topologie classique et théorie des groupes combinatoires . Berlin: Springer-Verlag. ISBN   0-387-97970-0 .