[GAP Forum] [group-pub-forum] Homomorphisms of finitely presented groups

[Hulpke,Alexander]

Dear Gabe Cunningham, (I am moving the reply into the GAP-Forum, which was probably the intended place in the hope that any further replies end up there),

> Suppose I have two finitely presented groups G and H with the same generating set (i.e. quotients of the same free group), and I want to use GAP to determine whether there is a natural homomorphism from G to H that sends the generators of G to the corresponding generators of H. Of course this is possible: GroupHomomorphismByImages(G,H). But sometimes the answer is obviously yes (by inspection of the presentation), and this command doesn't seem to take that into account. (For example, if G = <x, y  | (xy)^6> and H = <x, y | (xy)^3, x^2>, then clearly there is a natural homomorphism from G to H. The command takes about 7 seconds on my machine, and stopping the computation in the middle shows that it is performing a coset enumeration.)

What is happening is that GAP needs to determine a way for testing equality of elements in the image group H. This is done by requiring a "universal" method that will work for arbitrary words (and tries to find a faithful permutation representation through coset enumeration). No attempt is made to check that the word is a relator (as this is assumed to happen rarely).

> Is there already a clever way in GAP to use the presentation to optimize this operation for the kind of case I'm interested in? Or will I need to write such an optimization myself?

What you could do is to install your own,  method for \= (equality) for elements of fp group (the standard method is in line 164 of lib/grpfp.gi, you could just start from this method and modify it. If you read it in later it will rank higher than the library method) that would not only test for equality of the word expressions, but also checks --  if HasFpElementEquatityMethod(FamilyObj(left))-=false, i.e. no good equality test exists yet --
whether the word is  equal to any of the relators (or products, inverses, conjugates, etc.) This quickly will get more complicated than you might have hoped for, and you need to decide for a good heuristic how far you consider a consequence from relators as "obvious" (e.g. in your example, what if G has the relator (xy^4y^5x^4y^-5(xy)^2 instead while H is the same?)

Alternatively, you could install your own method for testing `IsMapping` for homomorphism (using the same strategy), but that is technically more complicated.

Finally, you could use `hom:=GroupGeneralMappingByImages(...)` instead of `GroupHomomorphismByImages`, and then do
SetIsMapping(hom,true) by hand if you (or your own routine) knows that it is a homomorphism.

Best wishes,

Alexander Hulpke