GAP and Free group

Question

Let $H$ and $K$ be finitely generated subgroups of the free group $F(n)$ such that $H\subseteq K$. We Know that $K$ is a free group. Now we choose basis for $K$ and $H$ and I want to rewrite the basis of $H$ in the choosen basis of $K$. I can do this calculation with hand by using automaton of $K$ but it take a long time. How can I do this with GAP?

Answer 1

You can do this using the FGA package which you will have if you installed GAP as suggested by its instructions, but which unfortunately is not included in the debian (or ubuntu) package archive. By the way, it also works by using automata.

Let's first ignore $H$ and see how to write a word in the generators of $K$.

First set up the stage:

gap> f:=FreeGroup("a","b");
<free group on the generators [ a, b ]>
gap> AssignGeneratorVariables(f);
#I  Assigned the global variables [ a, b ]
gap> k:=Group(a^2,a*b);
Group([ a^2, a*b ])
gap> word:=a^-1*b;
a^-1*b

Now the idiomatic way to express what we want is to define a homomorphism from another free group to $K$ and then ask for a preimage. We can do exactly that:

hom:=GroupHomomorphismByImages(FreeGroup(2),k);
[ f1, f2 ] -> [ a^2, a*b ]
gap> PreImagesRepresentative(hom,word);
f1^-1*f2

So we see that to get our word, we have to multiply the inverse of the first generator of $K$ with the second.

Note that this works no matter whether or not the generators of $K$ are free, we can use the same method to find a way how to write $a^2$ as a word in $a^{16}$ and $a^{42}$.

In this case, $K$ is given by a free generating set, so we could also use a homomorphism in the other direction:

gap> hom2:=GroupHomomorphismByImages(k,FreeGroup(2));
[ a^2, a*b ] -> [ f1, f2 ]
gap> word^hom2;                                      
f1^-1*f2

Depending on what you want to do with the result, you might prefer to avoid using homomorphisms and just get a list of numbers representing generators, with negative sign indicating inverse:

gap> AsWordLetterRepInGenerators(word,k);
[ -1, 2 ]

Now if we have a subgroup $H$, we just iterate over its generators and use any of the above methods, for example:

gap> h:=Group(a^-1*b,a^4);
Group([ a^-1*b, a^4 ])
gap> List(GeneratorsOfGroup(h),w->PreImagesRepresentative(hom,w));
[ f1^-1*f2, f1^2 ]

(See also section 2.3 of the FGA manual.)