|
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.
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.
(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
]
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 | a 2, b 3, (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, ~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.
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.
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.
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.
We determine all conjugacy classes of subgroups having index at most
15 in the triangle group <a, b | a 2, b 3, (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 }
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 | x 2, y 3, (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
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 | z 3 x z 3 x - 1, z 5 x 2 z 2 x 2 >.
> 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
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).
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.
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.
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.
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 H80E31.
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.
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
Consider the group G given by the presentation
< x, y | x 2, y 3, (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
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.
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
H80E31.
This function requires a closed coset table for H in G.
We illustrate some of the subgroup predicates by applying
them to some subgroups of the two-dimensional space
group p4g = < r, s | r 2, s 4, (r, s) 2 > from Example
H80E48.
> 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
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 J 2, 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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|