The functions in this section are concerned with the construction of subgroups of finite index. We first describe a method for computing all subgroups whose index does not exceed some (modest) integer bound. The next family of functions are concerned with constructing new subgroups of finite index from one or more known ones.
The function LowIndexSubgroups constructs all conjugacy classes of subgroups of G satisfying the following two conditions:
The subgroups are constructed using an algorithm due to Sims [Sim94, sect. 5.6]. This algorithm constructs the coset tables by using a backtrack algorithm. At a given position in the coset table, coset definitions are made systematically. Once a new definition has been made, the group relations are traced in an attempt to deduce further entries or to infer that this partial table will not extend to a table corresponding to a new class of subgroups. When either it cannot define a new entry, or when a complete table has been constructed, the algorithm backtracks to try the next possibility (this may introduce a new row, increasing the index). This algorithm may also be run as a process in such a way that the subgroups are returned one at a time, thereby allowing the user to analyze each subgroup as soon as it is found.
var ColumnMajor: BoolElt Default: false
If ColumnMajor is set false (default), then the location for a new definition in the coset table is determined by searching the table in row major order for undefined entries. If ColumnMajor is set true, then the position for a new definition is determined by searching the table in column major order. If the presentation for G contains explicit relators expressing the fact that certain of the generators have large order, then the presentation should be organized so that these generators appear first and the column major order should be selected for new coset definition. This strategy often leads to greatly improved performance.
var GeneratingSets: BoolElt Default: false
The conjugacy classes of subgroups are returned in the form of a sequence of sets of words, where the i-th set is a generating set for a representative subgroup from the i-th conjugacy class of subgroups satisfying the given conditions. This is a much more compact representation than returning the subgroups as a sequence of actual subgroups of G and should be used when a very large number of subgroups is expected, as there may be insufficient space to store each of them as a subgroup.
var Limit: RngIntElt Default: Infinity
Terminate after finding n conjugacy classes of subgroups satisfying the designated conditions.
var Long: [ RngIntElt ] Default: []
This option enables the user to designate certain of the defining relators for G as long relators. The relators of G are numbered from 1 to r, in the order they appear in the quo- or Group-constructors. The value L of Long is a subset of the integer set { 1, ..., r}. Magma interprets the relators whose numbers appear in L as long relators. A relator designated as long is not used during the construction of a coset table. Rather, it is applied once a complete table has been found. There is some evidence to suggest that better performance is achieved in those groups having one or more very long relators by deferring application of these relators until such time as a complete coset table has been obtained.
var Print: RngIntElt Default: 0
A description of each class of subgroups may be printed immediately after it is constructed. The value n assigned to the Print parameter specifies just what information is to be printed, according to the following rules:
By specifying a value H for Subgroup, only subgroups containing H will be constructed.
Given a finitely presented group G (possibly the free group), and an expression R defining a positive integer range (see below), determine the conjugacy classes of subgroups of G whose indices lie in the range specified by R. The subgroups are generated by systematically building all coset tables consistent with the defining relations for G and which satisfy the range condition R. The argument R is one of the following:The generation of subgroups can be controlled by a set of parameters described below.
- An integer n representing the range [1, n];
- A tuple <a, b> representing the range [a, b];
< q, r, s, h, a | h^3 = a^2 = p^2 = 1, p^h = p, p^a = q, q^h = r, r^a = s,
h^s = h^(-1), r^h = pqr, sr = pqrs, pq = qp, pr = rp, ps = sp, qr = rq, qs = sq>.
We use the low index function to construct these subgroups.
> G<p, q, r, s, h, a> := Group<p, q, r, s, h, a |
> h^3 = a^2 = p^2 = 1, p^h = p, p^a = q,
> q^h = r, r^a = s, h^s = h^-1, r^h = p * q * r,
> s * r = p * q * r * s, p * q = q * p,
> p * r = r * p, p * s = s * p, q * r = r * q,
> q * s = s * q>;
> LowIndexSubgroups(G, <10, 10>);
[
Finitely presented group on 6 generators
Index in group G is 10 = 2 * 5
Generators as words in group G
$.1 = p
$.2 = s
$.3 = h
$.4 = q^-2
$.5 = a * h^-1 * a * r^-1
$.6 = a * h * a * h^-1 * a * q^-1,
Finitely presented group on 6 generators
Index in group G is 10 = 2 * 5
Generators as words in group G
$.1 = p
$.2 = s
$.3 = h
$.4 = q^-2
$.5 = a * h^-1 * a * r^-1
$.6 = a * h * a * h^-1 * a
]
> G<a,b> := Group< a,b | a^2, b^3, (a*b)^8, (a,b)^5, > (a,(b*a)^3*b^-1)^2 >; > Order(G); 720In an infinite fp-group, finding all classes of subgroups up to an index of 720 by applying the low index subgroup algorithm, would be extremely hard. In the case of the finite group G, however, we succeed.
> time sgG := LowIndexSubgroups(G, Order(G)); Time: 31.859 > #sgG; 26We get a list of 26 representatives of the conjugacy classes of subgroups. For every representative, its index in G and a set of generating words are known. We just have a look at two of them.
> sgG[10];
Finitely presented group on 2 generators
Index in group G is 60 = 2^2 * 3 * 5
Generators as words in group G
$.1 = b
$.2 = a * b * a * b * a * b^-1 * a * b * a * b * a * b^-1 * a
* b^-1 * a
> sgG[21];
Finitely presented group on 1 generator
Index in group G is 180 = 2^2 * 3^2 * 5
Generators as words in group G
$.1 = (b * a)^2
ColumnMajor: BoolElt Default: false
GeneratingSets: BoolElt Default: false
Long: [ RngIntElt ] Default: []
Print: RngIntElt Default: 0
Subgroup: GrpFP Default: sub< G | >
Create a low index subgroups process. This process may be used to create the conjugacy classes of proper subgroups one at at time, with control being handed back to the Magma language processor each time a new class of subgroups is found. This function returns a process which is used by the function NextSubgroup to actually produce the subgroups.The arguments and parameters have the same interpretation as for the function LowIndexSubgroups, except that Limit is not available (since the same effect can be achieved by limiting the number of calls to NextSubgroup).
Given a low index subgroups process P, construct the next conjugacy class of proper subgroups. The process P must have been previously created using the function LowIndexProcess.
Extract a representative subgroup for the conjugacy class currently defined by the low index process P. The subgroup extracted will be the one found by the previous invocation of NextSubgroup, or the first subgroup if NextSubgroup has never been invoked on this process. Note that ExtractGroup will not search for a new subgroup.
Extract a generating set for the representative subgroup of the conjugacy class currently defined by the low index process P. The subgroup extracted will be the one found by the previous invocation of NextSubgroup, or the first subgroup if NextSubgroup has never been invoked on this process. Note that ExtractGenerators will not search for a new subgroup.
Return true if the low index process P has already found all conjugacy classes of subgroups. If IsEmpty is called immediately following the creation of the low index process, then it will return the value false if there are no subgroups satisfying the specified conditions.
> G<a, b> := Group< a, b | a^2, b^3, (a*b)^7 >;
> L := LowIndexSubgroups(G, 15: Print := 1);
Subgroup class 1 Index 7 Length 7 Subgroup generators :-
{ a, b * a * b^-1, b^-1 * a * b * a * b^-1 * a * b }
Subgroup class 2 Index 7 Length 7 Subgroup generators :-
{ a, b^-1 * a * b^-1 * a * b * a * b, b * a * b^-1 }
Subgroup class 3 Index 15 Length 15 Subgroup generators :-
{ a, b^-1 * a * b * a * b^-1 * a * b * a * b^-1 * a * b, b * a * b^-1 }
Subgroup class 4 Index 15 Length 15 Subgroup generators :-
{ a, b * a * b^-1, b^-1 * a * b^-1 * a * b * a * b^-1 * a * b * a * b }
Subgroup class 5 Index 14 Length 14 Subgroup generators :-
{ a, b^-1 * a * b * a * b^-1 * a * b * a * b * a * b^-1 * a * b, b * a * b^-1 }
Subgroup class 6 Index 14 Length 7 Subgroup generators :-
{ a, b^-1 * a * b * a * b^-1 * a * b * a * b^-1 * a * b * a * b^-1 * a * b, b *
a * b * a * b^-1 }
Subgroup class 7 Index 14 Length 14 Subgroup generators :-
{ a, b^-1 * a * b * a * b^-1 * a * b^-1 * a * b * a * b * a * b^-1 * a * b, b *
a * b * a * b^-1 }
Subgroup class 8 Index 14 Length 7 Subgroup generators :-
{ a, b * a * b * a * b^-1 * a * b^-1 * a * b * a * b * a * b^-1 * a * b^-1, b^-1
* a * b * a * b }
Subgroup class 9 Index 15 Length 15 Subgroup generators :-
{ a, b * a * b * a * b^-1 * a * b^-1, b^-1 * a * b^-1 * a * b * a * b }
Subgroup class 10 Index 9 Length 9 Subgroup generators :-
{ a, b * a * b * a * b * a * b^-1 }
Subgroup class 11 Index 14 Length 7 Subgroup generators :-
{ a, b * a * b * a * b * a * b^-1 * a * b, b * a * b^-1 * a * b * a * b^-1 }
Subgroup class 12 Index 14 Length 7 Subgroup generators :-
{ a, b * a * b * a * b^-1 * a * b * a * b, b * a * b^-1 * a * b * a * b^-1 }
Subgroup class 13 Index 14 Length 7 Subgroup generators :-
{ a, b^-1 * a * b * a * b^-1 * a * b, b * a * b * a * b * a * b^-1 * a * b^-1 }
Subgroup class 14 Index 14 Length 7 Subgroup generators :-
{ a, b * a * b * a * b^-1 * a * b * a * b, b^-1 * a * b * a * b^-1 * a * b }
Subgroup class 15 Index 14 Length 14 Subgroup generators :-
{ a, b^-1 * a * b * a * b * a * b^-1 * a * b, b * a * b * a * b * a * b^-1 * a *
b^-1 }
Subgroup class 16 Index 8 Length 8 Subgroup generators :-
{ b, a * b * a * b * a * b^-1 * a }
> F<x, y> := FreeGroup(2);
> G<x, y> := quo< F | x^2, y^3, (x*y)^7 >;
> LP := LowIndexProcess(G, 30);
> i := 0;
> while i le 100 and not IsEmpty(LP) do
> H := ExtractGroup(LP);
> NextSubgroup(~LP);
> P := CosetImage(G, H);
> if Order(P) eq 504 and IsSimple(P) then
> print "The group G has L(2, 8) as a homomorphic image.";
> print "It is afforded by the subgroup:-", H;
> break;
> end if;
> i +:= 1;
> end while;
The group G has L(2, 8) as a homomorphic image.
It is afforded by the subgroup:-
Finitely presented group H on 4 generators
Index in group G is 28 = 2^2 * 7
Generators as words in group G
H.1 = x
H.2 = y * x * y^-1
H.3 = y^-1 * x * y * x * y^-1 * x * y * x * y^-1 * x * y * x * y^-1 *
x * y * x * y
H.4 = y^-1 * x * y * x * y^-1 * x * y^-1 * x * y * x * y^-1 * x * y *
x * y * x * y^-1 * x * y
> F<x, z> := FreeGroup(2);
> G<x, z> := quo< F | z^3*x*z^3*x^-1, z^5*x^2*z^2*x^2 >;
> G;
Finitely presented group G on 2 generators
Relations
z^3 * x * z^3 * x^-1 = Id(G)
z^5 * x^2 * z^2 * x^2 = Id(G)
> LP := LowIndexProcess(G, 30);
> i := 0;
> found := false;
> while i le 100 and not IsEmpty(LP) do
> H := ExtractGroup(LP);
> NextSubgroup(~LP);
> if 0 in AbelianQuotientInvariants(H) then
> print "The group G has subgroup:-", H;
> print "whose abelian quotient has structure", AQInvariants(H);
> print "Hence G is infinite.";
> found := true;
> break;
> end if;
> i +:= 1;
> end while;
> if not found then print "Test fails."; end if;
The group G has subgroup:-
Finitely presented group H on 4 generators
Index in group G is 4 = 2^2
Generators as words in group G
H.1 = x
H.2 = z * x * z
H.3 = z^3
H.4 = z * x^-1 * z * x * z^-1
whose abelian quotient has structure [ 2, 6, 0 ]
Hence G is infinite.
Most operations described in this subsection require a closed coset table for at least one subgroup of an fp-group. If a closed coset table is needed and has not been computed, a coset enumeration will be invoked. If the coset enumeration does not produce a closed coset table, a runtime error is reported.
Experienced users can control the behaviour of such indirectly invoked 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 Chapter FP GROUPS - ADVANCED FEATURES.
Given an fp-group H and a word u in an fp-group K, such that H and K are subgroups of some common fp-group G and words in terms of the generators of G are known for the generators of both H and K, construct the subgroup of G obtained by conjugating H by u.
Given subgroups H and K, both of finite index in some fp-group G, return the subgroup which is the intersection of H and K.
This function requires closed coset tables for both, H and K in G.
Given a subgroup H of finite index in the fp-group G, construct the core of H in G.
This function requires a closed coset table for H in G.
Given a subgroup H of the fp-group G, this function returns a set of words in the generators of G, generating H as a subgroup of G (assuming such words are known or can be constructed). Note that the returned generating set does not necessarily correspond to the internal generators of H. In particular, generating words obtained using the function GeneratingWords cannot be used to coerce elements from H to G.
Given a subgroup H of finite index in the fp-group G, construct a maximal overgroup of H in G. A maximal overgroup of H is a maximal subgroup of G that contains H. If H is already maximal, the group G is returned.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, construct a minimal overgroup of H in G. A minimal overgroup of a subgroup H is a subgroup K of G such that K contains H as a maximal subgroup. If H is already maximal in G, the group G is returned.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, construct the normal closure of H in G.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, construct the normaliser of H in G. For a sample application of this function, see Example H19E34.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, return the Schreier generators for H as a set of words in G.
Simplify: BoolElt Default: trueIf the parameter Simplify is set to true (default), a heuristic method of eliminating redundant Schreier generators is applied. To switch this feature off, set Simplify to false.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, construct a (right) Schreier system of coset representatives for H in G. The function returns(a) the Schreier system as a set of words in G;
(b) the corresponding Schreier coset function.
This function requires a closed coset table for H in G.
Given subgroups H and K, both of finite index in the fp-group G, return an indexed set of words which comprise a set of representatives for the double cosets HuK of H and K in G, as well as a map from G to the representatives. It should be noted that this function is evaluated by first constructing the right cosets of H in G and then computing the orbits of the cosets under the action of the generators of the subgroup K.
This function requires a closed coset table for H in G.
We illustrate some of the subgroup constructions by using them to construct subgroups of small index in the two-dimensional space group p4g which has the presentation < r, s | r^2, s^4, (r, s)^2 >.
> p4g<r, s> := Group< r, s | r^2 = s^4 = (r*s^-1*r*s)^2 = 1 >;
> p4g;
Finitely presented group p4g on 2 generators
Relations
r^2 = Id(p4g)
s^4 = Id(p4g)
(r * s^-1 * r * s)^2 = Id(p4g)
We define two subgroups of p4g and compute their indices in p4g.
> h := sub< p4g | (s^-1*r)^4, s*r >; > k := sub< p4g | (s^-1*r)^2, (s*r)^2 >; > Index(p4g, h); 8 > Index(p4g, k); 8We construct the normal closure of h in p4g.
> n := NormalClosure(p4g, h);
> n;
Finitely presented group n on 6 generators
Index in group p4g is 2
Generators as words in group p4g
n.1 = (s^-1 * r)^4
n.2 = s * r
n.3 = r * s
n.4 = r^-1 * s * r^2
n.5 = s^2 * r * s^-1
n.6 = r * s
Next, we construct a subgroup of p4g containing h as maximal subgroup ...
> m := MinimalOvergroup(p4g, h);
> m;
Finitely presented group m on 3 generators
Index in group p4g is 4 = 2^2
Generators as words in group p4g
m.1 = (s^-1 * r)^4
m.2 = s * r
m.3 = (r * s)^2
... and a maximal subgroup of p4g containing k.
> n := MaximalOvergroup(p4g, k);
> n;
Finitely presented group n on 4 generators
Index in group p4g is 2
Generators as words in group p4g
n.1 = (s^-1 * r)^2
n.2 = (s * r)^2
n.3 = r
n.4 = s^2
Finally, we construct a transversal in p4g for the normaliser of h in
p4g ...
> T := Transversal(p4g, Normaliser(p4g, h));
> T;
{@ Id(p4g), r, s^-1, r * s @}
... compute the intersection of h and the conjugate of h by
r ... > l := h meet h^r; > l; Finitely presented group l Index in group p4g is 32 = 2^5 Subgroup of group p4g defined by coset table... and construct the core of h in p4g.
> c := Core(p4g, h); > c; Finitely presented group c Index in group p4g is 32 = 2^5 Subgroup of group p4g defined by coset tableNote, that the two subgroups l and c constructed last are defined as finite index subgroups of p4g by a coset table and that there are no generators known for them. Generators can be obtained e.g. by using the function GeneratingWords. We show this for the subgroup l.
> GeneratingWords(p4g, l);
{ (s * r)^4, (s^-1 * r)^4 }
Once computed, these generators are memorised. Compare the result of printing
l to the output obtained above.
> l;
Finitely presented group l on 2 generators
Index in group p4g is 32 = 2^5
Generators as words in group p4g
l.1 = (s * r)^4
l.2 = (s^-1 * r)^4
> G<x,y> := Group< x,y | x^2, y^3, (x*y)^7 >;We construct the subgroups of index less than or equal to 7 using the low index algorithm.
> L := LowIndexSubgroups(G, 7);
> L;
[
Finitely presented group on 2 generators
Index in group G is 1
Generators as words in group G
$.1 = x
$.2 = y,
Finitely presented group on 3 generators
Index in group G is 7
Generators as words in group G
$.1 = x
$.2 = y * x * y^-1
$.3 = y^-1 * x * y^-1 * x * y * x * y,
Finitely presented group on 3 generators
Index in group G is 7
Generators as words in group G
$.1 = x
$.2 = y * x * y^-1
$.3 = y^-1 * x * y * x * y^-1 * x * y
]
We define a subgroup as the core of one of the subgroups of index 7. The
function Core returns a subgroup of G defined by a coset
table.
> H := Core(G, L[2]); > H; Finitely presented group H Index in group G is 168 = 2^3 * 3 * 7 Subgroup of group G defined by coset tableA set of generators for H can be obtained e.g. with the function SchreierGenerators.
> sgH := SchreierGenerators(G, H); > #sgH; 6By default, SchreierGenerators returns a reduced generating set. The unreduced set of Schreier generators can be obtained by setting the value of the parameter Simplify to false.
> sgHu := SchreierGenerators(G, H : Simplify := false); > #sgHu; 85
The operations described in this subsection all require a closed coset table for at least one subgroup of an fp-group. If a closed coset table is needed and has not been computed, a coset enumeration will be invoked. If the coset enumeration does not produce a closed coset table, a runtime error is reported.
Experienced users can control the behaviour of such indirectly invoked 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 Chapter FP GROUPS - ADVANCED FEATURES.
Given an fp-group H and a word u in an fp-group K, such that H and K are subgroups of some common fp-group G, H is of finite index in G, and words for the generators of K in terms of the generators of G are known, return true if u is an element of H and false otherwise.
This function requires a closed coset table for H in G.
Given an fp-group H and a word u in an fp-group K, such that H and K are subgroups of some common fp-group G, H is of finite index in G, and words for the generators of K in terms of the generators of G are known, return true if u is not an element of H and false otherwise.
This function requires a closed coset table for H in G.
Given subgroups H and K, both of finite index in the fp-group G, return true if H and K are equal and false otherwise.
This function may require closed coset tables for both, H and K in G.
Given subgroups H and K, both of finite index in the fp-group G, return true if H and K are not equal and false otherwise.
This function may require closed coset tables for both, H and K in G.
Given subgroups H and K, both of finite index in the fp-group G, return true if H is contained in K and false otherwise.
This function requires a closed coset table for K in G.
Given subgroups H and K, both of finite index in the fp-group G, return true if H is not contained in K and false otherwise.
This function requires a closed coset table for K in G.
Given subgroups H and K, both of finite index in the fp-group G, return true if H and K are conjugate subgroups of G and false otherwise. If H and K are conjugate in G, a conjugating element is returned as second return value.
This function requires a closed coset table for both, H and K in G.
Given a subgroup H of finite index in the fp-group G, return true if H is a normal subgroup of G and false otherwise.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, return true if H is a maximal subgroup of G and false otherwise.
This function requires a closed coset table for H in G.
Given a subgroup H of finite index in the fp-group G, return true if H is a self-normalizing subgroup of G and false otherwise. For a sample application of this function, see Example H19E34.
This function requires a closed coset table for H in G.
> p4g<r, s> := Group< r, s | r^2 = s^4 = (r*s^-1*r*s)^2 = 1 >; > h := sub< p4g | (s^-1*r)^4, s*r >; > k := sub< p4g | (s^-1*r)^2, (s*r)^2 >;h and k have the same index in p4g ...
> Index(p4g, h); 8 > Index(p4g, k); 8... but they are not equal.
> h eq k; falseWe check for normality of h and k in p4g.
> IsNormal(p4g, h); false > IsNormal(p4g, k); trueWe construct the normal closure of h in p4g.
> n := NormalClosure(p4g, h);We see that it is maximal ...
> IsMaximal(p4g, n); true... and that it contains k.
> k subset n; trueWe define another subgroup of p4g.
> l := sub< p4g | (s*r)^4, s^-1*r >;In fact, it is conjugate to h.
> IsConjugate(p4g, h, l); true r^-1I.e. l = h^(r^(-1)). The intersection of h and h^(r^(-1)) already yields the core of h in p4g.
> h meet l eq Core(p4g, h); true
> J2<a, b, c> := Group<a, b, c | a^3, b^3, c^3, a*b*a*b^-1*a^-1*b^-1, (c*a)^5,
> (c*b)^5, (c*b^-1*c*b)^2,
> a^-1*b*a*c*a^-1*b*a*c^-1*a^-1*b^-1*a*c^-1,
> a*b*a^-1*c*a*b*a^-1*c^-1*a*b^-1*a^-1*c^-1>;
>
> Seen := { 0, 1 };
> Found := { };
> Sgs := [ ];
> for i := 1 to 30 do
> u := Random(J2, 1, 1);
> v := Random(J2, 3, 5);
> H := sub< J2 | u, v >;
> Indx := Index(J2, H);
> if Indx notin Seen then
> Include(~Seen, Indx);
> if not IsMaximal(J2, H) then
> H := MaximalOvergroup(J2, H);
> end if;
> if Indx notin Found then
> Include(~Sgs, H);
> Include(~Seen, Indx);
> Include(~Found, Indx);
> end if;
> end if;
> end for;
> Sgs;
[
Finitely presented group on 3 generators
Index in group J2 is 315 = 3^2 * 5 * 7
Generators as words in group J2
$.1 = b^-1
$.2 = a^-2 * c * a^-1
$.3 = c,
Finitely presented group on 3 generators
Index in group J2 is 1008 = 2^4 * 3^2 * 7
Generators as words in group J2
$.1 = b^-1
$.2 = c^-1 * a^-1 * c^-1 * b
$.3 = a * c * b * c^-1 * a^-1 * c * b * c^-1,
Finitely presented group on 3 generators
Index in group J2 is 100 = 2^2 * 5^2
Generators as words in group J2
$.1 = c
$.2 = (b * a^-1)^2
$.3 = a * b^-1
]
Thus after taking 30 2-generator random subgroups, we have obtained
three maximal subgroups, including the two largest maximal subgroups.