[GAP Forum] Subgroups of a given order

[Alexander Konovalov]

Dear Alireza,

On 25 Jul 2014, at 12:46, arashrafi at kashanu.ac.ir wrote:

> 
> Dear GAP Forum Members,
> 
> Suppose G is a group of a given order n and m is a divisor of n. I am
> interesting to the problem of computing all subgroups of G of order n.
> Please notice that if n is enough large, it is not efficient to first
> compute all subgroups of G and then obtain subgroups of order m. For
> example I need to the subgroups of order 32 in a group of order 1024.
> Any suggestions or comments will be highly appreciated.
> 
> Regards, Alireza

Here there is a collection of links that may be useful:

7.7: How do I get the subgroups of my group?
http://gap-system.org/Faq/faq.html#7.7

39.21 Specific Methods for Subgroup Lattice Computations
http://gap-system.org/Manuals/doc/ref/chap39.html#X85E613D57F28AEFF

In particular, for the case of a solvable group there is
SubgroupsSolvableGroup with the optional argument which
permits to specify the order of the group:

gap> G:=DihedralGroup(1024);
<pc group of size 1024 with 10 generators>
gap> l:=SubgroupsSolvableGroup(G,rec(consider:=ExactSizeConsiderFunction(32)));
[ Group([  ]), Group([ f10 ]), Group([ f10, f9 ]), 
  Group([ f10, f9, f8 ]), Group([ f10, f9, f8, f7 ]), 
  Group([ f10, f9, f8, f7, f6 ]), 
  Group([ f10, f9, f8, f7, f6, f5 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f3 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f3, f1 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f1 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f1 ]), 
  Group([ f10, f9, f8, f7, f6, f1 ]), 
  Group([ f10, f9, f8, f7, f1 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f3, f2 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f3, f1*f2 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f1*f2 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f1*f2 ]), 
  Group([ f10, f9, f8, f7, f6, f1*f2 ]), 
  Group([ f10, f9, f8, f7, f1*f2 ]), 
  Group([ f10, f9, f8, f7, f6, f5, f4, f3, f1, f2 ]) ]
gap> List(l,Size);
[ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 256, 128, 64, 32, 
  512, 512, 256, 128, 64, 32, 1024 ]

This list is redundant by reasons explained below, so we have 
to filter out groups of order 32 from this list:

gap> Filtered(l, g -> Size(g)=32);
[ Group([ f10, f9, f8, f7, f6 ]), 
  Group([ f10, f9, f8, f7, f1 ]), 
  Group([ f10, f9, f8, f7, f1*f2 ]) ]

- these are representatives of conjugacy classes of subgroups of order 32. 

SubgroupsSolvableGroup implements the algorithm published in 
[Hulpke, A., Computing subgroups invariant under a set of automorphisms, 
J. Symbolic Comput., 27 (4) (1999), 415–427] and computes subgroups of 
a solvable group G, using the homomorphism principle. It returns a list 
of representatives up to G-conjugacy.

Just quoting the manual, "the 'consider' function does not provide a perfect 
filter. It is guaranteed that all subgroups fulfilling the condition are 
returned, but not all subgroups returned necessarily fulfill the condition." 

Anyhow, this is a little bit faster than computing all subgroups for the 
group from the example (and may be much more faster for other groups):

gap> G:=DihedralGroup(1024);
<pc group of size 1024 with 10 generators>
gap> l:=SubgroupsSolvableGroup(G,rec(consider:=ExactSizeConsiderFunction(32)));;time;
164
gap> G:=DihedralGroup(1024);
<pc group of size 1024 with 10 generators>
gap> l:=SubgroupsSolvableGroup(G);;time;
226
gap>

Hope this helps
Alexander

P.S. Perhaps in an interactive session I would be typing just the following:

gap> G:=DihedralGroup(1024);
<pc group of size 1024 with 10 generators>
gap> cc:=ConjugacyClassesSubgroups(G);;
gap> Filtered(cc, c -> Size(Representative(c))=32);
[ Group( [ f10, f9, f8, f7, f6 ] )^G, 
  Group( [ f10, f9, f8, f7, f1*f2 ] )^G, 
  Group( [ f10, f9, f8, f7, f1 ] )^G ]
gap>