[GAP Forum] Counting subgroups

[Alexander Konovalov]

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  
a bit
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  
'ConjugacyClassesSubgroups'
(if the knowledge about inclusion is not required) will compute  
representatives
of all subgroups up to conjugacy. If the group gets bigger, however,  
this will
either run out of space or take too long to be feasible.

Now, if by "count subgroups" you mean "determine the number of  
subgroups", you
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 ) );
156

Also, GAP has the library of tables of marks. These tables give a  
compact
description of subgroup lattices of groups. So *for groups in this  
library*,
the numbers of (classes of) subgroups can be read off from the stored  
data.
For example, the same information for S_5 can be retrieved using the  
following
commands:

gap> t := TableOfMarks( "S5" );
TableOfMarks( "S5" )
gap> Sum( LengthsTom( t ) );
156

See the GAP reference manual for further details about tables of marks.

Further, if "count" means "enumerate", you can run a loop and consider  
either
a representative or the full list of subgroups from each class.  
Enumerating
representatives is much faster than enumerating all subgroups in each  
conjugacy
class (for non-abelian groups), so if you are looking for a a subgroup  
with certain
combination of properties, first check for the class representative  
those properties
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  
conjugacy
classes of subgroups. If you are interested only in normal or maximal  
subgroups,
there is no need to compute all classes - use 'NormalSubgroups' or  
'MaximalSubgroups'
instead. Other functions to look are 'SylowSubgroup', 'HallSubgroup',
'MaximalSubgroupClassReps'. Try to use the restricting conditions to  
reduce the
calculation (for example, p-subgroups can be found inside a Sylow  
subgroup).

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  
example, the
description of all subgroups of (Z,+), but this is not a kind of  
questions to
ask a computational algebra system.

However, if your group is pc-presented, you may use the GAP package  
"polycyclic"
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  
Questions:
http://www.gap-system.org/Faq/faq.html, including section 7 and, in  
particular,
question 7.7 "How do I get the subgroups of my group?". I used some  
text from
that page in my answer.

Best wishes,
Alexander