Problème du mot pour les groupes

On considère une présentation donnée par un couple ${\displaystyle (X\mid R)}$ où ${\displaystyle X}$ est l’ensemble des générateurs et ${\displaystyle R}$ l’ensemble des relateurs. Le problème du mot consiste à déterminer si deux mots sur ${\displaystyle X}$ et son inverse représentent le même élément du groupe modulo les relateurs. Plus formellement, soit ${\displaystyle G}$ un groupe de type fini, donné par une présentation ${\displaystyle G=\langle X\mid R\rangle }$ avec X fini. On considère l'alphabet ${\displaystyle \Sigma =X\sqcup X^{-1}}$, où ${\displaystyle X^{-1}}$ est un alphabet disjoint de ${\displaystyle X}$ et en bijection avec ${\displaystyle X}$; ses éléments représentent les inverses formels des éléments de ${\displaystyle X}$. On considère l'application ${\displaystyle \pi :X\to G}$ tel que ${\displaystyle \pi (X)\subseteq G}$ engendre ${\displaystyle G}$, étendue en un morphisme surjectif du monoïde libre ${\displaystyle \Sigma ^{*}}$ sur ${\displaystyle G}$. Le problème du mot consiste alors à déterminer si ${\displaystyle \pi (u)=\pi (v)}$, ou de manière équivalent, si ${\displaystyle \pi (uv^{-1})=e}$ pour deux mots ${\displaystyle u}$ et ${\displaystyle v}$, où ${\displaystyle v^{-1}}$ est l'inverse formel de ${\displaystyle v}$ dans ${\displaystyle \Sigma ^{*}}$ et où ${\displaystyle e}$ est l'élément neutre de ${\displaystyle G}$ . De manière équivalente, le problème est décider si ${\displaystyle \pi (x)=e}$ pour un mot ${\displaystyle x}$ de ${\displaystyle \Sigma ^{*}}$, donc si ${\displaystyle x}$ appartient au langage formel

${\displaystyle W(G,X)=\{w\in \Sigma ^{*}\mid \pi (w)=e\}}$.

Par un raccourci un peu elliptique, on dit aussi que l'ensemble ${\displaystyle W(G,X)}$ est le problème du mot. On dit aussi que le problème du mot est résoluble si l'appartenance au langage ${\displaystyle W(G,X)}$ est décidable.

Les groupes suivants ont un problème de mot résoluble :

• Les groupes automatiques, qui comprennent :
  • les groupes finis
  • les groupes hyperboliques
  • les groupes euclidiens
  • les groupes de Coxeter
  • les groupes de tresses
  • les groupes géométriquement finis (en)
• Les groupes libres de type fini
• Les groupes abéliens de type fini
• Les groupes polycycliques (en)
• Les groupes absolument présentés (en) de type fini^[3], comprenant :
  • Les groupes simples de type fini.
• Les groupes résiduellement finis (en) finiment présentés
• Les groupes à un relateur^[4] (par un théorème de Magnus), comprenant les groupes fondamentaux de variétés de dimension deux fermées et orientables.
• Les groupes virtuellement libres de type fini, puisque le langage des mots équivalents à l'élément neutre est un langage algébrique, par le théorème de Muller-Schupp.

• Soit X est un ensemble récursivement énumérable d'entiers naturels où le problème d'appartenance est indécidable. Alors le groupe ${\displaystyle \langle a,b,c,d\mid a^{n}ba^{n}=c^{n}dc^{n},n\in X\rangle }$ est de type fini avec une présentation récursivement énumérable et dont le problème du mot est indécidable^[5].
• Tout groupe de type fini avec une présentation récursivement énumérable et un problème du mot indécidable est un sous-groupe d'un groupe finiment présenté avec un problème du mot indécidable^[6]
• Le nombre de relateurs d'un groupe finiment présenté avec un problème du mot indécidable peut être égal à 14^[7] ou même 12^[8],[9].
• Un exemple explicite d'une présentation avec un problème du mot indécidable est le suivant^[10],[11] :

générateurs : ${\displaystyle \{a,b,c,d,e,p,q,r,t,k\}}$

relateurs : ${\displaystyle ra=ar,rb=br,rc=cr,rd=dr,re=er,pt=tp,qt=tq}$ (commutations), et de plus

${\displaystyle {\begin{array}{ll}&p^{10}a=ap,&pacqr=rpcaq,\\&p^{10}b=bp,&p^{2}adq^{2}r=rp^{2}daq^{2},\\&p^{10}c=cp,&p^{3}bcq^{3}r=rp^{3}cbq^{3},\\&p^{10}d=dp,&p^{4}bdq^{4}r=rp^{4}dbq^{4},\\&p^{10}e=ep,&p^{5}ceq^{5}r=rp^{5}ecaq^{5},\\&aq^{10}=qa,&p^{6}deq^{6}r=rp^{6}edbq^{6},\\&bq^{10}=qb,&p^{7}cdcq^{7}r=rp^{7}cdceq^{7},\\&cq^{10}=qc,&p^{8}ca^{3}q^{8}r=rp^{8}a^{3}q^{8},\\&dq^{10}=qd,&p^{9}da^{3}q^{9}r=rp^{9}a^{3}q^{9},\\&eq^{10}=qe,&a^{-3}ta^{3}k=ka^{-3}ta^{3}\end{array}}}$

• Théorème de Boone-Rogers : Il n'existe pas d'algorithme partiel qui résout le problème du mot dans tous les groupes de type fini ayant un problème du mot résoluble.En d'autres termes, le problème du mot uniforme n'est pas résoluble pour la classe de tous les groupes finiment présentés.
• Théorème de Boone-Higman : Un groupe finiment présenté a un problème du mot résoluble si et seulement s'il peut être plongé dans un groupe simple qui, lui, peut être plongé dans un groupe finiment présenté.
• Le résultat suivant a été démontré par Bernhard Neumann et Angus Macintyre:Un groupe finiment présenté a un problème du mot résoluble si et seulement s'il peut être plongé dans tout groupe algébriquement clos (en).
• Pour les groupes simples :Un groupe simple présenté récursivement a un problème du mot résoluble.Le problème du mot est uniformément résoluble pour la classe des groupes simples finiment présentés.