> < ^ Date: Wed, 13 Apr 1994 20:07:00 +0100 (MET)
> < ^ From: Martin Schoenert <martin.schoenert@math.rwth-aachen.de >
< ^ Subject: Re: GpHomByImages
Chris Wensley writes in his e-mail message of 1994/04/13

I have a query about how GroupHomomorphismByImages works.
In the listing below Q,P are copies of D4 with Q an fp-group
and P a permutation group. When mapping Q to P there is only
one way to express the images of the generators. In the reverse
direction the image of generator (1,2,3,4) is listed
(surprisingly to me) as f.2^-1*f.1^-2*f.2^-1 rather than f.1
(although, of course, these are equal).

Here is what happens if you have a 'GroupHomomorphismByImages' from a
permutation group $P$. First GAP computes the size of $P$. Then it
constructs a (second) stabilizer chain for $P$, which is stored in the
record that represents the homomorphism (see "Stabilizer Chains" in the
manual for a explanation of what a stabilizer chain is).

Each computation is performed in parallel also with the images of the
generators. That means that the stabilizer chain contains for each
strong generator $s_i$ also its image under the homomorphism $t_i$.

To compute the image of an arbitrary element $p$ in the permutation
group, this element is divided through the stabilizer chain, i.e.,
'Image' computes a word $w$ in the strong generators $s_i$, such that
$p w(s_i) = ()$. In parallel we perform the same computation with the
images of the strong generators, i.e., we compute $w(t_i)$, which is
the inverse of the image.

Now when 'GroupHomomorphismByImages' constructs the stabilizer chain
it works essentially random. That is, it constructs random elements
and builds the stabilizer chain from those. It stops when the chain
is complete, i.e., when the product of the indices in the stabilizer
chain is equal to the size of the group $P$.

This helps to keep down the length of the words somewhat (but not enough
in most cases). On the other hand it makes it impossible to predict what
word you get when you map from $P$ into the free group $F$ (or a factor
thereof, but the words are actually always in $F$).

He continues

(Sorry if this is a trivial query, but I am a new user.)

There would be no need to apologize even if the question was trivial,
which it is not.

Hope this helps (if not, don't hesitate to ask again).


-- .- .-. - .. -.  .-.. --- ...- . ...  .- -. -. .. -.- .-
Martin Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

> < [top]