Permutation Group Algorithms in Mathematica

Ádám Lelkes

We have implemented a number of important permutation group algorithms. With these new functions the Mathematica users can explore the structure of permutation groups. Among these functions there are group constructions (QuaternionGroup, DirectProduct), functions which identify key properties of groups (AbelianGroupQ, ElementaryAbelianGroupQ, NilpotentGroupQ, SolvableGroupQ, PerfectGroupQ) and functions which return important subgroups of a permutation group (DerivedSubgroup, CommutatorSubgroup, GroupCenter, GroupSubsetCentralizer) among others.

In this notebook we demonstrate the usage of these functions and briefly explain how they work.

<<groups.m

Basic properties of groups

CyclicGroupQ[G] gives True if the permutation group G is cyclic, False otherwise . The function tests if there is an element among the elements of G which generates the whole group. The alternating group of degree 3 is cyclic, the symmetric group of degree 3 is not.

CyclicGroupQ[AlternatingGroup[3]]

CyclicGroupQ[SymmetricGroup[3]]

AbelianGroupQ[G] gives True if G is abelian, False otherwise. The function tests if the generators of G commute.

AbelianGroupQ[SymmetricGroup[5]]

AbelianGroupQ[AbelianGroup[{2,2,3}]]

ElementaryAbelianGroupQ[G] gives True if G is an elementary abelian p-group, False otherwise. Elementary abelian p-groups are direct products of cyclic groups of order p. The function returns False if the group is not abelian or if the order of the group is not a prime power. If G is an abelian group of prime power order, ElementaryAbelianQ tests whether all generators of G have a prime order.

ElementaryAbelianGroupQ[AbelianGroup[{2,2,3}]]

ElementaryAbelianGroupQ[AbelianGroup[{3,3,3}]]

ElementaryAbelianGroupQ[AbelianGroup[{3,9,3}]]

TransitivePermutationGroupQ[G] gives True if G is a transitive permutation group, False otherwise.  Technically that means that the function returns True if and only if G acts transitively on the support of the generators of G (the generators are represented as permutations).

TransitivePermutationGroupQ[SymmetricGroup[4]]

TransitivePermutationGroupQ[PermutationGroup[{Cycles[{{1,3,6},{2,4}}],Cycles[{{6,7}}]}]]

CAGroupQ[G] gives True if G is a CA-group, ie. every non-central element of G has an abelian centralizer, and False otherwise. CA-groups are an important class of groups. In CA-groups commutativity is a transitive relation among the noncentral elements. Two dimensional projective special groups over a finite field of 2-power order are CA-groups. The following example is a permutation group representation of PSL(2,4).

CAGroupQ[PermutationGroup[{Cycles[{{1,2,3}}],Cycles[{{3,4,5}}]}]]

The symmetric group of degree 4 is not a CA-group.

CAGroupQ[SymmetricGroup[4]]

Group constructions

We can construct the direct product of two groups. The function DirectProduct shifts the support of the second group’s generators, and returns the permutation group generated by the first group’s original and the second group’s modified generators.

GroupGenerators/@{DihedralGroup[5],SymmetricGroup[4]}

DirectProduct[DihedralGroup[5],SymmetricGroup[4]]

GroupOrder[%]

AbelianGroupQ[DirectProduct[CyclicGroup[4],CyclicGroup[5]]]

QuaternionGroup[] returns a permutation group representation of the quaternion group Q.

QuaternionGroup[]

GroupOrder[%]

Centralizers and maximal abelian subgroups

GroupSubsetCentralizer[G, X] returns the centralizer of X in G, where X is a subset of G. The centralizer of a subset is the intersection of the centralizers of the subset’s elements.

GroupSubsetCentralizer[SymmetricGroup[5],{Cycles[{{1,2}}],Cycles[{{4,5}}]}]

GroupOrder[%]

MaximalAbelianSubgroupQ[G, H] gives True if H is a maximal abelian subgroup of G, ie. if H is abelian and is not contained in any other abelian subgroup of G, and False otherwise. H is a maximal abelian subgroup if and only if the H is its own centralizer, this is what this function tests.

