Subgroups of Finite Index

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.

Contents

Low Index Subgroups

If an fp-group G has subgroups of (small) finite index then there algorithms which can be used to find such subgroups and then use them to determine some properties of G.

The function LowIndexSubgroups constructs all conjugacy classes of subgroups of G satisfying the following two conditions:

(i)
The index of each subgroup is in the range defined by R;
(ii)
If the parameter Subgroup defines a subgroup H, then at least one subgroup in each conjugacy class contains the subgroup H.

The subgroups are returned as a sequence of subgroups G, unless otherwise specified by the parameter GeneratingSets (see below). The sequence is sorted by increasing index of the subgroups in G.

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: ∞ 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 FPGroup-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:

n = 0
: No printing (default).
n = 1
: For each class, print a heading and a set of generators for the class representative.
n = 2
: The information printed for n = 1, together with the permutation representation of G on the right cosets of the class representative.
n = 3
: The information printed for n = 2, together with generators for the normalizer N of the class representative, and a system of right coset representatives for N in G.

var Subgroup: GrpFP Default: sub< G | > By specifying a value H for Subgroup, only subgroups containing H will be constructed.

var TimeLimit: RngIntElt Default: 0 (no limit) A time limit in seconds. A value of 0 (default) means no limit.

LowIndexSubgroups(G, R : parameters) : GrpFP, RngIntElt -> [ GrpFP ]
LowIndexSubgroups(G, R : parameters) : GrpFP, RngIntElt -> [ { GrpFPElt } ]
LowIndexSubgroups(G, R: parameters) : GrpFP, <RngIntElt, RngIntElt> -> [ GrpFP ]
LowIndexSubgroups(G, R: parameters) : GrpFP, <RngIntElt, RngIntElt> -> [ { GrpFPElt } ]
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:
(a)
An integer n representing the range [1, n];
(b)
A tuple <a, b> representing the range [a, b];

The generation of subgroups can be controlled by a set of parameters described below. The returned sequence contains the subgroups found and is sorted in order of increasing index in G.

Example GrpFP_Lix1 (H78E43)

(Peter Lorimer) The two graphs known as Tutte's 8-cage and the Conder graph may be constructed as the Cayley graphs of two conjugacy classes of subgroups having index 10 in the finitely presented group 
     < 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> := FPGroup<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
]

Example GrpFP_Lix2 (H78E44)

A fairly surprising application for the low index subgroup algorithm is the enumeration of the conjugacy classes of a finite fp-group. In this example, we consider the group G simeq (PGL)2(9) = < a, b | a2, b3, (ab)8, [a, b]5, [a, (ba)3b - 1]2 >. 
> G<a,b> := FPGroup< a,b | a^2, b^3, (a*b)^8, (a,b)^5,
>                        (a,(b*a)^3*b^-1)^2  >;
> Order(G);
720
In 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;
26
We 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
LowIndexProcess(G, R : parameters) : GrpFP, RngIntElt -> Process(Lix)
LowIndexProcess(G, R: parameters) : GrpFP, < RngIntElt, RngIntElt > -> Process(Lix)
    ColumnMajor: BoolElt                Default: false
    GeneratingSets: BoolElt             Default: false
    Long: [ RngIntElt ]                 Default: []
    Print: RngIntElt                    Default: 0
    Subgroup: GrpFP                     Default: sub< G | >
    TimeLimit: RngIntElt                Default: 0  (no limit)
Create a low index subgroups process. This process may be used to create the conjugacy classes of proper subgroups one 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).

Setting a time limit for a process P limits the total amount of time spent in calls to NextSubgroup. If the time limit is exceeded in a call to NextSubgroup, this call is aborted and P becomes invalid. Further attempts to access P will cause a runtime error. The function IsValid can be used to check whether a process is valid in order to avoid runtime errors in loops or user written functions.

