|
For a general description of homomorphisms, we refer to Chapter MAPPINGS.
This section describes some special aspects of homomorphisms the
domain of which is a finitely presented group.
The kernel of a homomorphism with a domain of type GrpFP can be
computed using the function Kernel,
if the codomain is of one of the types GrpGPC, GrpPC
(cf. Chapter FINITE SOLUBLE GROUPS), GrpAb (cf. Chapter ABELIAN GROUPS),
GrpPerm (cf. Chapter PERMUTATION GROUPS),
GrpMat (cf. Chapter MATRIX GROUPS OVER GENERAL RINGS),
ModAlg or ModGrp (cf. Chapter MODULES OVER AN ALGEBRA AND GROUP REPRESENTATIONS), if the image
is finite and its order sufficiently small. In this case, a regular permutation
representation of the image is constructed and the kernel is created as a
subgroup of the domain, defined by a coset table.
The kernel may also be computable, if the codomain is of the type GrpFP,
the image is sufficiently small and a presentation for the image is known.
If the kernel of a map can be computed successfully, forming preimages of
substructures is possible. An attempt to compute the kernel of a map will
be made automatically, if the preimage of a substructure of the codomain
is to be computed.
Note, that trying to compute the kernel may be very time and memory
consuming; use this feature with care.
Returns the homomorphism from the fp-group P to the group G defined by the assignment S. S can be the one of the following:
- (i)
- A list, sequence or indexed set containing the images of the n generators P.1, ..., P.n of P. Here, the i-th element of S is interpreted as the image of P.i, i.e. the order of the elements in S is important.
- (ii)
- A list, sequence, enumerated set or indexed set, containing n tuples <xi, yi> or arrow pairs xi - > yi, where xi is a generator of P and yi∈G (i=1, ..., n) and the set {x1, ..., xn} is the full set of generators of P. In this case, yi is assigned as the image of xi, hence the order of the elements in S is not important.
Note, that it is currently not possible to define a homomorphism by assigning
images to the elements of an arbitrary generating set of P. It is the user's
responsibility to ensure that the arguments passed to the hom-constructor
actually yield a well-defined homomorphism. For certain codomain categories,
this may be checked using the function IsSatisfied described
below.
IsSatisfied(U, E) : { GrpFPElt }, [ GrpElt ] -> BoolElt
IsSatisfied(U, E) : [ RelElt ], [ GrpElt ] -> BoolElt
IsSatisfied(U, E) : [ GrpFPElt ], [ GrpElt ] -> BoolElt
The argument U is a set or sequence of either words belonging to an n-generator
fp-group H or relations over H. The second argument
E is a sequence of n elements
[e1, ..., en] belonging to a group G for which both, multiplication
and comparison of elements are possible.
Using the mapping H.i -> ei (i = 1, ..., n), we evaluate
the relations given by U. If U is a set
or sequence of relations, the left and right hand sides of each
relation are evaluated and compared for equality. Otherwise, each word
in U is evaluated and compared to the identity. If all relations are
satisfied, IsSatisfied returns the Boolean value true. On the
other hand, if any relation is not satisfied, IsSatisfied returns the
value false.
This function may be used to verify the correctness of the definition of
a homomorphism from an fp-group to a group in a category for which both,
multiplication and comparison of elements are possible.
f(w) : Map, GrpFPElt -> GrpElt
Given a homomorphism whose domain is an fp-group G and an element w
of G, return the image of w under f as an element of the codomain
of f.
f(H) : Map, GrpFP -> Grp
Given a homomorphism whose domain is an fp-group G and a subgroup H
of G, return the image of H under f as a subgroup of the codomain
of f.
Some maps do not support images of subgroups.
Given a homomorphism whose domain is an fp-group G and an element g
of the image of f, return the preimage of g under f as an element
of G.
Some maps do not support inverse images.
Given a homomorphism whose domain is an fp-group G and a subgroup H
of the image of f, return the preimage of H under f as a subgroup
of G.
Some maps do not support inverse images. The inverse image of a subgroup of
the codomain can only be computed if the kernel of the homomorphism can be
computed, i.e. if the kernel has moderate index in the domain.
The domain of the homomorphism f.
The codomain of the homomorphism f.
The image or range of the homomorphism f as a subgroup of the codomain of
f.
Some maps do not support this function.
Kernel(f) : Map -> Grp
The kernel of the homomorphism f as a (normal) subgroup of the domain of
f, represented by a coset table.
Some maps do not support this function. The kernel of a homomorphism can
only be computed, if it has moderate index in the domain.
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, we exhibit this
relationship for n=4.
We start with creating the braid group B on 5 strings, i.e. 4 Artin
generators.
> B := BraidFPGroup(5);
> B;
Finitely presented group B on 4 generators
Relations
B.1 * B.2 * B.1 = B.2 * B.1 * B.2
B.1 * B.3 = B.3 * B.1
B.1 * B.4 = B.4 * B.1
B.2 * B.3 * B.2 = B.3 * B.2 * B.3
B.2 * B.4 = B.4 * B.2
B.3 * B.4 * B.3 = B.4 * B.3 * B.4
In the symmetric group of degree 5, we define 4 transpositions 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, we check whether the potential images satisfy the defining
relations of B.
> rels := Relations(B);
> rels;
[ B.1 * B.2 * B.1 = B.2 * B.1 * B.2, B.1 * B.3 = B.3 * B.1,
B.1 * B.4 = B.4 * B.1, B.2 * B.3 * B.2 = B.3 * B.2 * B.3,
B.2 * B.4 = B.4 * B.2, B.3 * B.4 * B.3 = B.4 * B.3 * B.4 ]
> IsSatisfied(rels, imgs);
true
They do. So we can define the homomorphism from B to S.
> f := hom< B->S | imgs >;
We see that f is surjective, i.e. S is an epimorphic image of B as
claimed above.
> f(B) eq S;
true
We now check 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 later, we can
obtain a set of generators of ker(f) as a subgroup of B.
> GeneratingWords(B, Kernel(f));
{ B.2^-2, (B.1 * B.2 * B.3^-1 * B.2^-1 * B.1^-1)^2, B.1^-2,
(B.3 * B.4^-1 * B.3^-1)^2, (B.2 * B.3^-1 * B.2^-1)^2,
(B.2 * B.3 * B.4^-1 * B.3^-1 * B.2^-1)^2, B.4^-2,
(B.1 * B.2^-1 * B.1^-1)^2, B.3^-2,
(B.1 * B.2 * B.3 * B.4^-1 * B.3^-1 * B.2^-1 * B.1^-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. We check this, using the
normal closure constructor ncl described later.
> Kernel(f) eq ncl< B | B.1^2, B.2^2, B.3^2, B.4^2 >;
true
Thus, the braid relations together with the relations
B.1 2, B.2 2, B.3 2, B.4 2 are a set of defining relations for S.
This section describes functions for computing representatives of the
classes of homomorphisms from a finitely presented group F to a
finite group G modulo a group A of automorphisms of G.
Homomorphisms(F, G, A : parameters) : GrpFP, GrpPerm, GrpPerm -> [ HomGrp ]
Homomorphisms(F, G : parameters) : GrpFP, GrpPerm -> [ HomGrp ]
Given a finitely presented group F and two permutation groups G and A
with G triangleleft A, return a sequence containing representatives of the
classes of homomorphisms from F to G modulo automorphisms of G induced by
elements of A. (That is, two homomorphisms f1, f2 : F -> G
are considered equivalent if there exists an element a∈A such that
f1(x) = f2(x)a for all x∈F.) The call Homomorphisms(F, G)
is equivalent to Homomorphisms(F, G, G).
The function uses a backtrack algorithm testing certain conjugates of
representatives of the A-classes in G as possible images of the generators
of F.
The following parameters are available for this function.
Surjective: BoolElt Default: true
If this parameter is set to true (default), only epimorphisms are considered.
Limit: RngIntElt Default: 0 (no limit)
If this parameter is set to n, the function terminates after n classes
of homomorphisms satisfying the specified conditions have been found. A value
of 0 (default) means no limit.
TimeLimit: RngIntElt Default: 0 (no limit)
A limit in seconds for the amount of time spent in the backtrack search
for homomorphisms. The time spent in initial coset enumerations
is not counted towards this limit. A value of 0 (default) means
no limit.
CosetEnumeration: BoolElt Default: true
If this parameter is set to true (default), a number of short coset
enumerations are performed for each generator of F in order to check
whether some A-classes in G can be ruled out as possible images for
this generator. If a class can be ruled out, the complexity of the
backtrack search may be reduced significantly.
In situations where it seems unlikely that classes can be ruled out as
possible generator images, experienced users may wish to turn this feature
off in order to save the time spent on the coset enumerations.
CacheCosetAction: BoolElt Default: true
The value of this parameter indicates whether the actions of A on the cosets
of the centralisers of representatives of the A-classes in G are cached
during the backtrack search.
Setting this parameter to true (default) results in faster computations
and is recommended for normal applications. When computing homomorphisms
to large groups with many conjugate classes, this parameter can be set to
false in order to reduce memory requirements at the expense of increased
computing time.
Consider the finitely presented group
F := < a, b, c | ac - 1bc - 1aba - 1b,
abab - 1c 2b - 1,
a 2b - 1(ca) 4cb - 1>.
> F := 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 >;
We use the function Homomorphisms to prove that F maps onto
A 5.
> G := Alt(5);
> homs := Homomorphisms(F, G : Limit := 1);
> #homs gt 0;
true
Homomorphisms(F, G : parameters) : GrpFP, GrpPC -> [ HomGrp ]
Given a finitely presented group F and two finite polycyclic groups G and A
with G triangleleft A, return a sequence containing representatives of the
classes of homomorphisms from F to G modulo automorphisms of G induced by
elements of A. (That is, two homomorphisms f1, f2 : F -> G
are considered equivalent if there exists an element a∈A such that
f1(x) = f2(x)a for all x∈F.) The call Homomorphisms(F, G)
is equivalent to Homomorphisms(F, G, G).
The following parameters are available for this function.
Surjective: BoolElt Default: true
If this parameter is set to true (default), only epimorphisms are considered.
Limit: RngIntElt Default: 0 (no limit)
If this parameter is set to n, the function terminates after n classes
of homomorphisms satisfying the specified conditions have been found. A value
of 0 (default) means no limit.
The next group of intrinsics describe a process version of the algorithm
described above which computes the homomorphisms one at a time. When
searching for a quotient of the group having certain properties this
technique can save a great deal of time.
HomomorphismsProcess(F, G, A : parameters) : GrpFP, GrpPerm, GrpPerm -> GrpFPHomsProc
HomomorphismsProcess(F, G : parameters) : GrpFP, GrpPerm -> GrpFPHomsProc
Given a finitely presented group F and two permutation groups G and A
with G triangleleft A, return a process P for computing representatives
of the classes of homomorphisms from F to G modulo automorphisms of G
induced by elements of A. (That is, two homomorphisms
f1, f2 : F -> G are considered equivalent if there exists
an element a∈A such that f1(x) = f2(x)a for all x∈F.)
HomomorphismsProcess(F, G) is equivalent to
HomomorphismsProcess(F, G, G).
After constructing the process, the search for homomorphisms is started
and runs until
the first homomorphism is found, the time limit is reached (in which case P
is marked as invalid) or the search is completed without finding a
homomorphism (in which case P is marked as empty).
The parameters have the same meaning as for the function
Homomorphisms.
Surjective: BoolElt Default: true
Limit: RngIntElt Default: 0 (no limit)
TimeLimit: RngIntElt Default: 0 (no limit)
CosetEnumeration: BoolElt Default: true
CacheCosetAction: BoolElt Default: true
Setting a time limit for a process P limits the total amount of time
spent in the backtrack search for homomorphisms during the construction
of P and in subsequent calls to NextElement.
The time spent in initial coset enumerations
is not counted towards this limit.
If the time limit or the limit on the number of homomorphisms set for a process
P is reached, P becomes invalid. Calling
NextElement
for an invalid process or for a process which is
empty, that is, which has found all possible classes of homomorphisms,
will cause a runtime error. The functions IsValid and
IsEmpty can be used to check whether a process is valid
or empty, respectively. The use of these functions is recommended to avoid
runtime errors in loops or user written functions.
NextElement(~P) : GrpFPHomsProc ->
Given a valid and non-empty process P, continue the backtrack search
until a new class of homomorphisms is found. If the search completes
without a new representative being found, P is marked as empty. If a
limit set for P is reached, P is marked as invalid.
IsEmpty(P) : GrpFPHomsProc -> BoolElt
Returns whether P is empty, that is, whether all possible classes of
homomorphisms have been found.
IsValid(P) : GrpFPHomsProc -> BoolElt
Returns false if a limit set for P has been reached and true otherwise.
Note that the return value of IsValid is not related to whether or not
P currently defines a homomorphism.
Returns whether P currently defines a homomorphism which can be extracted
using the function Homomorphism.
Homomorphism(P) : GrpFPHomsProc -> HomGrp
Given a process P which defines a homomorphism, return this homomorphism,
that is, the homomorphism most recently found by P.
If P does not define a homomorphism, a runtime error will result. The
function DefinesHomomorphism can be used to test whether a
call to Homomorphism is legal for a process.
Return the number of homomorphisms that have been found by the process P.
Consider the braid group B on 4 strings.
We show how the interactive computation of homomorphisms can be used to
determine a homomorphism f: B -> PSL(2, 16) whose image
is a maximal subgroup of PSL(2, 16).
Note how the functions IsValid,
IsEmpty and DefinesHomomorphism
are used to avoid runtime errors in the while loop.
> B := BraidFPGroup(4);
> G := PSL(2,16);
> P := HomomorphismsProcess(B, G : Surjective := false,
> TimeLimit := 10);
> while not IsEmpty(P) do
> if DefinesHomomorphism(P) then
> f := Homomorphism(P);
> img := Image(f);
> if IsMaximal(G,img) then
> print "found image which is maximal subgroup";
> break;
> end if;
> end if;
> if IsValid(P) then
> NextElement(~P);
> else
> print "Limit has been reached";
> break;
> end if;
> end while;
found image which is maximal subgroup
>
> f;
Homomorphism of GrpFP: B into GrpPerm: G, induced by
B.1 |--> (1, 4, 3, 6, 12)(2, 11, 9, 16, 7)(5, 17, 8, 15, 13)
B.2 |--> (1, 4, 2, 10, 16)(3, 11, 9, 12, 14)(5, 15, 8, 13, 17)
B.3 |--> (1, 4, 3, 6, 12)(2, 11, 9, 16, 7)(5, 17, 8, 15, 13)
This example sketches how the interactive version of the homomorphism
algorithm could be used as part of a function trying to prove that a group is
infinite.
Note again how the functions IsValid,
IsEmpty and DefinesHomomorphism
are used to avoid runtime errors.
> function MyIsInfinite(F)
>
> // ...
>
> // quotient approach: check whether an obviously infinite
> // normal subgroup can be found in reasonable time.
> S := [ Alt(5), PSL(2,7), PSL(2,9), PSL(2,11) ];
> for G in S do
> P := HomomorphismsProcess(F, G : Surjective := false,
> TimeLimit := 5);
> while IsValid(P) and not IsEmpty(P) do
> if DefinesHomomorphism(P) then
> f := Homomorphism(P);
> if 0 in AQInvariants(Kernel(f)) then
> print "found infinite normal subgroup";
> print "Hence group is infinite";
> return true;
> end if;
> end if;
> if IsValid(P) then
> NextElement(~P);
> end if;
> end while;
> end for;
> print "quotient approach failed; trying other strategies";
>
> // ...
>
> end function;
We try the code fragment on the group
< a, b | ab - 1a - 1ba - 1b - 1abb,
ab - 1a - 1baaba - 1b - 1ab - 1a - 1baba - 1b - 1 >.
> F := FPGroup< a,b |
> a*b^-1*a^-1*b*a^-1*b^-1*a*b*b,
> a*b^-1*a^-1*b*a*a*b*a^-1*b^-1*a*b^-1*a^-1*b*a*b*a^-1*b^-1 >;
> MyIsInfinite(F);
found infinite normal subgroup
Hence group is infinite
true
This section describes a function for searching for isomorphisms
between two finitely presented groups.
SearchForIsomorphism(F, G, m : parameters) : GrpFP, GrpFP, RngIntElt -> BoolElt, HomGrp, HomGrp
Attempt to find an isomorphism from the finitely presented group F to the
finitely presented group G. The search will be restricted to those
homomorphisms for which the sum of the word-lengths of the images of the
generators of F in G 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.
An error will result if any of the generators of F turn out to be trivial.
By setting the verbose flag "IsoSearch" to 1, information about
the progress of the search will be printed.
The parameters available for the function SearchForIsomorphism
are:
All: BoolElt Default: false
If All is false (default), then the function halts and returns as soon as
a single isomorphism is found. If All is true, then the search continues
through all possible images that satisfy the image length condition, and
a list of pairs < φ, φ - 1 > for all isomorphisms
φ:F to G found is returned as the second return value.
IsomsOnly: BoolElt Default: true
If IsomsOnly is set to false, then all homomorphisms F to G will be
returned if All is true, and the first nontrivial homomorphism found
will be returned if All is false.
MaxRels: RngIntElt Default: 250*m
The value of the MaxRelations parameter used in runs of
RWSGroup.
It is
hard to find a sensible default, because if the value is unnecessarily
large then time can be wasted unnecessarily. This may need to be increased if
the function is used with finite groups, for example (although it is usually
much more efficient to use permutation or matrix representations when testing
isomorphism of finite groups).
CycConjTest: BoolElt Default: true
When CycConjTest is true and All is false, then images of the
first generator
which have a cyclic conjugate that comes earlier in the lexicographical order
are rejected, because there would be a conjugate isomorphism in which the
image was the cyclic conjugate. This nearly always results in faster
run-times, but occasionally it can happen that the conjugate isomorphism
has a larger sum of lengths of generator images, which is clearly bad.
So the user has the option of not rejecting such images.
John 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
The search for an isomorphism succeeded and returned the isomorphisms
explicitly.
Walter Neumann asked whether the next 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 here.
> G1s := Simplify(G1);
> Ngens(G1s);
2
> G1!G1s.1, G1!G1s.2;
x z
Now a direct call 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 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]
|