decidability of group homomorphism existence - MathOverflow

decidability of group homomorphism existence

2009-10-18T16:46:43Z

Fix a finitely-presented group G with distinguished non-identity element g. For any finitely-presented group H with element h, is it decidable whether there is a homomorphism h: G -> H such that h(g) = h?

If we know G is cyclic, the question is undecidable by reduction from the Word Problem. But what if we don't know anything about G? What if we know g has finite order in G?

Answer by Charles Siegel for decidability of group homomorphism existence

2009-10-19T14:45:10Z

I'm with Reid. If G,H are finitely presented, and g,h elements, and we want to know if there's a morphism f:G->H with f(g)=h, wouldn't that restrict to a morphism on the cyclic group generated by g, and thus be immediately undecidable?

Answer by Hugh Thomas for decidability of group homomorphism existence

2009-10-19T21:11:02Z

If G is infinite cyclic and g generates G, then the answer is: "yes, there is such a map" (so in particular, it's not undecidable at all).

So I'm not quite sure what the original poster meant by saying that if G is cyclic, the problem is redicible to the word problem. Maybe, if someone sees how that argument would go (and what the right hypothesis is), they could explain it.

Then it might be more clear whether this same argument can be applied if G is not cyclic.

Charles is right, of course, to say that a map from G to H restricts to a map from the cyclic group generated by g, to H, but if you could determine that there was no appropriate map from G to H, that wouldn't necessarily tell you that there was no appropriate map from < g> to H, so, on the face of it, it's possible that it could be decidable that there were no appropriate maps from G to H, but not decidable whether or not there were appropriate maps from < g> to H. (Here, "appropriate" means "taking g to h".)

(Edited to correct html issue.)

Answer by Henry Wilton for decidability of group homomorphism existence

2009-11-04T03:09:56Z

As people have already observed, if G is infinite cyclic and g is a generator, then the answer is always "yes". Steven Sam's comment shows that there can't be a uniform algorithm that works for all cyclic groups Z/n. In fact, the problem is undecidable for any given n. For instance:-

For finite cyclic G of order n with generator g, the question can be rephrased as "Is it decidable whether the element h is of finite order dividing n?". Suppose H is torsion-free. If this problem is decidable for some n then the word problem is solvable in H.

But the word problem is not solvable in torsion-free groups. For instance, Collins and Miller constructed a sequence of presentations for torsion-free groups H_1, H_2,... with the property that each H_i is torsion-free and it is undecidable which of the H_i are trivial. (More precisely, the set of all i such that H_i is trivial is recursively enumerable but not recursive.)