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
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
