14
$\begingroup$

I am learning algebra and I am a bit confused.

Let's say I have a finitely presented group $G$, can anyone tell me if it is possible to find out if $G\cong \mathbb{Z}$?

Thanks

$\endgroup$
  • 8
    $\begingroup$ In general determining whether a finite presentation defines the trivial group is an undecidable problem. This is surely equally as hard. $\endgroup$ – Lord Shark the Unknown Jul 12 '18 at 15:20
  • 1
    $\begingroup$ Without specifying some properties of the group, problems like these tend to be unsolvable. See The Word Problem $\endgroup$ – lulu Jul 12 '18 at 15:20
  • 2
    $\begingroup$ If G is infinite, and If all of $G$ can be generated by one element, then it is isomorphic to $\mathbb Z$ $\endgroup$ – amWhy Jul 12 '18 at 15:21
  • 6
    $\begingroup$ Others have pointed out that this problem is undecidable, but it is semi-decidable in the sense that if $G \cong \mathbb{Z}$ then it is possible to prove it. $\endgroup$ – Derek Holt Jul 12 '18 at 16:23
  • 1
    $\begingroup$ Note that the answers assume that by "I have a finitely presented group $G$" you mean "I have a given finite presentation". $\endgroup$ – YCor Jul 13 '18 at 23:14
20
$\begingroup$

No. More strikingly: it is undecidable if a finitely presented group is the trivial group! These facts were proven (independently) by Adyan and Rabin in the 50s. The key idea is that of "Markov properties":

A property $\mathcal{P}$ of finitely presentable groups is a Markov property if:

  1. the property $\mathcal{P}$ is preserved under group isomorphism.
  2. there exists a finitely presentable group (a witness) $K_+$ with property $\mathcal{P}$.
  3. there exists a finitely presentable group $K_{-}$ which cannot be embedded as a subgroup in any finitely presentable group with property $\mathcal{P}$.

The theorem is as follows:

Theorem (Adyan-Rabin). If $\mathcal{P}$ is a Markov property then there does not exist an algorithm with input a finite presentation $G = \langle \mathbf{x} \mid \mathbf{r}\rangle$ and which decides whether or not the group $G$ defined by this presentation has property $\mathcal{P}$.

For a reference, see Lydon and Schupp, Combinatorial group theory, Section IV.4, p192. I tried to set this theorem, and some related results, in the "big picture" of group theory in this old answer.

So, for the examples I mentioned above:

  • being infinite cyclic is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid-\rangle$ and $K_-=\langle a\mid a^2\rangle$.
  • being trivial is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a\mid a^2\rangle$.

Another example:

  • being finite is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a\mid -\rangle$.

Now, being infinite is not a Markov property (as every finite group embeds in an infinite group). However, this is still undecidable as it is the complement of a Markov property: Suppose I have an algorithm with input $\langle \mathbf{x}\mid\mathbf{r}\rangle$ and which tells me if the associated group is infinite. If it returns "no" then my group is finite. Hence, I can detect finiteness, a contradiction.

A third example (hyperbolic groups are standard objects in geometric group theory):

  • being hyperbolic is a Markov property: it is preserved under isomorphism, and take $K_+=\langle a\mid a\rangle$ and $K_-=\langle a, b\mid [a, b]\rangle$. (It is a theorem that $\mathbb{Z}\times\mathbb{Z}$ does not embed into any hyperbolic group.)

Derek Holt points out in the comments to the question that the problem is semi-decidable. I thought it would be a good idea to build on this a litte:

Lemma. If $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ is (infinite) cyclic then it is possible to prove it.

This does not contradict undecidability, as you will never know when to conclude that the input group $G$ is not infinite cyclic. That is, suppose that we input $\langle \mathbf{x}\mid\mathbf{r}\rangle$ into the procedure given by the above lemma, and it doesn't terminate after 1 hour. What can we conclude? Well, we can conclude nothing! It may be the case that the underlying group is infinite cyclic, but we need 100 years of computation to prove that it is so.

Proof of Lemma. Write $\mathbf{x}=\{x_1, \ldots, x_n\}$. If $G$ is cyclic then there exists a word $w\in F(\mathbf{x})$ and integers $p_0, \ldots, p_n$ such that $x_i=_Gw^{p_i}$. So, enumerate all consequences of the relators and then check each consequence to see if it has the form $x_i^{-1}w^{p_i}$ for some $i, p_i, w$. Terminate the procedure if we have a "complete" set $\{x_i^{-1}w^{p_i}\mid i=1, \ldots, n\}$ with $w$ fixed. If we conclude that $G$ is cyclic then we can easily determine if it is infinite cyclic, as required.

Sticking with the examples above, we also have the following lemma:

Lemma. If $G=\langle \mathbf{x}\mid\mathbf{r}\rangle$ is trivial then it is possible to prove it.

Proof. Write $\mathbf{x}=\{x_1, \ldots, x_n\}$. Enumerate all consequences of the relators and then check each consequence to see if it has the form $x_i$. Terminate the procedure if we have a "complete" set $\{x_i^{-1}\mid i=1, \ldots, n\}$.

$\endgroup$
  • 2
    $\begingroup$ For reference for the OP, there are smaller categories of groups (e.g., word-hyperbolic groups) in which the word problem and similar problems are decidable. $\endgroup$ – anomaly Jul 12 '18 at 15:38
  • 3
    $\begingroup$ The analogy to Rice's theorem is interesting and possibly instructive. (Or, viewed another way, this is Rice's theorem. I think.) $\endgroup$ – MJD Jul 12 '18 at 15:39
  • 3
    $\begingroup$ This is the clearest summary of this stuff that I’ve ever seen. $\endgroup$ – Randall Jul 12 '18 at 17:09
  • $\begingroup$ The statement of the Adian–Rabin theorem reminds me of Rice's theorem. $\endgroup$ – user76284 Jul 13 '18 at 3:11
  • 1
    $\begingroup$ In the proof of the first lemma, I don't think that if $\langle\mathbf x|\mathbf r\rangle$ is cyclic then there is one among the $x$'s such that all the others are powers of that one. For example, $(\mathbb Z,+)$ is generated by $2$ and $3$. So the search in the proof should terminate when you find some word $w$ such that all the $x$'s have been found to be powers of $w$ (whether or not $w$ is one of the given generators). $\endgroup$ – Andreas Blass Jul 13 '18 at 18:07
1
$\begingroup$

It depends. If there's only one generator, the answer is easy. But if there is more than one generator, then in general no, the problem is provably undecidable!

$\endgroup$

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.