# Function that Generates all Normal Subgroups of a Group

I am trying to create a function which, given a group structure, generates a list of all the normal subgroups contained within it. But I am not sure how to proceed.

For now, I have the following:

A = { 0, 1, 2, 3, 4 }; (* Set of Elements *)
CirclePlus[a_, b_] := Mod[a + b, 5] (* Group Operation *)

GroupQ[set_, op_] (* determins whether a set with an operation has the structure of a group *)


Example:

GroupQ[A, CirclePlus]


But how do I create a function which would generate all the normal subgroups of that group?

• There's a straightforward, from-the-definitions way to implement this, but it'll be inefficient. Map your operation and use Sort to check whether your group is closed and while doing that make sure there's an element that doesn't require Sort for equality. Then check whether the group itself is normal using the left and right cosets. Then recursively check if for normality as you drop elements other than the identity (as you know that has to be in there) using a depth-first recurrence and some caching to avoid rechecking things. It'll be slow though (like worse than $O((n \log n)^2)$). Apr 2, 2018 at 14:25
• @b3m2a1 Do you think you can demonstrate with an example? Apr 2, 2018 at 15:20
• If you're going to do a lot of group theory computation, you might want to use a more specialized piece of software such as GAP or Magma Apr 2, 2018 at 23:06

When the number of orbits is small, this solution is work:

G = SymmetricGroup[5];
orbits = GroupOrbits[G, GroupElements[G]];
{f, l} = TakeDrop[orbits, 1];
DeleteDuplicatesBy[
PermutationGroup /@
Select[Flatten[{f, #}] & /@ Subsets[l],
GroupOrder[PermutationGroup[#]] == Length[#] &], GroupElements]


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

The result is a little dirty, but it's right. As the delCyc from here, the simplified result is:

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