Homomorphisms of FP-Groups

In this section the following topics are covered:

(i)

The specialisation of the general hom-constructor to the case in which the domain is an fp-group

(ii)

Searching for homomorphisms from an fp-group to a given permutation group.

(iii)

Searching for an isomorphism between two fp-groups.

While this section presents general machinery for fp-group homomorphisms the following section covers more specialised tools, specifically those that search for specific types of epimorphisms.

Homomorphism Constructor

The specialisation of the general hom–constructor to the case in which the domain is an fp-group is described in this section.

Constructor/Intrinsic:

hom\(\langle\ P \rightarrow G\ |\ S \ \rangle\) : Returns the homomorphism from the \(n\)-generator fp-group \(P\) to the group \(G\) defined by the assignment \(S\). Here \(S\) is either a list, sequence or indexed set containing the images of the \(n\) generators of \(P\) or a list, sequence, enumerated set or indexed set, containing \(n\) tuples \(\langle x_i,\ y_i\rangle\) or \(n\) arrow pairs \(x_i \rightarrow y_i\) defining the \(n\) generator-image pairs.

IsSatisfied\((U, E)\) : Let \(U\) be a set or sequence of words or relations constituting the defining presentation of an \(n\)-generator fp-group \(H\) and \(E\) be a sequence of \(n\) elements in a group \(G\) for which there is a unique representation for each element. This intrinsic evaluates the words/relations of \(U\) in \(G\) where the \(i\)-th generator of \(H\) maps to the \(i\)-th element of \(G\) and returns true if and only if each word in \(U\) evaluates to the identity or each relation in \(U\) is satisfied.

Notes:

(i)

The hom constructor does not check that the given mapping is a homomorphism and so the IsSatisfied intrinsic is provided to allow the user to verify the correctness of the definition of those homomorphisms that are from an fp-group to a group whose elements have unique representations.

(ii)

The kernel of a homomorphism having a domain of type GrpFP can be calculated using the intrinsic Kernel in many cases. This is the case if the codomain is one of the group types GrpPerm, GrpMat, GrpAb, GrpPC, GrpGPC, as well as the image being finite and its order small. The kernel may also be computable when the codomain is of the type GrpFP if the image is finite, sufficiently small and has a known presentation.

(iii)

