GAP:NormalSubgroups

From Groupprops
Jump to: navigation, search
This article is about a GAP function.



Definition

Function type

NormalSubgroups is a GAP command that takes in one argument representing a group and outputs a list of groups.

Behavior

Applying NormalSubgroups to a given group returns a list of all its normal subgroups. This list is not sorted in any standard way, i.e., it is not sorted based on the orders of subgroups or based on group IDs, and the ordering of the members of this list may be different for isomorphic groups.

Nonetheless, the ordering of the list has the following features:

  • If H and K are both normal subgroups of the group and H \le K, then H occurs before K in the list.
  • In particular, the trivial subgroup occurs first in the list, and the whole group occurs last.
  • For a normal-comparable group, the ordering of the list is unique.

Related functions

  • GAP:IsNormal: This takes as input a group and a subgroup and outputs whether the subgroup is normal in the group.
  • GAP:ConjugacyClassesSubgroups: This takes as input a group and outputs a list of conjugacy classes of subgroups.

Examples of usage

Some examples involving prespecified groups

gap> NormalSubgroups(SymmetricGroup(3));
[ Group(()), Group([ (1,2,3) ]), Sym( [ 1 .. 3 ] ) ]
gap> L := NormalSubgroups(SymmetricGroup(4));
[ Group(()), Group([ (1,4)(2,3), (1,3)(2,4) ]), Group([ (2,4,3), (1,4)(2,3), (1,3)(2,4) ]), Sym( [ 1 .. 4 ] ) ]
gap> K := List(L,IdGroup);
[ [ 1, 1 ], [ 4, 2 ], [ 12, 3 ], [ 24, 12 ] ]
gap> Length(L);
4
gap> NormalSubgroups(SmallGroup(8,4));
[ Group([  ]), Group([ f3 ]), Group([ f1*f2, f3 ]), Group([ f1, f3 ]), Group([ f2, f3 ]), <pc group of size 8 with 3 generators> ]

The first example lists all the normal subgroups of the symmetric group on three letters. The set here is \{ 1,2, 3 \}. Each of these normal subgroups (except the whole group) is described by its generating set.

The second example computes the normal subgroups of the symmetric group on four letters and outputs the list of its normal subgroups. This list is stored with the variable name L. In the next command, the members of this list are mapped to their group IDs, using the IdGroup command. The GAP:List command is used to achieve the mapping on each member of the list. The next command computes the length of this list.

The final example computes the normal subgroups of a certain group specified by the group ID (this is in fact the quaternion group).

Method

Time analysis

The following is the total time and average time over all groups of specific orders. Times were measured on a 6-core virtual machine and are in milliseconds. While the actual times may be different on a machine with different processor specifications, the relative time should hold up.

The time on second run is generally very low since it relies on pre-computed data.

The sequence of commands used was as follows, where n is the order:

A := AllSmallGroups(n);
List(A, NormalSubgroups);
time;
Order Number of groups of that order Total time on first run (milliseconds) Average time on first run (milliseconds) Total time on second run (milliseconds) Average time on second run (milliseconds)
1 1 4 4 0 0
2 1 23 23 0 0
3 1 20 20 3 3
4 2 50 25 3 1.5
5 1 4 4 0 0
6 2 37 18.5 3 1.5
8 5 50 10 0 0
12 5 57 11.4 0 0
16 14 317 22.6 17 1.2
24 15 230 15.3 6 0.4
32 51 1837 36.0 63 1.2
48 52 1597 30.7 60 1.2
64 267 19820 74.2 677 2.5
96 231 13010 56.3 410 1.8
128 2328 396414 170.3 11817 5.1
168 57 1663 29.2 34 0.6

Here is the data on symmetric groups of degree n. Note that for n \ge 5, the only three normal subgroups are the trivial group, alternating group, and whole symmetric group. Starting with a degree of around 15, the computation time approximately doubles for every increase in degree of about five.

n Symmetric group of degree n Order (equals n!) Time for first computation (in milliseconds)
1 trivial group 1 3
2 cyclic group:Z2 2 16
3 symmetric group:S3 6 30
4 symmetric group:S4 24 40
5 symmetric group:S5 120 60
6 symmetric group:S6 720 23
7 symmetric group:S7 5040 17
8 symmetric group:S8 40320 24
9 symmetric group:S9 362880 23
10 symmetric group:S10 3628800 44
15 63
20 123
25 367
30 597
35 1140
40 2286
45 3786
50 6340