16
$\begingroup$

Is it algorithmically decidable if two finitely presented amenable groups are isomorphic?

Or slightly different:

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

$\endgroup$

3 Answers 3

26
$\begingroup$

EDIT: The isomorphism problem for finitely presented solvable groups in the variety of all solvable groups of derived length $\le 7$ is undecidable. This was proved by Kirkinskiĭ and Remeslennikov (Kirkinskiĭ, A. S.; Remeslennikov, V. N. `The isomorphism problem for solvable groups.' (Russian) Mat. Zametki 18 (1975), no. 3, 437–443.). The Russian version of this article can be downloaded from here. The English translation is available here.

Unfortunately this does not fully answer the original question, because the groups in this construction are finitely presented in the variety of solvable groups but may not be finitely presented in the variety of all groups.

I would guess that one could use O. Kharlampovich's example of a finitely presented 3-step solvable group with unsolvable word problem (Harlampovič, O. G., `A finitely presented solvable group with unsolvable word problem.' (Russian) Izv. Akad. Nauk SSSR Ser. Mat. 45 (1981), no. 4, 852–873, 928.) to construct the family of groups you need. Perhaps someone has already done this...

Second EDIT: Indeed, this was done by Baumslag, Gildenhuys and Strebel (see Theorem 1 in Baumslag, Gilbert; Gildenhuys, Dion; Strebel, Ralph, `Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. II.' J. Algebra 97 (1985), no. 1, 278–285.), who proved that the isomorphism problem is undecidable in the class of finitely presented solvable groups of derived length 3.

In fact, in one of her talks Olga Kharlampovich mentioned that she can construct a finitely presented 3-step solvable group $G$ with unsolvable word problem that is Hopfian. Then the isomorphism problem among the quotients of $G$ by one defining relation is unsolvable (because $G/\langle\langle g \rangle\rangle^G$ is isomorphic to $G$ if and only if $g=1$ in $G$).

$\endgroup$
4
  • $\begingroup$ @Hans: sorry for the confusion, my original response was wrong and it actually does not answer your question -- see the edit. However, I still think that the answer is negative for f.p. solvable groups. Kharlampovich's example could probably be used as a starting point. You should probably `unaccept' the answer, if possible. $\endgroup$ Mar 1, 2013 at 15:36
  • $\begingroup$ @Ashot Minasyan: I also had somewhat Kharlampovich's paper in mind, and wondered somewhat, because it is often cited when it comes to word problem and amenable groups. So I thought you found an earlier reference. But anyway your answer is indeed already helpful, as I am not necessarily interested in a finite representation but any reasonable indexing (second question, which is a somewhat unproper as one may always concatenate the index with an undecidable function). $\endgroup$
    – Hans
    Mar 1, 2013 at 16:30
  • $\begingroup$ @Hans: the new edit hopefully settles the question. You could probably email to O. Kharlampovich asking about the construction of Hopfian examples. She mentioned it quite recently -- in a conference in Diablerets in 2010. Her talk is entitled "Algorithmic problems in solvable groups, Part 2", you can google it. $\endgroup$ Mar 1, 2013 at 16:39
  • $\begingroup$ @Ashot Minasyan: Thank you very much for your new references and further edit. Yes, this answers the question completely. Thanks again for your help. $\endgroup$
    – Hans
    Mar 1, 2013 at 17:37
10
$\begingroup$

According to the diagram on page 31 of Chuck Miller's authoritative MSRI notes, the isomorphism problem is known to be undecidable for finitely presented solvable groups of derived length 3, and hence for amenable group. I'll add further details when I have time.

$\endgroup$
2
  • 2
    $\begingroup$ Thank you very much. The reference you state can be downloaded here: ms.unimelb.edu.au/~cfm/papers/paperpdfs/msri_survey.all.pdf I see.. $\endgroup$
    – Hans
    Mar 1, 2013 at 16:48
  • $\begingroup$ Looks like Ashot added the details to his answer around the same time as I posted mine, so I'll leave it at that. $\endgroup$
    – HJRW
    Mar 1, 2013 at 22:08
7
$\begingroup$

This answer is to point out that the particular way in which you have posed the second question is not actually the question you meant to ask, for it admits a trivial answer, requiring almost no knowledge about amenable groups. Namely, you ask,

Does there exist a family of amenable groups (indexed by natural numbers) for which one cannot algorithmically decide if two elements of the family are isomorphic?

The answer is yes. Fix any non-computable set $A\subset\mathbb{N}$, and then enumerate the groups you are interested in $G_0,G_1,G_2,\ldots$ (assuming there are at least two non-isomorphic such groups) in such a way so that the indices $n$ of one of the isomorphism classes is exactly $A$, and use the rest of the indices for the rest of the groups (or just some of them) in an arbitrary manner. That is, we make all $G_n$ for $n\in A$ isomorphic, and not isomorphic to any other $G_m$ for $m\notin A$. With such an enumeration, the isomorphism problem is not decidable, simply because for a fixed $k\in A$, we cannot tell if $G_n\cong G_k$, because this would provide a decision procedure for $n\in A$, which is undecidable.

For example, a similar argument shows that there is an enumeration $G_0,G_1,G_2,\ldots$ of copies of the two groups $\mathbb{Z}$ and $\mathbb{Z}/2\mathbb{Z}$, such that the isomorphism problem is not decidable. Simply make $G_n\cong\mathbb{Z}$ if $n\in A$ and otherwise $G_n\cong \mathbb{Z}/2\mathbb{Z}$, for a fixed undecidable set $A$.

Of course this isn't the answer you or anyone is interested in, even though it does answer the question you actually asked. So the point is that you shouldn't consider such arbitrary enumerations when asking decidability questions about finitely presented groups, but rather you want to ask about decidability questions for the more natural enumerations of the presentations that arise from a natural indexing of the presentations, by means of a coding of the syntax of the presentation.

$\endgroup$
11
  • 1
    $\begingroup$ I took a recursion theory class as an undergrad and haven't really interacted with "logic" type things sense, but one thing I do miss is being able to make constructions as sneaky as this :-) $\endgroup$ Mar 2, 2013 at 2:35
  • $\begingroup$ @Joel David Hamkins: In group theory by decidability of such a problem we would understand the the algorithm takes on input two finite presentations (and not their indices) from the given family and outputs whether or not the groups given by these presentations are isomorphic. In this sense the isomorphism problem is decidable for any subclass of a class where it is decidable (the enumeration plays no role here). $\endgroup$ Mar 2, 2013 at 9:42
  • $\begingroup$ Surely the point is that the OP meant a recursive enumeration (ie such a family of presentations output by some Turing machine). So it's really just a typo. You don't need anything as fancy as 'a coding of the syntax of the presentation'. $\endgroup$
    – HJRW
    Mar 2, 2013 at 9:58
  • $\begingroup$ @Joel David Hamkins: Thank your for your comment. I was quickly aware of this afterwards when I posted it. I answered already Ashot Minasyan: "but any reasonable indexing (second question, which is a somewhat unproper as one may always concatenate the index with an undecidable function)." @HW: That's a good way to interpret it. $\endgroup$
    – Hans
    Mar 2, 2013 at 10:57
  • 1
    $\begingroup$ Joel, I take your point. I suppose a better group-theoretic example would be the difference between having a fp linear group represented by a generating set of matrices or as a finite presentation---in general, there's no algorithm to go from one to the other. (Though the isomorphism problem is unsolvable for both, as it happens.) $\endgroup$
    – HJRW
    Mar 2, 2013 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.