> < ^ From:

> < ^ Subject:

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.

> < [top]