Quotient Group Methods#
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.
Abelian Quotient#
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 GrpFP_1:HasInfiniteComputableAbelianQuotient can be used.
- AbelianQuotient(G): GrpFP -> GrpAb, Map#
The maximal abelian quotient \(G/G^\prime\) of the group \(G\) as
GrpAb(cf. Chapter Abelian Groups). The natural epimorphism \(\pi:G\rightarrow G/G^\prime\) is returned as second value.
- ElementaryAbelianQuotient(G, p): GrpFP, RngIntElt -> GrpAb, Map#
The maximal \(p\)-elementary abelian quotient \(Q\) of the group \(G\) as
GrpAb(cf. Chapter Abelian Groups). The natural epimorphism \(\pi:G\rightarrow Q\) is returned as second value.
- AbelianQuotientInvariants(G): GrpFP -> [ RngIntElt ]#
- AQInvariants(G): GrpFP -> [ RngIntElt ]#
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
the ring of integers \({\mathbb{Z}}\) using clever heuristics to minimize the growth of coefficients.
The divisors are returned as a sequence of integers.
- AbelianQuotientInvariants(H): GrpFP -> [ RngIntElt ]#
- AQInvariants(H): GrpFP -> [ RngIntElt ]#
- AbelianQuotientInvariants(G, T): GrpFP, Map -> [ RngIntElt ]#
- AQInvariants(G, T): GrpFP, Map -> [ RngIntElt ]#
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.
- AbelianQuotientInvariants(G, n): GrpFP, RngIntElt -> [ RngIntElt ]#
- AQInvariants(G, n): GrpFP, RngIntElt -> [ RngIntElt ]#
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.
- AbelianQuotientInvariants(H, n): GrpFP, RngIntElt -> [ RngIntElt ]#
- AQInvariants(H, n): GrpFP, RngIntElt -> [ RngIntElt ]#
- AbelianQuotientInvariants(G, T, n): GrpFP, Map, RngIntElt -> [ RngIntElt ]#
- AQInvariants(G, T, n): GrpFP, Map, RngIntElt -> [ RngIntElt ]#
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.
- HasComputableAbelianQuotient(G): GrpFP -> BoolElt, GrpAb, Map#
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 \(\pi:G\rightarrow A\). If the abelian quotient of \(G\) cannot be computed, the valuefalseis returned.This function is especially useful to avoid runtime errors in user written loops or functions.
- HasInfiniteComputableAbelianQuotient(G): GrpFP -> BoolElt, GrpAb, Map#
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 \(\pi:G\rightarrow A\). If the abelian quotient of \(G\) cannot be computed or if it is finite, the valuefalseis 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.
- IsPerfect(G): GrpFP -> BoolElt#
Given an fp-group \(G\), this function tries to decide whether \(G\) is perfect by checking whether the abelian quotient of \(G\) is trivial.
- TorsionFreeRank(G): GrpFP -> RngIntElt#
Given the finitely presented group \(G\), return the torsion-free rank of the derived quotient group of \(G\).
- Example: F27 (ex-5b646e)#
The Fibonacci group \(F(7)\) has the following \(2\)-generator presentation:
\[<a,b \ |\ a^2b^{-2}a^{-1}b^{-2}(a^{-1}b^{-1})^2, abab^2abab^{-1}(ab^2)^2>.\]We proceed to investigate the structure of this group.
> 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 > ); 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.
- Example: Modular Abelian Quotient (ex-818c7a)#
The group \(G = (8, 7\ |\ 2, 3)\) is defined by the presentation
\[< a, b \ | \ a^8, b^7, (ab)^2, (a^{-1}b)^3 >.\]We consider the subgroup \(H\) of \(G\), generated by the words \(a^2\) and \(a^{-1}b\):
> 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); 1
We see that the maximal 2-elementary abelian quotient of \(H\) has order \(2^1\).
- HasFiniteAbelianQuotient(G): GrpFP -> [ RngIntElt ]#
- HasFiniteAQ(G): GrpFP -> [ RngIntElt ]#
Return
trueif \(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.
- AQPrimes(G): GrpFP -> [ RngIntElt ]#
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.
\(p\)-Quotient#
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 [Newman and O'Brien, 1996]. In Magma the result is returned as a group of type GrpPC (cf. Chapter Finite Soluble Groups).
Assume that the \(p\)-quotient has order \(p^n\), Frattini rank \(d\), and that its generators are \(a_1, \ldots, a_n\). Then the power-conjugate presentation constructed has the following additional structure. The set \(\{a_1,\ldots,a_d\}\) is a generating set for \(G\). For each \(a_k\) in \(\{a_{d+1},\ldots,a_n\}\), there is at least one relation whose right hand side is \(a_k\). One of these relations is taken as the definition of \(a_k\). (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.
- pQuotient(F, p, c: parameters): GrpFP, RngIntElt, RngIntElt -> GrpPC, Map, SeqEnum, BoolElt#
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 \(\pi\) 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.
If \(S[k] = [0,r]\), then \(G.k\) is defined via the image of \(F.r\) under \(\pi\).
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.r^{G.s}\).
There exist a number of parameters for controlling the behaviour of this function, which are described below.
- Example: p Quotient1 (ex-e7285c)#
We construct the largest \(2\)-quotient of class \(6\) for a two-generator, two-relator group.
> 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
The parameters available for the function pQuotient are:
Exponent: RngIntElt Default: 0
If Exponent := m, enforce the exponent law, \(x^m = 1\), on the group.
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\).
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).
Workspace: RngIntElt Default: 5000000
The amount of space requested for the \(p\)-quotient computation.
- Example: p Quotient2 (ex-090d87)#
We construct the largest \(3\)-quotient of class \(6\) for a two-generator group of exponent \(9\).
> 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
- Example: p Quotient3 (ex-bccae5)#
We use the metabelian parameter to construct a metabelian \(5\)-quotient of the group
\[< a, b\ |\ a^{625} = b^{625} = 1, (b, a, b) = 1, (b, a, a, a, a) = (b, a)^5>.\]> 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
- Example: p Quotient4 (ex-a5910e)#
In the final example, we construct the largest finite 2-generator group having exponent \(5\).
> 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
- HaspQuotientDefinitions(G): GrpPC -> BoolElt#
Given a pc-group \(G\), this function returns
trueiff and only if \(G\) has generator definitions set bypQuotient.
- pQuotientDefinitions(G): GrpPC -> SeqEnum#
Given a pc-group G, this function returns the generator definitions set by
pQuotient, and will throw an error if none exist.
\(p\)-Quotient Process#
In this and the next subsections the interative \(p\)-quotient process is described.
- pQuotientProcess(F, p, c: parameters): GrpFP, RngIntElt, RngIntElt -> Process#
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
pQuotientand returns a process \(P\).
- NextClass(~P : parameters): GrpPCpQuotientProc#
- NextClass(~P, k : parameters): GrpPCpQuotientProc, RngIntElt#
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, andMetabelianare used as before. IfMaxOccurrence := 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.
Using \(p\)-Quotient Interactively#
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.
- StartNewClass(~P: parameters): GrpPCpQuotientProc#
If \(P\) is a process for a class \(c\) \(p\)-quotient, commence construction of class \(c + 1\).
- Tails(~P: parameters): GrpPCpQuotientProc#
- Tails(~P, k: parameters): GrpPCpQuotientProc, RngIntElt#
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, \ldots, k + 1\) have already been added. The valid range of \(k\) is \(2, \ldots, c + 1\). The one valid parameter is
Metabelian; iftrue, then only the tails for the metabelian \(p\)-quotient are inserted.
- Consistency(~P: parameters): GrpPCpQuotientProc#
- Consistency(~P, k: parameters): GrpPCpQuotientProc#
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, \ldots, c + 1\). The one valid parameter is
Metabelian; iftrue, we assume that the tails inserted were those for a metabelian \(p\)-quotient and hence invoke the (less expensive) metabelian consistency algorithm.
- CollectRelations(~P): GrpPCpQuotientProc#
Collect the defining relations (if any) in the current pcp. If the tails operation is not complete, then the relations may be evaluated incorrectly.
- ExponentLaw(~P : parameters): GrpPCpQuotientProc#
- ExponentLaw(~P, Start, Fin: parameters): GrpPCpQuotientProc, RngIntElt, RngIntElt#
Exponent : RngIntElt Default: 0 Print : RngIntElt Default: 1 Trial : BoolElt Default: false ShortList : BoolElt Default: false DisplayList : BoolElt Default: false IdentifyFilters: BoolElt Default: false InitialSegment : [<GrpFPElt, RngIntElt>] Default: [] Report : RngIntElt Default: 0
Enforce the supplied exponent law on the current pcp. If
StartandFinare supplied, then enforce the law for those weights betweenStartandFin; otherwise, enforce the law for all weights. It is assumed that the tails operation is complete. If the display parameterDisplayLevel(which may be set usingSetDisplayLevel) has value \(2\), those words whose powers are collected and give redundancies among the pcp generators are printed out. IfDisplayLevelhas value \(3\), all words whose powers are collected are printed out. The following additional parameters are available:If
Exponent := m, enforce the exponent law, \(x^m = 1\), on the group.As for
pQuotient.Generate the list of words used to enforce the exponent law and print out statistics but do not power words or echelonise the results.
Generate 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\).
Display the list of all enforcement words generated – not just those which are collected.
Identify filters used to eliminate words from list.
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.If
Report := n, report after computing the powers of each collection of \(n\) enforcement words.
- EliminateRedundancy(~P): GrpPCpQuotientProc#
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 \(p\)Quotient process.
- Display(P): GrpPCpQuotientProc#
- Display(P, DisplayLevel): GrpPCpQuotientProc, RngIntElt#
Display the pcp for the \(p\)-quotient \(G\) of the fp-group \(F\). The argument
DisplayLevelmay 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
DisplayLevelis not supplied, the information displayed is determined by its existing (or default) value.
- RevertClass(~P): GrpPCpQuotientProc#
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.
- pCoveringGroup(~P): GrpPCpQuotientProc#
- pCoveringGroup(G): GrpPC -> GrpPC#
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).
- GeneratorStructure(P): GrpPCpQuotientProc#
- GeneratorStructure(P, Start, Fin): GrpPCpQuotientProc, RngIntElt, RngIntElt#
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.
- Jacobi(~P, c, b, a, ~r): GrpPCpQuotientProc, RngIntElt, RngIntElt, RngIntElt -> RngIntElt ->#
- Jacobi(~P, c, b, a): GrpPCpQuotientProc, RngIntElt, RngIntElt, RngIntElt -> RngIntElt ->#
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\).
- Collect(P, Q): GrpPCpQuotientProc, [ <RngIntElt, RngIntElt> ] -> [ RngIntElt ] ->#
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.
- EcheloniseWord(~P, ~r): GrpPCpQuotientProc -> RngIntElt#
- EcheloniseWord(~P): GrpPCpQuotientProc -> RngIntElt#
Echelonise the word most recently collected using
Collectagainst 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 afterCollect.
- SetDisplayLevel(~P, Level): GrpPCpQuotientProc, RngIntElt#
This procedure alters the display level for the process to the supplied value,
Level.
- ExtractGroup(P): GrpPCpQuotientProc -> GrpPC#
Extract the group \(G\) defined by the pcp associated with the process \(P\), as a member of the category
GrpPCof finite soluble groups. The function also returns the natural homomorphism \(\pi\) 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 \(\pi\).
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.r^{G.s}\).
- Order(P): GrpPCpQuotientProc -> RngIntElt#
The order of the group defined by the pcp associated with the process \(P\).
- FactoredOrder(P): GrpPCpQuotientProc -> [ <RngIntElt, RngIntElt> ]#
The factored order of the group defined by the pcp associated with the process \(P\).
- NumberOfPCGenerators(P): GrpPCpQuotientProc -> RngIntElt#
The number of pc-generators of the group defined by the pcp associated with the process \(P\).
- pClass(P): GrpPCpQuotientProc -> RngIntElt#
The lower exponent-\(p\) class of the group defined by the pcp associated with the process \(P\).
- NuclearRank(G): GrpPC -> RngIntElt#
- NuclearRank(P): GrpPCpQuotientProc -> RngIntElt#
Return the rank of the \(p\)-multiplicator of the \(p\)-group \(G\), where \(G\) may be supplied or defined by the process \(P\).
- pMultiplicatorRank(G): GrpPC -> RngIntElt#
- pMultiplicatorRank(P): GrpPCpQuotientProc -> RngIntElt#
Return the rank of the \(p\)-multiplicator of the \(p\)-group \(G\), where \(G\) may be supplied or defined by the process \(P\).
- Example: p Quotient5 (ex-ea9994)#
Starting with an exponent 9 group having two generators of order 3, we set up the largest class 4 quotient and then interactively compute two more classes.
> 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 ] = .6
We construct the class 5 quotient using the function
NextClass.> NextClass(~q); Group: G to lower exponent-3 central class 5 has order 3^9
We 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
- Example: p Quotient6 (ex-0cb2c6)#
Starting with the free product of two cyclic groups of order 5, we bound the number of occurrences of pcp generators of the class 1 quotient in definitions of new pcp generators.
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^2
Now 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
- Example: p Quotient7 (ex-371e40)#
We construct the class \(6\) quotient \(q\) of \(R(2, 5)\) and then partially construct the class \(7\) quotient interactively to find out how many normal words having initial segment \(q.1^2\) need to be considered when imposing the exponent law.
> 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
- Example: p Quotient8 (ex-0ff68f)#
We demonstrate several of the remaining procedures in the course of interactively extending the class \(6\) quotient of the group
\[<a, b, c, d\ |\ (bc^{-1}d)^7, (cd^{-1})^7, (b,a) = c^{-1}, (c,a) = 1, (c,b) = d^{-1}>\]to class \(7\).
> 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
Nilpotent Quotient#
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 [Nickel, 1996]. The version included in Magma is Version 2.2 of January 2007.
The lower central series \(G_0, G_1, \dots\) of a group G can be defined inductively as \(G_0 = G\), \(G_i = [G_(i-1),G]\). \(G\) is said to have nilpotency class c if \(c\) is the smallest non-zero integer such that \(G_c = 1\). If \(N\) is a normal subgroup of \(G\) and \(G/N\) is nilpotent, then \(N\) contains \(G_i\) for some non-negative integer \(i\). \(G\) has infinite nilpotent quotients if and only if \(G/G_1\) (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/G_1\). The \(i\)-th (\(i > 1\)) factor \(G_{i-1}/G_i\) of the lower central series is generated by the elements \([g,h]G_i\), where \(g\) runs through a set of representatives of \(G/G_1\) and \(h\) runs through a set of representatives of \(G_{i-2}/G_{i-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/G_c\).
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.
- NilpotentQuotient(G, c: parameters): GrpFP, RngIntElt -> GrpGPC, Map#
This function returns the class \(c\) nilpotent quotient of \(G\) as a group in category
GrpGPC, together with the epimorphism \(\pi\) 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.
- Example: Nilpotent Quotient0 (ex-7067cc)#
Here is a finitely presented group. The abelian quotient is infinite, so we look at the class 2 nilpotent quotient.
> 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
- Example: Nilpotent Quotient1 (ex-8a4940)#
The free nilpotent group of rank \(r\) and class \(e\) is defined as \(F / \gamma_{e+1}(F)\), where \(F\) is a free group of rank \(r\) and \(\gamma_{e+1}(F)\) denotes the \((e+1)\) st term of the lower central series of \(F\).
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
NilpotencyClassdescribed in Chapter Polycyclic Groups, we check the nilpotency class of the quotient.> NilpotencyClass(N); 3
- Example: Nilpotent Quotient2 (ex-b77879)#
The Baumslag-Solitar groups
\[BS(p,q) = \langle<a,b\vert ab^pa^{-1} = b^q\rangle\]form a fascinating class of 1-relator groups. We compute the nilpotent of class 4 quotient of two of them, and print out the resulting presentations, and the structure of the generators.
> 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)
The parameters available for the function NilpotentQuotient are:
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.
LeftEngel: RngIntElt Default: 0
Setting this parameter to \(n\) forces the first \(k\) generators \(g_1,\dots,g_k\) of the quotient \(Q\) to be left \(n\)-Engel elements. That is, they satisfy \([x, \dots, x, g_i] = 1\) (\(x\) appearing \(n\) times) for all \(x\) in \(Q\). The value of \(k\) is determined by the parameter NumberOfEngelGenerators.
RightEngel: RngIntElt Default: 0
This is the same as for LeftEngel, but here the generators are right \(n\)-Engel elements, so \([g_i, x, \dots, x] = 1\).
Engel: RngIntElt Default: 0
Setting this parameter to \(n\) enforces the \(n\)th Engel law on the quotient \(Q\). That is, \([x,y,\dots,y]=1\) (\(y\) appearing \(n\) times) for all \(x\), \(y\) in \(Q\).
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.
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.
ReverseOrder: BoolElt Default: false
In checking Engel identities, instances are processed in order of increasing weight. This flag reverses the order.
ReverseEngel: BoolElt Default: false
This flag changes the Engel conditions from the first \(k\) generators, to the last \(k\) generators.
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.
Nickel: BoolElt Default: false
Enforce the identities \(x^8\) and \([[x_1,x_2,x_3],[x_4,x_5,x_6]]\) on the nilpotent quotient.
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.
PrintResult: BoolElt Default: false
If set to true, this parameter switches on the printing of results given by the stand alone version of NQ.
- SetVerbose("NilpotentQuotient", n): MonStgElt, RngIntElt#
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.
- Example: Nilpotent Quotient3 (ex-85800d)#
We compute the maximal nilpotent quotient \(N1\) of the group \(G\) given by the following presentation
\[\langle 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) \rangle.\]> 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
NilpotencyClassdescribed in Chapter Polycyclic Groups, we check the nilpotency class of the quotient. It turns out to have nilpotency class 6.> NilpotencyClass(N1); 6
Next 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] @}
Soluble Quotient#
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.
- SolvableQuotient(G : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolubleQuotient(G : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
Let \(G\) be a finitely presented group. The function constructs the largest finite soluble quotient of \(G\).
- Example: Soluble Quotient1 (ex-a7ae66)#
We compute the soluble quotient of the group
\[\langle a,b \,\,|\,\, a^2, b^4, ab^{-1}ab(abab^{-1})^5ab^2ab^{-2} \rangle.\]> 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
- SolvableQuotient(F, n : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolubleQuotient(F, n : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolvableQuotient(F, P : parameters): GrpFP, Set -> GrpPC, Map, SeqEnum, MonStgElt#
- SolubleQuotient(F, P : parameters): GrpFP, Set -> GrpPC, Map, SeqEnum, MonStgElt#
Find a soluble quotient \(G\) and the epimorphism \(\pi:F\rightarrow \!\!\!\!\rightarrow 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.
- Example: Soluble Quotient2 (ex-130896)#
Consider the group \(G\) defined by the presentation
\[\langle x, y \;\;|\;\; x^3, y^8, [x,y^4], x^{-1}yx^{-1}y^{-1}xyxy^{-1}, (xy^{-2})^2(x^{-1}y^{-2})^2(xy^2)^2(x^{-1}y^2)^2, (x^{-1}y^{-2})^6(x^{-1}y^2)^6 \rangle.\]> 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); 165888
Note that \(165888 = 2^{11} \cdot 3^4\). 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); 165888
Hence 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
Soluble Quotient Advanced#
Introduction#
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.
Construction#
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)} = \langle 1 \rangle\). Each section \(G^{(i)}/G^{(i+1)}\) is a finite abelian group, hence it can be identified with a \({\mathbb{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^{(r_i)},\) 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)} = \langle 1 \rangle\) of the commutator series with the properties:
The series is normal,
Each section \(G_{(i)}/G_{(i+1)}\) is elementary abelian of prime power order, and is irreducible as a \(G/G_{(i)}\)-module.
If \(G = H_{(0)} > H_{(1)} > ... > H_{(t)} = \langle 1 \rangle\) is another series with these properties, then \(n = t\) and there exists a permutation \(\pi \in S_n\) such that \(G_{(i)}/G_{(i+1)}\) is isomorphic to \(H_{(i\pi)}/H_{(i\pi+1)}\) (as \(GF(p)\) modules).
Note: A PC-presentation defined by a further refinement of this series leads to a “conditioned” presentation. The converse is not always true, because the irreducibility of the sections is not required for a conditioned presentation.
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 \(M_i\) and extensions
which give rise to exact sequences
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
where \(w_i,w_{ij}\) are the canonical representatives of \(H\) in \(G\). Then \(\bar{g_i^{p_i}}=\bar{w_i}\) resp. \(\bar{g_j}^{\bar{g_i}} =\bar{w_{ij}}\) is a PC-presentation of \(H\) and the set of images \(\left((g_i^{p_i-1},g_i)\rightarrow m_i,(g_j,g_i)\mapsto m_{ij}\right)\) determines a unique element of the cocycle space \(C^2(H,M)\).
According to the \(p\)-group situation, we call the system \(t= (m_i, m_{ij})\), the tail defining \(G = H.M_t\) as an extension of \(M\) by \(H\).
Not every choice of a system \(t = (m_i, m_{ij})\) defines an extension. To make sure that \(t\) corresponds to an element \(s\) of \(C^2(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 \(\varepsilon: F\rightarrow \!\!\!\!\rightarrow 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 \(\delta: F\rightarrow \!\!\!\!\rightarrow H.\) Then \(\delta\) is uniquely determined by the images \(\delta(f_i)=h_i, 1\leq i \leq r,\) where \(\{f_1, \ldots,f_r\}\) is a generating set of \(F\). We want to find a lift \(\varepsilon\) of \(\delta\), i.e. \(\varepsilon (f)=\delta(f) \ {\rm mod} \ M\) for all \(f \in F\). This means that \(\varepsilon(f_i)=h_i x_i\) for all \(i\leq r\), where \(x_i \in M\) are to be determined. Since \(\varepsilon\) will be a homomorphism, we require \(\varepsilon(r_j(f_1,\ldots,f_r))=1_G\) for the defining relations \(r_j\) of \(F\). This leads to a linear equation system for the variables \((x_1,\ldots,x_r)\in M^r\). We solve this equation system together with the consistency equations, hence we find a subspace \(S\) of \(M^r \times H^2(H,M)\) of those extensions for which the epimorphism \(\delta\) 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 \(S_S\) of split extensions, i.e. the projection of \(S_S\) into \(H^2(H,M)\) is only the trivial element. For any element \(t \in S/S_S\) the corresponding map \(\varepsilon_t: F \rightarrow H.M_t\) is necessarily surjective, hence defines a soluble quotient. Let \(s_1,s_2\) be two elements of \(S/S_S\) and let \(\varepsilon_i: F \rightarrow \!\!\!\!\rightarrow H.M_{s_i} =: G_i\) denote the corresponding soluble quotients. If \(s_1\) and \(s_2\) are \(K\)-linear dependent, the groups \(G_1\) and \(G_2\) will be isomorphic. Unfortunately, the converse is not true, even \(K\)-linear independent elements may lead to isomorphic groups. Nevertheless, if \(s_1\) and \(s_2\) are independent, the kernels of the epimorphisms will be different, hence one can iterate the lifting to
(The last equality can be read as a definition of \(s_1\cdot s_2\) in the righthand side term.)
The dimension \(a=dim_K(S/S_S)\) is therefore characterised as the maximal multiplicity
\(S_S\) itself also has a \(K\)-subspace \(S_C\), for which the map
is not surjective. The \(K\)-dimension \(b=dim_K(S_S/S_C)\) is again characterised as the maximal multiplicity
Moreover, after taking a maximal extension \(\varepsilon:F \rightarrow \!\!\!\!\rightarrow H.M^b\), \(M\) never has to be considered for split extensions again.
Calculating the Relevant Primes#
A crucial step in finding finite soluble quotients \(\varepsilon: F \rightarrow \!\!\!\!\rightarrow 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 \(\varepsilon:F \rightarrow \!\!\!\!\rightarrow G\) be a finite soluble quotient and let \(N\) denote the kernel of \(\varepsilon\). If a module \(M\) allows an extension \(\bar{\varepsilon}:F \rightarrow \!\!\!\!\rightarrow G.M\), then \(M\) must be a constituent of \(N/N^\prime\), and the relevant primes are the prime divisors of \(N/N^\prime\). Again \(N/N^\prime\) can be viewed as an \(F/N\)- module, hence an \(H\)-module. Therefore it is a direct sum \(N/N^\prime \cong M_{p_1} \oplus M_{p_2} \oplus \ldots \oplus {\mathbb{Z}}^d\), where the \(M_{p_i}\) are finite modules of order a power of the prime \(p_i\). Let \(p\) not divide \(|H|\). Then by Zassenhaus the extension \(H.M_p\) must split. We consider an irreducible module \(M\) in the head of \(M_p\), i.e. there is an \(H\)-epimorphism \(M_p \rightarrow \!\!\!\!\rightarrow M\). Then there is a valid soluble quotient \(\varepsilon: F \rightarrow \!\!\!\!\rightarrow H.M\) and the extension \(H.M\) splits.
Now there exists an irreducible \({\mathbb{Z}}H\)- module \(L\) such that \(M\) is a \(GF(p)\)-modular constituent of \(L/pL\). Moreover, \(\Delta: H \rightarrow GL(L)\) is the corresponding representation of \(H\) and any \(\Delta\)-module will have this property.
Now using the theory of space groups, one can construct homomorphisms \(\varepsilon_1: F \rightarrow \!\!\!\!\rightarrow H.L\) and \(\varepsilon_2: H.L \rightarrow \!\!\!\!\rightarrow H.M\) such that the composition is surjective. Hence \(p\) can be detected in \(\Delta\). Let \(P_\Delta\) denote the set of primes obtained from \(\Delta\). 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/K^\prime\) is a subset of
We want to point out the following:
: Usually the set of primes dividing \(\left|K/K^\prime\right|\) is a proper subset of \(P\), because the primes dividing \(|G|\) may or may not divide \(\left|K/K^\prime\right|\).
- •
Conversely, if \(p\) does not divide \(|G|\), then there certainly exists a module \(M\) in characteristic \(p\) such that there is a soluble quotient \(F \rightarrow \!\!\!\!\rightarrow G.M\), and the extension splits.
- -
The algorithm can also recognise infinite abelian sections. This means that already \(\varepsilon_1: F \rightarrow \!\!\!\!\rightarrow H.L\) is surjective. All primes are relevant and no maximal finite soluble quotient exists.
- -
Let \(\phi:F \rightarrow \!\!\!\!\rightarrow H\) be a lift of \(\varepsilon:F \rightarrow \!\!\!\!\rightarrow G\), i.e. \(G\) is a quotient of \(H\): \(\phi:H \rightarrow \!\!\!\!\rightarrow G\). If the relevant primes of \(G\) are known, these are also relevant primes of \(H\), and only those representations \(\Delta\) of \(H\) must be considered for which \(\ker\phi \not\subset\ker\Delta\) is valid.
The Intrinsics#
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.
- SolubleQuotient(F, n : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolvableQuotient(F, n : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolubleQuotient(F : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolvableQuotient(F : parameters): GrpFP, RngIntElt -> GrpPC, Map, SeqEnum, MonStgElt#
- SolubleQuotient(F, P : parameters): GrpFP, Set -> GrpPC, Map, SeqEnum, MonStgElt#
- SolvableQuotient(F, P : parameters): GrpFP, Set -> GrpPC, Map, SeqEnum, MonStgElt#
SeriesLength : RngIntElt Default: 0 SubseriesLength : RngIntElt Default: 0 \vapour QuotientSize: RngIntElt Default: 0 \vapour SectionSize : RngIntElt Default: 0 \vapour MSQ_Series : MonStgElt Default: "sag" MSQ_PrimeSearchModus: RngIntElt Default: 3 MSQ_ModulCalcModus : RngIntElt Default: 0 MSQ_CollectorModus : RngIntElt Default: 2 Print : RngIntElt Default: 0 verbose : MSQ_Messages Default: Verbose : 2 verbose : MSQ_PrimeSearch Default: Verbose : 15 verbose : MSQ_RepsCheck Default: Verbose : 3 verbose : MSQ_RepsCalc Default: Verbose : 3 verbose : MSQ_Collector Default: Verbose : 1 verbose : MSQ_TraceFunc Default: Verbose : 2
Find a soluble quotient \(\varepsilon:F\rightarrow \!\!\!\!\rightarrow 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 \(\varepsilon: F \rightarrow \!\!\!\!\rightarrow 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:
A quotient of the given order has been constructed.
A maximal quotient (with respect to the conditions given on the order) has been constructed.
The algorithm will be aborted and returns a warning if:
A bound on the length of a series or subseries has been hit.
A limit on the size of the quotient or a section has been hit.
The algorithm detects a free abelian section.
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.
Limits 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.
Limits 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 \(C_8\), but not by \(C_2^3\) and not even by \(C_4^2\).
If 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.
If 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.
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.
Defines 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).
In 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.
Defines the setup modus for the symbolic collector, i.e. the ratio of precalculation to dynamic setup:
- 0:
Full precalculation, preferable for small soluble groups.
- 1:
Partial precalculation (test version).
- 2:
Dynamic setup (default).
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.
Determines what timing information and status messages are given during the calculation (0 = no printing, 5 = maximal information).
If set to 1, the sizes of new soluble quotients are printed.
Bitflag 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.
- 1:
Timing for checking extensions of modules.
- 2:
Statistics about the modules to be checked.
- 1:
Timing information about the module calculation.
- 2:
Statistics about the module calculation.
If set to 1, the timing for the setup of the symbolic collector is printed.
Give messages about the main function calls (1) resp. most function calls (2) in the Magma language during the algorithm.
Simple Group Quotients#
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 \(\le 10^{10}\). Such a list is dominated by \({\operatorname{PSL}}(2,q)\)’s with \(q\) odd. In this implementation these \({\operatorname{PSL}}(2,q)\)’s are treated as an infinite family rather than stored individually, and so continue beyond the above limit.
- SimpleQuotients({F, deg1, deg2, }{ord1, ord2: parameters}): GrpFP, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> List#
- SimpleQuotients(F, ord1, ord2: parameters): GrpFP, RngIntElt, RngIntElt -> List#
- SimpleQuotients(F, ord2: parameters): GrpFP, RngIntElt -> List#
Family : Any Default: "All" Limit : RngIntElt Default: 1 HomLimit: RngIntElt Default: 0
Uses
Homomorphismsto 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 \(10^7\) 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
Limitlimits the number of successful searches to be carried out byHomomorphisms. 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
HomLimitlimits the number of homomorphisms that will be searched for by any particular call toHomomorphisms. It defaults to zero, so that all homomorphisms for any group found will be returned.The parameter
Familyselects 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.
- SimpleQuotientProcess({F, deg1, deg2, }{ord1, ord2: parameters}): GrpFP, RngIntElt, RngIntElt, RngIntElt, RngIntElt -> Rec#
Family: Any Default: "All"
Produce a record that defines a process for searching for simple quotients of \(F\) as
SimpleQuotientsdoes. 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 callingNextSimpleQuotient. Extracting the epimorphisms found is achieved usingSimpleEpimorphisms, and testing if the process has expired is the task ofIsEmptySimpleQuotientProcess.
- NextSimpleQuotient(~P): Rec#
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.
- IsEmptySimpleQuotientProcess(P): Rec -> BoolElt#
When \(P\) is a record returned by
SimpleQuotientProcess, test whether or not \(P\) has expired.
- SimpleEpimorphisms(P): Rec -> SeqEnum, Tup#
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 whenIsEmptySimpleQuotientProcessreturnsfalse.
- Example: Simple Quotients (ex-b2e434)#
We take a perfect finitely presented group and search for simple quotients.
> 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); true
No, there are no more within the limits given.
The \({\rm L}_2\)-Quotient Algorithm#
Given an fp-group \(G\), the \(L_2\)-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 [Jambor, 2012] or [Jambor, 2015] for more information about the \(L_2\)-quotient algorithm.
Note that the algorithm does not return images onto the groups \({{\operatorname{PSL}}}(2,2)\), \({{\operatorname{PSL}}}(2,3)\), and \({{\operatorname{PSL}}}(2, 4) = {{\operatorname{PSL}}}(2, 5)\).
Basic Usage#
- L2Quotients(G): GrpFP -> [ L2Quotient ]#
This is the main method. It takes as parameter a finitely presented group and returns a sequence of \({\rm L}_2\)-quotients, which have type
L2Quotient.
- Example: L2Quotient (ex-656deb)#
We first compute \(L_2\)-quotients of a certain finitely-presented group.
> 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 \({\operatorname{PSL}}(2,43)\) as quotient, but no other \({\operatorname{PSL}}(2,q)\) or \({\operatorname{PGL}}(2,q)\) is a quotient of \(G\). Similarly, the only \(L_2\)-quotient of \(H\) is \({\operatorname{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 \({\operatorname{PGL}}(2,23)\) occurs twice. This means that there are two epimorphisms of \(G\) onto \({\operatorname{PGL}}(2,23)\) which do not differ by an automorphism of \({\operatorname{PGL}}(2,23)\). In other words, the kernels of the epimorphisms are distinct.
Some groups have infinitely many \(L_2\)-quotients. This is indicated by one of the \(L_2\)-quotients
L_2(infty^k), L_2(p^(infty^d)), orL_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.
- GetMatrices(Q): L2Quotient -> GrpMat, SeqEnum#
For a finite \(L_2\)-quotient \(Q\) of \(G\), that is, a quotient \(L_2(p^k)\) or \({\operatorname{PGL}}(2,p^k)\), this function returns a matrix group \(H\) and a sequence \(A\) of \(2\times 2\) matrices in \(H\), where \(A[i]\) corresponds to the \(i\)-th generator of \(G\). Note that \(G \rightarrow H\), \(G.i \rightarrow A[i]\) does not in general define a homomorphism, but the induced map \(G \rightarrow H/Z(H)\) does.
- Example: L2Quotient Get Matrices (ex-d6f5a7)#
The following example illustrates how the quotient matrix groups can be accessed.
> 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] ]
- Example: Modular Finite (ex-0ea7a6)#
The next few examples are taken from Conder, Havas and Newman [Conder et al., 2011].
> 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 \({\rm 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 \({\rm L}_2\) quotient, isomorphic to \({{\operatorname{PGL}}}(2, 13)\), and the second group has no \({\rm L}_2\) quotients at all.
- Example: Coxeter Finite (ex-3ecfb1)#
Next, we look at Coxeter presentations of the form
\[(l, m | n, k) = \langle x, y | x^l, y^m, (xy)^n, (x^{-1}y)^k \rangle\]and
\[(l, m, n; q) = \langle x, y | x^l, y^m, (xy)^n, [x, y]^k \rangle\]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 \({{\operatorname{PSL}}}(2, 71)\) occurs three times. This means that there are three essentially different epimorphisms of \(G\) onto \({{\operatorname{PSL}}}(2, 71)\), i.e., there is no automorphism of \({{\operatorname{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) [Havas and Holt, 2010]). They are \((3, 4, 9; 2)\), \((3, 4, 11; 2)\), and \((3, 5, 6; 2)\). Each of them has only one \({\rm 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) ]
Intermediate Usage#
- L2Quotients(M): AlgMatElt -> [ L2Quotient ]#
A Coxeter group is a finitely presented group on \(m\) generators, such that the only other relations are \((g_ig_j)^{M_{ij}}\), 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
L2Quotientsaccepts a Coxeter matrix as input, and computes the smooth quotients of the associated Coxeter group. However, it omits the quotients in characteristic \(p\) if \(M_{12} = p\). Furthermore, if a quotient has characteristic \(p\) and \(p\) divides some entry of \(M\), then the quotient is not guaranteed to be smooth.
- Example: L2Quotient Coxeter (ex-cc44da)#
> 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) ]
- L2Quotients(G): GrpFP -> [ L2Quotient ]#
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.
- Example: L2Quotientexact Orders (ex-39db62)#
> 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
Advanced Usage#
- L2Quotients(G): GrpFP -> [ L2Quotient ]#
Saturate : Boolean Default: false AddMoreRelations : Boolean Default: false Primes : SeqEnum Default: [] ExcludePrimes : SeqEnum Default: [] SingleInfinite : Boolean Default: false UseRandomTechniques: Boolean Default: FactorizationBound : RngIntElt Default: TrialDivisionBound : RngIntElt Default: GroebnerBasisBound : RngIntElt Default:
The algorithm discards prime ideals containing \(\rho = x_1^2 + x_2^2 + x_{12}^2 - x_1x_2x_{12} - 4\). If the optional boolean parameter
Saturateistrue, then prior to the primary decomposition the ideal is saturated at \(\rho\), which can be faster in some cases.If the optional boolean parameter
AddMoreRelationsistrue, then the algorithm adds further relations to the ideal, which speeds up the computation in some cases.Given a sequence \(P\) of primes, this variant only produces quotients \(Q\) in characteristic \(p\) only, where \(p\) must lie in \(P\).
The optional parameter
ExcludePrimesis a sequence of primes. The algorithm does not compute \({\rm L}_2\)-quotients in characteristic \(p\) if \(p\) is inexclude.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.
These parameters are passed to the method
MinimalAssociatedPrimes(see documentation there).
Handling Infinite \({\rm L}_2\)-quotients#
Quotients of type \({\rm L}_2(\infty^k)\)
If \(G\) has a quotient \({\rm L}_2(\infty^k)\), then for almost all (all but finitely many) primes \(p\), \(G\) has finitely many quotients of type \({{\operatorname{PSL}}}(2,p^r)\) or \({{\operatorname{PGL}}}(2,p^{r/2})\) with \(r \leq k\). So \({\rm L}_2(\infty^k)\) is a mnemonic, where \(\infty\) 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.
- SpecifyCharacteristic(Q, n): L2Quotient, RngIntElt -> [ L2Quotient ]#
Compute the \({\rm L}_2\)-quotients in characteristic \(p \mid n\).
- Example: L2Quotient Specify Characteristic (ex-dd2847)#
> 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) ]
- AddGroupRelations(Q, R): L2Quotient, [ GrpFPElt ] -> [ L2Quotient ]#
Compute the \({\rm L}_2\)-quotients which satisfy the additional relations \(R\).
- Example: L2Quotient Add Group Relations (ex-6e7481)#
> 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) ]
Quotients of type \({\rm L}_2(p^{\infty^d})\)
If \(G\) has a quotient \({\rm L}_2(p^{\infty^d})\), then there are infinitely many positive integers \(k\) such that \(G\) has a quotient of type \({{\operatorname{PSL}}}(2,p^k)\) or \({{\operatorname{PGL}}}(2,p^k)\). So \({\rm L}_2(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\).
Again, we can use AddGroupRelations to sudy this quotient further.
- Example: L2Quotient Specify Add Group Relations2 (ex-d05ba8)#
> 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) ]
- AddRingRelations(Q, R): L2Quotient, [ RngMPolElt ] -> [ L2Quotient ]#
Compute the \({\rm L}_2\)-quotients whose traces satisfy the polynomial relations given in \(R\).
- Example: L2Quotient Specify Add Ring Relations (ex-6b7dfd)#
> 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) ]
Quotients of type \({\rm L}_2(\infty^{\infty^d})\)
If \(G\) has a quotient \({\rm L}_2(\infty^{\infty^d})\), then for almost all primes \(p\) and infinitely many positive integers \(k\), \(G\) has a quotient of type \({{\operatorname{PSL}}}(2,p^k)\) or \({{\operatorname{PGL}}}(2,p^k)\). So \({\rm L}_2(\infty^{\infty^d})\) is a mnemonic, where \(\infty\) in the base stands for infinitely many primes, and \(\infty\) 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.
Infinite L2 Quotients#
This section contains functions that use the L2-quotient algorithm of Plesken and Fabianska ([Plesken and Fabianska, 2009]) to establish the existence or not of an infinite quotient of a finitely-presented group in \({\operatorname{PSL}}_2(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 \({\mathbb{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 \(SL_2(K)\). If \(g_1,\ldots,g_n\) are the generators of \(G\), then the affine coordinates of \(X\) correspond to the trace under the representation of various products of the \(G_i\). For example, when \(n=2\), \(X\) lies in \(3\)-dimensional affine space and the coordinates correspond to the traces of \(g_1\), \(g_2\) and \(g_1g_2\). The ideal is actually generated by polynomials with coefficients in \({\mathbb{Z}}\) so \(X\) is naturally defined as a scheme over \(Spec({\mathbb{Z}})\), whose reduction mod \(p\) just gives the scheme corresponding to characteristic \(p\) representations of \(G\) for \(p > 2\).
Homomorphisms into \({\operatorname{PSL}}_2\) rather than \({\operatorname{SL}}_2\) 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 \(SL_2\) that takes each word in the set of relations defining \(G\) to either \(I\) or \(-I\). Each of the \(2^r\) choices of sign for the \(r\) defining relations gives an \(X\) (by the same procedure) and the totality cover all possibilities for maps to \({\operatorname{PSL}}_2\).
The set of points of \(X\) corresponding to geometrically reducible, dihedral \(A_4\), \(S_4\) or \(A_5\) images in \({\operatorname{PSL}}_2\) is a closed subscheme \(Y\). In fact the first two possibilities give closed subschemes with equations defined over \({\mathbb{Z}}\) and the last three give a dimension zero scheme over \({\mathbb{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 ([Fabianska, 2009]). Let \(U\) be the open complement of \(Y\) in \(X\).
There are two possibilities.
- 1
A \(U\) is non-empty, so an algebraic point gives \(\phi: G \rightarrow {\operatorname{PSL}}_2(K)\), \(K\) a number field, with infinite image, so \(G\) is infinite. Further, for all but finitely many primes \(p\), \(\phi\) can be reduced mod \(v\) for any place \(v\) of characteristic \(p\) AND the reduction \(\phi_v\) corresponds to a point in the analogue of \(U\) over the finite field. Thus the reductions give surjections of \(G\) onto a \({\operatorname{PSL}}_2(k)\) [or maybe a \({\operatorname{PGL}}_2(k)\)] for finite fields of any characteristic outside of a finite set.
- 2
All \(U\)s are empty. Here, all the homomorphisms of \(G\) into \({\operatorname{PSL}}_2(K)\) in characteristic zero have geometrically reducible, dihedral, \(A_4\), \(S_4\) or \(A_5\) images and the same holds for \(K\) a field of characteristic \(p\) for all \(p\) outside of a finite set of primes. \(G\) may or may not be infinite.
NB: In case 2), there may still be images of \(G\) which ARE infinite, but lie in a Cartan or Borel subgroup, so are geometrically reducible, or lie in the normaliser of a Cartan and have an infinite dihedral image. These infinite reducible/dihedral possibilities are not currently checked for.
- HasInfinitePSL2Quotient(G): : GrpFP -> BoolElt, SeqEnum#
Signs : SeqEnum Default: 0 Full : BoolElt Default: false verbose: IsInfGrp Default: Verbose : 1
Function to return whether the two-generator finitely-presented group \(G\) has an infinite quotient lying in a \({\operatorname{PSL}}_2(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 = [w_1,..,w_r]\).
As described in the introduction, for each of the \(2^r\) combinations of signs attached to the \(w_i\) - let \(s\) be one - the program will consider the scheme \(X\) of homomorphisms of \(G\) into \({\operatorname{PSL}}_2\) such that, when lifted to a homomorphism of the two-generator free cover \(F\) of \(G\) into \(SL_2\), \(w_i\) maps to \(s_i*I\).
In some cases, the user may realise that there is no point in considering certain choices of signs. For example, if \(g_1^2\) is a relation in \(ws\), \(g_1^2 \mapsto I\) in \(SL_2(K)\) means that \(g_1 \mapsto 1\) in \({\operatorname{PSL}}_2(K)\), so the \({\operatorname{PSL}}_2(K)\) image would be (maybe infinitely) cyclic, and it is a waste of time to consider this possibility. Similarly, if \(g_1^r\), \(r\) odd, is a relation then ,without loss of generality, in a \({\operatorname{PSL}}_2\) to \(SL_2\) lift, \(g_1^r \mapsto I\), which could be specified.
The parameter
Signsallows the user to specify a restricted set of sign options to analyse.Signsshould 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 \(w_i\) map to \(eI\) in the lift to \(SL_2\). If \(e = 0\), then there is no condition at place \(i\) of the sign sequences considered. The default value forSignsis 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 \({\operatorname{PSL}}_2\) then comes down to examining the finite set of closed points remaining and finding one that is not geometrically reducible, dihedral, \(A_4\), \(S_4\) or \(A_5\) 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
Fullis set totrue(the default isfalse), 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
IsInfGrptotrueor \(1\) gives output of information on the various stages as the function progresses, including the analysis of dimension zero loci.
- Example: Fp Gps:inf Psl2 Quot (ex-5b2c63)#
We look at two examples of quotients of the two-generator free group with relations \(g_1^2\), \(g_2^3\) and one further word. The first is infinite, the second is not. As noted above, we may as well specify that \(g_1^2\) maps to \(-I\) and \(g_2^3\) to \(I\) in \(SL_2\) and this can be done with the
Signsparameter.> 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 \(A_5\).
> 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 ] *] ]
The \({\rm L}_3{\rm U}_3\)-Quotient Algorithm#
Given a finitely presented group \(G\) on two generators, the \({\rm L}_3{\rm U}_3\)-quotient algorithm of Jambor [Jambor, 2012] computes all quotients of \(G\) which are isomorphic to some \({{\operatorname{PSL}}}(3, q)\), \({{\operatorname{PGL}}}(3, q)\), \({\rm PSU}(3, q)\), or \({\rm 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 \({{\operatorname{PSL}}}(3,2) = {{\operatorname{PSL}}}(2,7)\).
- L3Quotients(G: parameters): GrpFP -> [ L3Quotient ]#
ExactOrders : SeqEnum Default: [] ExcludePrimes: SeqEnum Default: []
Given a group \(G\) with 2 generators, this function returns a sequence of \({\rm L}_3\)-quotients, which have type
L3Quotient.Given a sequence of pairs \(\langle w, n \rangle\) 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\).
Given a sequence \(P\) of primes, this variant only produces quotients \(Q\) in characteristic \(p\), where \(p\) does not lie in \(P\).
- SpecifyCharacteristic(Q, p): L2Quotient, RngIntElt -> [ L2Quotient ]#
- SpecifyCharacteristic(Q, p): L3Quotient, RngIntElt -> [ L3Quotient ]#
Compute the restrictions of the given quotient object \(Q\) to the prime characteristic \(p\).
- AddGroupRelations(Q, r): L2Quotient, [ GrpFPElt ] -> [ L2Quotient ]#
- AddGroupRelations(Q, r): L3Quotient, [ GrpFPElt ] -> [ L3Quotient ]#
Compute quotient objects from \(Q\) for the group of \(Q\) with relators \(r\) added.
- GetMatrices(Q): L2Quotient -> GrpMat#
- GetMatrices(Q): L3Quotient -> GrpMat#
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.
- Example: L3Quotient (ex-0214ac)#
We first compute \({\rm L}_3{\rm U}_3\)-quotients of a some finitely-presented groups.
> 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 \({\operatorname{PSL}}(3,q)\), \({\operatorname{PGL}}(3,q)\), \({\operatorname{PSU}}(3,q)\) or \({\operatorname{PGU}}(3,q)\) is a quotient of \(G\). Similarly, the only \({\rm L}_3{\rm 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.
- Example: L3infinite (ex-ba1556)#
Some groups have infinitely many L3-quotients. This is indicated by one of the L3-quotients
L_3(infty^k),L_3(p^(infty^d)), orL_3(infty^(infty^d)). See below for an interpretation of this output, and how to get more information about the quotients.> 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 \(L_3(p^r)\) or \(U_3(p^r)\), with \(r\le 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) 1
If 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 \({\operatorname{PSL}}(3,p^k)\), \({\operatorname{PGL}}(3, p^k)\), \(\rm{PSU}(3, p^k)\), or \(\rm{PGU}(3,p^k)\). SoL_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 useAddGroupRelationsto 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) ]