MaximalAbelianSubgroupQ[AlternatingGroup[4],PermutationGroup[{Cycles[{{1,2},{3,4}}],Cycles[{{1,3},{2,4}}]}]]

MaximalAbelianSubgroupQ[AlternatingGroup[4],PermutationGroup[{Cycles[{{1,2},{3,4}}]}]]

Derived and commutator subgroups, perfect, nilpotent and solvable groups

Using the following two functions we can calculate the derived subgroup G’=[G,G] of any permutation group G, and the commutator subgroup [G,H] of two permutation groups G and H. DerivedSubgroup calculates the normal closure (see next section) of the subgroup generated by the commutators of the group’s generators.

DerivedSubgroup[SymmetricGroup[4]]//GroupOrder

CommutatorSubgroup[PermutationGroup[{Cycles[{{1,2,3}}],Cycles[{{1,2}}]}],PermutationGroup[{Cycles[{{2,3,4}}],Cycles[{{3,4}}]}]]//GroupOrder

PerfectGroupQ[G] gives True if G is a perfect group (ie. G=G’), False otherwise. G is a perfect group if and only if G has no proper normal subgroup N such that the factor group G/N is abelian, or equivalently: if the only abelian homomorphic image of G is the trivial group. The symmetric group of degree 5 is not perfect, but the alternating group of degree 5 is perfect.

PerfectGroupQ/@{SymmetricGroup[5],AlternatingGroup[5]}

GroupCenter[G] returns the center of the permutation group G.

GroupCenter[SymmetricGroup[4]]

GroupCenter[DirectProduct[AbelianGroup[{2,2}],AlternatingGroup[4]]]//GroupOrder

LowerCentralSeries[G] returns the lower central series of G. The lower central series of G is the following descending series of subgroups: G ≥ [G,G] ≥ [[G,G],G] ...

GroupOrder/@LowerCentralSeries[SymmetricGroup[4]]

Last@LowerCentralSeries[QuaternionGroup[]]//GroupOrder

NilpotentGroupQ[G] gives True if the permutation group G is nilpotent (ie. the lower central series terminates in the trivial subgroup), False otherwise. NilpotencyClass[G] returns the nilpotency class (the length of the lower central series) of a nilpotent group G. A finite group G is nilpotent if and only if G is the direct product of its Sylow-subgroups.

NilpotentGroupQ[DirectProduct[QuaternionGroup[],QuaternionGroup[]]]

NilpotentGroupQ[AlternatingGroup[5]]

NilpotencyClass[DirectProduct[QuaternionGroup[],QuaternionGroup[]]]

DerivedSeries[G] returns the derived series of the permutation group G. The derived series of G is the series G, G’, [G’,G’], ... The derived series should not be confused with the lower central series.

GroupOrder/@DerivedSeries[SymmetricGroup[4]]

GroupOrder/@DerivedSeries[SymmetricGroup[5]]

SolvableGroupQ[G] returns True if G is a solvable permutation group (ie. the derived series of G terminates in the trivial subgroup), False otherwise. DerivedLength[G] returns the derived length of the solvable permutation group G.

SolvableGroupQ/@{DirectProduct[SymmetricGroup[3],AbelianGroup[{2,2}]],SymmetricGroup[5]}

DerivedLength[SymmetricGroup[4]]

Normal subgroups, normal closure

NormalClosure[G,X] returns the normal closure of X in G (the smallest normal subgroup of G containing X, not to be confused with the normalizer), where X is either a subgroup or a subset of elements of G.

NormalClosure[SymmetricGroup[5],AlternatingGroup[4]]//GroupOrder

NormalSubgroupQ[G, N] gives True if N is a normal subgroup of G (ie. N is its own normal closure), False otherwise.

NormalSubgroupQ[SymmetricGroup[8],AlternatingGroup[8]]

NormalSubgroupQ[SymmetricGroup[8],AlternatingGroup[7]]

Derek F. Holt, Handbook of Computational Group Theory. In the series ‘Discrete Mathematics and its Applications’, Chapman & Hall/CRC 2005, xvi + 514 p.

The GAP Group, GAP -- Groups, Algorithms, and Programming, Version 4.4.12; 2008. (http://www.gap-system.org)