NextSubgroup(~P) : GrpFPLixProc ->
NextSubgroup(~P, ~G) : GrpFPLixProc, GrpFP ->
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 and must be valid. Calling NextSubgroup for an empty process has no effect.
ExtractGroup(P) : GrpFPLixProc -> GrpFP
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. If P is empty or invalid, a runtime error will result.
ExtractGenerators(P) : GrpFPLixProc -> { GrpFPElt }
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. If P is empty or invalid, a runtime error will result.
IsEmpty(P) : GrpFPLixProc -> BoolElt
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 or advance P to the first such subgroup otherwise.
IsValid(P) : GrpFPLixProc -> BoolElt
Return true if the low index process P is valid, that is, no limit has been exceeded. If IsValid is called immediately following the creation of the low index process, then it will return the value false if no subgroups satisfying the specified conditions can be found within the specified time or advance P to the first such subgroup otherwise.

Example GrpFP_Lix3 (H78E45)

We determine all conjugacy classes of subgroups having index at most 15 in the triangle group <a, b | a2, b3, (ab)^ 7 >. 
> G<a, b> := FPGroup< 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 }

Example GrpFP_Lix4 (H78E46)

In this example we illustrate the use of the low index subgroup process by using it to determine whether the simple group PSL(2, 8) is a homomorphic image of the triangle group < x, y | x2, y3, (xy)7 >. 
> 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

Example GrpFP_Lix5 (H78E47)

This example shows how the low index subgroup machinery may be used as part of a function trying to prove that a group is infinite: 
> function MyIsInfinite(G)
>
>  // ...
>
>  // Low index subgroup approach: check whether an obviously
>  //    infinite subgroup can be found in reasonable time.
>  P := LowIndexProcess(G, 30 : TimeLimit := 5);
>  while IsValid(P) and not IsEmpty(P) do
>     H := ExtractGroup(P);
>     NextSubgroup(~P);
>     if 0 in AbelianQuotientInvariants(H) then
>        print "The group G has subgroup:-", H;
>        print "whose abelian quotient is infinite";
>        print "Hence G is infinite.";
>        return true;
>     end if;
>  end while;
>  print "Low index approach fails; trying other methods...";
>
>  // ...
>
> end function;
We try the code fragment on the group < x, z | z3 x z3 x - 1, z5 x2 z2 x2 >. 
> G<x, z> := FPGroup<x,z | z^3*x*z^3*x^-1, z^5*x^2*z^2*x^2 >;
> MyIsInfinite(G);
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.
true
LowIndexNormalSubgroups(G, n: parameters) : GrpFP, RngIntElt -> [ Rec ]
The normal subgroups of finitely presented group G up to index n, n ≤100 000. The subgroups are returned as a sequence of records (ordered by subgroup index) where the ith record contains fields

Group: A presentation of the ith normal subgroup.

Index: The index of the ith normal subgroup in G.

Supergroups: The set of positions in the sequence of the groups which are supergroups of the ith group. 

     PrintLevel: RingIntElt              Default: 0
This parameter may be set to 0, 1 or 2. At 0, the function prints no diagnostic output. At level 1, it outputs details of each normal subgroup being tested for further normal subgroups. Level 2 gives details of each test being performed on each normal subgroup. 
     Simplify: MonStgElt                 Default: "No"

     Workspace: RngIntElt                Default: 1000000000
This sets the Workspace parameter for calls of pQuotient.

The possible values are "No", "Yes" and "LengthLimit". This determines the parameter values passed to the Rewrite(G,H) function, when this function is used. The value "No" sets parameter Simplify:=false. The value "Yes" sets parameter Simplify:=true. The value "LengthLimit" sets parameter LengthLimit:=Index(G,H).

Operations for Subgroups of Finite Index

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 Subsec. Interactive Coset Enumeration.

H ^ u : GrpFP, GrpFPElt -> GrpFP
Conjugate(H, u): GrpFP, GrpFPElt -> GrpFP
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.
H meet K : GrpFP, GrpFP -> GrpFP
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.

Core(G, H) : GrpFP, GrpFP -> GrpFP
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.

