1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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)$). $\endgroup$
    – b3m2a1
    Apr 2, 2018 at 14:25
  • $\begingroup$ @b3m2a1 Do you think you can demonstrate with an example? $\endgroup$ Apr 2, 2018 at 15:20
  • 1
    $\begingroup$ 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 $\endgroup$
    – Michael E2
    Apr 2, 2018 at 23:06

1 Answer 1

1
$\begingroup$

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}}]}]}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.