A powerful technique for investigating a fp-group is to study some of its quotients. In this section we present tools for constructing various types of quotient group. Specifically, machinery is available for constructing abelian quotients, p-quotients, nilpotent quotients, soluble quotients and L(2), L(3), and U(3) quotients.
The functions in this section compute information about the abelian quotient of an fp-group G. Some functions may require the computation of a coset table. Experienced users can control the behaviour of an implicit coset enumeration with a set of global parameters. These global parameters can be changed using the function SetGlobalTCParameters. For a detailed description of the available parameters and their meanings, we refer to Subsec. Interactive Coset Enumeration.
The functions returning the abelian quotient or the abelian quotient invariants report an error if the abelian quotient cannot be computed, for example, because the relation matrix is too large. To avoid problems in user written programs or loops, the functions HasComputableAbelianQuotient and HasInfiniteComputableAbelianQuotient can be used.
The maximal abelian quotient G/Gprime of the group G as GrpAb (cf. Chapter ABELIAN GROUPS). The natural epimorphism π:G -> G/Gprime is returned as second value.
The maximal p-elementary abelian quotient Q of the group G as GrpAb (cf. Chapter ABELIAN GROUPS). The natural epimorphism π:G -> Q is returned as second value.
Given a finitely presented group G, this function computes the elementary divisors of the derived quotient group G/G', by constructing the relation matrix for G and transforming it into Smith normal form. The algorithmthe ring of integers Z using clever heuristics to minimize the growth of coefficients.
The divisors are returned as a sequence of integers.
Given a subgroup H of the finitely presented group G, this function computes the elementary divisors of the derived quotient group of H. (The coset table T may be used to define H.) This is done by abelianising the Reidemeister-Schreier presentation for H and then proceeding as above. The divisors are returned as a sequence of integers.
Given a finitely presented group G, this function computes the elementary divisors of the quotient group G/N, where N is the normal subgroup of G generated by the derived group G' together with all n-th powers of elements of G. The algorithm constructs the relation matrix corresponding to the presentation of G and computes its Smith normal form over the ring Z/nZ. The calculation is particularly efficient when n is a small prime. The divisors are returned as a sequence of integers.
Given a subgroup H of the finitely presented group G, this function computes the elementary divisors of the quotient group H/N, where N is the normal subgroup of H generated by H' together with all n-th powers of elements of H. (The coset table T may be used to define H.) This is done by abelianising the Reidemeister-Schreier presentation for H and then proceeding as above. The divisors are returned as a sequence of integers.
Given an fp-group G, this function tests whether the abelian quotient of G can be computed. If so, it returns the value true, the abelian quotient A of G and the natural epimorphism π:G -> A. If the abelian quotient of G cannot be computed, the value false is returned.This function is especially useful to avoid runtime errors in user written loops or functions.
Given an fp-group G, this function tests whether the abelian quotient of G can be computed and is infinite. If so, it returns the value true, the abelian quotient A of G and the natural epimorphism π:G -> A. If the abelian quotient of G cannot be computed or if it is finite, the value false is returned.The function first checks the modular abelian invariants for a set of small primes. If for one of these primes, the modular abelian quotient is trivial, A must be finite and the function returns without actually computing the abelian quotient. If one is interested only in infinite quotients, this heuristics may save time.
Given an fp-group G, this function tries to decide whether G is perfect by checking whether the abelian quotient of G is trivial.
Given the finitely presented group G, return the torsion-free rank of the derived quotient group of G.
> F<a, b> := FreeGroup(2);
> F7<a, b> := quo< F | a^2*b^-2*a^-1*b^-2*(a^-1*b^-1)^2,
> a*b*a*b^2*a*b*a*b^-1*(a*b^2)^2 >;
> F7;
Finitely presented group F7 on 2 generators
Relations
a^2 * b^-2 * a^-1 * b^-2 * a^-1 * b^-1 * a^-1 * b^-1 =Id(F7)
a * b * a * b^2 * a * b * a * b^-1 * a * b^2 * a * b^2 = Id()7
We begin by determining the structure of the maximal abelian quotient of
F(7).
> AbelianQuotientInvariants(F7); [ 29 ]The maximal abelian quotient of F(7) is cyclic of order 29. At this point there is no obvious way to proceed, so we attempt to determine the index of some subgroups.
> Index( F7, sub< F7 | a > ); 1We are in luck: F(7) is generated by a and so must be cyclic. This fact coupled with the knowledge that its abelian quotient has order 29 tells us that the group is cyclic of order 29.
> G<a, b> := FPGroup<a, b| a^8, b^7, (a * b)^2, (a^-1 * b)^3>; > H<x, y> := sub< G | a^2, a^-1 * b >;The fastest way to determine the order of the maximal 2-elementary abelian quotient of H is to use the function AbelianQuotientInvariants:
> #AbelianQuotientInvariants(H,2); 1We see that the maximal 2-elementary abelian quotient of H has order 21.
Return true if G has finite abelian quotient. The algorithm requires either a presentation for G, or the coset table for G inside some supergroup of G which has a presentation. If such a coset table cannot be computed, an error will result.
Return a sequence of primes containing all prime divisors of the order of G/G', if this is finite. Note that there may be primes in the return sequence which do not divide this order. If [ 0 ] is returned then G/G' is infinite. If [] is returned, then G is perfect. The algorithm requires either a presentation for G, or the coset table for G inside some supergroup of G which has a presentation. If such a coset table cannot be computed, an error will result.
Let F be a finitely presented group, p a prime and c a positive integer. A p-quotient algorithm constructs a consistent power-conjugate presentation for the largest p-quotient of F having lower exponent-p class at most c. The p-quotient algorithm used by Magma is part of the ANU p-Quotient program. For details of the algorithm, see [NO96]. In Magma the result is returned as a group of type GrpPC (cf. Chapter FINITE SOLUBLE GROUPS).
Assume that the p-quotient has order pn, Frattini rank d, and that its generators are a1, ..., an. Then the power-conjugate presentation constructed has the following additional structure. The set {a1, ..., ad} is a generating set for G. For each ak in {ad + 1, ..., an}, there is at least one relation whose right hand side is ak. One of these relations is taken as the definition of ak. (The list of definitions is also returned by pQuotient.) The power-conjugate generators also have a weight associated with them: a generator is assigned a weight corresponding to the stage at which it is added and this weight is extended to all normal words in a natural way.
The p-quotient function and its associated commands allows the user to construct a power-conjugate presentation (pcp) for a p-group. Note that there is also a process version of the p-quotient algorithm, which gives the user complete control over its execution. For a description, we refer to Subsec. p-Quotient Process.
The parameters available for the function pQuotient are:
var Exponent: RngIntElt Default: 0 If Exponent := m, enforce the exponent law, xm = 1, on the group.
var Metabelian: BoolElt Default: false If Metabelian := true, then a consistent pcp is constructed for the largest metabelian p-quotient of F having lower exponent-p class at most c.
var Print: RngIntElt Default: 0 This parameter controls the volume of printing. By default its value is that returned by GetVerbose("pQuotient"), which is 0 unless it has been changed through use of SetVerbose. The effect is the following:
Print := 0: No output.
Print := 1: Report order of p-quotient at each class.
Print := 2: Report statistics and redundancy information about tails, consistency, collection of relations and exponent enforcement components of calculation.
Print := 3: Report in detail on the construction of each class.
Note that the presentation displayed is a power-commutator presentation (since this is the version stored by the p-quotient).
var Workspace: RngIntElt Default: 5000000 The amount of space requested for the p-quotient computation.
Given an fp-group F, a prime p and a positive integer c, construct a pcp for the largest p-quotient G of F having lower exponent-p class at most c. If c is given as 0, then the limit 127 is placed on the class. The function also returns the natural homomorphism π from F to G, a sequence S describing the definitions of the pc-generators of G and a flag indicating whether G is the maximal p-quotient of F.The k-th element of S is a sequence of two integers, describing the definition of the k-th pc-generator G.k of G as follows.
There exist a number of parameters for controlling the behaviour of this function, which are described below.
- -
- If S[k] = [0, r], then G.k is defined via the image of F.r under π.
- -
- If S[k] = [r, 0], then G.k is defined via the power relation for G.r.
- -
- If S[k] = [r, s], then G.k is defined via the conjugate relation involving G.rG.s.
> F<a,b> := FreeGroup(2); > G := quo< F | (b, a, a) = 1, (a * b * a)^4 = 1 >; > Q, fQ := pQuotient(G, 2, 6); > Order(Q); 524288 > fQ; Mapping from: GrpFP: G to GrpPC: Q
> F<a,b> := FreeGroup(2); > G := quo< F | a^3 = b^3 = 1 >; > q := pQuotient(G, 3, 6: Print := 1, Exponent := 9); Lower exponent-3 central series for G Group: G to lower exponent-3 central class 1 has order 3^2 Group: G to lower exponent-3 central class 2 has order 3^3 Group: G to lower exponent-3 central class 3 has order 3^5 Group: G to lower exponent-3 central class 4 has order 3^7 Group: G to lower exponent-3 central class 5 has order 3^9 Group: G to lower exponent-3 central class 6 has order 3^11
> F<a, b> := FreeGroup(2); > G := quo< F | a^625 = b^625 = 1, (b, a, b) = 1, > (b, a, a, a, a) = (b, a)^5 >; > q := pQuotient(G, 5, 20: Print := 1, Metabelian := true); Lower exponent-5 central series for G Group: G to lower exponent-5 central class 1 has order 5^2 Group: G to lower exponent-5 central class 2 has order 5^5 Group: G to lower exponent-5 central class 3 has order 5^8 Group: G to lower exponent-5 central class 4 has order 5^11 Group: G to lower exponent-5 central class 5 has order 5^12 Group: G to lower exponent-5 central class 6 has order 5^13 Group: G to lower exponent-5 central class 7 has order 5^14 Group: G to lower exponent-5 central class 8 has order 5^15 Group: G to lower exponent-5 central class 9 has order 5^16 Group: G to lower exponent-5 central class 10 has order 5^17 Group: G to lower exponent-5 central class 11 has order 5^18 Group: G to lower exponent-5 central class 12 has order 5^19 Group: G to lower exponent-5 central class 13 has order 5^20 Group completed. Lower exponent-5 central class = 13, order = 5^20
> F := FreeGroup(2); > q := pQuotient (F, 5, 14: Print := 1, Exponent := 5); Lower exponent-5 central series for F Group: F to lower exponent-5 central class 1 has order 5^2 Group: F to lower exponent-5 central class 2 has order 5^3 Group: F to lower exponent-5 central class 3 has order 5^5 Group: F to lower exponent-5 central class 4 has order 5^8 Group: F to lower exponent-5 central class 5 has order 5^10 Group: F to lower exponent-5 central class 6 has order 5^14 Group: F to lower exponent-5 central class 7 has order 5^18 Group: F to lower exponent-5 central class 8 has order 5^22 Group: F to lower exponent-5 central class 9 has order 5^28 Group: F to lower exponent-5 central class 10 has order 5^31 Group: F to lower exponent-5 central class 11 has order 5^33 Group: F to lower exponent-5 central class 12 has order 5^34 Group completed. Lower exponent-5 central class = 12, order = 5^34
Given a pc-group G, this function returns true iff and only if G has generator definitions set by pQuotient.
Given a pc-group G, this function returns the generator definitions set by pQuotient, and will throw an error if none exist.
In this and the next subsections the interative p-quotient process is described.
Given an fp-group F, a prime p and a positive integer c, create a p-quotient process for the group F with the indicated arguments. As part of the initialisation of the process, a pcp for the largest p-quotient of F having class at most c will be constructed. If c is given as 0, then the limit 127 is placed on the class. This function supports the same parameters as pQuotient and returns a process P.
Exponent: RngIntElt Default:
Metabelian: BoolElt Default:
Print: RngIntElt Default:
MaxOccurrence: [ RngIntElt ] Default: []
Assumes that a pcp has already been constructed for the class c quotient of F. It seeks to construct a pcp for the class c + 1 p-quotient of F. If k is supplied, continue to construct until the pcp for the largest quotient of class k is constructed.The parameters Exponent, Print, and Metabelian are used as before. If MaxOccurrence := Q, then the sequence Q has length equal to the rank of the class 1 quotient of F; its entries are integers which specify the maximum number of occurrences of the class 1 generators in the definitions of pcp generators of F. An entry of 0 for a particular generator indicates that no limit is placed on the number of occurrences of this generator.
Care should be exercised when supplying values for parameters. Once set, they retain their values until explicitly reassigned.
We assume that we have constructed a pcp for the largest class c p-quotient of F and now seek to construct a pcp for the largest class c + 1 p-quotient.
The following options allow the user to construct a pcp for the next class of the group interactively. The steps are laid out in one of a number of natural sequences in which they may be executed. Some of them may be interleaved; however, the user should pay particular attention to the assumptions mentioned below. The procedures that drive the process do not verify that the assumptions are satisfied.
If P is a process for a class c p-quotient, commence construction of class c + 1.
Metabelian: BoolElt Default: false
Add tails to the current pcp; default is to add all tails for this class. If k is supplied, then tails for weight k only are added; in this case, it is assumed that the tails for each of weight c + 1, c, ..., k + 1 have already been added. The valid range of k is 2, ..., c + 1. The one valid parameter is Metabelian; if true, then only the tails for the metabelian p-quotient are inserted.
Metabelian: BoolElt Default: false
Apply the consistency algorithm to the pcp to compute any redundancies among the tails already added. Default is to apply it to all tails; in this case, it is assumed that all tails have been added. If k is supplied, it is assumed that tails for weight k have been added; in this case, the tails added for weight k only are checked. The range of k is 3, ..., c + 1. The one valid parameter is Metabelian; if true, we assume that the tails inserted were those for a metabelian p-quotient and hence invoke the (less expensive) metabelian consistency algorithm.
Collect the defining relations (if any) in the current pcp. If the tails operation is not complete, then the relations may be evaluated incorrectly.
Enforce the supplied exponent law on the current pcp. If Start and Fin are supplied, then enforce the law for those weights between Start and Fin; otherwise, enforce the law for all weights. It is assumed that the tails operation is complete. If the display parameter DisplayLevel (which may be set using SetDisplayLevel) has value 2, those words whose powers are collected and give redundancies among the pcp generators are printed out. If DisplayLevel has value 3, all words whose powers are collected are printed out. The following additional parameters are available:Exponent: RngIntElt Default: 0If Exponent := m, enforce the exponent law, xm = 1, on the group.Print: RngIntElt Default: 1As for pQuotient.Trial: BoolElt Default: falseGenerate the list of words used to enforce the exponent law and print out statistics but do not power words or echelonise the results.ShortList: BoolElt Default: falseGenerate the list of enforcement words whose entries have the form w or 1 ast w where w is an element of the Frattini subgroup of F.DisplayList: BoolElt Default: falseDisplay the list of all enforcement words generated -- not just those which are collected.IdentifyFilters: BoolElt Default: falseIdentify filters used to eliminate words from list.InitialSegment: [<GrpFPElt, RngIntElt>] Default: []If InitialSegment := w, generate only those enforcement words which have w as an initial segment, where w is supplied as a sequence of generator-exponent pairs.Report: RngIntElt Default: 0If Report := n, report after computing the powers of each collection of n enforcement words.
Eliminate all redundant generators from the pcp defined by process P. This operation may be performed at any time.
We now list the remaining functions which can be applied to a pQuotient process.
Display the pcp for the p-quotient G of the fp-group F. The argument DisplayLevel may be 1, 2, or 3, and is used to control the amount of information given:The presentation displayed by this function is in power-commutator form. If DisplayLevel is not supplied, the information displayed is determined by its existing (or default) value.
- 1 :
- Display order and class of G;
- 2 :
- Display non-trivial relations for G;
- 3 :
- Display the structure of pcp generators of G, non-trivial relations of G, and the map from the defining generators of F to the pcp generators of G.
Given a pcp for the class c + 1 p-quotient of F, this procedure reverts to the pcp for the class c p-quotient of F. Note that this command can be applied only once during construction of a single class.
Given a process or a pcp for a p-group, this procedure computes a pcp for the p-covering group of this group. In the process case, it is equivalent to Tails(~P); Consistency(~P); EliminateRedundancy(~P).
Display the structure of the generators in the pcp. If Start and Fin are given, then print out the structure of those pcp generators numbered from Start to Fin.
Calculate the Jacobi c, b, a and echelonise the resulting relation against the current pcp. If a redundant generator results from the echelonisation, the optional variable r is the number of that generator; otherwise r has value 0.
The sequence Q, consisting of generator-exponent pairs, defines a word w in the pcp generators of the group defined by the process P. Collect this word and return the resulting normal word as an exponent vector.
Echelonise the word most recently collected using Collect against the relations of the pcp. If a redundant generator results from the echelonisation, the optional variable r is the number of that generator; otherwise r has value 0. This function must be called immediately after Collect.
This procedure alters the display level for the process to the supplied value, Level.
Extract the group G defined by the pcp associated with the process P, as a member of the category GrpPC of finite soluble groups. The function also returns the natural homomorphism π from the original group F to G, a sequence S describing the definitions of the pc-generators of G and a flag indicating whether G is the maximal p-quotient of F.The k-th element of S is a sequence of two integers, describing the definition of the k-th pc-generator G.k of G as follows.
- -
- If S[k] = [0, r], then G.k is defined via the image of F.r under π.
- -
- If S[k] = [r, 0], then G.k is defined via the power relation for G.r.
- -
- If S[k] = [r, s], then G.k is defined via the conjugate relation involving G.rG.s.
The order of the group defined by the pcp associated with the process P.
The factored order of the group defined by the pcp associated with the process P.
The number of pc-generators of the group defined by the pcp associated with the process P.
The lower exponent-p class of the group defined by the pcp associated with the process P.
Return the rank of the p-multiplicator of the p-group G, where G may be supplied or defined by the process P.
Return the rank of the p-multiplicator of the p-group G, where G may be supplied or defined by the process P.
> G<a, b> := FPGroup<a, b | a^3, b^3>; > q := pQuotientProcess(G, 3, 4: Exponent := 9, Print :=1); Lower exponent-3 central series for G Group: G to lower exponent-3 central class 1 has order 3^2 Group: G to lower exponent-3 central class 2 has order 3^3 Group: G to lower exponent-3 central class 3 has order 3^5 Group: G to lower exponent-3 central class 4 has order 3^7 > Display(q, 2); Group: G to lower exponent-3 central class 4 has order 3^7 Non-trivial powers: .3^3 = .6^2 Non-trivial commutators: [ .2, .1 ] = .3 [ .3, .1 ] = .4 [ .3, .2 ] = .5 [ .4, .1 ] = .6 [ .4, .2 ] = .7 [ .5, .1 ] = .7 [ .5, .2 ] = .6We construct the class 5 quotient using the function NextClass.
> NextClass(~q); Group: G to lower exponent-3 central class 5 has order 3^9We now construct the class 6 quotient step by step. For this, we set the output level to 1.
> SetDisplayLevel(~q, 1);Now we start the next class.
> StartNewClass(~q);The first step is to add the tails.
> Tails(~q);After that, we apply the consistency algorithm, ...
> Consistency(~q);... collect the defining relations, ...
> CollectRelations(~q);... and enforce the exponent law.
> ExponentLaw(~q);Finally, we eliminate redundant generators.
> EliminateRedundancy(~q);This results in the following presentation for class 6 quotient.
> Display(q, 2); Group: G to lower exponent-3 central class 6 has order 3^11 Non-trivial powers: .3^3 = .6^2 .8^2 .10 .11 Non-trivial commutators: [ .2, .1 ] = .3 [ .3, .1 ] = .4 [ .3, .2 ] = .5 [ .4, .1 ] = .6 [ .4, .2 ] = .7 [ .4, .3 ] = .8 .10^2 .11^2 [ .5, .1 ] = .7 .8 .9^2 .10^2 .11^2 [ .5, .2 ] = .6 .8 .9^2 .10^2 [ .5, .3 ] = .9^2 .11 [ .5, .4 ] = .10 .11 [ .6, .2 ] = .10^2 [ .7, .1 ] = .8 [ .7, .2 ] = .9 [ .7, .3 ] = .10^2 .11 [ .8, .2 ] = .10 [ .9, .1 ] = .11
We start with setting up the class 1 quotient of the group.
> G := FPGroup<a, b | a^5, b^5>; > q := pQuotientProcess(G, 5, 1); > Display(q, 1); Group: G to lower exponent-5 central class 1 has order 5^2Now we start the next class, setting bounds on the number of occurrences of the pcp generators of the class 1 quotient in the definitions of new pcp generators.
> NextClass(~q, 6: MaxOccurrence := [3, 2]); Group: G to lower exponent-5 central class 2 has order 5^3 Group: G to lower exponent-5 central class 3 has order 5^5 Group: G to lower exponent-5 central class 4 has order 5^7 Group: G to lower exponent-5 central class 5 has order 5^9 > Display(q, 2); Group: G to lower exponent-5 central class 5 has order 5^9 Non-trivial powers: Non-trivial commutators: [ .2, .1 ] = .3 [ .3, .1 ] = .4 [ .3, .2 ] = .5 [ .4, .1 ] = .6 [ .4, .2 ] = .7 [ .4, .3 ] = .8^4 .9 [ .5, .1 ] = .7 .8^4 .9 [ .6, .2 ] = .8 [ .7, .1 ] = .9
> F := FreeGroup(2); > q := pQuotientProcess(F, 5, 6: Exponent := 5); Lower exponent-5 central series for F Group: F to lower exponent-5 central class 1 has order 5^2 Group: F to lower exponent-5 central class 2 has order 5^3 Group: F to lower exponent-5 central class 3 has order 5^5 Group: F to lower exponent-5 central class 4 has order 5^8 Group: F to lower exponent-5 central class 5 has order 5^10 Group: F to lower exponent-5 central class 6 has order 5^14 > StartNewClass(~q); > Tails(~q); > Consistency(~q); > SetDisplayLevel(~q, 3); > ExponentLaw(~q, 1, 6: InitialSegment := [<1, 2>], Trial := true); 0 Relations of class 1 will be collected 0 Relations of class 2 will be collected Will collect power 5 of the following word: 1^2 2^1 1 Relation of class 3 will be collected Will collect power 5 of the following word: 1^2 2^2 1 Relation of class 4 will be collected Will collect power 5 of the following word: 1^2 2^3 Will collect power 5 of the following word: 1^2 5^1 2 Relations of class 5 will be collected Will collect power 5 of the following word: 1^2 2^4 Will collect power 5 of the following word: 1^2 2^1 4^1 2 Relations of class 6 will be collected
> G := FPGroup<a, b, c, d | (b * c^-1 * d)^7, (c * d^-1)^7, (b,a) = c^-1,
> (c,a) = 1, (c,b) = d^-1>;
> q := pQuotientProcess(G, 7, 6);
Lower exponent-7 central series for G
Group: G to lower exponent-7 central class 1 has order 7^2
Group: G to lower exponent-7 central class 2 has order 7^4
Group: G to lower exponent-7 central class 3 has order 7^6
Group: G to lower exponent-7 central class 4 has order 7^8
Group: G to lower exponent-7 central class 5 has order 7^11
Group: G to lower exponent-7 central class 6 has order 7^14
> StartNewClass(~q);
> Tails(~q);
> GeneratorStructure(q, 15, 34);
Class 7
15 is defined on [12, 1] = 2 1 2 2 1 2 1
16 is defined on [12, 2] = 2 1 2 2 1 2 2
17 is defined on [13, 1] = 2 1 2 2 2 2 1
18 is defined on [13, 2] = 2 1 2 2 2 2 2
19 is defined on [14, 1] = 1 1 1 1 1 1 1
20 is defined on [14, 2] = 1 1 1 1 1 1 2
21 is defined on 14^7 = 1 1 1 1 1 1 1
22 is defined on [9, 1] = 2 1 2 2 1 1
23 is defined on [10, 1] = 2 1 2 2 2 1
24 is defined on [11, 1] = 1 1 1 1 1 1
25 is defined on [11, 2] = 1 1 1 1 1 2
26 is defined on [8, 1] = 1 1 1 1 1
27 is defined on [8, 2] = 1 1 1 1 2
28 is defined on [5, 1] = 2 1 2 1
29 is defined on [6, 1] = 1 1 1 1
30 is defined on [6, 2] = 1 1 1 2
31 is defined on [3, 1] = 2 1 1
32 is defined on [4, 1] = 1 1 1
33 is defined on [4, 2] = 1 1 2
34 is defined on 2^7 = 2 2
> Jacobi(~q, 6, 6, 1);
Generator 26 is trivial
Jacobi was 6 6 1
> Jacobi(~q, 3, 2, 1);
Generator 28 is redundant
Jacobi was 3 2 1
> v := Collect(q, [<29, 2>, <26, -3>]);
> v;
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 4, 0, 0, 2, 0, 0, 0, 0, 0 ]
> EcheloniseWord(~q, ~redgen);
Generator 29 is trivial
> Display(q, 1);
Group: G to lower exponent-7 central class 7 has order 7^34
Now we enforce the relations ... > CollectRelations(~q);... and apply the consistency algorithm.
> Consistency(~q); > Display(q, 1); Group: G to lower exponent-7 central class 7 has order 7^36 > EliminateRedundancy(~q); > Display(q, 1); Group: G to lower exponent-7 central class 7 has order 7^19
A nilpotent quotient algorithm constructs, from a finite presentation of a group, a polycyclic presentation of a nilpotent quotient of the finitely presented group. The nilpotent quotient algorithm used by Magma is the Australian National University Nilpotent Quotient program, as described in [Nic96]. The version included in Magma is Version 2.2 of January 2007.
The lower central series G0, G1, ... of a group G can be defined inductively as G0 = G, Gi = [G_(i - 1), G]. G is said to have nilpotency class c if c is the smallest non-zero integer such that Gc = 1. If N is a normal subgroup of G and G/N is nilpotent, then N contains Gi for some non-negative integer i. G has infinite nilpotent quotients if and only if G/G1 (the maximal abelian quotient of G) is infinite and a prime p divides a finite factor of a nilpotent quotient if and only if p divides a cyclic factor of G/G1. The i-th (i > 1) factor Gi - 1/Gi of the lower central series is generated by the elements [g, h]Gi, where g runs through a set of representatives of G/G1 and h runs through a set of representatives of Gi - 2/Gi - 1.
Any finitely generated nilpotent group is polycyclic and, therefore, has a subnormal series with cyclic factors. Such a subnormal series can be used to represent the group in terms of a polycyclic presentation. The ANU NQ computes successively the factor groups modulo the terms of the lower central series. Each factor group is represented by a special form of polycyclic presentation, a nilpotent presentation, that makes use of the nilpotent structure of the factor group.
The algorithm has highly efficient code for enforcing the n-Engel identity in nilpotent groups. When appropriate parameters are set, the algorithm computes the largest n-Engel quotient of G/Gc.
More generally, the algorithm has code for enforcing arbitrary identical relations. You can even enforce relations which combine generators of G with "free variables". (Werner Nickel calls these "identical generators".) For instance, the relation (a,x) = 1, where a is a group generator and x is a free variable, will force the construction of quotients where the image of a is central.
Mike Vaughan-Lee offers advice on when to use the nilpotent quotient algorithm. If you know nothing about the finitely presented group, it is probably a good idea to look at the abelian quotient first. If the abelian quotient is trivial then all nilpotent quotients will be trivial. Similarly, if the abelian quotient is cyclic, then all nilpotent quotients will be cyclic. Less trivially, if the abelian quotient is finite then all nilpotent quotients will be finite and so will be the direct product of finite p-groups. Moreover, the relevant primes p will all occur in the abelian quotient. Usually it will be more effective to use the p-quotient algorithm to study the direct factors. However, if you want to study 3-Engel quotients (say), then you are better using the nilpotent quotient even when the abelian quotient is finite.
The parameters available for the function NilpotentQuotient are:
var NumberOfEngelGenerators: RngIntElt Default: 1 Setting this parameter to k forces the first k generators to be left or right Engel elements, provided one (or both) of the parameters LeftEngel or RightEngel is positive. Otherwise it is ignored.
var LeftEngel: RngIntElt Default: 0 Setting this parameter to n forces the first k generators g1, ..., gk of the quotient Q to be left n-Engel elements. That is, they satisfy [x, ..., x, gi] = 1 (x appearing n times) for all x in Q. The value of k is determined by the parameter NumberOfEngelGenerators.
var RightEngel: RngIntElt Default: 0 This is the same as for LeftEngel, but here the generators are right n-Engel elements, so [gi, x, ..., x] = 1.
var Engel: RngIntElt Default: 0 Setting this parameter to n enforces the nth Engel law on the quotient Q. That is, [x, y, ..., y]=1 (y appearing n times) for all x, y in Q.
var SemigroupOnly: BoolElt Default: true This option causes the program to check only semigroup words in the generating set of the nilpotent quotient when an Engel condition is enforced. If none of the Engel parameters are set, then it is ignored.
var SemigroupFirst: BoolElt Default: false This option causes the program to check semigroup words in the generating set of the quotient first and then all other words, when an Engel condition is enforced. If SemigroupOnly is set, or no Engel condition is enforced, then it is ignored.
var ReverseOrder: BoolElt Default: false In checking Engel identities, instances are processed in order of increasing weight. This flag reverses the order.
var ReverseEngel: BoolElt Default: false This flag changes the Engel conditions from the first k generators, to the last k generators.
var CheckFewInstances: BoolElt Default: false This option stops checking the Engel law at each class if all the checks of a certain weight did not yield any non-trivial instances of the law.
var Nickel: BoolElt Default: false Enforce the identities x8 and [[x1, x2, x3], [x4, x5, x6]] on the nilpotent quotient.
var NumberOfFreeVariables: RngIntElt Default: 0 If this parameter is set to n > 0 then the last n variables of the group are treated as variables rather than generators of the group. In any relation they are treated as standing for all group elements, enabling the user to enforce identical relations on the quotient being computed. The value of n must be less than the number of generators of the input group. When this facility is used, the domain of the epimorphism returned is the subgroup of G generated by the (first) non-free generators.
var PrintResult: BoolElt Default: false If set to true, this parameter switches on the printing of results given by the stand alone version of NQ.
This function returns the class c nilpotent quotient of G as a group in category GrpGPC, together with the epimorphism π from G onto this quotient. When c is set to zero, the function attempts to compute the maximal nilpotent quotient of G. Using the parameters described below, the user can enforce certain conditions on the quotient found.
> G := FPGroup<x,y,z|(x*y*z^-1)^2, (x^-1*y^2*z)^2, (x*y^-2*x^-1)^2 >; > AbelianQuotient(G); Abelian Group isomorphic to Z/2 + Z/2 + Z Defined on 3 generators Relations: 2*$.1 = 0 2*$.2 = 0 > N := NilpotentQuotient(G,2); N; GrpGPC : N of infinite order on 6 PC-generators PC-Relations: N.1^2 = N.3^2 * N.5, N.2^2 = N.4 * N.6, N.4^2 = Id(N), N.5^2 = Id(N), N.6^2 = Id(N), N.2^N.1 = N.2 * N.4, N.3^N.1 = N.3 * N.5, N.3^N.2 = N.3 * N.6
We construct the free nilpotent group N of rank 2 and class 3 as quotient of the free group F of rank 2 and the natural epimorphism from F onto N.
> F<a,b> := FreeGroup(2);
> N<[x]>, pi := NilpotentQuotient(F, 3);
> N;
GrpGPC : N of infinite order on 5 PC-generators
PC-Relations:
x[2]^x[1] = x[2] * x[3],
x[2]^(x[1]^-1) = x[2] * x[3]^-1 * x[4],
x[3]^x[1] = x[3] * x[4],
x[3]^(x[1]^-1) = x[3] * x[4]^-1,
x[3]^x[2] = x[3] * x[5],
x[3]^(x[2]^-1) = x[3] * x[5]^-1
Using the function NilpotencyClass, we check the nilpotency
class of the quotient.
> NilpotencyClass(N); 3
> G<a,b> := FPGroup<a,b|a*b*a^-1=b^4>; > N,f := NilpotentQuotient(G,4); > N; GrpGPC : N of infinite order on 5 PC-generators PC-Relations: N.2^3 = N.3^2 * N.4^2 * N.5, N.3^3 = N.4^2 * N.5^2, N.4^3 = N.5^2, N.5^3 = Id(N), N.2^N.1 = N.2 * N.3, N.2^(N.1^-1) = N.2 * N.3^2 * N.4^2 * N.5, N.3^N.1 = N.3 * N.4, N.3^(N.1^-1) = N.3 * N.4^2 * N.5^2, N.4^N.1 = N.4 * N.5, N.4^(N.1^-1) = N.4 * N.5^2 > for i := 1 to Ngens(N) do > N.i @@ f; > end for; a b (b, a) (b, a, a) (b, a, a, a) > G<a,b> := FPGroup<a,b|a*b^2*a^-1=b^4>; > N,f := NilpotentQuotient(G,4); > N; GrpGPC : N of infinite order on 8 PC-generators PC-Relations: N.2^2 = Id(N), N.3^2 = N.5 * N.8, N.4^2 = N.7, N.5^2 = N.8, N.6^2 = Id(N), N.7^2 = Id(N), N.8^2 = Id(N), N.2^N.1 = N.2 * N.3, N.2^(N.1^-1) = N.2 * N.3 * N.4 * N.5 * N.6, N.3^N.1 = N.3 * N.4, N.3^(N.1^-1) = N.3 * N.4 * N.6 * N.7, N.3^N.2 = N.3 * N.5, N.4^N.1 = N.4 * N.6, N.4^(N.1^-1) = N.4 * N.6, N.4^N.2 = N.4 * N.7, N.5^N.1 = N.5 * N.7, N.5^(N.1^-1) = N.5 * N.7, N.5^N.2 = N.5 * N.8 > for i := 1 to Ngens(N) do > N.i @@ f; > end for; a b (b, a) (b, a, a) (b, a, b) (b, a, a, a) (b, a, b, a) (b, a, b, b)
Turn on and off the printing of information as the nilpotent quotient algorithm proceeds. n may be set to any of 0, 1, 2 or 3. Setting n to be 0 turns printing off, while successively higher values for n print more and more information as the algorithm progresses. The default value of n is 0.
< a, b, c, d, e | (b, a), (c, a), (d, a)=(c, b), (e, a)=(d, b), (e, b)=(d, c), (e, c), (e, d) >.
> F<a,b,c,d,e> := FreeGroup(5); > G<a,b,c,d,e> := > quo<F | (b,a), (c,a), > (d,a)=(c,b), (e,a)=(d,b), (e,b)=(d,c), > (e,c), (e,d)>; > N1<[x]>, pi1 := NilpotentQuotient(G, 0);Using the function NilpotencyClass, we check the nilpotency class of the quotient. It turns out to have nilpotency class 6.
> NilpotencyClass(N1); 6Next we compute a metabelian quotient N2 of G, construct the natural epimorphism from N1 onto N2 and check its kernel. (The functions applied to the nilpotent quotients are described in Chapter POLYCYCLIC GROUPS.) To get a metabelian quotient we adjoin 4 variables and a relation to the presentation of G and use the "free variables" facility.
> M := FPGroup<w,x,y,z|((w,x),(y,z))>; // metabelian identity
> D := FreeProduct(G,M); // adjoin to G
> N2, pi2 := NilpotentQuotient(D, 0: NumberOfFreeVariables := 4);
> NilpotencyClass(N2);
4
> DerivedLength(N2);
2
> f := hom< N1->N2 | [ pi1(G.i)->pi2(D.i) : i in [1..Ngens(G)] ] >;
> PCGenerators(Kernel(f), N1);
{@ x[14], x[15] * x[17], x[16], x[17]^2, x[18], x[19], x[20],
x[21], x[22], x[23], x[24], x[25], x[26], x[27], x[28], x[29],
x[30], x[31] @}
We compute a quotient N3 of G satisfying the 4 th Engel law,
construct the natural epimorphism from N1 onto N3 and again check the
kernel. (The functions applied to the nilpotent quotients are described
in Chapter POLYCYCLIC GROUPS.)
> N3, pi3 := NilpotentQuotient(G, 0 : Engel := 4);
> NilpotencyClass(N3);
4
> DerivedLength(N3);
3
> h := hom< N1->N3 | [ pi1(g)->pi3(g) : g in Generators(G) ] >;
> PCGenerators(Kernel(h), N1);
{@ x[19], x[20], x[21], x[22], x[23], x[24], x[25], x[26], x[27],
x[28], x[29], x[30], x[31] @}
A soluble quotient algorithm computes a consistent power-conjugate presentation of the largest finite soluble quotient of a finitely presented group, subject to certain algorithmic and user supplied restrictions. In this section we describe only the simplest use of such an algorithm within Magma. For more information the user is referred to Subsec. Soluble Quotient Advanced.
Let G be a finitely presented group. The function constructs the largest finite soluble quotient of G.
> G<a,b> := FPGroup< a, b | a^2, b^4,
> a*b^-1*a*b*(a*b*a*b^-1)^5*a*b^2*a*b^-2 >;
> Q := SolubleQuotient(G);
> Q;
GrpPC : Q of order 1920 = 2^7 * 3 * 5
PC-Relations:
Q.1^2 = Q.4,
Q.2^2 = Id(Q),
Q.3^2 = Q.6,
Q.4^2 = Id(Q),
Q.5^2 = Q.7,
Q.6^2 = Id(Q),
Q.7^2 = Id(Q),
Q.8^3 = Id(Q),
Q.9^5 = Id(Q),
Q.2^Q.1 = Q.2 * Q.3,
Q.3^Q.1 = Q.3 * Q.5,
Q.3^Q.2 = Q.3 * Q.6,
Q.4^Q.2 = Q.4 * Q.5 * Q.6 * Q.7,
Q.4^Q.3 = Q.4 * Q.6 * Q.7,
Q.5^Q.1 = Q.5 * Q.6,
Q.5^Q.2 = Q.5 * Q.7,
Q.5^Q.4 = Q.5 * Q.7,
Q.6^Q.1 = Q.6 * Q.7,
Q.8^Q.1 = Q.8^2,
Q.8^Q.2 = Q.8^2,
Q.9^Q.1 = Q.9^3,
Q.9^Q.2 = Q.9^4,
Q.9^Q.4 = Q.9^4
Find a soluble quotient G and the epimorphism π:F mapsur G with a specified order. n must be a nonnegative integer. P must be a set of primes.The three forms reflect possible information about the order of an expected soluble quotient. In the first form the order of G is given by n, if n is greater than zero. If n equals zero, nothing about the order is known and the relevant primes will be calculated completely.
The second form, with no n argument, is equivalent to the first with n = 0. This is a standard argument, and usually it is the most efficient way to calculate soluble quotients.
Note that, if n>0 is not the order of the maximal finite soluble quotient, it may happen that no group of order n can be found, since an epimorphic image of size n may not be exhibited by the chosen series.
In the third form a set P of relevant primes is given. The algorithm calculates the biggest quotient such that the order has prime divisors only in P. P may have a zero as element, this is just for consistency reasons. It is equivalent to the first form with n equal zero.
For a description of the algorithm used and of the set of parameters available for this function, see Subsec. Soluble Quotient Advanced. Other more specialised functions for computing soluble quotients and some examples can be found there as well.
> G<x, y> := FPGroup< x, y | > x^3, y^8, (x,y^4), x^-1*y*x^-1*y^-1*x*y*x*y^-1, > (x*y^-2)^2*(x^-1*y^-2)^2*(x*y^2)^2*(x^-1*y^2)^2, > (x^-1*y^-2)^6*(x^-1*y^2)^6 >;We apply the soluble quotient algorithm to G and compute the order of the soluble quotient Q.
> time Q := SolubleQuotient(G); Time: 116.920 > Order(Q); 165888Note that 165888 = 211 .34. If we knew the possible primes in advance the soluble quotient can be computed much more quickly by using this knowledge.
> time Q := SolubleQuotient(G, {2, 3});
Time: 39.400
Note that this reduces the execution time by a factor of almost three.
We now assume that G is finite and try to compute its order by means of the Todd-Coxeter algorithm.
> Order(G); 165888Hence the group is finite and soluble and G is isomorphic to Q. We may use the tools for finite soluble groups to investigate the structure of G. For example we can easily find the number of involutions in G.
> cls := ConjugacyClasses(Q); > &+ [ cl[2] : cl in cls | cl[1] eq 2 ]; 511
This section presents a short overview towards the theory of the soluble quotient algorithm, the functions designed for computing soluble quotients and the functions designed for dealing with soluble quotient processes.
For a finite group G, the property of being soluble means that the derived series G = G(0) > G(1) > ... > G(n) terminates with G(n) = < 1 >. Each section G(i)/G(i + 1) is a finite abelian group, hence it can be identified with a Z G/G(i)-module M, where the action of G/G(i) on M is given by the conjugation action on G(i)/G(i + 1).
From module theory we see that there exists a series M = M(0) > M(1) > ... > M(ri), where each section is an irreducible GF(p) G/G((i))-module for some prime p. Using these series we obtain a refinement G = G(0) > G(1) > ... > G(n) = < 1 > of the commutator series with the properties:
The soluble quotient algorithm uses these series to construct soluble groups. Starting with the trivial group G/G(0), it successively chooses irreducible G/G(i) modules Mi and extensions ζi ∈H2(G/G(i), Mi) which give rise to exact sequences 1 -> Mi -> G/G(i + 1)=G/G(i).Mi -> G/G(i) -> 1. To describe the algorithmic approach, we consider the following situation. Let G be a finite soluble group, M a normal elementary abelian subgroup of G such that M is a H=G/M irreducible module. (The action of H on M is identified with the conjugation action of G/M on the subgroup M.) Then the relations of the group G have the shape gipi=wimi (resp.) gjgi=wijmij, mi, mij∈M where wi, wij are the canonical representatives of H in G. Then bar(gipi)=bar(wi) resp. bar(gj)^(bar(gi)) =bar(wij) is a PC-presentation of H and the set of images ((gipi - 1, gi) -> mi, (gj, gi) |-> mij) determines a unique element of the cocycle space C2(H, M).
According to the p-group situation, we call the system t= (mi, mij), the tail defining G = H.Mt as an extension of M by H.
Not every choice of a system t = (mi, mij) defines an extension. To make sure that t corresponds to an element s of C2(G, M) it must satisfy a certain equation system, the so-called consistency equations (see Vaughan-Lee). These are linear homogeneous equations in M, so the solution space can be determined.
For the construction of soluble quotients we also have to find the epimorphism ε: F mapsur G. The existence of the epimorphism is obviously a restriction of the possible images G, and it can be checked simultaneously with constructing G. Let G be an extension G = H.M, where M is a H-module and H is a known soluble quotient δ: F mapsur H. Then δ is uniquely determined by the images δ(fi)=hi, 1≤i ≤r, where {f1, ..., fr} is a generating set of F. We want to find a lift ε of δ, i.e. ε (f)=δ(f) (mod) M for all f ∈F. This means that ε(fi)=hi xi for all i≤r, where xi ∈M are to be determined. Since ε will be a homomorphism, we require ε(rj(f1, ..., fr))=1G for the defining relations rj of F. This leads to a linear equation system for the variables (x1, ..., xr)∈Mr. We solve this equation system together with the consistency equations, hence we find a subspace S of Mr x H2(H, M) of those extensions for which the epimorphism δ has a lift. Let us call an element of S an extended tail.
Let K be the minimal splitting field of M, i.e. the character field of the unique character of H which corresponds to M. Then M is obviously a KH-module and S is also a K-space. The space S has a K-subspace SS of split extensions, i.e. the projection of SS into H2(H, M) is only the trivial element. For any element t ∈S/SS the corresponding map εt: F -> H.Mt is necessarily surjective, hence defines a soluble quotient. Let s1, s2 be two elements of S/SS and let εi: F mapsur H.Msi =: Gi denote the corresponding soluble quotients. If s1 and s2 are K-linear dependent, the groups G1 and G2 will be isomorphic. Unfortunately, the converse is not true, even K-linear independent elements may lead to isomorphic groups. Nevertheless, if s1 and s2 are independent, the kernels of the epimorphisms will be different, hence one can iterate the lifting to ε1, 2: F mapsur (G1).Ms2 = (H.Ms1).Ms2 = H.(M direct-sum M)s1.s2. (The last equality can be read as a definition of s1.s2 in the righthand side term.)
The dimension a=dimK(S/SS) is therefore characterised as the maximal multiplicity a = max {z ∈Z^ + | exists ε:F mapsur H, Mz }. SS itself also has a K-subspace SC, for which the map εs: F -> H.Ms, s∈SC is not surjective. The K-dimension b=dimK(SS/SC) is again characterised as the maximal multiplicity b=max{z∈Z^ + | existsε:F mapsur H, Mz }. Moreover, after taking a maximal extension ε:F mapsur H.Mb, M never has to be considered for split extensions again.
A crucial step in finding finite soluble quotients ε: F mapsur G is the calculation of the relevant primes, i.e. the prime divisors of |G|. This is the most time consuming part of the algorithm, so it is crucial to apply it as efficiently as possible, and any other information about possible prime divisors is very helpful. We do not explain this calculation in detail. However, to use the functions and options provided by Magma in a correct manner, we outline the idea of the calculation.
Let ε:F mapsur G be a finite soluble quotient and let N denote the kernel of ε. If a module M allows an extension bar(ε):F mapsur G.M, then M must be a constituent of N/Nprime, and the relevant primes are the prime divisors of N/Nprime. Again N/Nprime can be viewed as an F/N- module, hence an H-module. Therefore it is a direct sum N/Nprime isomorphic to Mp1 direct-sum Mp2 direct-sum ... direct-sum Zd, where the Mpi are finite modules of order a power of the prime pi. Let p not divide |H|. Then by Zassenhaus the extension H.Mp must split. We consider an irreducible module M in the head of Mp, i.e. there is an H-epimorphism Mp mapsur M. Then there is a valid soluble quotient ε: F mapsur H.M and the extension H.M splits.
Now there exists an irreducible Z H- module L such that M is a GF(p)-modular constituent of L/pL. Moreover, Δ: H -> GL(L) is the corresponding representation of H and any Δ-module will have this property.
Now using the theory of space groups, one can construct homomorphisms ε1: F mapsur H.L and ε2: H.L mapsur H.M such that the composition is surjective. Hence p can be detected in Δ. Let PΔ denote the set of primes obtained from Δ. To find these primes, we have to know a set D of representatives of the irreducible rational representations of F/N, hence of H. The set of prime divisors of K/Kprime is a subset of P= bigcupΔ ∈D PΔ ∪{p | p (prime ), p | |G|}. We want to point out the following:
Magma provides two different ways to calculate finite soluble quotients: a main function for the whole calculation, and a process which gives control over each individual step.
Let F be a finitely presented group.
Find a soluble quotient ε:F mapsur G with a specified order. The argument n must be a nonnegative integer and P must be a set of primes.The three forms reflect possible information about the order of an expected soluble quotient. In the first form the order of G is given by n, if n is greater than zero. If n equals zero, nothing about the order is known and the relevant primes will be calculated completely.
The second form, with no n argument, is equivalent to the first with n = 0. This is a standard argument, and usually it is the most efficient way to calculate soluble quotients.
Note that, if n>0 is not the order of the maximal finite soluble quotient, it may happen that no group of order n can be found, since an epimorphic image of size n may not be exhibited by the chosen series.
In the third form a set P of relevant primes is given. The algorithm calculates the biggest quotient such that the order has prime divisors only in P. The set P may have a zero as an element, this is just for consistency reasons. It is equivalent to the first form with n equal zero.
The returned values are the group G and the epimorphism ε: F mapsur G. The third returned value is a sequence describing the series and modules by which G has been constructed.
The fourth value is a string which explain the reason for termination. The following list gives the termination conditions. The algorithm terminates normally if:
The algorithm will be aborted and returns a warning if:
- 1.
- A quotient of the given order has been constructed.
- 2.
- A maximal quotient (with respect to the conditions given on the order) has been constructed.
With the following options one can define abort conditions corresponding to the third and fourth item. The idea of all these conditions is to control the occurrence of infinite soluble quotients.
- 3.
- A bound on the length of a series or subseries has been hit.
- 4.
- A limit on the size of the quotient or a section has been hit.
- 5.
- The algorithm detects a free abelian section.
SeriesLength: RngIntElt Default: 0Limits the length of the chief series to r. For sag-series it is the nilpotent length of the series, for derived series it is the derived length. The default value of zero means no limit.If the algorithm hits the limit, it gives a warning message and returns the last soluble quotient.
SubseriesLength: RngIntElt Default: 0Limits the length of a series in a section. If the sag-series is used, it is the length of the lower descending series. For the derived series, the limit is applied to the exponent of an element of a section with maximal prime power order. For example, if the limit is set to 3, the limit would be hit by a section of type C8, but not by C23 and not even by C42.vapour QuotientSize: RngIntElt Default: 0If the value n is bigger than zero, the algorithm returns if a quotient of order bigger or equal to n has been found. A warning message will be printed.vapour SectionSize: RngIntElt Default: 0If the value s is bigger than zero, the algorithm returns if the order of a section is bigger than or equal to s. A warning message will be printed.Note: Since an additive bound on a group order is not as meaningful as a multiplicative bound, the latter options are only useful as break conditions when the quotient gets too big for further calculations. The return quotient which hits such a bound is somewhat randomly chosen, since only a change in the order of checking modules may lead to other quotients.
With the following options the strategy of the algorithm and some subalgorithms can be chosen.
vapour MSQ_Series: MonStgElt Default: "sag"Determines the series which is used for the construction of soluble groups.The default value is "sag", since it is usually the most efficient choice. Of course, there is a value "derived", exhibiting the derived series.
Another choice is "lowercentral", choosing the lower central series. This restricts the algorithm to finite nilpotent quotients. The choice "pcentral" only exhibits p-groups as quotients.
The nilpotent resp. p-quotient algorithms are usually more efficient, so these options may only be useful to obtain additional information needed for a SQ-process.
MSQ_PrimeSearchModus: RngIntElt Default: 3Defines at what status of the algorithm the relevant prime search is called.The possible choices reflect the different intentions of constructing a soluble quotient; for the general situation, (i.e. finding a finite soluble quotient without any information about relevant primes and check its maximality) this option makes only little difference in runtime behaviour.
- 0:
- No calculation of relevant primes. This is the default value, if the second argument does not request a prime calculation, e.g. if the order of the quotient or its relevant primes are known.
- 1:
- The relevant primes will be calculated after the soluble quotient algorithm (with the given input) terminates normally. Possibly new relevant primes are returned in a message. If, for example, the second argument is a set S (so no limit on the exponent) and no new relevant primes have been found, the maximality of the soluble quotient is proved.
- 2:
- As 1, but continues the algorithm when finding new relevant primes.
- 3:
- Perform the relevant prime calculation after a "main" step in the series, i.e. after completing a nilpotent section in a sag-series resp. a commutator section for the derived series. This is the default value, if prime calculation is required by the second argument. It is a good choice if one wants to construct large finite quotients quickly.
- Note: This option can cause problems in case of a sag-series when infinite soluble quotients exist. For finite quotients, it seems to be the best choice.
- 4:
- Perform the relevant prime calculation after calculating an elementary abelian layer. This option is preferable, if the sag-series is used and an infinite soluble quotient is possible.
- 5:
- Perform the relevant prime calculation after each successful lift of a quotient. This option is preferable when infinite sections shall be detected as soon as possible (with respect to the chosen series).
MSQ_ModulCalcModus: RngIntElt Default: 0In the construction of soluble quotients using a sag-series one can restrict the number of modules by using tensor products and skew symmetric products. This can improve the performance in the case of big soluble quotients, for small quotients the overhead may invalidate the improvement. For other series this option has no meaning. The possible values are:
- 0:
- Do not apply this technique (default).
- 1:
- Fast version, just apply those parts which can be calculated quickly.
- 2:
- Full version, this is only recommended for "big" soluble quotients, i.e. quotients with long descending series in nilpotent sections.
MSQ_CollectorModus: RngIntElt Default: 2Defines the setup modus for the symbolic collector, i.e. the ratio of precalculation to dynamic setup:The function also provides a general print option determining the amount of timings status information during the function call. Additionally there are some verbose flags which determine the amount of information given about various subalgorithms. If both a general print value and a verbose flag are given, the verbose flag has higher preference.
- 0:
- Full precalculation, preferable for small soluble groups.
- 1:
- Partial precalculation (test version).
- 2:
- Dynamic setup (default).
Print: RngIntElt Default: 0Determines what timing information and status messages are given during the calculation (0 = no printing, 5 = maximal information).SetVerbose("MSQ_Messages", n): Maximum: 2If set to 1, the sizes of new soluble quotients are printed.SetVerbose("MSQ_PrimeSearch", n): Maximum: 15Bitflag for print levels during the calculation of relevant primes:
- 1:
- Timings and statistics about the calculation of rational representations.
- 2:
- Timings for transforming rational into integral representations.
- 4:
- Timing for finding the relevant primes.
- 8:
- Printing of new relevant primes.
SetVerbose("MSQ_RepsCheck", n): Maximum: 3
- 1:
- Timing for checking extensions of modules.
- 2:
- Statistics about the modules to be checked.
SetVerbose("MSQ_RepsCalc", n): Maximum: 3
- 1:
- Timing information about the module calculation.
- 2:
- Statistics about the module calculation.
SetVerbose("MSQ_Collector", n): Maximum: 1If set to 1, the timing for the setup of the symbolic collector is printed.SetVerbose("MSQ_TraceFunc", n): Maximum: 2Give messages about the main function calls (1) resp. most function calls (2) in the Magma language during the algorithm.
We describe intrinsics for finding homomorphisms of an fp-group G onto simple groups. This may be useful when the presentation for G defines a perfect group. The algorithm maintains a list of simple groups to try and the function Homomorphisms is used to run through the list looking for a homomorphism onto G.
The list of simple groups supplied in versions beginning with V2.25 contain all non-abelian simple groups with order ≤1010. 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.
Family: Any Default: "All"
Limit: RngIntElt Default: 1
HomLimit: RngIntElt Default: 0
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. If the degree arguments are not present then bounds of 5 and 107 are used. 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 a quick search is wanted.) If ord1 is not given then it defaults to 1.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 HomLimit limits the number of homomorphisms that will be searched for by any particular call to Homomorphisms. It defaults to zero, so that all homomorphisms for any group found will be returned.
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"; sets of these strings are also allowed, which searches on the union of the appropriate 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 := FPGroup<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) and 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.
Given an fp-group G, the L2-quotient algorithm of Plesken, Fabianska and Jambor computes all quotients of G which are isomorphic to the 2-dimensional linear groups PSL(2, q) or PGL(2, q) simultaneously for any prime power q. The algorithm can handle the case of infinitely many quotients, and also works for very large prime powers. In practice it is fast when the number of generators is small and can be used to show that many fp-groups are infinite. While the simple groups PSL(2, q) represent just one dimension in one family out of 16 families of simple groups, in a given range of orders, they are very numerous compared to other simple groups. See [Jam12] or [Jam15] for more information about the L2-quotient algorithm.
Note that the algorithm does not return images onto the groups (PSL)(2, 2), (PSL)(2, 3), and (PSL)(2, 4) = (PSL)(2, 5).
This is the main method. It takes as parameter a finitely presented group and returns a sequence of (L)2-quotients, which have type L2Quotient.
> G := FPGroup< a,b | a^2, b^3, (a*b)^7, (a,b)^11 >;
> L2Quotients(G);
[
L_2(43)
]
> H := FPGroup< a,b,c | a^3, b^7, c^19, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;
> L2Quotients(H);
[
L_2(113)
]
This means that G has PSL(2, 43) as quotient, but no other PSL(2, q)
or PGL(2, q) is a quotient of G. Similarly, the only L2-quotient
of H is PSL(2, 113).
The next example has more quotients:
> G := FPGroup< a,b | a^2, b^3, (a*b)^16, (a,b)^11 >;
> L2Quotients(G);
[
PGL(2,23),
PGL(2,23),
PGL(2,463)
]
Here PGL(2, 23) occurs twice. This means that there are two epimorphisms
of G onto PGL(2, 23) which do not differ by an automorphism of
PGL(2, 23). In other words, the kernels of the epimorphisms are distinct.
Some groups have infinitely many L2-quotients. This is indicated by one of the L2-quotients L_2(infty^k), L_2(p^(infty^d)), or L_2(infty^(infty^d)), as the follow examples illustrate.
> G := FPGroup< a,b,c | a^3, b^7, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;
> L2Quotients(G);
[
L_2(infty^6)
]
> H := FPGroup< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b,
> a*b*a*c^-1 = c*a*b*a >;
> L2Quotients(H);
[
L_2(3^infty)
]
> K := FPGroup< a,b | a^3*b^3 >;
> L2Quotients(K);
[
L_2(infty^infty)
]
See below for an interpretation of this output, and for instructions as how to use
Magma to get more information about the quotients.
For a finite L2-quotient Q of G, that is, a quotient L2(pk) or PGL(2, pk), this function returns a matrix group H and a sequence A of 2 x 2 matrices in H, where A[i] corresponds to the i-th generator of G.Note that G -> H, G.i -> A[i] does not in general define a homomorphism, but the induced map G -> H/Z(H) does.
> H := FPGroup< a,b,c | a^3, b^7, c^19, (a*b)^2, (a*c)^2, (b*c)^2, (a*b*c)^2 >;
> quot := L2Quotients(H); quot;
[
L_2(113)
]
> H, A := GetMatrices(quot[1]);
> H;
MatrixGroup(2, GF(113))
Generators:
[ 0 1]
[112 112]
[ 0 85]
[109 24]
[102 104]
[ 63 72]
> A;
[
[ 0 1]
[112 112],
[ 0 85]
[109 24],
[102 104]
[ 63 72]
]
> Gamma< x, y > := FPGroup< x, y | x^2, y^3 >;
> u := x*y; v := x*y^-1;
> G := quo< Gamma | u^10*v^2*u*v*u*v^2 >;
> quot := L2Quotients(G); quot;
[
L_2(5^2)
]
> H, A := GetMatrices(quot[1]);
> H;
MatrixGroup(2, GF(5^2))
Generators:
[ 2 4*$.1 + 2]
[ 0 3]
[0 4]
[1 4]
There are other quotients of the modular group with only finitely many (L)2 quotients:
> G := quo< Gamma | u^3*v*u^3*v*u^3*v^2*u*v^2 >;
> quot := L2Quotients(G);
> quot;
[
PGL(2,13)
]
> G := quo< Gamma | u^3*v*u^3*v^2*u*v^3*u*v^2 >;
> quot := L2Quotients(G);
> quot;
[]
This tells us that the first group has only one (L)2 quotient,
isomorphic to (PGL)(2, 13), and the second
group has no (L)2 quotients at all.
(l, m | n, k) = < x, y | xl, ym, (xy)n, (x - 1y)k >
and
(l, m, n; q) = < x, y | xl, ym, (xy)n, [x, y]k >
for various values of l, m, n, k, q.
> G := FPGroup< x,y | x^8, y^9, (x*y)^5, (x^-1*y)^7 >;
> quot := L2Quotients(G);
> quot;
[
L_2(71),
L_2(71),
L_2(71),
L_2(2521),
L_2(41),
L_2(3056201),
L_2(239),
L_2(449),
L_2(3876207679),
L_2(1009),
L_2(29113631)
]
The group (PSL)(2, 71) occurs three times. This means that there are three essentially different epimorphisms of G onto (PSL)(2, 71), i.e., there is no automorphism of (PSL)(2, 71) which transforms one epimorphism into another.
Here is another example, this time for the other family.
> G := FPGroup< x, y | x^4, y^3, (x*y)^5, (x,y)^6 >;
> L2Quotients(G);
[
L_2(79),
L_2(3^2),
L_2(5^2)
]
There are three groups in the second family for which it is not known whether they are finite or infinite (Havas & Holt (2010) [HH10]). They are (3, 4, 9; 2), (3, 4, 11; 2), and (3, 5, 6; 2). Each of them has only one (L)2 image.
> G := FPGroup< x, y | x^3, y^4, (x*y)^9, (x,y)^2 >;
> L2Quotients(G);
[
L_2(89)
]
> G := FPGroup< x, y | x^3, y^4, (x*y)^11, (x,y)^2 >;
> L2Quotients(G);
[
L_2(769)
]
> G := FPGroup< x, y | x^3, y^5, (x*y)^6, (x,y)^2 >;
> L2Quotients(G);
[
L_2(61)
]
var ExactOrders: SeqEnum Default: [] Even if the finitely presented group in question is not a Coxeter group, we often are only interested in quotients where certain orders are satisfied (for instance, we might know that the generator must have a certain order). Usually this yields a great speed-up in the computation, or even allows the computation to finish in the first place. The orders can be specified using the optional parameter exactOrders. This is a list of pairs, where the first entry is a word in the group, and the second entry is the order.
A Coxeter group is a finitely presented group on m generators, such that the only other relations are (gigj)Mij, where M is a symmetric matrix with non-negative integer entries and 1's along the diagonal. The matrix M is also called a Coxeter matrix. Often when dealing with Coxeter groups we are only interested in smooth quotients, that is, those which preserve the orders. The method L2Quotients accepts a Coxeter matrix as input, and computes the smooth quotients of the associated Coxeter group. However, it omits the quotients in characteristic p if M12 = p. Furthermore, if a quotient has characteristic p and p divides some entry of M, then the quotient is not guaranteed to be smooth.
> M := Matrix([[1,2,3,3],[2,1,4,5],[3,4,1,6],[3,5,6,1]]);
> L2Quotients(M);
[
L_2(4391),
L_2(71)
]
> G< a,b,c > := FPGroup< a,b,c | a^16, b^4, c^2, (a*b)^8, (a,b)^4 >; > time quot := L2Quotients(G : ExactOrders := [< a, 16 >, < b, 4 >, > < c, 2 >, < a*b ,8 >, < (a,b), 4 >]); Time: 1.530
var Saturate: Boolean Default: false The algorithm discards prime ideals containing ρ = x12 + x22 + x122 - x1x2x12 - 4. If the optional boolean parameter Saturate is true, then prior to the primary decomposition the ideal is saturated at ρ, which can be faster in some cases.
var AddMoreRelations: Boolean Default: false If the optional boolean parameter AddMoreRelations is true, then the algorithm adds further relations to the ideal, which speeds up the computation in some cases.
var Primes: SeqEnum Default: [] Given a sequence P of primes, this variant only produces quotients Q in characteristic p only, where p must lie in P.
var ExcludePrimes: SeqEnum Default: [] The optional parameter ExcludePrimes is a sequence of primes. The algorithm does not compute (L)2-quotients in characteristic p if p is in exclude.
var SingleInfinite: Boolean Default: false With this option, the function returns immediately when an infinite family of quotients is found and this family is returned. This is useful when attempting to prove an FP group infinite, since only one infinite family is needed to prove the group infinite.
var UseRandomTechniques: Boolean Default: var FactorizationBound: RngIntElt Default: var TrialDivisionBound: RngIntElt Default: var GroebnerBasisBound: RngIntElt Default: These parameters are passed to the method MinimalAssociatedPrimes (see documentation there).
Quotients of type (L)2(∞k)
If G has a quotient (L)2(∞k), then for almost all (all but finitely many) primes p, G has finitely many quotients of type (PSL)(2, pr) or (PGL)(2, pr/2) with r ≤k. So (L)2(∞k) is a mnemonic, where ∞ in the base stands for infinitely many primes, and k stands for the highest possible exponent.
There are two basic methods to further investigate such quotients.
Quotients of type (L)2(p∞d)
If G has a quotient (L)2(p∞d), then there are infinitely many positive integers k such that G has a quotient of type (PSL)(2, pk) or (PGL)(2, pk). So (L)2(p∞d) is a mnemonic, where ∞ in the exponent stands for infinitely many possible exponents. The parameter d describes the degree of infinity, and is omitted if d = 1.
Again, we can use AddGroupRelations to sudy this quotient further.
Quotients of type (L)2(∞∞d)
If G has a quotient (L)2(∞∞d), then for almost all primes p and infinitely many positive integers k, G has a quotient of type (PSL)(2, pk) or (PGL)(2, pk). So (L)2(∞∞d) is a mnemonic, where ∞ in the base stands for infinitely many primes, and ∞ in the exponent stands for infinitely many possible exponents. The parameter d describes the degree of infinity, and is omitted if d = 1. These quotients can be further investigated using the methods AddGroupRelations, AddRingRelations, and SpecifyCharacteristic.
Compute the (L)2-quotients in characteristic p | n.
> G := FPGroup< a,b | a^2, b^3, (a*b)^7 >;
> quot := L2Quotients(G); quot;
[
L_2(infty^3)
]
> Q := quot[1];
> SpecifyCharacteristic(Q, 7);
[
L_2(7)
]
> SpecifyCharacteristic(Q, 11);
[
L_2(11^3)
]
> SpecifyCharacteristic(Q, 13);
[
L_2(13),
L_2(13),
L_2(13)
]
Compute the (L)2-quotients which satisfy the additional relations R.
> G<a,b> := FPGroup< a,b | a^2, b^3, (a*b)^7 >;
> quot := L2Quotients(G); quot;
[
L_2(infty^3)
]
> Q := quot[1];
> AddGroupRelations(Q, [(a*b*a*b^-1*a*b)^12]);
[
L_2(13),
L_2(7)
]
> H< a,b,c > := FPGroup< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b,
> a*b*a*c^-1 = c*a*b*a >;
> quot := L2Quotients(H); quot;
[
L_2(3^infty)
]
> Q := quot[1];
> AddGroupRelations(Q, [((b^2*c^3)^2*a)^5]);
[
L_2(3^2),
L_2(3^4)
]
Compute the (L)2-quotients whose traces satisfy the polynomial relations given in R.
> H< a,b,c > := FPGroup< a,b,c | a^3, (a,c) = (c,a^-1), a*b*a = b*a*b,
> a*b*a*c^-1 = c*a*b*a >;
> quot := L2Quotients(H); quot;
[
L_2(3^infty)
]
> Q := quot[1];
> Q`Ideal;
Ideal of Graded Polynomial ring of rank 7 over Integer Ring
Order: Grevlex with weights [3, 2, 2, 2, 1, 1, 1]
Variables: x123, x23, x13, x12, x3, x2, x1
Variable weights: [3, 2, 2, 2, 1, 1, 1]
Inhomogeneous, Dimension >0
Groebner basis:
[
x123^2 + 2*x123*x3 + 1,
x23 + 2*x3,
x13 + 2*x3,
x12 + 2,
x2 + 1,
x1 + 1,
3
]
> R< x123, x23, x13, x12, x3, x2, x1 > := Generic(Q`Ideal);
> AddRingRelations(Q, [x3^(3^4) - x3]);
[
L_2(3^2),
L_2(3^4),
L_2(3^4),
L_2(3^4),
L_2(3^4),
L_2(3^4),
L_2(3^4),
PGL(2,3^2),
PGL(2,3^2),
L_2(3^4),
L_2(3^8),
L_2(3^8),
L_2(3^8),
L_2(3^8),
L_2(3^8),
L_2(3^4)
]
This section contains functions that use the L2-quotient algorithm of Plesken and Fabianska ([PF09]) to establish the existence or not of an infinite quotient of a finitely-presented group in PSL2(K) for K a field of characteristic zero. The algorithm is often used to find surjective quotients over finite fields but as a test for non-finiteness it is easier to work directly in characteristic zero. We make some comments on the relation to finite fields below.
The algorithm first constructs an affine scheme X over Q from the "trace ideal" of the group G, for which the algebraic points over a field K are in 1-1 correspondence with equivalence classes of representations of G into SL2(K). If g1, ..., gn are the generators of G, then the affine coordinates of X correspond to the trace under the representation of various products of the Gi. For example, when n=2, X lies in 3-dimensional affine space and the coordinates correspond to the traces of g1, g2 and g1g2. The ideal is actually generated by polynomials with coefficients in Z so X is naturally defined as a scheme over Spec(Z), whose reduction mod p just gives the scheme corresponding to characteristic p representations of G for p > 2.
Homomorphisms into PSL2 rather than SL2 are dealt with by considering a number of X schemes for a particular G. Each one represents the homomorphisms from the free cover of G to SL2 that takes each word in the set of relations defining G to either I or -I. Each of the 2r choices of sign for the r defining relations gives an X (by the same procedure) and the totality cover all possibilities for maps to PSL2.
The set of points of X corresponding to geometrically reducible, dihedral A4, S4 or A5 images in PSL2 is a closed subscheme Y. In fact the first two possibilities give closed subschemes with equations defined over Z and the last three give a dimension zero scheme over Q. The overall equations defining Y reduce mod p to those defining the corresponding subscheme in characteristic p for almost all primes p. The explicit equations defining Y are determined by the algorithm as explained for n = 2 or 3 in the above reference or in more detail in Fabianska's MSc thesis ([Fab09]). Let U be the open complement of Y in X.
There are two possibilities.
Signs: SeqEnum Default: 0
Full: BoolElt Default: false
SetVerbose("IsInfGrp", n): Maximum: 1
Function to return whether the two-generator finitely-presented group G has an infinite quotient lying in a PSL2(K) with K a field of characteristic 0 as described above.For the convenience of the user, we have provided some parameters to output more detailed information coming from the analysis of the X representation schemes as well as to control which sign variations are considered.
Let ws be the sequence of words giving the defining relations of G (if a defining relation is of the form w = v where v is not the identity word, then the corresponding word is w * v - 1). Let ws = [w1, .., wr].
As described in the introduction, for each of the 2r combinations of signs attached to the wi - let s be one - the program will consider the scheme X of homomorphisms of G into PSL2 such that, when lifted to a homomorphism of the two-generator free cover F of G into SL2, wi maps to si * I.
In some cases, the user may realise that there is no point in considering certain choices of signs. For example, if g12 is a relation in ws, g12 |-> I in SL2(K) means that g1 |-> 1 in PSL2(K), so the PSL2(K) image would be (maybe infinitely) cyclic, and it is a waste of time to consider this possibility. Similarly, if g1r, r odd, is a relation then ,without loss of generality, in a PSL2 to SL2 lift, g1r |-> I, which could be specified.
The parameter Signs allows the user to specify a restricted set of sign options to analyse. Signs should be an 0, 1, - 1 or a sequence of length #ws of such integers. A single value is converted into the sequence containing that value #ws times. An entry e of 1 or -1 in position i means that the function will only consider sign sequences s with s[i] = e, ie homomorphisms where wi map to eI in the lift to SL2. If e = 0, then there is no condition at place i of the sign sequences considered. The default value for Signs is the single value 0.
For each representation space X (corresponding to an allowable choice of signs s), after removing positive dimensional components of Y corresponding to geometrically reducible or dihedral type representations, there is often a zero-dimensional subscheme left. The existence of an infinite (non-cyclic or dihedral) image homomorphism to PSL2 then comes down to examining the finite set of closed points remaining and finding one that is not geometrically reducible, dihedral, A4, S4 or A5 type. Clearly, once one such is found the procedure can stop. However, it might be of interest for the user to see the types of ALL of the representations corresponding to closed points if the zero-dimensional analysis stage is performed.
If parameter Full is set to true (the default is false), the program will continue analysing all of the representations in the 0-dimensional locus, even after one corresponding to an infinite image is found. Furthermore a sequence of (signs,types) pairs is also returned which gives, for each sign combination s of maps considered, the sequence of types corresponding to the 0-dimensional locus (or empty if we don't reduce to dimension 0). These types are given as strings: "infinite", "reducible", "dihedral", "A4", "S4", and "A5".
Setting the verbose flag IsInfGrp to true or 1 gives output of information on the various stages as the function progresses, including the analysis of dimension zero loci.
> F := FreeGroup(2);
> rel := (F.1 * F.2 * F.1 * F.2 * F.1 * F.2 * F.1 * F.2 * F.1 * F.2 *
> F.1 * F.2 * F.1 * F.2 * F.1 * F.2^-1 * F.1 * F.2 * F.1 * F.2^-1)^2;
> G := quo<F | [F.1^2 ,F.2^3, rel]>;
> HasInfinitePSL2Quotient(G : Full := true);
true
[ [*
[ 1, 1, 1 ],
[]
*], [*
[ 1, 1, -1 ],
[]
*], [*
[ 1, -1, 1 ],
[]
*], [*
[ 1, -1, -1 ],
[]
*], [*
[ -1, 1, 1 ],
[ A4, A4 ]
*], [*
[ -1, 1, -1 ],
[ A5, A5, infinite ]
*], [*
[ -1, -1, 1 ],
[ A4, A4 ]
*], [*
[ -1, -1, -1 ],
[ A5, A5, infinite ]
*] ]
Now try it with the sign restriction.
> HasInfinitePSL2Quotient(G : Full := true, Signs := [-1,1,0]);
true
[ [*
[ -1, 1, 1 ],
[ A4, A4 ]
*], [*
[ -1, 1, -1 ],
[ A5, A5, infinite ]
*] ]
The second example is just A5.
> G := quo<F | [F.1^2 ,F.2^3, (F.1*F.2)^5]>;
> HasInfinitePSL2Quotient(G);
false
> HasInfinitePSL2Quotient(G : Full := true, Signs := [-1,1,0]);
false
[ [*
[ -1, 1, 1 ],
[ A5 ]
*], [*
[ -1, 1, -1 ],
[ A5 ]
*] ]
Given a finitely presented group G on two generators, the (L)3(U)3-quotient algorithm of Jambor [Jam12] computes all quotients of G which are isomorphic to some (PSL)(3, q), (PGL)(3, q), (PSU)(3, q), or (PGU)(3, q), simultaneously for all prime powers q. It can handle the case of infinitely many quotients, and also works for very large prime powers.
Note that the algorithm does not return images onto groups (PSL)(3, 2) = (PSL)(2, 7).
Given a group G with 2 generators, this function returns a sequence of (L)3-quotients, which have type L3Quotient.ExactOrders: SeqEnum Default: []Given a sequence of pairs < w, n > where w is a word in the generators of G and n is a positive integer, this returns only those quotients Q for which the order of the image of w in Q is n.ExcludePrimes: SeqEnum Default: []Given a sequence P of primes, this variant only produces quotients Q in characteristic p, where p does not lie in P.
Compute the restrictions of the given quotient object Q to the prime characteristic p.
Compute quotient objects from Q for the group of Q with relators r added.
Compute the matrix images of the generators of the group of the quotient object Q as a matrix group. Requires Q to be a finite object. Note that G.i to M.i, where M is the matrix group returned, does not always define a homomorphism, but the induced map into M/Z(M) is a homomorphism.
> G := FPGroup< a,b | a^2, b^3, (a*b)^11, (a,b)^11 >;
> L3Quotients(G);
[
U_3(43)
]
> H := FPGroup< a,b | a^2, b^3, (a*b)^11, (a,b)^28 >;
> Q := L3Quotients(H); Q;
[
U_3(43),
U_3(14057)
]
This means that G has PSU(3, 43) as quotient, but no other PSL(3, q),
PGL(3, q), PSU(3, q) or PGU(3, q) is a quotient of G.
Similarly, the only (L)3(U)3-quotients of H are
PSU(3, 43) and PSU(3, 14057).
We can further investigate finite quotients using GetMatrices.
> M := GetMatrices(Q[1]); M; MatrixGroup(3, GF(43^2)) Generators: [ $.1^756 $.1^202 38] [ $.1^960 $.1^1243 $.1^934] [ $.1^192 $.1^192 $.1^1529] [ $.1^379 $.1^1759 $.1^503] [$.1^1326 $.1^804 $.1^374] [$.1^1214 $.1^524 $.1^612]The next example has more quotients:
> G := FPGroup< a,b | a^2, b^3, (a*b)^18, (a,b)^16 >;
> L3Quotients(G);
[
PGU(3, 71),
U_3(1889),
PGU(3, 17),
PGU(3, 17),
PGU(3, 17),
PGL(3, 19)
]
In this example, PGU(3, 17) occurs three times.
This means that there are three epimorphisms of G onto PGU(3, 17) which
do not differ by an automorphism of PGU(3, 17).
In other words, the kernels of the epimorphisms are distinct.
> G := FPGroup< a, b | a^2, b^3, (a*b)^9 >;
> QG := L3Quotients(G); QG;
[
L_3(infty^18)
]
> H := FPGroup< a, b | a^2, b^3, (a,b)^5, (a, b*a*b*a*b)^3 >;
> L3Quotients(H);
[
L_3(2^infty)
]
> K := FPGroup< a, b | a^2, b^3 >;
> L3Quotients(K);
[
L_3(infty^(inft ^2))
]
Even without further interpretation of the output, this tells us that these
groups are all infinite.
The object L_3(infty^18) means that for almost all primes p there are quotients of G of the form L3(pr) or U3(pr), with r≤18. We can specify the characteristic to get explicit examples.
> SpecifyCharacteristic(QG[1], 37); [ PGL(3, 37), PGL(3, 37), PGL(3, 37) ] > X := SpecifyCharacteristic(QG[1], 2); X; [ PGU(3, 2^3) ] > M := GetMatrices(X[1]); > M:Minimal; MatrixGroup(3, GF(2^18)) > LMGChiefFactors(M); G | Cyclic(3) * | 2A(2, 8) = U(3, 8) * | Cyclic(3) 1If G has a quotient L_3(p^(infty^d)), then there are infinitely many positive integers k such that G has a quotient of type PSL(3, pk), PGL(3, pk), (PSU)(3, pk), or (PGU)(3, pk). So L_3(p^(infty^d)) is a mnemonic, where infty in the exponent stands for infinitely many possible exponents. The parameter d describes the degree of infinity, and is omitted if d = 1. We can use AddGroupRelations to study this quotient further.
> H< a, b > := FPGroup< a, b | a^2, b^3, (a,b)^5, (a, b*a*b*a*b)^3 >;
> quot := L3Quotients(H); quot;
[
L_3(2^infty)
]
> Q := quot[1];
> AddGroupRelations(Q, [(a*b)^(2*3*5*7)]);
[
PGL(3, 2^2),
U_3(2^2)
]
Another possibility is to add further ring relations to the ideal describing
the L3-quotient, using the intrinsic AddRingRelations.
It takes an L3-quotient and a list of polynomials, and computes the L3-quotients
whose traces satisfy these polynomial relations.
> Q := quot[1];
> Q`Ideal;
Ideal of Graded Polynomial ring of rank 10 over Integer Ring
Order: Grevlex with weights [8, 2, 2, 2, 2, 4, 4, 4, 4, 1]
Variables: xcom, x1, xm1, x2, xm2, x12, xm12, xm21, xm2m1, zeta
Variable weights: [8, 2, 2, 2, 2, 4, 4, 4, 4, 1]
Inhomogeneous, Dimension >0
Groebner basis:
[
xcom + zeta + 1,
xm12*xm2m1 + zeta,
x12 + xm12,
xm21 + xm2m1,
x1 + 1,
xm1 + 1,
x2,
xm2,
zeta^2 + zeta + 1,
2
]
> R< xcom, x1, xm1, x2, xm2, x12, xm12, xm21, xm2m1, zeta > := Generic(Q`Ideal);
> AddRingRelations(Q, [x12^5 + xm21^2 + 1]);
[
L_3(2^8),
L_3(2^6)
]