# Difference between revisions of "GAP:NormalSubgroups"

(→Time analysis) |
(→Time analysis) |
||

(4 intermediate revisions by the same user not shown) | |||

Line 47: | Line 47: | ||

== Method == | == 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 | + | 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 <math>n</math> is the order: | The sequence of commands used was as follows, where <math>n</math> is the order: | ||

Line 91: | Line 93: | ||

|- | |- | ||

| 168 || [[groups of order 168|57]] || 1663 || 29.2 || 34 || 0.6 | | 168 || [[groups of order 168|57]] || 1663 || 29.2 || 34 || 0.6 | ||

+ | |} | ||

+ | |||

+ | Here is the data on symmetric groups of degree <math>n</math>. Note that for <math>n \ge 5</math>, 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. | ||

+ | |||

+ | {| class="sortable" border="1" | ||

+ | ! <math>n</math> !! Symmetric group of degree <math>n</math> !! Order (equals <math>n!</math>) !! 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 | ||

|} | |} |

## Latest revision as of 04:28, 11 September 2016

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 and are both normal subgroups of the group and , then occurs before 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 . 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 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 . Note that for , 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.

Symmetric group of degree | Order (equals ) | 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 |