[GAP Forum] Counting subgroups
alexander.konovalov at gmail.com
Wed Oct 1 14:55:02 BST 2008
Dear Dr. Erfanian, dear GAP Forum,
On 18 Jul 2008, at 17:48, erfanian wrote:
> Dear Gap Forum,
> I would like to know if there is a way to count all subgroups for
> given group G (finite and infinite) in Gap. Thanks in advance for
> any help
> and comments.
> Best regards,
> A. Erfanian.
First, the finite case. This is a hard problem in general. For example,
the number of subgroups of the symmetric group of degree n is known only
for very small values of n. In particular, the On-Line Encyclopedia of
Integer Sequences contains the number of subgroups of S_n up to n=12
(see the sequence http://www.research.att.com/~njas/sequences/A005432).
For groups of moderate size (the actual meaning of "moderate" depends
on the group structure; should work well for groups of orders at least
of up to
10^4..10^5) the commands 'LatticeSubgroups' (if you are also
interested in the
relations of inclusion on the set of subgroups) or
(if the knowledge about inclusion is not required) will compute
of all subgroups up to conjugacy. If the group gets bigger, however,
either run out of space or take too long to be feasible.
Now, if by "count subgroups" you mean "determine the number of
may compute the sum of orders of each conjugacy class. For example:
gap> G := SymmetricGroup( 5 );
Sym( [ 1 .. 5 ] )
gap> Sum( List( ConjugacyClassesSubgroups( G ), Size ) );
Also, GAP has the library of tables of marks. These tables give a
description of subgroup lattices of groups. So *for groups in this
the numbers of (classes of) subgroups can be read off from the stored
For example, the same information for S_5 can be retrieved using the
gap> t := TableOfMarks( "S5" );
TableOfMarks( "S5" )
gap> Sum( LengthsTom( t ) );
See the GAP reference manual for further details about tables of marks.
Further, if "count" means "enumerate", you can run a loop and consider
a representative or the full list of subgroups from each class.
representatives is much faster than enumerating all subgroups in each
class (for non-abelian groups), so if you are looking for a a subgroup
combination of properties, first check for the class representative
which are conjugacy classes invariants, and then, if necessary,
continue the search
over the whole list of subgroups from the class.
It is also advised to think whether do you really need to compute all
classes of subgroups. If you are interested only in normal or maximal
there is no need to compute all classes - use 'NormalSubgroups' or
instead. Other functions to look are 'SylowSubgroup', 'HallSubgroup',
'MaximalSubgroupClassReps'. Try to use the restricting conditions to
calculation (for example, p-subgroups can be found inside a Sylow
Now the infinite case. Of course, you can not really count all
subgroups of an
infinite group. It might be an easy theoretical fact, like for
description of all subgroups of (Z,+), but this is not a kind of
ask a computational algebra system.
However, if your group is pc-presented, you may use the GAP package
to compute certain families of its subgroups, using its functions
- MaximalSubgroupClassesByIndex( U, p )
- LowIndexSubgroupClasses( U, n )
- LowIndexNormals( U, n )
See the manual of the "polycyclic" package for details.
Finally, let me refer to such resource as the GAP Frequently Asked
http://www.gap-system.org/Faq/faq.html, including section 7 and, in
question 7.7 "How do I get the subgroups of my group?". I used some
that page in my answer.
More information about the Forum