GeneratingWords(G, H) : GrpFP, GrpFP -> { GrpFPElt }
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.
MaximalOvergroup(G, H) : GrpFP, GrpFP -> GrpFP
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.

MinimalOvergroup(G, H) : GrpFP, GrpFP -> GrpFP
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.

H ^ G : GrpFP, GrpFP -> GrpFP
NormalClosure(G, H) : GrpFP, GrpFP -> GrpFP
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.

Normaliser(G, H) : GrpFP, GrpFP -> GrpFP
Normalizer(G, H) : GrpFP, GrpFP -> GrpFP
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 H78E31.

This function requires a closed coset table for H in G.

SchreierGenerators(G, H : parameters) : GrpFP, GrpFP -> { GrpFPElt }
    Simplify: BoolElt                   Default: true
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.

If 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.

SchreierSystem(G, H) : GrpFP, GrpFP -> {@ GrpFPElt @}, Map
Transversal(G, H) : GrpFP, GrpFP -> {@ GrpFPElt @}, Map
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.

Transversal(G, H, K) : GrpFP, GrpFP, GrpFP -> {@ GrpFPElt @}, Map
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.

Example GrpFP_SubgroupConstructions (H78E48)

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 | r2, s4, (r, s)2 >. 

> p4g<r, s> := FPGroup< 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);
8
We 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 table
Note, 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

Example GrpFP_SchreierGenerators (H78E49)

Consider the group G given by the presentation < x, y | x2, y3, (xy)7 >. 
> G<x,y> := FPGroup< 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 table
A set of generators for H can be obtained e.g. with the function SchreierGenerators. 
> sgH := SchreierGenerators(G, H);
> #sgH;
6
By 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

Properties of Subgroups

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 Subsec. Interactive Coset Enumeration.

u in H : GrpFPElt, GrpFP -> BoolElt
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.

u notin H : GrpFPElt, GrpFP -> BoolElt
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.

H eq K : GrpFP, GrpFP -> BoolElt
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.

H ne K : GrpFP, GrpFP -> BoolElt
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.

H subset K : GrpFP, GrpFP -> BoolElt
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.

H notsubset K : GrpFP, GrpFP -> BoolElt
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.

IsConjugate(G, H, K) : GrpFP, GrpFP, GrpFP -> BoolElt, GrpFPElt
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.

IsNormal(G, H) : GrpFP, GrpFP -> BoolElt
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.

IsMaximal(G, H) : GrpFP, GrpFP -> BoolElt
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.

IsSelfNormalizing(G, H) : GrpFP, GrpFP -> BoolElt
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 H78E31.

This function requires a closed coset table for H in G.

Example GrpFP_SubgroupOps (H78E50)

We illustrate some of the subgroup predicates by applying them to some subgroups of the two-dimensional space group p4g = < r, s | r2, s4, (r, s)2 > from Example H78E48. 
> p4g<r, s> := FPGroup< 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;
false
We check for normality of h and k in p4g. 
> IsNormal(p4g, h);
false
> IsNormal(p4g, k);
true
We 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;
true
We 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^-1
I.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

Example GrpFP_BuildSubgroups (H78E51)

The constructions of the previous section together with the Boolean function IsMaximal may be used to locate large maximal subgroups in a finite group. Consider the Hall-Janko group J2, which may be defined by the presentation <a, b, c | a^3, b^3, c^3, abab^{-1}a^{-1}b^{-1}, (ca)^5, (cb)^5, (cb^{-1}cb)^2, a^{-1}baca^{-1}bac^{-1}a^{-1}b^{-1}ac^{-1}, aba^{-1}caba^{-1}c^{-1}ab^{-1}a^{-1}c^{-1}>. We examine subgroups generated by pairs of randomly chosen short words. Whenever we obtain a proper subgroup, if it is not already maximal we replace it by a maximal subgroup that contains it. 
> J2<a, b, c> := FPGroup<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.
V2.28, 13 July 2023