9
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It's the fundamental theorem of finitely generated abelian groups. I'd like to consider countable groups. $\endgroup$ – Rasmus Jan 8 '11 at 15:13
  • $\begingroup$ Any group having a finite presentation is by definition finitely generated. The isomorphism problem doesn't make sense for infinite presentations. $\endgroup$ – Myself Jan 8 '11 at 15:21
  • 2
    $\begingroup$ @Myself: why not? Can't you give a Turing machine which prints out the relations? $\endgroup$ – Qiaochu Yuan Jan 8 '11 at 15:23
  • 2
    $\begingroup$ @Myself: sometimes people considered recursively presented groups as well in this theory. Apparently the fact that it is practically impossible for finite groups and provably impossible for some infinite finitely presented groups is not enough to deter the desire for more infininininitude. Countable torsion abelian groups actually have pretty recursive presentations, so I guess there is a good reason to study them. $\endgroup$ – Jack Schmidt Jan 8 '11 at 16:07
  • 1
    $\begingroup$ Looking at some papers though, it strikes me yet again as how ugly these problems are. Bounded abelian groups are direct sums of cyclic groups, just like finitely generated groups. However, it may not be possible to write down a set of direct summands of a recursive presentation of a bounded (countable) abelian group. So at the very least the "constructive recognition problem" is impossible, even if the "there is an isomorphism, we just have no idea what it is" problem is solvable. $\endgroup$ – Jack Schmidt Jan 8 '11 at 16:11
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thank you for this interesting answer. Actually, the groups that come up in the application I have in mind come with or are defined via a finite presentation, and I have to check whether they are free or not. Do you know if there is an algorithm known for this particular case? $\endgroup$ – Rasmus Jan 9 '11 at 0:10
  • $\begingroup$ Also a reference for the decidability in the finitely presented abelian case would be great. $\endgroup$ – Rasmus Jan 9 '11 at 10:09
  • $\begingroup$ I kind of linked you through to the algorithm for finite presentations below... it's called the Smith normal form. $\endgroup$ – Myself Jan 9 '11 at 21:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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