Dear GAP Forum

Dima Pasechnik wrote:

Dear Forum,

What is the best way to do the following in GAP ?

Given a finite finitely presented group, not so big, of order <10^4, but
with somewhat biggish presentation, G=< x_1...x_n | R_k(x_i) 0<k<r >, express
an identity word W(x_1..x_n)=1 as a product of conjugates of the
original relations R_k, i.e.
W(x_1..x_n)=R_{k_1}^{V_{i_1}} R_{k_2}^{V_{i_2}}..R_{k_w}^{V_{i_w}},
preferably having w as small as possible, and the words V_j as short as
possible.

(Perhaps it's better talking about R_k being generators for the kernel of the
homomorphism F(x_1...x_n) -> G. )

Also, it would help to be able to compute the following chain
of transformations leading to W:

[etc.]

This sounds like a difficult problem! In terms of complexity
theory, it has been proved that the problem of expressing group
relators as products of conjugates of the defining relators
is significantly more difficult than just solving the word
problem in a finitely presented group.

I have been trying to find a way of solving this in GAP, at least
for small groups, but I have got stuck on a related problem,
so perhaps somebody could help me with that.

Let H be a subgroup of a finitely presented group G, where H is
defined by generators given as words in the generators of G.
Let g be an element of H defined as a word in the generators of
G. How do you express g as a word in the given generators of H?
I haven't found a way of doing this, although it seems to me
that the information necessary to do it must be present in the
record returned by AugmentedCosetTableMtc. Of course, if H has
large index in G, then I would expect very long words to come out.

One possible approach to Dima Pasechnik's problem is to do the
following.

1. Suppose G is a finitely presented group defined as F/[R], where
F is a free group, and R is the set of defining relators of G.
Find a set R+ of conjugates of R that generates the normal closure
K of R as a subgroup of F.

2. Let x be an element of F that maps onto the identity of G.
Then write x as a word in R+.

Step 2 is the problem I mentioned above that I couldn't solve.

As for Step 1, it will often work if you take R+ to be the set of
conjugates of all elements of R under the inverse images in F of
all elements of G+.
This will not always work, but it is something to try.
In general, you might need to take conjugates of R under all words
in F that were used to define cosets of K in G in the coset
enumeration of G over the identity. (In fact, you could devise
a variant of the modified coset enumeration process to get a
more efficient version of R+, but that would involve serious
work!)

Example:

gap> F:=FreeGroup(2); R:=[F.1^2,F.2^3,(F.1*F.2)^3]; G:=F/R;  #A4.
gap> SG := [];
gap> for r in R do for e in List(Elements(G),UnderlyingElement) do
>     Add(SG,r^e);
>    od; od;
gap> Size(SG);
36
gap> K:=Subgroup(F,SG);
Group(<36 generators>)
gap> Index(F,K);
12

So SG has enough conjugates of R to generate K as a subgroup.
It is actually highly redundant, but that doesn't matter much.

I tried the following approach for Step 2.

gap> phi := IsomorphismFpGroupByGenerators(K,SG);;

But that wasn't very useful! It worked on some elements of K
but not on others.

gap> K.4^phi;
_x1
gap> (K.1*K.4)^phi;
_x1^2
gap> (K.1*K.5)^phi;
fail

Incidentally, other homomorphisms defined with domain K, such
as EpimorphismPGroup behave in a similar way.

Derek Holt.