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 $\{ 1,2,3, \dots, n \}$, 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 $\{ 1 \}$ is tested for normality in the symmetric group on $\{ 1,2 \}$, while in the second example, the symmetric group on $\{ 1,2 \}$ is tested for normality in the symmetric group on $\{ 1,2,3 \}$.

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 $A$ is the stored generating set for $G$ and $B$ is the stored generating set for $H$. Then, to test whether $G$ normalizes $H$, GAP tests whether the conjugate of any element of $B$ by any element of $A$ lies inside $H$.
• Infinite case: Suppose $A$ is the stored generating set for $G$ and $B$ is the stored generating set for $H$. Then, to test whether $G$ normalizes $H$, GAP tests whether the conjugate of any element of $B$ by any element of $A$ lies inside $H$, as well as whether the conjugate of every element of $B$ by every element of $A$ lies inside $H$.

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.