Théorème d'Adian-Rabin

En mathématiques, et plus précisément en théorie des groupes, le théorème d'Adyan-Rabin est un résultat qui affirme qu'une classe de propriétés des groupes finiment présentables sont algorithmiquement indécidables. Le théorème est dû à Sergei Adyan (1955)^[1] et, indépendamment, à Michael O. Rabin (1958).

Une propriété de Markov est une propriété P portant sur les groupes finiment présentables telle que :

1. P est une propriété abstraite, c'est-à-dire que P est préservé par isomorphisme de groupes.
2. Il existe un groupe finiment présentable ${\displaystyle A_{+}}$ avec la propriété P.
3. Il existe un groupe finiment présentable ${\displaystyle A_{-}}$ tel que tout groupe possédant ${\displaystyle A_{-}}$ comme sous-groupe ne possède pas P.

Par exemple, être un groupe fini est une propriété de Markov : on peut prendre pour ${\displaystyle A_{+}}$ le groupe trivial et pour ${\displaystyle A_{-}}$ le groupe infini ${\displaystyle \mathbb {Z} }$.

En langage moderne, le théorème d'Adyan-Rabin s'énonce^[2],[3],[4] :

Soit P une propriété de Markov. Il n’existe pas d’algorithme qui, étant donné une présentation finie ${\displaystyle G=\langle X\mid R\rangle }$, décide si le groupe ${\displaystyle G}$ défini par cette présentation a la propriété P.

Le mot « algorithme » est utilisé ici dans le sens de la théorie de la calculabilité. Plus formellement, le théorème d'Adyan-Rabin signifie que l'ensemble de toutes les présentations finies

${\displaystyle \langle x_{1},x_{2},x_{3},\dots \mid R\rangle }$

(où ${\displaystyle x_{1},x_{2},x_{3},\dots }$ est un alphabet dénombrable infini fixé, et ${\displaystyle R}$ est un ensemble fini de relations en ces générateurs et leurs inverses) définissant les groupes ayant la propriété P, n'est pas un ensemble récursif.

Une propriété P non triviale et héréditaire (i.e. telle que si un groupe possède P, alors ses sous-groupes aussi) est une propriété de Markov.

Le théorème d'Adyan-Rabin généralise un résultat antérieur similaire pour les semi-groupes d'Andrey Markov, Jr.^[5], prouvé par des méthodes analogues. C'est aussi pour les semi-groupes que Markov a introduit la notion de propriété de Markov. Ce Markov, logicien soviétique, ne doit pas être confondu avec son père, le probabiliste Andreï Markov.

Selon Don Collins, la notion de propriété de Markov, telle que définie ci-dessus, a été introduite par William Boone dans son exposition de l'article de Rabin de 1958.

Une preuve du théorème d'Adyan-Rabin^[2],[3] consiste à réduire la décidabilité de P à un problème du mot, via des produits amalgamés et des extensions HNN bien choisies.

Soit ${\displaystyle P}$ une propriété de Markov et ${\displaystyle A_{+},A_{-}}$ les témoins positifs et négatifs de la propriété de Markov. Choisissons ${\displaystyle G=\langle X\mid R\rangle }$ un groupe de présentation finie dont le problème du mot est indécidable.

La preuve construit alors récursivement, pour un mot ${\displaystyle w}$ en les générateurs ${\displaystyle X\cup X^{-1}}$, un groupe de présentation finie ${\displaystyle G_{w}}$ tel que si ${\displaystyle w=_{G}1}$ alors ${\displaystyle G_{w}}$ est isomorphe à ${\displaystyle A_{+}}$, et si ${\displaystyle w\neq _{G}1}$ alors ${\displaystyle G_{w}}$ contient ${\displaystyle A_{-}}$ en tant que sous-groupe.

Les propriétés suivantes sont des propriétés de Markov et donc sont algorithmiquement indécidables :

1. Être le groupe trivial.
2. Être un groupe fini.
3. Être un groupe abélien.
4. Être un groupe libre.
5. Être un groupe nilpotent.
6. Être un groupe résoluble.
7. Être un groupe moyennable.
8. Être un hyperbolique.
9. Être un groupe sans torsion.
10. Être un groupe polycyclique.
11. Être un groupe avec un problème de mots résoluble.
12. Être un groupe résiduellement fini.
13. Être un groupe de dimension cohomologique finie.
14. Être un groupe automatique (les groupes automatiques ont un problème du mot résoluble).
15. Être un groupe simple. (On peut prendre ${\displaystyle A_{+}}$ être le groupe trivial et ${\displaystyle A_{-}}$ être un groupe de présentation finie avec un problème du mot non résoluble. Alors le théorème de Kuznetsov implique que ${\displaystyle A_{-}}$ (ne se plonge dans aucun groupe simple finiment présentable.)
16. Être un groupe de dimension asymptotique finie.

Le théorème d’Adyan-Rabin implique également que la négation d’une propriété de Markov est également algorithmiquement indécidable. Par exemple, les propriétés d’être non trivial, infini, non abélien, etc., pour les groupes finiment présentables sont indécidables. Il existe cependant des exemples de propriétés indécidables telles que ni ces propriétés ni leurs négation ne soient de Markov. Ainsi, Collins (1969) a prouvé que la propriété d'être hopfien est indécidable pour les groupes finiment présentables.

• Théorème de plongement de Higman (en)
• Théorie de Bass-Serre (en)

• C. F. Miller, III, Decision problems for groups — survey and reflections. Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), pp. 1–59, Math. Sci. Res. Inst. Publ., 23, Springer, New York, 1992, (ISBN 0-387-97685-X)

• Portail de l’algèbre