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:
> 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:
> 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.
> 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 G2(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:
> 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
]
> 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); 720In 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; 26A 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:
> 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.
> 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:
> 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 order262!
> 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> ]
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); 1At 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 L2(7) as is shown here:
> Order(DeleteRelation(H, 5)) eq Order(H); true