[GAP Forum] extensions of subgroups of a finite 2-group

[Petr Savicky]

On Thu, Jul 17, 2014 at 04:29:18PM +0200, Max Horn wrote:
...
> On 16.07.2014, at 16:39, Petr Savicky <savicky at cs.cas.cz> wrote:
..
> > Assume, G is a finite 2-group and A is its subgroup.
> > The groups may be permutation groups or pc groups.
> > I would like to construct all extensions B of A, such
> > that [B:A] = 2.
> 
> I assume you meant "all extensions B *in G* of A...".

Yes. I am sorry for confusion.

> > One way is to perform
> > 
> >    N := Normalizer(G, A);
> >    R := RightTransversal(N, A);
> >    L := [];
> >    for elm in R do
> >        if elm in A then
> >            continue;
> >        fi;
> >        if elm^2 in A then
> >            Add(L, ClosureGroup(A, elm));
> >        fi;
> >    od;
> > 
> > Is there a better way?
> 
> Yes, there is, at least asymptotically -- it will be slower for small examples, but faster for larger ones. Do this:
> 
> 1. Compute the quotient H:=N_G(A)/A
> 2. Compute the conjugacy classes of involutions in H
> 3. For each involution in H, its preimage in N_G(A) resp. G
>    is a group with the desired property, and this correspondence 
>    is bijective.
> 
> Here is a direct implementation:
> 
>     N := Normalizer(G, A);
>     hom := NaturalHomomorphismByNormalSubgroup(N, A);
>     H := ImagesSource(hom);
>     cc := ConjugacyClasses(H);
>     L := [];
>     for cl in cc do
>         if Order(Representative(cl)) <> 2 then
>             continue;
>         fi;
>         for elm in cl do
>             elm := PreImagesRepresentative(hom, elm);
>             Add(L, ClosureGroup(A, elm));
>         od;
>     od;

Thank you very much for this improvement. The purpose of
the code is not listing all extensions of the specified
type, but taking one at random from the uniform distribution.
If the number of conjugacy classes is significantly smaller
than the order of H, then the above approach may be much
faster. It is sufficient to compute the sizes of the classes
of the involutions, choose a class at random with the
probability given by its relative size and then take an
element from the uniform distribution on the class.

I do not have an example of a group H = N_G(A)/A, where
G is 2-group and the number of conjugacy classes of H is
significantly smaller than the order of H. However, a direct
construction of a 2-group H with this property is easy

    WP := Group( [ (1,2), (1,3)(2,4), (1,5)(2,6)(3,7)(4,8),
      ( 1, 9)( 2,10)( 3,11)( 4,12)( 5,13)( 6,14)( 7,15)( 8,16),
      ( 1,17)( 2,18)( 3,19)( 4,20)( 5,21)( 6,22)( 7,23)( 8,24)
      ( 9,25)(10,26)(11,27)(12,28)(13,29)(14,30)(15,31)(16,32) ] );
    pciso := IsomorphismPcGroup(WP);
    H := Image(pciso, WP);
    CC := ConjugacyClasses(H);
    Print(Length(CC), "  ", Size(H), "\n");

    26795  2147483648

This computation takes about 55 seconds on my computer,
even together with a run through all classes in CC, which
is omitted from the code above.

The estimate of going through all elements of H, based
on a partial run, is about 15 hours.

> > Another question is as follows. Let G be a 2-group
> > and H and A its subgroups, such that the intersection
> > of H and A is trivial. Is it possible to determine
> > in GAP, whether there is a subgroup B of G, such
> > that B contains A and is a complement of H in G?
> 
> I am not aware of a direct method. When H is normal, maybe using ComplementClassesRepresentatives would help a bit, by reducing the problem to conjugacy classes of complements.

Thank you for your reply. The group H is a point stabilizer
of a transitive action, so it is not normal.

All the best,
Petr.