[GAP Forum] Subgroups of a given order
Alexander Konovalov
alexk at mcs.st-andrews.ac.uk
Fri Jul 25 14:54:22 BST 2014
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>
More information about the Forum
mailing list