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:

• An integer n representing the range [1, n];
• A tuple <a, b> representing the range [a, b];

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

• The index of each subgroup is in the range defined by R;
• 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 subgroups are constructed using a new algorithm due to Sims [C.C. Sims, Computation with Finitely Presented Groups, Cambridge University Press, Encyclopaedia of Mathematics and its Applications 48, 1994.]. 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.

    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.

    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.

    Limit: RngIntElt                    Default: Infinity

Terminate after finding n conjugacy classes of subgroups satisfying the designated conditions.

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

    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.

    Subgroup: GrpFP                     Default: sub< G | >

By specifying a value H for Subgroup, only subgroups containing H will be constructed.

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

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

NextSubgroup(~P, ~G) : Process(Lix), 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.

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.

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 }

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

> 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
]

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