6
$\begingroup$

Given a normal subgroup H of a (large, finite permutation) group G, knowing a set of generators for each of H and G, how to find a subgroup K of G that is isomorphic to G/H? (Using Mathematica.)

$\endgroup$
9
  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$
    – Michael E2
    Aug 31, 2015 at 12:29
  • $\begingroup$ For what sort of groups and how are they presented (in Mathematica)? BTW, it's not true in general. E.g. the additive reals modulo integers is isomorphic to the circle group, but the circle group is not isomorphic to a subgroup of the real numbers. $\endgroup$
    – Michael E2
    Aug 31, 2015 at 12:35
  • $\begingroup$ The problem is when the order of the group is very large, so listing the elements of the group is not possible. Patrick's answer requires listing all the elements of the group. Also, GroupElements requires two arguments. $\endgroup$
    – r jones
    Aug 31, 2015 at 14:15
  • $\begingroup$ To quote the docs: "GroupElements[group] returns the list of all elements of group." I agree that it's a horrible way to do it. $\endgroup$ Aug 31, 2015 at 14:28
  • $\begingroup$ Thanks, Patrick. I was just quoting the error message I got from Mathematica. $\endgroup$
    – r jones
    Aug 31, 2015 at 14:45

3 Answers 3

6
$\begingroup$

The following is a hacky way of doing it for finite groups only:

