|
Constructor:
sub < G | L > :
Construct the subgroup H of the fp-group G generated by the words
specified by the terms of the generator list L = L1, ..., Lr.
A term Li of the generator list may consist of a word, a set or sequence
of words, a subgroup or a set or sequence of subgroups.
The collection of words and groups specified by the list must all
belong to the group G and H will be constructed as a subgroup
of G.
Notes:
- (i)
- The generators of H consist of the words specified directly by
terms Li together with the stored generating words for any
groups specified by terms of Li. Repetitions of an element and
occurrences of the identity element are removed (unless H is trivial).
If the sub-constructor is invoked with an empty list L, the
trivial subgroup will be constructed.
The group (8, 7 | 2, 3) is defined by the presentation
< a, b | a 8, b 7, (ab) 2, (ab - 1) 3 >,
and has a subgroup of index 448 generated by the words a 2 and ab - 1:
> G<a, b> := FPGroup<a, b| a^8, b^7, (a * b)^2, (a * b^-1)^3>;
> G;
Finitely presented group G on 2 generators
Relations
a^8 = Id(G)
b^7 = Id(G)
(a * b)^2 = Id(G)
(a * b^-1)^3 = Id(G)
> H<x, y> := sub< G | a^2, a * b^-1 >;
> H;
Finitely presented group H on 2 generators
Generators as words in group G
x = a^2
y = a * b^-1
Intrinsics:
Index (G, H) : The index of H in G.
CosetTable (G, H) : The coset table for H in G (right action).
Transversal (G, H) : A (right) Schreier system of coset representatives
for H in G together with the coset map.
SchreierGenerators (G, H) : Schreier generators for H as a set of words
in G.
ToddCoxeter (G, H) : The Todd--Coxeter procedure for coset enumeration is
applied to construct the coset table for the subgroup H of fp-group G. The
convention here is that G acts on the right. If successful the index of H in
G and the coset table are returned otherwise zero is returned for the index.
SetGlobalTCParameters ( : parameters) : Set the parameter values used for
indirect invocations of the Todd-Coxeter coset enumeration procedure.
UnsetGlobalTCParameters ( ) : Restore the default values for the parameters
used for indirect invocations of the Todd--Coxeter coset enumeration procedure.
Notes:
- (i)
- While strictly speaking the user does not need to invoke ToddCoxeter
explicitly, it underpins many of the algorithms used to compute with subgroups in
fp-groups and so a serious user needs to understand how to set the parameters in
the case of computations that involve hard coset enumerations.
- (ii)
- The ToddCoxeter intrinsic has a large number of parameters which
provide the user with control over the enumeration. Descriptions of these may be found
in chapter FINITELY PRESENTED GROUPS. Perhaps the most useful are CosetLimit which specifies
the number of cosets which may be defined before abandoning an enumeration,
Time which limits the maximum CPU time that can be expended, and Strategy
which if set to "Hard" chooses a strategy which has the best chance of
succeeding with a hard enumeration.
- (iii)
- Two intrinsics, SetGlobalTCParameters and
UnsetGlobalTCParameters, allow a user to set the parameters for
implicit calls to the Todd--Coxeter algorithm.
- (iv)
- Descriptions of the Todd-Coxeter algorithm can be found in
Chapter 5 of Holt [HEO05] and Chapter 5 of Sims [Sim94].
These intrinsics are illustrated using the infinite group G defined by
x 2 = y 3 = (xy) 7 = 1
and H a certain subgroup of G having index 15.
> G<x, y> := FPGroup< x, y | x^2, y^3, (x*y)^7 >;
> G;
Finitely presented group G on 2 generators
Relations
x^2 = Id(G)
y^3 = Id(G)
(x * y)^7 = Id(G)
>
> H := sub< G | x, y*x*y*x*y^-1*x*y^-1, y^-1*x*y^-1*x*y*x*y>;
> Index(G, H);
15
>
> CosetTable(G, H);
Mapping from: Cartesian Product<{ 1 .. 15 }, GrpFP: G> to { 1 .. 15 }
$1 $2 -$2
1. 1 2 3
2. 4 3 1
3. 5 1 2
4. 2 6 7
5. 3 8 9
6. 6 7 4
7. 10 4 6
8. 11 9 5
9. 9 5 8
10. 7 11 12
11. 8 12 10
12. 13 10 11
13. 12 14 15
14. 15 15 13
15. 14 13 14
>
> T := Transversal(G, H);
> T;
{@ Id(G), y, y^-1, y*x, y^-1*x, y*x*y, y*x*y^-1, x^y, y^-1*x*y^-1,
y*x*y^-1*x, y^-1*x*y*x, y*x*y^-1*x*y^-1, y*x*y^-1*x*y^-1*x,
y*x*y^-1*x*y^-1*x*y, y*x*y^-1*x*y^-1*x*y^-1 @}
The columns of the coset table for a subgroup H in fp-group G are
permutations giving the action of the generators of G on the cosets of H.
If these columns are treated as permutation generators of a group P then the
homomorphism φ : G -> P is an epimorphism of G. This quotient
group and its kernel often provide useful information about the structure of G.
In Magma the group G acts on the right of cosets and this should be assumed
unless left action is explicitly stated.
Intrinsics:
CosetAction (G, H) : The permutation representation φ of G given by
the action of G on the cosets of H in G. It returns φ and the image group
φ(G). If the kernel of φ can be computed easily then it will also be
returned.
CosetImage (G, H) : The image of the permutation action of G on the
cosets of H.
CosetKernel (G, H) : The kernel of the permutation action of G on the
cosets of H.
The exceptional group G 2(3) is a homomorph of the fp-group G defined below.
First, a permutation representation G1 on 351 points is constructed for
G 2(3), and then the subgroup generated by the images of the first four
generators of G in G1 is computed. (The permutation group intrinsics are
described in chapter PERMUTATION GROUPS.)
> F<a,b,c,d,y,x,w> := FreeGroup(7);
> z := y*c*a^2*b;
> u := x*d;
> t := w*c*a*d*b^2*c;
> G<a,b,c,d,y,x,w>, psi :=
> quo< F | a^4, b^4, c^2, d^2, (a,b), (a*c)^2, (b*c)^2,
> (c*d)^2, d*a*d*b^-1, y^3, (a^-1*b)^y*d*a^-1*b^-1,
> (c*d*a^-1*b)^y*b^-1*a*d*c, a*d*y*d*a^-1*y, x^3,
> a^x*b^-1, b^x*a*b, c^x*c, (x*d)^2, (u*z)^6, w^3,
> (w,y), (a*b)^w*b^-1*a*d*c, (c*d*a^-1*b)^w*d*c*b^2,
> (b^2*c*d)^w*a^-1*b^-1, (c*a^2*b*w)^2,
> (a^-1*b)^w*d*a^-1*b^-1, (t*u)^3 >;
> z1 := psi(z);
> u1 := psi(u);
> t1 := psi(t);
> H := sub< G | z1*a^2*b^2, u1*c, t1*a^2*b^2 >;
> phi, G1, K := CosetAction(G, H);
> Degree(G1);
351
> print Order(G1), FactoredOrder(G1);
4245696 [ <2, 6>, <3, 6>, <7, 1>, <13, 1> ]
> CompositionFactors(G1);
G
| G(2, 3)
1
> S := sub< G1 | phi(a), phi(b), phi(c), phi(d) >;
> BSGS(S);
> S;
Permutation group S of degree 351
Order = 64 = 2^6
Thus the images of a, b, c and d in G1 generate the Sylow 2-subgroup of G 2(3).
If an fp-group G has subgroups of finite index and their index is
moderate then they may be enumerated. There are two methods, the first
of which enumerates all subgroups down to a given index while the second
enumerates normal subgroups down to a given index.
Intrinsics:
LowIndexSubgroups (G, R) : Given a 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 expression R is either an integer n which indicates
the range [1..n] or a tuple < m, n > which represents
the range [m..n].
LowIndexNormalSubgroups(G, n) : The normal subgroups of G having index
in the range [1..n] are enumerated. The subgroups are returned as a sequence of
records (ordered by subgroup index). The upper bound for n is 1010.
Notes:
- (i)
- The LowIndexSubgroups intrinsic has many applications and in
favourable situations it can locate subgroups of index several hundred. The
intrinsic also has parameters which can be found in chapter FINITELY PRESENTED GROUPS.
Two useful parameters are:
- -
- Limit which accepts a positive integer giving a limit on the
the number of subgroups satisfying expression R that are sought.
- -
- Print which accepts an integer in the range [0 ... 3]
which controls verbose output. Thus 0 specifies no verbose output while the
integers greater than 0 turn on increasing amounts of verbose output.
- (ii)
- Another version of the LowIndexSubgroups intrinsic implements
what is called a process. This version can be restarted and returns each
subgroup immediately it is found. If more subgroups are needed then the computation
is restarted. This is particularly useful in that a subgroup satisfying the user's
requirements may be found long before all the subgroups specified by R are computed.
- (iii)
- The algorithm used to find subgroups of small index is described in
Section 5.6 of Sims [Sim94] and Section 5.4 of Holt [HEO05].
(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
The low index intrinsic will be used 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 subgroups of a finite fp-group.
Consider the group
(PGL) 2(9) simeq G =
< 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 conjugacy classes of subgroups up to index
720 using the low index subgroup algorithm would be extremely difficult. In the
case of a fp-group G of order 720, however, it is not so difficult.
> time sgG := LowIndexSubgroups(G, Order(G));
Time: 31.859
> #sgG;
26
A list of representatives of the 26 conjugacy classes of subgroups of G
have been found. For every representative, its index in G and a set of
generating words are stored. Here are two examples:-
> 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
Operations on subgroups that construct a new subgroup or quotient group are
listed. Here G will be a finitely presented group with a presentation while
H and K will be subgroups having finite index in G unless otherwise
stated. The subgroups H and K are assumed to be defined either by
generators as words in G or by the coset table for H in G.
Intrinsics:
Hu : The conjugate Hu where u is a word in G.
H meet K : The intersection of subgroups H and K as a subgroup of G.
G / H : The quotient group of G by the normal closure of subgroup H.
Core (G, H) : The core of H in G.
DerivedSubgroup (G) : The derived subgroup of G.
TorsionFreeRank (G) : The torsion-free rank of the derived quotient
group of G.
MaximalOverGroup (G, H) : A maximal overgroup of H in G.
MinimalOverGroup (G, H) : A minimal overgroup of H in G.
NormalClosure (G, H) : The normal closure of H in G.
Normaliser (G, H) : The normaliser of H in G.
Notes:
- (i)
- The first four intrinsics involve using the Todd--Coxeter algorithm.
In the case of
DerivedSubgroup it is necessary for Magma to be able to
compute the coset table for the derived group of G. Thus the intrinsic will
fail if the derived group has very large or infinite index in G.
- (ii)
- If H is defined by a coset table then the SchreierGenerators
intrinsic can be used to produce generating words for H. In many cases
this will be done automatically.
The group (8, 7 | 2, 3) is defined by the presentation
< a, b | a 8, b 7, (ab) 2, (ab - 1) 3 >,
and has a subgroup of index 448 generated by the words a 2 and ab - 1:
> G<a, b> := FPGroup<a, b| a^8, b^7, (a * b)^2, (a * b^-1)^3>;
> G;
Finitely presented group G on 2 generators
Relations
a^8 = Id(G)
b^7 = Id(G)
(a * b)^2 = Id(G)
(a * b^-1)^3 = Id(G)
> H<x, y> := sub< G | a^2, a * b^-1 >;
> H;
Finitely presented group H on 2 generators
Generators as words in group G
x = a^2
y = a * b^-1
The subgroup functions will now be demonstrated on the subgroup H.
First of all its index and order are calculated.
> Index(G, H);
448
> Order(H);
24
The derived group of G is trivial:-
> DerivedSubgroup(G);
Finitely presented group
Index in group G is 1 = 1
Subgroup of group G defined by coset table
The group G is perfect so it is necessary to look elsewhere to
find some other subgroups.
> P := MinimalOvergroup(G, H);
> P;
Finitely presented group P on 3 generators
Index in group G is 224 = 2^5 * 7
Generators as words in group G
P.1 = a^2
P.2 = a * b^-1
P.3 = a * b^2 * a^3 * b^-1 * a^3 * b^3
> Order(P);
48
So H sits inside a subgroup P having twice its order.
> N := Normalizer(G, H);
> N;
Finitely presented group N on 4 generators
Index in group G is 112 = 2^4 * 7
Generators as words in group G
N.1 = a^2
N.2 = a * b^-1
N.3 = b^-1 * a * b^2 * a^4 * b^-1 * a * b^2
N.4 = a * b^2 * a^3 * b^-1 * a^3 * b^3
> Order(N);
96
The subgroup H has a normaliser N of order 96.
> Q := MaximalOvergroup(G, H);
> Q;
Finitely presented group Q on 3 generators
Index in group G is 7
Generators as words in group G
Q.1 = a^2
Q.2 = a * b^-1
Q.3 = b^-1 * a * b^2
> #Q;
1536
So the largest subgroup Q that contains H has index 7 in G.
> M := NormalClosure(G, H);
> M;
Finitely presented group M on 7 generators
Index in group G is 1 = 1
Generators as words in group G
M.1 = a^2
M.2 = a * b^-1
M.3 = a^2 * b^-1 * a^-1
M.4 = b^-1 * a
M.5 = b * a * b^-2
M.6 = (b^-1 * a * b)^2
M.7 = b^-1 * a
To summarise, proper subgroups of G having orders 48, 96 and 1536 that
contain H have been found. The normal closure of H is G.
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, refer
to chapter FINITELY PRESENTED GROUPS.
Intrinsics:
u in H : True if and only if the word u in G is a member of H.
u notin H : True if and only if the word u in G is not a member of H.
H eq K : True if and only if subgroups H and K are equal.
H ne K : True if and only if subgroups H and K are not equal.
H subset K : True if and only if the subgroup H is a subset of K.
IsConjugate(G, H, K) : True if and only if subgroups H and K are conjugate in G.
If H and K are conjugate an element that conjugates H into K is also returned.
IsMaximal(G, H) : True if subgroup H is maximal in G.
IsNormal(G, H) : True if subgroup H is normal in G.
IsSelfNormalizing(G, H) : True if subgroup H is a self-normalising subgroup of G.
IsPerfect(H) : True if the subgroup H is perfect.
Some of these subgroup predicates are illustrated by applying them to some subgroups
of the two-dimensional space group p4g = < r, s | r 2, s 4, (r, s) 2 >.
> p4g<r, s> := FPGroup< r, s | r^2 = s^4 = (r,s)^2 = 1 >;
> h := sub< p4g | (s^-1*r)^4, s*r >;
> k := sub< p4g | (s^-1*r)^2, (s*r)^2 >;
Subgroups h and k have the same index in p4g but they
are neither equal nor conjugate.
> Index(p4g, h), Index(p4g, k);
8 8
> h eq k;
false
> IsConjugate( p4g, h, k);
false
Are subgroups h and k normal in p4g?
> IsNormal(p4g, h), IsNormal(p4g, k);
false true
Since h is not normal it makes sense to construct its normal closure
n in p4g. It turns out that n is maximal in p4g and contains k.
> n := NormalClosure(p4g, h);
Index( p4g, n)l
2
> IsMaximal(p4g, n);
true
> k subset n;
true
Here is a new subgroup l of p4g that turns out to be conjugate to h.
> l := sub< p4g | (s*r)^4, s^-1*r >;
> 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
Let H be a subgroup of finite index in the finitely presented group
G. It frequently happens that it is desirable to construct a set of
defining relations for H from those of G. Such a presentation can be
obtained either on a set of Schreier generators for H or on the given
generators of H using the Reidemeister--Schreier rewriting
technique [MKS76], if necessary together with extended coset
enumeration [AR84], [HKRR84].
It should be emphasised that if the user wishes only to determine the
structure of the maximal abelian quotient of H, then the function
AbelianQuotientInvariants should be used. In this case there is
no need to first construct a presentation for H using the Rewrite
function described below, since AbelianQuotientInvariants
employs a special form of the Reidemeister--Schreier rewriting process which
abelianises each relator as soon as it is constructed. Thus, compared to
the function Rewrite, the function AbelianQuotientInvariants
can be applied to subgroups of much larger index.
Intrinsics:
Rewrite (G, H) : Given an fp group G and a subgroup H having finite
index in G, return a group K isomorphic to H with a presentation on some
of the Schreier generators of H in G. The group K is created as a
subgroup of G with a presentation on the new generators. The isomorphism
from H onto K is returned as second return value. Note that the
generators of K will, in general, not correspond to the generators of H.
Rewrite (G, ~H) : Given a finitely presented group G and a
subgroup H having finite index in G, a set of defining relations for
H is constructed on the given generators. The information stored for H
is changed to include these defining relations.
Notes:
- (i)
- The first version of Rewrite selects its own generators and
consequently is faster and often produces a simpler presentation.
The second version constructs a presentation on the given generators. This is
a more complicated process and the resulting presentation is often large.
Consequently, by default, simplification is attempted using Tietze
transformations that do not involve any changes to the generators of H.
If is not necessary to obtain a presentation for H on the original
generators of H, the first method is strongly recommended.
Starting with the group G defined by
< x, y | x 2, y 3, (xy) 12, (xy) 6(xy - 1) 6 >,
a subgroup H of index 3 is generated by the words x, yxy - 1
and yxy - 1xy - 1xy:
> G<x, y> := FPGroup< x, y | x^2, y^3, (x*y)^12, (x*y)^6*(x*y^-1)^6 >;
> G;
Finitely presented group G on 2 generators
Relations
x^2 = Id(G)
y^3 = Id(G)
(x * y)^12 = Id(G)
x * y * x * y * x * y * x * y * x * y * x * y * x * y^-1 * x *
y^-1 * x * y^-1 * x * y^-1 * x * y^-1 * x * y^-1 = Id(G)
> H := sub< G | x, y*x*y^-1, y*x*y^-1*x*y^-1*x*y >;
> H;
Finitely presented group H on 3 generators
Generators as words in group G
H.1 = x
H.2 = y * x * y^-1
H.3 = y * x * y^-1 * x * y^-1 * x * y
> Index(G, H);
3
A presentation for H is now computed. Then using
AbelianQuotientInvariants, H is found to have a non-trivial
soluble quotient. Using the p-quotient algorithm described later,
H is found to have a 2-quotient of order2 62!
> K := Rewrite(G, H);
> K;
Finitely presented group K on 3 generators
Generators as words in group G
K.1 = x
K.2 = y * x * y^-1
K.3 = x^y
Relations
K.1^2 = Id(T)
K.2^2 = Id(T)
K.3^2 = Id(T)
(K.3 * K.2 * K.1 * K.3 * K.2)^2 = Id(K)
(K.1 * K.3 * K.2 * K.1 * K.3)^2 = Id(K)
(K.1 * K.2 * K.1 * K.3 * K.2)^2 = Id(K)
> AbelianQuotientInvariants(K);
[ 2, 2, 2 ]
> Q2 := pQuotient(K, 2, 30);
> FactoredOrder(Q2);
[ <2, 62> ]
This example demonstrates how the intrinsic Rewrite can be used to obtain
a presentation of a finitely presented group on a different set of generators.
Firstly, a presentation for L2(7) on two generators x and y is used to
define the group.
> L27<x, y> := FPGroup< x, y | x^3 = 1, y^3 = 1, (x*y)^4 = 1,
> (y*y^x)^2 = y^x*y >;
The group is also generated by the elements a = (xy) 2 and b = y.
> H<a, b> := sub<L27 | (x*y)^2, y >;
> Index(L27, H);
1
At this point, no defining relations of H isomorphic to L27 on the generators a and
b are known.
> H;
Finitely presented group H on 2 generators
Index in group L27 is 1
Generators as words in group L27
a = (x * y)^2
b = y
The intrinsic Rewrite is applied to H as a subgroup of L27
in order to compute defining relations on the generators a and b.
> Rewrite(L27, ~H);
> H;
Finitely presented group H on 2 generators
Index in group L27 is 1
Generators as words in group L27
a = (x * y)^2
b = y
Relations
a^2 = Id(H)
b^3 = Id(H)
(a * b)^7 = Id(H)
(a * b^-1 * a * b)^4 = Id(H)
(b * a * b^-1 * a * b * a)^4 = Id(H)
The fifth relation turns out to be redundant: a and b are standard
generators for L 2(7) as is shown here:
> Order(DeleteRelation(H, 5)) eq Order(H);
true
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|