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 algorithm used is a new algorithm of Havas which does the reduction entirely over the 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 abelianizing the Reidemeister-Schreier presentation for H and then proceeding as above. The divisors are returned as a sequence of integers.
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 abelian quotient of F(7)
> AbelianQuotientInvariants(F7);
[ 29 ]
> /* > It 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 > );
1
> /* > We 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. > */
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 [For details of this algorithm, see George Havas and M.F. Newman (1980), "Application of computers to questions like those of Burnside", Burnside Groups, Lecture Notes in Math., 806, (Bielefeld, 1977), pp. 211--230. Springer-Verlag, Berlin, Heidelberg, New York.].
The p-quotient process and its associated commands allows
the user to construct a power-conjugate presentation (pcp)
for a p-group.
The Construction of p-Quotients
pQuotient(F, p, c: parameters) : GrpFP, RngIntElt, RngIntElt -> GrpPC, Map
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 min(c, 63). If c is given as 0, then the limit 63 is placed on the class. The function also returns the homomorphism from F to G.The parameters are:
Exponent: RngIntElt Default: 0If Exponent := m, enforce the exponent law, x^m = 1, on the group.
Metabelian: BoolElt Default: falseIf Metabelian := true, then a consistent pcp is constructed for the largest metabelian p-quotient of F having lower exponent-p class at most c.
Print: RngIntElt Default: 0This 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).
Workspace: RngIntElt Default: 1000000The amount of space requested for the p-quotient computation.
> F<a,b> := FreeGroup(2); > G := quo< F | (b, a, a) = 1, (a * b * a)^4 = 1 >; > q := pQuotient(G, 2, 6: Print := 1); Lower exponent-2 central series for G Group: G to lower exponent-2 central class 1 has order 2^2 Group: G to lower exponent-2 central class 2 has order 2^5 Group: G to lower exponent-2 central class 3 has order 2^8 Group: G to lower exponent-2 central class 4 has order 2^11 Group: G to lower exponent-2 central class 5 has order 2^15 Group: G to lower exponent-2 central class 6 has order 2^19
> 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 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 initialization of the process, a pcp for the largest p-quotient of F having class at most min(c, 63) will be constructed. If c is given as 0, then the limit 63 is placed on the class. This function supports the same parameters as pQuotient and returns a process P.
Exponent: RngIntElt Default: previously set value
Metabelian: BoolElt Default: previously set value
Print: RngIntElt Default: previously set value
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.
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.
Tails(~P: parameters) : Process(pQuot) ->
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, x^m = 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.
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: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.
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.
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 pcp for a p-quotient of F, this procedure computes a pcp for the p-covering group of this quotient. 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 defined by the pcp associated with the process P, as a member of the category GrpPC of soluble groups.
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.
> // Take exponent 9 group with two generators of order 3 > > // Set up class 4 quotient > > G<a, b> := Group<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 ] = .6 > NextClass(~q);
Group: G to lower exponent-3 central class 5 has order 3^9
> // Set output level to 1 > SetDisplayLevel(~q, 1); > // Add tails > Tails(~q); > // Apply consistency algorithm > Consistency(~q); > // Collect the defining relations > CollectRelations(~q); > // Enforce the exponent law > ExponentLaw(~q); > // Eliminate redundant generators > EliminateRedundancy(~q); > // Display 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
> // Set up class 1 quotient of 5-group > > G := Group<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^2
> /* Now set bounds on number of occurrences of pcp generators of > class 1 quotient in 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 > > 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 := Group<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
> 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 enforce relations > CollectRelations(~q); > // Apply 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