0
$\begingroup$

Here are my questions:

(Weakened Word Problem) Let $\langle X |R\rangle$ be a finite presentation of a group $G$, and let $w$ be an element of the free group $F(X)$. Does there exist an algorithm (allowed to depend on $w$ as well as the presentation) that determines whether or not $w=_G 1$? If not, is there a concrete counterexample? Is this weakened problem easier than the classical Word Problem?

(Weakened Isomorphism Problem) Let $\langle X |R\rangle$ and $\langle Y |S\rangle$ be finite presentations of groups $G$ and $H$ respectively. Does there exist an algorithm (allowed to depend on the two presentations) that determines whether or not $G$ and $H$ are isomorphic? If not, is there a concrete counterexample? Is this problem easier than the classical Isomorphism Problem?

My understanding, which may be mistaken, is that the nub of the Word Problem is whether there is a uniform algorithm for deciding whether a word in a group is equal to the identity. It is now well known that there is no such algorithm in general, though if one restricts to groups belonging to various classes then the Word Problem is decidable. Similar remarks apply to the other classical group theoretic decision problems.

Is it true - perhaps trivially true - that if the algorithm is allowed to change with the input then these problems are solvable?

I see that in Magnus, Karrass and Solitar's book for example, the Isomorphism Problem is stated in terms of a fixed $G$ and a varying $H$ which suggests that the algorithm is allowed to be tailored to $G$ although not to $H$. This would appear to lie between the two alternative statements

(Classical Isomorphism Problem) $(\exists A)(\forall G, H)(\ldots)$ There exists an algorithm such that for all pairs of finite presentations$\ldots$

and

(Weakened Isomorphism Problem) $(\forall G,H)(\exists A)(\ldots)$ Fix finite presentations of $G$ and $H$. There exists an algorithm that decides$\ldots$

Of course if $G$ and $H$ are isomorphic, there is a finite string of Tietze transformations that demonstrate that they are isomorphic, so this gives the algorithm in this case; but what if the groups are not isomorphic?

We are used to showing groups are not isomorphic by pointing out natural group-theoretic properties enjoyed by one but not the other, such as finiteness, torsion, being abelian etc. But it seems unlikely to me that for every pair of non-isomorphic groups there exists some group theoretic property - detectable from the presentations, no less! - that distinguishes them.

On the other hand, are there examples of a pair of presentations where it is an open question whether or not they are isomorphic? Perhaps there are examples where deciding isomorphism would amount to finding, say, the smallest counterexample to a known conjecture. But in this case perhaps the statement that there exists an algorithm to determine isomorphism or non-isomorphism is demonstrably true, even if the algorithm itself and its output are not known.

(Similar remarks and questions apply with the Isomorphism Problem replaced by the Word Problem.)

$\endgroup$
  • $\begingroup$ I think it would be helpful to summarize your very long text so that there is a concise short question. Is it "if the algorithm is allowed to change with the input then these problems are solvable?" So far I am not sure what the exact question is. $\endgroup$ – Dietrich Burde Feb 22 at 10:37
  • $\begingroup$ what do you mean with "the algorithm depends on the presentation and $w$"? Apparently, there are groups where the word problem is not decidable (see en.m.wikipedia.org/wiki/Word_problem_for_groups#Examples). So even if "the algorithm depends on the presentation", for those examples, there should be no algo. $\endgroup$ – Babelfish Feb 22 at 10:39
  • $\begingroup$ @DietrichBurde OK, I've moved the questions to the top. The rest is background. Your paraphrase is correct; if the answer to that happens to be no, then I would also like to know if the problem is at least any easier than the Word Problem/Iso Problem. $\endgroup$ – user876789 Feb 22 at 10:46
  • $\begingroup$ @Babelfish Indeed, the Word Problem is undecidable: in general there is no algorithm that will decide, for all $w$, whether $w$ is equal to $1$ in $G$. But what if I allow the algorithm $A_w$ to vary with $w$? $\endgroup$ – user876789 Feb 22 at 10:49
  • $\begingroup$ See also this question. It is not clear how to ask for an explicit example for a group where we don't know whether it is the trivial group or not. $\endgroup$ – Dietrich Burde Feb 22 at 10:55
3
$\begingroup$

The answer to both of your questions is yes. In the first case, either the algorithm that outputs "Yes, $w=_G 1$", or the algorithm that outputs "no, $w \ne_G 1$" correctly determines whether $w =_G 1$. The fact that we might not know which of these is the correct algorithm does not alter the fact that such an algorithm exists.

A similar argument applies to the second question (and also to questions like "Is Goldbach's Conjecture true").

$\endgroup$
  • $\begingroup$ Thank you, this has helped to clarify my muddled thinking. $\endgroup$ – user876789 Feb 24 at 20:44

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.