|
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.
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< P -> G | S > : 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 < xi, yi > or n arrow pairs
xi -> yi 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.
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
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) ];
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
They do. So now the homomorphism from B to S can be defined:-
> f := hom< B->S | imgs >;
Note that f is surjective, i.e., S is an epimorphic image of B as
claimed above.
> f(B) eq S;
true
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
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 }
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
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
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 φ1, φ2 : G -> H are considered
equivalent if there exists an element a∈A such that φ1(x) = φ2(x)a
for all x∈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.
Consider the finitely presented group
G := < a, b, c | ac - 1bc - 1aba - 1b,
abab - 1c 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 >;
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)
]
Hence there exists at least one such homomorphism. Are there any more?
> homs := Homomorphisms(G, H);
> #homs;
4
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
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 φ
is found, then the values true, φ, φ - 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 φ:F to G will be sought. The
reader should consult chapter FINITELY PRESENTED GROUPS for a full description of all the
parameters.
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
So the search for an isomorphism succeeded and returned the isomorphism and its
inverse.
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>;
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
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
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|