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 FINITELY PRESENTED ABELIAN GROUPS), GrpPerm (cf. Chapter PERMUTATION GROUPS), GrpMat (cf. Chapter MATRIX GROUPS), ModAlg or ModGrp (cf. Chapter MODULES OVER A MATRIX ALGEBRA), 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: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.
- (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 <x_i, y_i> or arrow pairs x_i - > y_i, where x_i is a generator of P and y_i in G (i=1, ..., n) and the set {x_1, ..., x_n} is the full set of generators of P. In this case, y_i is assigned as the image of x_i, hence the order of the elements in S is not important.
U is a set or sequence of either words belonging to an n-generator fp-group H or relations over H. E is a sequence of n elements [e_1, ..., e_n] belonging to a group G for which both, multiplication and comparison of elements are possible. Using the mapping H.i -> e_i (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.
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.
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.
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 := BraidGroup(GrpFP, 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 := SymmetricGroup(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); trueThey 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; trueWe 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 tableUsing 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 >; trueThus, 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 permutation group G modulo a group A of automorphisms of G.
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 f_1, f_2 : F -> G are considered equivalent if there exists an element a in A such that f_1(x) = f_2(x)^a for all x in 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: trueIf 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: trueIf 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: trueThe 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.
> F := Group< 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
A process version of the algorithm used by Homomorphisms is available for computing homomorphisms one at a time. The functions relevant for this interactive version are described in this section.
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 f_1, f_2 : F -> G are considered equivalent if there exists an element a in A such that f_1(x) = f_2(x)^a for all x in 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: trueSetting 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 and Complete. 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 or Complete 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.
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.
Given a valid and non-empty process P, continue the search for homomorphisms until all classes of homomorphisms have been found or a limit set for P is reached. If the search for homomorphisms completes, P is marked as empty. If a limit set for P is reached, P is marked as invalid.
Returns whether P is empty, that is, whether all possible classes of homomorphisms have been found.
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.
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.
Return a sequence containing all homomorphisms that have been found by the process P. Note that the sequence will only contain a complete set of representatives of the classes of homomorphisms if P is empty, that is, if the backtrack search for P has been completed.
Note how the functions IsValid, IsEmpty and DefinesHomomorphism are used to avoid runtime errors in the while loop.
> B := BraidGroup(GrpFP, 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)
> 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^(-1)a^(-1)ba^(-1)b^(-1)abb, ab^(-1)a^(-1)baaba^(-1)b^(-1)ab^(-1)a^(-1)baba^(-1)b^(-1) >.
> F := Group< 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
We describe utilities for finding homomorphisms onto simple groups. As in the previous example, this may be useful when the presentation defines a perfect group. The methods used are similar to the example, with a list of simple groups to try, and using the function Homomorphisms.
The list of simple groups supplied in V2.10 contains all non-abelian simple groups with order <= 10^9. Such a list is dominated by PSL(2, q)'s with q odd. In this implementation these PSL(2, q)'s are treated as an infinite family rather than stored individually, and so continue beyond the above limit.
Limit: RngIntElt Default: 1
Family: Any Default: "All"
Uses Homomorphisms to find epimorphisms from F onto simple groups in a fixed list. The arguments deg1 and deg2 are respectively lower and upper bounds for the degree of the image group. The arguments ord1 and ord2 are respectively lower and upper bounds for the orders of the image group. (Setting ord2 low enough is particularly important if you want a quick search.)The return value is a list of sequences of epimorphisms found. Each sequence contains epimorphisms onto one simple group. The parameter Limit limits the number of successful searches to be carried out by Homomorphisms. The default value is 1, so by default the search terminates with the first simple group found to be a homomorphic image of F.
The parameter Family selects sublists of the main list to search. Possible values of this parameter are "All", "PSL", "PSL2", "Mathieu", "Alt", "PSp", "PSU", "Other" and "notPSL2", or sets of these strings, which joins sublists.
Family: Any Default: "All"
Produce a record that defines a process for searching for simple quotients of F as SimpleQuotients does. Calling this function sets up the record and conducts the initial search until a quotient is found. Continuing the search for another quotient is done by calling NextSimpleQuotient. Extracting the epimorphisms found is achieved using SimpleEpimorphisms, and testing if the process has expired is the task of IsEmptySimpleQuotientProcess.
When P is a record returned by SimpleQuotientProcess, advance the search to the next simple group which is a homomorphic image of the finitely presented group. Does nothing if the process has expired.
When P is a record returned by SimpleQuotientProcess, test whether or not P has expired.
When P is a record returned by SimpleQuotientProcess, extract the most recently found epimorphisms onto a simple group, plus a tuple describing the image group. This is a valid operation when IsEmptySimpleQuotientProcess returns false.
> F := Group<a,b,c|a^13,b^3,c^2,a = b*c>;
> IsPerfect(F);
true
> L := SimpleQuotients(F,1, 100, 2, 10^5:Limit := 2);
> #L;
2
> for x in L do CompositionFactors(Image(x[1])); end for;
G
| A(1, 13) = L(2, 13)
1
G
| A(2, 3) = L(3, 3)
1
> L[2,1];
Homomorphism of GrpFP: F into GrpPerm: , Degree 13, Order
2^4 * 3^3 * 13 induced by
F.1 | - -> (1, 10, 4, 5, 11, 8, 3, 6, 7, 12, 9, 13, 2)
F.2 | - -> (2, 10, 4)(3, 6, 7)(5, 11, 13)(8, 12, 9)
F.3 | - -> (1, 10)(2, 5)(3, 12)(8, 13)
> #L[2];
2
We've found L(2, 13) ans L(3, 3) as images, with 2 inequivalent homomorphisms
onto the second. We'll try a process looking through a smaller family.
> P := SimpleQuotientProcess(F, 1, 100, 2, 10^6:Family:="PSU"); > IsEmptySimpleQuotientProcess(P); false > eps, info := SimpleEpimorphisms(P); > info; <65, 62400, PSU(3, 4)>We've found PSU(3, 4) of order 62400 and degree 65 as an image. We continue with this process.
> NextSimpleQuotient(~P); > IsEmptySimpleQuotientProcess(P); trueNo, there are no more within the limits given., Degree 13, Order 2^4 * 3^3 * 13 induced by F.1 |--> (1, 10, 4, 5, 11, 8, 3, 6, 7, 12, 9, 13, 2) F.2 |--> (2, 10, 4)(3, 6, 7)(5, 11, 13)(8, 12, 9) F.3 |--> (1, 10)(2, 5)(3, 12)(8, 13) > #L[2]; 2 We've found L(2,13) ans L(3,3) as images, with 2 inequivalent homomorphisms onto the second. We'll try a process looking through a smaller family.
> P := SimpleQuotientProcess(F,1, 100, 2, 10^6:Family:="PSU"); > IsEmptySimpleQuotientProcess(P); false > eps, info := SimpleEpimorphisms(P); > info; <65, 62400, PSU(3, 4)>We've found PSU(3,4) of order 62400 and degree 65 as an image. We continue with this process.
> NextSimpleQuotient(~P); > IsEmptySimpleQuotientProcess(P); trueNo, there are no more within the limits given.