Is the group isomorphism problem decidable for abelian groups?

Question

According to wikipedia the group isomorphism problem is an undecidable problem.

When we restrict to (countable) abelian groups does it become decidable or does it remain undecidable?

In case it becomes decidable I'd love to have a reference to an algorithm deciding it.

Answer 1

This is not a full answer (somehow I cannot comment), but when talking about presentations of abelian groups only the exponentvectors matter. This means: for a relation $x_1^{a_1}...x_n^{a_n}$ the only $[a_1,...,a_n]$ matters.

Therefore I presume the question can be decided by creating a matrix where the exponentvectors are its rows (entries are in $\mathbb Z$ ) and bringing it to some normal form (upper triangular) utilizing the euclidean algorithm (note that $\mathbb Z$ is not a field) which will then yield the isomorphism type as stated by the fundamental theorem of abelian groups.

I don't have a reference on this common knowledge but it might point you in some direction.

update2: I just noticed this is exactly what the Smith normal form computes. But this only applies to finite presentations, as stated in comments.

Answer 2

If you are considering the notion of decidability in the sense of Turing decidability, as is usual in computability theory, then it doesn't make immediate sense to ask whether the isomorphism problem for arbitrary countable groups is decidable or not, since the "input" for an instance of this problem would consist of two infinite objects, the groups in some form of presentation. This takes one outside the context of decidability with Turing machines, which work with finite input and output.

The problem does make sense for finitely presented groups, since here one can be given two such presentations. In the abelian case, the isomorphism problem in this case is decidable. In the non-abelian case, it is not decidable---a result following from the non-decidability of the word problem, since one cannot even determine the special case of whether a given presentation is a presentation of the trivial group.

If you consider computably presented groups, by taking as inputs two programs that will enumerate the relations, then you will not be able to decide in finite time any nontrivial property of the sets they enumerate. This is a consequence of Rice's theorem. For example, you will not be able to decide whether the programs will enumerate no relations or all relations, and so the isomorphism problem will not be decidable in this context.

Nevertheless, by adopting a more set-theoretic rather than computational perspective, one could inquire what is the descriptive-set-theoretic complexity of the set of pairs of isomorphic countable abelian groups. It clearly has complexity at most $\Sigma^1_1$, that is, lightface analytic, since two groups are isomorphic iff there is an isomorphism, and I believe that it is likely $\Sigma^1_1$-complete, since the countable abelian groups can code quite a bit of information, but I would have to check with my descriptive set-theoretic collegues.

There is also the subject of Borel equivalence relation theory, which considers the complexity of equivalence relations under Borel reducibility, and in general, the isomorphism relation for finitely generated groups (not necessarily abelian) is a Borel relation in the relevant space, but quite high in complexity. The isomorphism relation of arbitrary countable groups is much higher still, and as I've said, I think it remains high even just for countable abelian groups.