Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can anybody guide me towards, or possibly even explain here, the algorithm that GAP uses to compute the semidirectproduct of two permutation groups which outputs another permutation group?

EXAMPLE:

gap> C3:=CyclicGroup(IsPermGroup,3);
Group([ (1,2,3) ])
gap> C7:=CyclicGroup(IsPermGroup,7);
Group([ (1,2,3,4,5,6,7) ])
gap> A:=AutomorphismGroup(C7);
< group with 1 generators >
gap> elts := Elements(A);
[ IdentityMapping( Group([ (1,2,3,4,5,6,7) ]) ),
[ (1,2,3,4,5,6,7) ] -> [ (1,3,5,7,2,4,6) ],
[ (1,2,3,4,5,6,7) ] -> [ (1,4,7,3,6,2,5) ],
[ (1,2,3,4,5,6,7) ] -> [ (1,5,2,6,3,7,4) ],
[ (1,2,3,4,5,6,7) ] -> [ (1,6,4,2,7,5,3) ],
[ (1,2,3,4,5,6,7) ] -> [ (1,7,6,5,4,3,2) ] ]
gap> sigma := elts[2];
[ (1,2,3,4,5,6,7) ] -> [ (1,3,5,7,2,4,6) ]
gap> sigma^3;
[ (1,2,3,4,5,6,7) ] -> [ (1,2,3,4,5,6,7) ]
gap> map := GroupHomomorphismByImages(C3, A, GeneratorsOfGroup(C3), [sigma]);
[ (1,2,3) ] -> [ [ (1,2,3,4,5,6,7) ] -> [ (1,3,5,7,2,4,6) ] ]
gap> SDP := SemidirectProduct(C3, map, C7);
Group([ (2,3,5)(4,7,6), (1,2,3,4,5,6,7) ])

share|improve this question
    
The code is on line 919 of lib/gprdperm.gi I'll look over it to see if it is easy to explain. –  Jack Schmidt Aug 3 '12 at 20:11
3  
Oh my, yes it is very simple. A little scary. It rewrites the normal subgroup in its regular action (so $K$ acting on $|K|$ points), and then of course the complement subgroup acts on the normal subgroup giving the semidirect product of $H/C_H(K)$ with $K$. If $C_H(K) \neq 1$, then do the subdirect product smooshy thing with $H$'s original rep. –  Jack Schmidt Aug 3 '12 at 20:15
    
In particular, please don't try this with $S_{20}$ as the normal subgroup. :-) –  Jack Schmidt Aug 3 '12 at 20:15
    
@JackSchmidt Please consider converting your comment into an answer, so that this question gets removed from the unanswered tab. If you do so, it is helpful to post it to this chat room to make people aware of it (and attract some upvotes). For further reading upon the issue of too many unanswered questions, see here, here or here. –  Julian Kuelshammer Jun 23 '13 at 8:20
add comment

1 Answer

up vote 2 down vote accepted

The code is on line 919 of lib/gprdperm.gi and is very easy to understand.

It rewrites the normal subgroup in its regular action (so $K$ acting on $|K|$ points), and then of course the complement subgroup acts on the normal subgroup giving the semidirect product of $H/C_H(K)$ with $K$. If $C_H(K) \neq 1$, then it does the subdirect product smooshy thing with $H$'s original rep: that is $H \ltimes K$ acts on $X \dot\cup K$ where $H$ acts on $X$ as usual, $K$ centralizes $X$, and $H,K$ have the previously described action on $K$.

In particular, this method is impractical with $S_{20} as the normal subgroup.

If $K$ acts on $Y$ and $|H|$ is small, then $H \ltimes K$ can act on $H \times Y$ as well, but this is not implemented.

There is a special method implemented on line 961 to catch a nice case: if $K$ acts on $Y$, and if the action of $H$ on $K$ lifts to a homomorphism from $H$ to $\operatorname{Sym}(Y)$, then one can view $H$ more compactly as a subgroup of $\operatorname{Sym}(X \dot\cup Y)$. This method is not guaranteed to succeed even if applicable if $C_{\operatorname{Sym}(Y)}(K)$ is large, as the method to check if the homomorphism lifts is just to choose a random section and see if it a homomorphism.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.