The standard tools for working with homomorphisms are available for fp-groups: image of an element or subgroup x@phi (or phi(x), preimage of an element or subgroup x@@phi, domain (Domain), codomain (Codomain), image (Image), and kernel (Kernel). However, in some cases it will not be possible to compute the kernel of a homomorphism and if the kernel is not available then the computation of preimages of subgroups will not be possible.

Example: Homomorphism (ex-1337d3)

For arbitrary \(n>0\), the symmetric group of degree \(n+1\) is an epimorphic image of the braid group on \(n\) generators. In this example, this relationship for the case \(n=4\) will be exhibited.

The first step is to create the braid group \(B\) on 5 strings, that is, 4 Artin generators.

> B<x,y,z,t> := BraidFPGroup(5);
> B;
Finitely presented group B on 4 generators
Relations
    x * y * x = y * x * y
    x * z = z * x
    x * t = t * x
    y * z * y = z * y * z
    y * t = t * y
    z * t * z = t * z * t

Run in calculatorCopy input

In the symmetric group of degree 5, 4 transpositions are defined which will be the images of the generators of \(B\).

> S := Sym(5);
> imgs := [ S!(1,2), S!(2,3), S!(3,4), S!(4,5) ];

Run in calculatorCopy input

In order to verify that this assignment actually gives rise to a well-defined homomorphism, a check is made to decide whether the potential images satisfy the defining relations of \(B\).

> rels := Relations(B);
> rels;
[ x*y*x = y*x*y, x*z = z*x, x*t = t*x, y*z*y = z*y*z,
  y*t = t*y, z*t*z = t*z*t ]
> IsSatisfied(rels, imgs);
true

Run in calculatorCopy input

They do. So now the homomorphism from \(B\) to \(S\) can be defined:-

> f := hom< B->S | imgs >;

Run in calculatorCopy input

Note that \(f\) is surjective, i.e., \(S\) is an epimorphic image of \(B\) as claimed above.

> f(B) eq S;
true

Run in calculatorCopy input

What is the kernel of \(f\)?

> Kernel(f);
Finitely presented group
Index in group B is 120 = 2^3 * 3 * 5
Subgroup of group B defined by coset table

Run in calculatorCopy input

Using the function GeneratingWords described elsewhere, a set of generators for \(\ker(f)\) as a subgroup of \(B\) can be constructed.

> GeneratingWords(B, Kernel(f));
{  x^-2, y^-2, z^-2, t^-2, (y*z^-1*y^-1)^2, (z*t^-1*z^-1)^2,
   (x*y^-1*x^-1)^2, (x*y*z^-1*y^-1*x^-1)^2, (y*z*t^-1*z^-1*y^-1)^2,
   (x*y*z*t^-1*z^-1*y^-1*x^-1)^2 }

Run in calculatorCopy input

It is easy to see that all generators of \(\ker(f)\) are conjugates of words of the form \(g^{\pm2}\), where \(g\) is a generator of \(B\). This is checked, using the normal closure intrinsic NormalClosure.

> N := sub< B | x^2, y^2, z^2, t^2 >;
> Kernel(f) eq NormalClosure(B, N);
true

Run in calculatorCopy input

Thus the braid relations together with the relators \(x^2, y^2, z^2, t^2\) are a set of defining relations for \(S\). This is confirmed by running the following code:-

> BS := quo< B | x^2, y^2, z^2, t^2 >;
> Order(BS);
120
> P := PermutationGroup(BS);
> P;
Permutation group P acting on a set of cardinality 10
Order = 120 = 2^3 * 3 * 5
> IsIsomorphic(P, Sym(5));
true

Run in calculatorCopy input

Searching for Homomorphisms

This section describes functions for computing representatives of the classes of homomorphisms from a finitely presented group \(G\) to a finite group \(H\) modulo a group \(A\) of automorphisms of \(H\). The algorithm and code are due to Derek Holt.

Intrinsics:

Homomorphisms \((G, H, A )\) : Given a finitely presented group \(G\) and two permutation groups \(H\) and \(A\) with \(H\triangleleft A\), a sequence containing representatives of the classes of homomorphisms from \(G\) to \(H\) modulo automorphisms of \(G\) induced by elements of \(A\) is returned.

Homomorphisms \((G, H, A )\) : This version is identical except that \(H\) and \(A\) are polycyclic groups rather than permutation groups.

Notes:

(i)

Two homomorphisms \(\phi_1\), \(\phi_2 : G \rightarrow H\) are considered equivalent if there exists an element \(a\in A\) such that \(\phi_1(x) = \phi_2(x)^a\) for all \(x\in G\).

(ii)

There is a process version of this intrinsic; that is, a restartable version that returns each homomorphism as soon as it is discovered.

(iii)

The call Homomorphisms(G, H, H) may be abbreviated to Homomorphisms(G, H).

(iv)

The permutation group version of the intrinsic has parameters Surjective, Limit, TimeLimit, CosetEnumeration and CacheCosetAction. If Surjective is set to true then the search is restricted to epimorphisms. The final two parameters relate to the runtime and memory usage of the calculation. The polycyclic group version of the intrinsic has only parameters Surjective and Limit. The default values of Surjective and Limit are true and 1, respectively. If Limit is set to \(0\) this indicates no limit.

Example: Homomorphisms1 (ex-1803a5)

Consider the finitely presented group

\[G\ := \ < a,b,c \ |\ ac^{-1}bc^{-1}aba^{-1}b, abab^{-1}c^2b^{-1}, a^2b^{-1}(ca)^4cb^{-1}>.\]

> G := FPGroup< a,b,c | a*c^-1*b*c^-1*a*b*a^-1*b,
>                     a*b*a*b^-1*c^2*b^-1,
>                     a^2*b^-1*c*a*c*a*c*a*c*a*c*b^-1 >;

Run in calculatorCopy input

The intrinsic Homomorphisms will be used to prove that there is a homomorphism from \(G\) onto \(A_5\).

> H := Alt(5);
> homs := Homomorphisms(G, H : Limit := 1);
> homs;
[
    Homomorphism of GrpFP: G into GrpPerm: H, Degree 5, Order 2^2 * 3 * 5
        G.1 |--> (1, 2, 3)
        G.2 |--> (1, 2, 4)
        G.3 |--> (2, 4)(3, 5)
]

Run in calculatorCopy input

Hence there exists at least one such homomorphism. Are there any more?

> homs := Homomorphisms(G, H);
> #homs;
4

Run in calculatorCopy input

So there are four distinct classes of homomorphisms! Finally, the kernel of the first of these homomorphisms is found.

> phi :=  homs[1];
> K := Kernel(phi);
> K;
Finitely presented group K
Index in group G is 60 = 2^2 * 3 * 5
Subgroup of group G defined by coset table

Run in calculatorCopy input

Searching for Isomorphisms

This section describes an intrinsic that searches for isomorphisms between two finitely presented groups. The algorithm and code are due to Derek Holt.

Intrinsics:

SearchForIsomorphism \((G,~H,~m)\) : Attempt to find an isomorphism from the finitely presented group \(G\) to the finitely presented group \(H\). The search will be restricted to those homomorphisms for which the sum of the word-lengths of the images of the generators of \(G\) in \(H\) is at most \(m\). If an isomorphism \(\phi\) is found, then the values true, \(\phi\), \(\phi^{-1}\) are returned. Otherwise, the values false, _, _ are returned; of course, that does not necessarily mean that the groups are not isomorphic.

Notes:

(i)

Setting the verbose flag "IsoSearch" to \(1\), will cause information about the progress of the search to be printed.

(ii)

There are a number of parameters available for the intrinsic SearchForIsomorphism. If the boolean parameter All is set to true then the search will be continued until all possible isomorphisms that are defined by images of the generators of \(G\) in \(H\) that satisfy the image length condition are considered. If the boolean parameter IsomsOnly is set to false then homomorphisms \(\phi:F\to G\) will be sought. The reader should consult chapter Finitely Presented Groups for a full description of all the parameters.

Example: Search For Iso1 (ex-cebd96)

Jonathon Hillman asked whether the following two groups are isomorphic:

> G1<s,t,u> := FPGroup <s,t,u | s*u*s^-1=u^-1, t^2=u^2, t*s^2*t^-1=s^-2,
>                             u*(s*t)^2=(s*t)^2*u >;
> G2<x,y,z> := FPGroup<x,y,z | x*y^2*x^-1=y^-2, y*x^2*y^-1=x^-2, x^2=z^2*(x*y)^2,
>                            y^2=(z^-1*x)^2, z*(x*y)^2=(x*y)^2*z >;
> isiso, f1, f2 := SearchForIsomorphism(G1,G2,7);
> isiso;
true
> f1;
Homomorphism of GrpFP: G1 into GrpFP: G2 induced by
    s |--> x * z^-1
    t |--> y * z
    u |--> x * y^-1 * z
> f2;
Homomorphism of GrpFP: G2 into GrpFP: G1 induced by
    x |--> s^2 * u * t^-1
    y |--> s^-1 * u^-1
    z |--> s * u * t^-1

Run in calculatorCopy input

So the search for an isomorphism succeeded and returned the isomorphism and its inverse.

Example: Search For Iso2 (ex-8e44ee)

Walter Neumann asked whether these two groups are isomorphic:

> G1<x,y,z> := FPGroup< x,y,z | x^2*y^5, x^14*z^23, (x^2,y), (x^2,z), x*y*z>;
> G2<a,b> := FPGroup<a,b | a*b^16*a*b^-7, a^4*b^7*a^-1*b^7>;

Run in calculatorCopy input

It is a good idea to minimize the number of generators of \(G1\) since there is clearly a redundant generator.

> G1s := Simplify(G1);
> Ngens(G1s);
2
> G1!G1s.1, G1!G1s.2;
x z

Run in calculatorCopy input

Now SearchForIsomorphism \((G1,\ G2,\ 15)\) will succeed, but will take many hours, and also use a lot of memory. In contrast to \(G1\), it can sometimes help to introduce a new generator in the presentation for \(G2\) if there are common substrings in relators.

> G2b<a,b,c> := FPGroup< a,b,c | a*b^16*a*b^-7, a^4*b^7*a^-1*b^7, c=b^7>;
> isiso, f1, f2 := SearchForIsomorphism(G1s,G2b,4);
> isiso;
true
> f1;
Homomorphism of GrpFP: G1s into GrpFP: G2b induced by
    G1s.1 |--> a * c^-1
    G1s.2 |--> c
> f2;
Homomorphism of GrpFP: G2b into GrpFP: G1s induced by
    a |--> G1s.1 * G1s.2
    b |--> G1s.1^6 * G1s.2^10
    c |--> G1s.2

Run in calculatorCopy input