7
$\begingroup$

Given two finite presentations of torsion-free groups, is there an algorithm to determine whether the given groups are isomorphic or not?

I have found results for narrower classes (for example, they are briefly reviewed in The isomorphism problem for finitely generated fully residually free groups).

$\endgroup$
2
  • 7
    $\begingroup$ No. This follows from Adian-Rabin but, more explicitly, Adian in his original paper(s) (see my translation here) gave an infinite family of torsion-free groups for which the triviality problem is undecidable. So one cannot even decide whether a given torsion-free group is trivial. In general there is no simplification by assuming torsion-freeness, the first groups with undecidable word problem are torsion-free. $\endgroup$ Commented May 4, 2023 at 4:58
  • $\begingroup$ Thanks a lot! If you post your comment as an answer, I will accept it. $\endgroup$ Commented May 4, 2023 at 5:28

1 Answer 1

9
$\begingroup$

Novikov's centrally-symmetric group $\mathfrak{A}_P$ is a torsion-free group with undecidable word problem, constructed in [1]. Novikov did not prove it is torsion-free but, as Adian points out in [Adi1957b] (p. 76 of my translation, and referenced as in there; he calls the group $F_0$ in that article), it is not difficult to prove this fact using Novikov's work.

The statement of the Adian-Rabin theorem is today done via Markov properties (as defined by Markov when he proved the corresponding theorem for semigroups a few years earlier). And this is how Adian does it in [Adi1957b], too, but in his main article [Adi1957a], which contains all the detailed proofs, there are no Markov properties, only a slightly smaller family of properties (I call them "pseudo-Markov"). Instead, what Adian does in [Adi1957a] is the following:

Let $A, B$ be any two words in $\mathfrak{A}_P$. From these two words and $\mathfrak{A}_P$ he constructs a new finitely presented group, which he calls $\mathfrak{A}_{q, A, B}$, and which has the following property: $\mathfrak{A}_{q, A, B}$ is trivial if and only if $A = B$ in $\mathfrak{A}_P$. Furthermore, the groups $\mathfrak{A}_{q, A, B}$, for all $A, B$, are all torsion-free (he does not state it directly but it follows from the same type of argument as in his behemoth Main Lemma).

This yields the weaker Adian-Rabin theorem, but it also yields the undecidability you want; the family $\mathfrak{A}_{q, A, B}$, together with the trivial group, is recursively enumerable (indeed the way one constructs the groups is given explicitly, and in modern terminology it is just taking some HNN-extensions of $\mathfrak{A}_P$), and so if we could decide the isomorphism problem for torsion-free groups, then we could decide the isomorphism in this class, so we could also decide the word problem for $\mathfrak{A}_P$, a contradiction.

(Footnote: note that there are Markov properties $\mathcal{P}$ such that the isomorphism problem for all groups with $\mathcal{P}$ is decidable (trivially, we may take the property "being trivial"; but less trivially we may take "being hyperbolic" or "being abelian"). But I suspect that given any Markov property $\mathcal{P}$ such that there are groups with undecidable word problem with $\mathcal{P}$, the isomorphism problem for the class of groups with $\mathcal{P}$ is undecidable; I think I am missing some simple argument for why this is the case.)

[1] Novikov, P. S., On the algorithmic insolvability of the word problem in group theory, Am. Math. Soc., Transl., II. Ser. 9, 1-122 (1958). ZBL0093.01304.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .