GAP:IsNormal
This article is about a GAP function.
This GAP function takes as input two groups, both having a common parent group. See other GAP functions like this.
This GAP function outputs a Boolean variable, i.e., it returns either true or false. View other GAP functions with Boolean output
Definition
Function type
IsNormal is a GAP function that takes in two arguments, both of which represent groups, and outputs a Boolean answer (true/false).
Behavior
The ideal behavior is as follows:
Nature of input | Output | Example inputs | Additional comments |
---|---|---|---|
Both groups are subgroups of a common big group, and the first group normalizes the second, i.e., the first subgroup is contained in the normalizer of the second subgroup. | true | IsNormal(SymmetricGroup(2),SymmetricGroup(3)) IsNormal(AlternatingGroup(3),SymmetricGroup(3)) |
An answer of true could be returned even if the second group is not contained in the first. Containment can be verified separately using IsSubgroup. |
Both groups are subgroups of a common big group, and the first group does not normalize the second, i.e., the first subgroup is not contained in the normalizer of the second subgroup. | false | IsNormal(SymmetricGroup(3),SymmetricGroup(2)) | |
One of the arguments provided is not a group, or the two groups provided are not subgroups of a common big group | NoMethodFound error | IsNormal(CyclicGroup(4),CyclicGroup(2)) |
Typical use
The function is typically used in the form:
IsNormal(group,subgroup);
The first argument is a group and the second argument is a subgroup of that group. In this case:
- The function returns true if the subgroup is a normal subgroup of the whole group.
- The function returns false if the subgroup is not a normal subgroup of the whole group.
Note that if the order of the group and the subgroup are interchanged, GAP will not detect an error and will return true, because any subgroup of a group normalizes the whole group.
Related functions
- GAP:NormalSubgroups: This takes as input a group and outputs the list of all normal subgroups of the group.
- GAP:IsCharacteristicSubgroup: These functions (that are equivalent in terms of external behavior but use somewhat different internal algorithms) checks whether a given subgroup is a characteristic subgroup of the whole group.
- GAP:CharacteristicSubgroups: This takes as input a group and outputs the list of all characteristic subgroups of the group.
Examples of usage
Some examples involving prespecified groups
gap> IsNormal(SymmetricGroup(2),SymmetricGroup(1)); true gap> IsNormal(SymmetricGroup(3),SymmetricGroup(2)); false gap> IsNormal(SymmetricGroup(2),SymmetricGroup(3)); true gap> IsNormal(SymmetricGroup(3),AlternatingGroup(3)); true gap> IsNormal(SymmetricGroup(3),AlternatingGroup(4)); true gap> IsNormal(CyclicGroup(4),CyclicGroup(2)); Error, no method found! For debugging hints type ?Recovery from NoMethodFound Error, no 1st choice method found for `IsNormalOp' on 2 arguments called from oper( super, sub ) called from <function>( <arguments> ) called from read-eval-loop Entering break read-eval-print loop ... you can 'quit;' to quit to outer loop, or you can 'return;' to continue brk>
GAP defines the symmetric group SymmetricGroup(n) as the symmetric group on the set , and all these groups are viewed as subgroups inside the symmetric group on the natural numbers. Thus, for the first example, the symmetric group on is tested for normality in the symmetric group on , while in the second example, the symmetric group on is tested for normality in the symmetric group on .
In the third example, the subgroup is specified on the left, and since we know that any subgroup of a group normalizes the whole group, an answer of true is returned. In the fifth example, neither the symmetric group on three elements nor the alternating group on four elements is contained in the other, but the symmetric group on three elements normalizes the alternating group on four elements, resulting in an output of true.
In the sixth example, GAP does not recognize the two groups provided as living inside a common big group, and hence throws an error message.
Some examples involving groups defined on the fly
Here are some examples:
gap> G := SmallGroup(56,4); <pc group of size 56 with 4 generators> gap> C := Center(G); Group([ f2, f3]) gap> IsNormal(G,C); true
Here is a similar example involving infinite groups:
gap> F := FreeGroup(3); <free group on the generators [ f1, f2, f3 ]> gap> H := DerivedSubgroup(F); Group(<free, no generators known>) gap> IsNormal(F,H); true
Method
General method
Since GAP stores groups in the forms of generating sets and relations, the checking is done as follows:
- Finite case: Suppose is the stored generating set for and is the stored generating set for . Then, to test whether normalizes , GAP tests whether the conjugate of any element of by any element of lies inside .
- Infinite case: Suppose is the stored generating set for and is the stored generating set for . Then, to test whether normalizes , GAP tests whether the conjugate of any element of by any element of lies inside , as well as whether the conjugate of every element of by every element of lies inside .
More about possible algorithms to check for normality is available at normality testing problem.
Time analysis
The time taken by the previous command can be determined by typing time; (see more at GAP:time). Note that the time taken is not a repeatable value, and the same command may take different amounts of time when given in different contexts. In general, the following are true for this command:
- The time taken is less if the groups are pre-computed -- in other words, if the assignments to the groups have been done before, or if computations related to the groups have been performed before.
- From the algorithm, it is clear that the time taken depends on the sizes of generating sets in use for the group and for the subgroup. In particular, testing whether the trivial subgroup is normal takes zero time, so long as the group and subgroup are pre-computed. Here are some examples:
gap> G := SymmetricGroup(100000); Sym( [ 1 .. 100000 ] ) gap> H := SymmetricGroup(1); Sym( [ ] ) gap> IsNormal(G,H); true gap> time; 0
On the other hand, directly giving the command takes more time, because GAP first needs to interpret the group and the subgroup:
gap> IsNormal(SymmetricGroup(100000),SymmetricGroup(1)); true gap> time; 26
- Other things being equal, the larger the size of the generating set for the group and for the subgroup, the more the time taken. Thus, in general, the algorithm takes more time for bigger subgroups. Also, for a given group, the algorithm takes more time for bigger subgroups. However, big groups can have very small generating sets (such as the symmetric groups, which can be generated by two elements), so this is not always a reliable indicator.