Problème du mot pour les groupes

En mathématiques, plus précisément dans le domaine de la théorie combinatoire des groupes, le problème du mot pour un groupe de type fini G est le problème algorithmique de décider si deux mots en les générateurs du groupe représentent le même élément.

Plus précisément, si X un ensemble fini de générateurs pour G, on considère le langage formel constitué des mots sur X et son ensemble d'inverses formels qui sont envoyés par l'application naturelle sur l'identité du groupe G. Le problème du mot est le problème algorithmique qui consiste à décider de l’appartenance ou non d'un mot à ce langage formel. On peut voir que si Y est un autre ensemble de générateurs pour G, alors le problème du mot avec l'ensemble Y est équivalent au problème du mot avec ensemble X. On peut donc parler sans ambiguïté de la décidabilité du problème du mot pour un groupe G de type fini.

Un problème différent mais lié est le problème du mot uniforme pour une classe K de groupes donnés par un ensemble récursif de présentations ; le problème algorithmique est alors de décider, étant donné une présentation P d'un groupe G de la classe K, si deux mots représentent le même élément de G. On peut aussi considérer que la classe K est définissable seulement par un ensemble récursivement énumérable de présentations.

Le problème du mot est indécidable dans le cas général, mais est décidable pour de nombreux groupes. Par exemple, les  ont un problème du mot décidable ; de même, l'algorithme de Todd-Coxeter et la complétion de Knuth-Bendix donnent des résultats effectifs. D'un autre côté, le fait qu'un algorithme particulier ne s'applique pas dans un cas particulier n'implique pas que le problème du mot est indécidable. Par exemple, l'algorithme de Dehn ne résout pas le problème du mot pour le groupe fondamental du tore, et pourtant ce groupe est le produit direct de deux groupes cycliques infinis et possède donc un problème du mot décidable.

Une description plus concrète 
On considère une présentation donnée par un couple  où  est l’ensemble des générateurs et  l’ensemble des relateurs. Le problème du mot consiste à déterminer si deux mots sur  et son inverse représentent le même élément du groupe modulo les relateurs. Plus formellement, soit  un groupe de type fini, donné par une présentation  avec X fini. On considère l'alphabet , où  est un alphabet disjoint de  et en bijection avec ; ses éléments représentent les inverses formels des éléments de . On considère l'application  tel que  engendre , étendue en un morphisme surjectif du monoïde libre  sur . Le problème du mot consiste alors à déterminer si , où si  pour deux mots  et , et où  est l'inverse formel de  dans  et où  est l'élément neutre de  . De manière équivalente, le problème est décider si  pour un mot  de , donc si  appartient au langage formel
.
Par un raccourci un peu elliptique, on dit aussi que l'ensemble  est le problème du mot.
On dit aussi que le problème du mot est résoluble si l'appartenance au langage  est décidable.

Exemples

Groupes avec un problème de mot résoluble 
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 
 Les groupes libres de type fini
 Les groupes abéliens de type fini
 Les 
 Les  de type fini, comprenant :
 Les groupes simples de type fini.
 Les groupes  finiment présentés
 Les groupes à un relateur (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.

Groupes avec un problème de mot indécidable 

 Soit X est un ensemble récursivement énumérable d'entiers naturels où le problème d'appartenance est indécidable. Alors le groupe  est de type fini avec une présentation récursivement énumérable et dont le problème du mot est indécidable.
 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 de type fini avec un problème du mot indécidable
 Le nombre de relateurs d'un groupe finiment présenté avec un problème du mot indécidable peut être égal à 14 ou même 12.
 Un exemple explicite d'une présentation avec un problème du mot indécidable est le suivant :
générateurs : 
relations :  (commutations), et de plus

Résultat généraux 

 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.
 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:
 Pour les groupes simples :

Note historique 
Les calculs dans les groupes sont souvent effectués en utilisant diverses formes normales. L'existence d'une telle forme normale résout en général implicitement le problème du mot pour les groupes étudiés. En 1911 Max Dehn propose de considérer le problème du mot comme un sujet d'étude important en lui-même, de même que le  et le . En 1912, il donne un algorithme pour résoudre le problème du mot et le problème de conjugaison pour les groupes fondamentaux de variétés fermées orientables de dimension 2 de genre supérieur ou égal à 2. D'autres auteurs ont ensuite étendu grandement l'algorithme de Dehn et l'ont appliqué à de nombreux problèmes de décision.

En 1955, Piotr Novikov montre qu'il existe un groupe finiment présenté G dont le problème du mot est indécidable. Il en résulte immédiatement que le problème du mot uniforme est également indécidable. Une preuve indépendant a été donnée par William Boone en 1958.

Le problème du mot a été l'un des premiers exemples d'un problème indécidable qui n'est pas issu de la logique mathématique ou de la théorie des algorithmes, mais de algèbre générale, branche centrale des mathématiques classiques.

Notes et références

Notes

Références citées

Livres
 
 

Articles

Voir aussi

Articles connexes
 Combinatoire des mots
 Problème du mot
 Automate à piles emboîtées (ils ont servi à la résolution du problème du mot dans les groupes)

Bibliographie complémentaire

Lien externe

Théorie des groupes
Combinatoire des mots