quotientGroup[g_, h_] := 
 RightCosetRepresentative[h, #] & /@ GroupElements[g] // 
 DeleteDuplicates
$\endgroup$
10
  • $\begingroup$ It's been along time since my group theory days. This generates the factor group; is it necessarily isomorphic to a subgroup of the original group? $\endgroup$
    – march
    Aug 31, 2015 at 15:16
  • $\begingroup$ @march If it's not, then the OP is asking for something which doesn't exist. It is indeed not always possible: consider the quaternion group $Q_8$ with generators $\langle i, j, k \rangle$ quotiented by the normal subgroup $\{1, -1\}$. This is isomorphic to $V_4$, which is not a subgroup of the quaternion group because any single non-$\pm 1$ element generates a cyclic 4-group. $\endgroup$ Aug 31, 2015 at 15:21
  • $\begingroup$ Good, thanks. That's vaguely what I remembered. I suppose one could directly check whether or not the output of your code is a subset (and therefore necessarily a subgroup) of the original group (by using SubsetQ), which would completely answer OP's question. $\endgroup$
    – march
    Aug 31, 2015 at 15:25
  • $\begingroup$ In the Q8 example, my code results in a group of order 384 as the "factor group". I'm decidedly confused. $\endgroup$ Aug 31, 2015 at 15:28
  • 2
    $\begingroup$ Upshot: Mathematica makes it hard to do group theory. $\endgroup$ Aug 31, 2015 at 15:52
5
$\begingroup$

Extending Patrick Stevens answer and modifying it somewhat. As an example, I'll use the Quaternions {1, -1, i, -i, j, -j, k, -k} (per our discussion in the comments to his answer) and factor by the normal subgroup {-1, 1}.

Warning: if the groups are too big, the following calculations will probably take too much time.

To extract a permutation-group representation of the group, we do

q = PermutationCycles /@ FiniteGroupData["Quaternion", "PermutationRepresentation"] // Sort
(* {Cycles[{}], Cycles[{{1, 2, 5, 6}, {3, 4, 7, 8}}]
     , Cycles[{{1, 3, 5, 7}, {2, 8, 6, 4}}]
     , Cycles[{{1, 4, 5, 8}, {2, 3, 6, 7}}]
     , Cycles[{{1, 6, 5, 2}, {3, 8, 7, 4}}]
     , Cycles[{{1, 7, 5, 3}, {2, 4, 6, 8}}]
     , Cycles[{{1, 8, 5, 4}, {2, 7, 6, 3}}]
     , Cycles[{{1, 5}, {2, 6}, {3, 7}, {4, 8}}]} *)

We can verify that this set is closed under group multiplication by doing

q === Sort@Union@Flatten@Outer[PermutationProduct, q, q]
(* True *)

The subgroup {-1, 1} can be picked out using

h = {First@q, Last@q}
(* {Cycles[{}], Cycles[{{1, 5}, {2, 6}, {3, 7}, {4, 8}}]} *)

We construct the right-cosets of h using

cosets = Sort /@ Outer[PermutationProduct, q, h] // DeleteDuplicates;
cosets // TableForm
(* Cycles[{}]                       Cycles[{{1,5},{2,6},{3,7},{4,8}}]
   Cycles[{{1,2,5,6},{3,4,7,8}}]    Cycles[{{1,6,5,2},{3,8,7,4}}]
   Cycles[{{1,3,5,7},{2,8,6,4}}]    Cycles[{{1,7,5,3},{2,4,6,8}}]
   Cycles[{{1,4,5,8},{2,3,6,7}}]    Cycles[{{1,8,5,4},{2,7,6,3}}] *)

and we will use

cosetReps = cosets[[All, 1]]

(the first column above) as our set of right-coset representatives.

Finally, we construct a (clunky) multiplication for cosets via

factorGroupMultiply[elements__List, cosetReps_] /; SubsetQ[cosetsReps, elements] := 
 First@@Select[cosets, MemberQ[#, PermutationProduct @@ elements] &]

(Pre-MMA-v.10, you can use a (again clunky) homebrew subsetQ,

subsetQ[list1_, list2_] := Sort@Intersection[list1, list2] === Sort@Union@list2

which is not well, tested, but should work.) This multiplication function will accept members of cosetReps, multiply them using PermutationProduct, find in which coset the result lives, then return the corresponding coset representative.

To visualize the resulting group, let's form the Cayley table:

factorGroupCayley = Outer[factorGroupMultiply[{##}, cosetReps] &, cosetReps, cosetReps];
factorGroupCayley /. Thread[cosetReps -> {1, 2, 3, 4}] // TableForm
(* 1   2   3   4
   2   1   4   3
   3   4   1   2
   4   3   2   1 *)

Finally, we can decide whether or not this group is isomorphic to a subgroup of the original group by extracting the subgroup data for the group:

subgroups = FiniteGroupData["Quaternion", "Subgroups"]
(* {"Trivial", {"CyclicGroup", 2}, {"CyclicGroup", 4}, "Quaternion"} *) 

The only subgroup of order 4 is cyclic, and the Cayley table above is clearly not the Cayley table of a cyclic group. In general, we might go through the process of finding the Cayley tables for each of the subgroups using

subGroupCayleyTables = FiniteGroupData[#, "MultiplicationTable"] & /@ subgroups;
$\endgroup$
0
$\begingroup$

Thanks Patrick and march for your ideas about looking at the quaternion group.

FiniteGroupData["Quaternion", "Subgroups"]
{"Trivial", {"CyclicGroup", 2}, {"CyclicGroup", 4}, "Quaternion"}.

The quotient group march mentions is clearly not cyclic but does have order 4, and there are only 2 of those, and the other is not a subgroup of the quaternion group.

FiniteGroupData[4]
{{"CyclicGroup", 4}, {"AbelianGroup", {2, 2}}}.

This quotient group goes by several names.

FiniteGroupData[{"AbelianGroup", {2, 2}}, "IsomorphicGroups"]
{"Vierergruppe", {4, 2}, {"CrystallographicPointGroup", 5}, {"CrystallographicPointGroup", 6}, {"CrystallographicPointGroup", 7}, {"CyclicGroupUnits", 8}, {"CyclicGroupUnits", 12}, {"DihedralGroup", 2}}.

So the answer to my question is that, generally speaking, there isn't necessarily a subgroup isomorphic to a quotient group. I have learned a lot talking with you.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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