GroupHomomorphism

Construct homomorphisms between groups

DefinitionResourceCreateNotebook

Under a homomorphism ϕ, if generator e has order n whereas ϕ(e) has order m, then we must have that m|n.

validGeneratorsQ[g1_,images_List]:=
Module[
{gens=GroupGenerators[g1]},
And@@MapThread[Divisible[PermutationOrder[#1],
PermutationOrder[#2]]&,{gens,images}]]

This is not a two-way result, therefore some generator assignments might still be accepted that do not specify valid homomorphisms. See possible issues below.

ClearAll[GroupHomomorphism]
GroupHomomorphism::subset="Images `1` do not all belong to the codomain.";
GroupHomomorphism::ngen="Expected `1` generator images but got `2`.";
GroupHomomorphism::vgen="Images `1` do not specify a valid group homomorphism.";

GroupHomomorphism[g1_,_,f_List]/;Length[f]!=Length@GroupGenerators[g1]:=
(Message[GroupHomomorphism::ngen,Length@GroupGenerators[g1],Length[f]];$Failed)
GroupHomomorphism[_,g2_,f_List]/;Not@AllTrue[f,GroupElementQ[g2,#]&]:=
(Message[GroupHomomorphism::subset,f];$Failed)
GroupHomomorphism[g1_,_,f_List]/;Not@validGeneratorsQ[g1,f]:=
(Message[GroupHomomorphism::vgen,f];$Failed)

GroupHomomorphism/:GroupHomomorphism[g1_,_,_]["Domain"]:=g1
GroupHomomorphism/:GroupHomomorphism[_,g2_,_]["CoDomain"]:=g2
GroupHomomorphism/:GroupHomomorphism[_,_,f_List]["Image"]:=PermutationGroup[f]

For calculating the kernel, we simulate (Subscript[G, 1])×(Subscript[G, 2]) and consider its graph Γ which is isomorphic to (Subscript[G, 1]). The kernel of ϕ:(Subscript[G, 1])->(Subscript[G, 2]) is precisely the elements of Γ whose (Subscript[G, 2])-component is identity. We isolate these elements by computing the pointwise stabilizer of Γ over the domain of (Subscript[G, 2]):

GroupHomomorphism/:h_GroupHomomorphism["Kernel"]:=
Module[
{images,gens,m1,m2,graphGroup},
gens=GroupGenerators[h["Domain"]];
images=h/@gens;
(* maximum integer in the supports *)
m1=Max[Cases[gens,_Integer,Infinity],0];
m2=Max[Cases[images,_Integer,Infinity],0];
(* shift images so they operate on a completely separate set of points: *)
images=images/. c_Integer:>c+m1;
graphGroup=PermutationGroup[
MapThread[PermutationProduct,{gens,images}] (* gen of Γ *)
];
PermutationGroup[GroupGenerators[
GroupStabilizer[graphGroup,Range[m1+1,m1+m2]]]]]

Normal form:

GroupHomomorphism/:Normal[h:GroupHomomorphism[g1_,_,_]]:=
AssociationThread[GroupElements[g1],h/@GroupElements[g1]]

Finally:

GroupHomomorphism/:GroupHomomorphism[g1_,_,f_List][x:(_Cycles|_List)]:=
Module[
{to},
to=GroupElementToWord[g1,x];
If[to==={},
Cycles[{}],
Apply[PermutationProduct,
PermutationPower[Part[f,Abs[#]],Sign[#]]&/@to]]]

GroupHomomorphism/:GroupHomomorphism[g1_,g2_,f_Association]:=
GroupHomomorphism[g1,g2,f/@GroupGenerators[g1]]

GroupHomomorphism[g_,f_]:=GroupHomomorphism[g,g,f]

GroupHomomorphism/:MakeBoxes[h:GroupHomomorphism[g1_,g2_,f_],form_]:=BoxForm`ArrangeSummaryBox[GroupHomomorphism,h,None,{BoxForm`SummaryItem[{"Domain: ",g1}],BoxForm`SummaryItem[{"Codomain: ",g2}]},
{BoxForm`SummaryItem[{"Injective: ",GroupOrder[g1]==GroupOrder[h["Image"]]}],
BoxForm`SummaryItem[{"Surjective: ",GroupOrder[g2]==GroupOrder[h["Image"]]}]},form]

Documentation

UsageResourceCreateNotebook

Details & OptionsResourceCreateNotebook

(Subscript[G, 1]) and (Subscript[G, 2]) must be valid group objects such as CyclicGroup, DihedralGroup, SymmetricGroup, MathieuGroupM11, etc.

f must be a list or an association specifying the image of each generator under the required homomorphism.

ExamplesResourceCreateNotebook

Basic Examples

Embed CyclicGroup[2] in CyclicGroup[4] via (12)↦(13)(24):

ϕ=GroupHomomorphism[CyclicGroup[2],CyclicGroup[4],{Cycles[{{1,3},{2,4}}]}]

Click on + to reveal more information about the homomorphism. For example, ϕ is injective but not surjective. Obtain the underlying mapping:

Normal[ϕ]

Retrieve the domain or co-domain of a homomorphism:

ϕ["Domain"]

ϕ["CoDomain"]

Find the kernel of this homomorphism, indeed the kernel is singleton thus ϕ is an embedding:

ϕ["Kernel"]

This is the trivial group:

GroupElements[%]

Find the image group:

ϕ["Image"]

Try to specify an invalid homomorphism:

GroupHomomorphism[CyclicGroup[2],CyclicGroup[3],<|Cycles[{{1,2}}]->Cycles[{{1,2,3}}]|>]

The package efficiently works with large groups. For example, here is the identity homomorphism from SymmetricGroup[10] to itself:

id=AbsoluteTiming@GroupHomomorphism[SymmetricGroup[20],SymmetricGroup[20],GroupGenerators[SymmetricGroup[20]]]

Its image and kernel groups:

AbsoluteTiming@id[[2]]["Image"]

AbsoluteTiming@id[[2]]["Kernel"]

Scope

Specify the homomorphism using an association:

gens=GroupGenerators[SymmetricGroup[4]]

assoc=AssociationThread[gens->gens]

Build the homomorphism:

GroupHomomorphism[SymmetricGroup[4],SymmetricGroup[4],assoc]

This is the identity homomorphism (an isomorphism, since it is both injective and surjective):

Select[Normal[%],%[[1]]!=%[[2]]]

Specify an endomorphism (from G to itself):

GroupHomomorphism[CyclicGroup[2],{Cycles[{{1,2}}]}]

Options

Applications

Construct the sign homomorphism from SymmetricGroup[4] to CyclicGroup[2]:

S4=SymmetricGroup[4];
C2=CyclicGroup[2];

Odd generators must map to (12):

GroupGenerators[S4]

sgn=GroupHomomorphism[S4,C2,{Cycles[{{1,2}}],Cycles[{{1,2}}]}]

Find all even permutations:

sgn["Kernel"]//GroupElements

Confirm that there are exactly 12 even permutations:

Length[%]

Quotient DihedralGroup[3] by CyclicGroup[2] sending all rotations to ϵ and reflections to (12):

GroupGenerators[DihedralGroup[3]]

quo=GroupHomomorphism[DihedralGroup[3],CyclicGroup[2],<|Cycles[{{2,3}}]->Cycles[{{1,2}}],Cycles[{{1,2,3}}]->Cycles[{{}}]|>]

Again, kernel is all 3 rotations:

quo["Kernel"]//GroupOrder

For an AbelianGroup to itself, the map x↦(x^k) is a homomorphism:

GroupGenerators[Ab=AbelianGroup[{2,2,3}]]

pow=GroupHomomorphism[Ab,
AssociationMap[PermutationPower[#,3]&,GroupGenerators[Ab]]]

Its kernel:

pow["Kernel"]

Properties and Relations

GroupHomomorphism preserves operation:

{c1,c2}=RandomChoice[GroupElements[S4],2]

sgn[c1\[PermutationProduct]c2]==sgn[c1]\[PermutationProduct]sgn[c2]

GroupHomomorphism preserves inverses:

sgn@PermutationPower[c1,-1]==PermutationPower[sgn[c1],-1]

The specified images of generators must belong to (Subscript[G, 2]):

GroupHomomorphism[CyclicGroup[2],{Cycles[{{1,2,3}}]}]

Applying the homomorphism to an arbitrary object returns unevaluated:

sgn[x]

Replace x by an element:

%/.x->Cycles[{{}}]

Possible Issues

Consider the homomorphism from SymmetricGroup[3] to CyclicGroup[6]:

bad=GroupHomomorphism[SymmetricGroup[3],CyclicGroup[6],
{PermutationPower[Cycles[{{1,2,3,4,5,6}}],3],PermutationPower[Cycles[{{1,2,3,4,5,6}}],2]}]

We mapped an order 2 generator to order 2 element, and 3 to 3. This violates the group relations of SymmetricGroup[3]. Consider for example:

bad[PermutationProduct[Cycles[{{1,2}}],Cycles[{{1,2,3}}]]]

But:

PermutationProduct[bad[Cycles[{{1,2}}]],bad[Cycles[{{1,2,3}}]]]

Neat Examples

Source & Additional Information

Contributed ByResourceCreateNotebook

Naman T.

KeywordsResourceCreateNotebook

group theory

group homomorphism

morphism

kernel

subgroups

CategoriesResourceCreateNotebook

Related SymbolsResourceCreateNotebook

Related Resource ObjectsResourceCreateNotebook

FindGroupIsomorphism

SubgroupQ

SubsetGroup

Source/Reference CitationResourceCreateNotebook

Source, reference or citation information

LinksResourceCreateNotebook

TestsResourceCreateNotebook

VerificationTest[
GroupHomomorphism[CyclicGroup[2],CyclicGroup[4],{Cycles[{{1,3},{2,4}}]}][Cycles[{{1,2}}]],
Cycles[{{1,3},{2,4}}]
]

VerificationTest[
GroupHomomorphism[CyclicGroup[2],CyclicGroup[2],
\[LeftAssociation]Cycles[{{1,2}}]->Cycles[{{1,2}}]\[RightAssociation]
],
GroupHomomorphism[CyclicGroup[2],CyclicGroup[2],
{Cycles[{{1,2}}]}
]
]

VerificationTest[
GroupHomomorphism[CyclicGroup[2],{Cycles[{{1,2}}]}],
GroupHomomorphism[CyclicGroup[2],CyclicGroup[2],{Cycles[{{1,2}}]}]
]

CompatibilityResourceCreateNotebook

Wolfram Language VersionResourceCreateNotebook

14.3+

Operating SystemResourceCreateNotebook

EnvironmentsResourceCreateNotebook

Cloud SupportResourceCreateNotebook

Required FeaturesResourceCreateNotebook

Author NotesResourceCreateNotebook

Additional information about limitations, issues, etc.

Submission NotesResourceCreateNotebook

Additional information for the reviewer.