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?

Improve this question
$\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$ Commented Apr 2, 2018 at 14:25
  • $\begingroup$ @b3m2a1 Do you think you can demonstrate with an example? $\endgroup$ Commented 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$ Commented Apr 2, 2018 at 23:06

1 Answer 1

Reset to default
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}}]}]}

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.