|
A composition tree for a group G can be viewed as a data structure
which presents a group in terms of its composition factors. The tree is
constructed recursively and the data structure facilitates the rewriting
of elements of G in terms of different generating sets.
The basic strategy for computing a composition tree of a matrix group
employs a combination of a constructive version of Aschbacher's theorem
[Asc84] and constructive recognition algorithms for
finite simple groups. The basic algorithms are described
in [LG01], [O'B06], [O'B11] while some new ideas introduced
in [NS06] are incorporated. A detailed account of the
entire CompositionTree procedure appears in [BHLGO15].
The algorithm for constructing a composition tree for a group G proceeds
as follows.
- (i)
- Attempt to construct an effective homomorphism φ : G to G1, for
some group G1. The homomorphism φ is called a reduction
of G since G1 is "smaller" than G in some sense -- for example,
with respect to its degree or field of definition.
- (ii)
- Otherwise deduce that G is cyclic, elementary abelian, or "close"
to being non-abelian simple. In this case G becomes a leaf
in the tree.
If Case (i) applies the algorithm proceeds as follows:-
- 1.
- Construct a composition tree for G1.
- 2.
- Determine generators for G0 := (Ker)(φ).
This requires a rewriting algorithm for G1.
- 3.
- Construct a composition tree for G0.
- 4.
- Combine the composition trees for G1 and G0 to
produce a composition tree for G.
If G ≤GL(d, q), then Aschbacher's theorem [Asc84]
is applied in Step (1). This requires algorithms that can decide whether
G lies in a certain Aschbacher class, and to construct the corresponding
φ. Other homomorphisms, such as the determinant map, may also be used.
The group associated with a leaf need not be simple. It may be cyclic
or elementary abelian, a soluble or non-abelian simple primitive
permutation group, or an absolutely irreducible matrix group that is
simple modulo its centre. The decision on just which groups are
treated as leaves is partly dictated by complexity considerations,
and partly based on the quality of available algorithms for processing
a leaf. For example, refining a cyclic group into its composition
factors appears to offer no practical advantage.
Once a composition tree for G = < X > has been constructed,
then a second list Y of nice generators are stored with G.
The group < Y > is called the nice group. The intrinsic
CompositionTree constructs the nice generators Y as straight-line
programs (SLPs) with respect to X. The rewriting algorithm solves
rewriting problems with respect to Y and the resulting SLPs can then
be rewritten to provide SLPs on X.
The verbose flag SetVerbose("CompositionTree", n) with
n=1, ..., 10 may be used to print increasing levels of
information on the progress of the functions.
In this case we use CompositionTreeFastVerification to
check that verification wont be expensive and then apply the
intrinsic CompositionTreeVerify to actually do the
verification. Again, it takes less than 2 seconds.
Let G be a finite group generated by matrices over a finite field.
The intrinsic constructs a composition tree for G using the
algorithm outlined at the beginning of this section. The tree is
returned as the value of this intrinsic and is also stored with G
and it is usually accessed by reference to G.
The intrinsic has a number of parameters that are described below.
Even in the case of a small group, the tree is a very voluminous object
so that information about it should be extracted using the intrinsics
described below. The tree is constructed using Monte Carlo algorithms
and so there is a small probability that it is incorrect. Algorithms
are available to verify the correctness of the tree and may be invoked
either by setting a parameter for the CompositionTree intrinsic
or by a separate intrinsic CompositionTreeVerify that may be
applied to the tree produced by a call to CompositionTree and
which is described below.
The minimum degree of a permutation representation of the sporadic
simple group J4 is 173, 067, 389 while there is a matrix
representation of degree 112 over the finite field F2. We
extract this matrix representation of J4 from the Atlas database
and apply CompositionTree to it.
> G := MatrixGroup(AtlasGroup("J4"));
> G:Minimal;
MatrixGroup(112, GF(2))
> time G_Tree := CompositionTree(G);
Time: 3.030
We now extract the order and list the isomorphism types of the non-abelian
composition trees.
> CompositionTreeOrder(G);
86775571046077562880
> nafact := CompositionTreeNonAbelianFactors(G);
> nafact[1][3];
"J4"
Verify: BoolElt Default: false
Scalar: FldFinElt Default: 1
KernelBatchSize: RngIntElt Default: 5
MandarinBatchSize: RngIntElt Default: 100
MaxHomFinderFails: RngIntElt Default: 1
MaxQuotientOrder: RngIntElt Default: 10^6
FastTensorTest: BoolElt Default: true
MaxBSGSVerifyOrder: RngIntElt Default: 2000
AnalysePermGroups: BoolElt Default: false
KnownLeaf: BoolElt Default: false
NamingElements: RngIntElt Default: 200
UnipotentBatchSize: RngIntElt Default: 100
PresentationKernel: BoolElt Default: true
Let G be a finite group generated by matrices over a finite field.
The intrinsic constructs a composition tree for G and returns the
tree using the algorithm outlined at the beginning of this section.
The intrinsic has a number of parameters which are now described.
Verify: If true, then verify correctness of the tree during
construction.
KernelBatchSize: The number of normal generators
used to construct the kernel of homomorphism.
MandarinBatchSize: The number of random elements used
to check correctness of the outcome of Monte-Carlo algorithms.
MaxHomFinderFails:
Assume a negative answer after MaxHomFinderFails failures
of certain Monte Carlo algorithms.
MaxQuotientOrder: A leaf with larger order will not
be fully refined to its composition factors.
FastTensorTest: Use only the fast tensor product test.
MaxBSGSVerifyOrder: If RandomSchreier is used on
a leaf and it has order less than MaxBSGSVerifyOrder, then
Verify the calculation.
AnalysePermGroups:
If false, then always treat the permutation group as a
leaf, and do not analyse its structure.
NamingElements:
The number of random elements used in
calls to LieType and RecogniseClassical.
PresentationKernel: Use presentations to obtain kernels,
where possible.
UnipotentBatchSize: Batch size for the unipotent kernels.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. The intrinsic determines if correctness of
the composition tree can be verified at modest cost using
presentations. In effect, the intrinsic determines whether
presentations on nice generators are known for all the leaves.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. The intrinsic verifies the correctness of the
composition tree by using it to construct a presentation for G.
If G satisfies the presentation, then return true, and the
relators of the presentation as SLPs; otherwise return false.
The presentation is on the group returned by
CompositionTreeNiceGroup(G).
We use the two methods of establishing correctness to verify the result
of applying hfil
CompositionTree to a wreath product.
> U33 := MatrixGroup(AtlasGroup("U33"), 1);
> G := TensorWreathProduct( U33, Sym(3) );
> time G_Tree := CompositionTree(G);
Time: 26.620
> G := TensorWreathProduct( U33, Sym(3) );
> time G_Tree := CompositionTree(G : Verify := true);
Time: 28.450
Thus, verification adds a little under 2 seconds to the runtime.
> G := TensorWreathProduct( U33, Sym(3) );
> time G_Tree := CompositionTree(G );
Time: 26.620
> time CompositionTreeFastVerification(G);
Time: 0.000
true
> time CompositionTreeVerify(G);
Time: 1.850
true
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns the order of G.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. The intrinsic returns the isomorphism types of
the non-abelian composition factors of G as a sequence of
triples where each triple defines an isomorphism type.
NonTrivial: BoolElt Default: true
Leaves: BoolElt Default: false
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic displays information about the nodes
in the composition tree for G. The tree is traversed in-order.
If parameter NonTrivial is true, then only non-trivial
nodes will be displayed. If parameter Leaves is true
then only leaves will be displayed.
The composition tree (CT) machinery allows us to create a subgroup
H of a group G with a CT, to determine the order of H and to
test membership in H. In general, additional machinery is needed
in order to be able to determine information about the subgroup
structure of G. However, there are two Monte Carlo algorithms for
computing subgroups, specifically, an algorithm for computing the
centralizer of an involution and an algorithm for computing the
normal closure of a subgroup. We illustrate how the centralizer
algorithm can be used by applying it to compute a large subgroup
in the sporadic group J4. The group J4 has a maximal subgroup
of order 21,799,895,040 which is the centralizer of an involution.
We will try to find this maximal subgroup by working with J4 in
its matrix representation of degree 112 over GF(2).
> G := MatrixGroup(AtlasGroup("J4"));
> G:Minimal;
MatrixGroup(112, GF(2))
> CT := CompositionTree(G);
> CompositionTreeOrder(G);
86775571046077562880
> found := false;
> for i := 1 to 30 do
> bool, x := RandomElementOfOrder(G, 2);
> C := CentraliserOfInvolution(G, x);
> CTree := CompositionTree(C);
> n := CompositionTreeOrder(C);
> if n eq 21799895040 then
> found := true;
> break;
> end if;
> end for;
> found;
true
> CompositionTreeOrder(C);
21799895040
Our random search has produced a subgroup of the right order.
We now display part of the composition tree in order to get
an idea of the group structure of C.
> DisplayCompTreeNodes(C : Leaves := true);
node = 6
parent = 5
depth = 5
scalar = 1
info = leaf, GrpPerm, RandomSchreier, order 2
fast verify = true
----------
node = 7
parent = 5
depth = 5
scalar = 1
info = leaf, GrpMat, almost simple, <18, 3, "M22">
fast verify = true
----------
node = 15
parent = 14
depth = 11
scalar = 1
info = leaf, GrpAb, abelian group, order 3
fast verify = true
----------
node = 25
parent = 24
depth = 3
scalar = 1
info = leaf, GrpAb, abelian group, order 16
fast verify = true
----------
node = 27
parent = 26
depth = 4
scalar = 1
info = leaf, GrpAb, abelian group, order 256
fast verify = true
----------
node = 29
parent = 28
depth = 5
scalar = 1
info = leaf, GrpAb, abelian group, order 2
fast verify = true
----------
From this information we deduce that structure of the subgroup is
consistent with 21 + 12.3.M22.2 which is the structure of
the second largest maximal subgroup of J4.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. The intrinsic returns the nice group for G.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure and the associated nice
group H has previously been constructed. The intrinsic returns
the word group W for H, and the map from W to H.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns the coercion map from SLPs in
nice generators of G to SLPs in input user generators of G,
as well as the SLPs of the nice generators given in terms the
user generators.
CompositionTreeFactoredOrder(G) : Grp -> RngIntEltFact
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. The intrinsics return the (factored) order of G.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. Given an element g∈G, return true and
an SLP for g in the nice generators of G, otherwise return
false.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns a list naming the non-abelian
composition factors of G.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns a change-of-basis matrix
that exhibits the Aschbacher reductions of G given by the
composition tree.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns a string description of the
reduction at the internal node t in the composition tree for G,
as well as the image and kernel of this reduction.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns:
- 1.
- A normal series of subgroups 1 = G0 < G1 < ... < Gk = G.
- 2.
- Maps Gi |-> Si, where Si is the standard copy of Gi / Gi - 1,
where i ≥1. The kernel of this map is Gi - 1.
Observe that Si may be the standard copy plus scalars Z,
and the map is then a homomorphism modulo scalars, so that the kernel is
(Gi - 1.Z)/Z.
- 3.
- Maps Si |-> Gi.
- 4.
- Maps Si |-> WordGroup(Si).
- 5.
- Boolean flag true or false
to indicate if the series is a true composition series.
- 6.
- A sequence of the leaf nodes in the composition tree corresponding to each
composition factor. All maps are defined by rules, so Function
can be applied on them to avoid built-in membership testing.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic returns the minimal integer i such
that g lies in the ith-term of the normal series returned by
CompositionTreeSeries for G.
Given a matrix group G defined over a finite field, this
intrinsic returns true if G has a composition tree
and false otherwise.
The argument G must be a matrix group over a finite field for
which a composition tree datastructure has previously been
constructed. This intrinsic removes all data related to the
composition tree datastructure for G.
A composition tree for the conformal orthogonal group G of plus
type of degree 4 over GF(5 2) will be constructed.
> G := CGOPlus(4, 5^2);
>
> T := CompositionTree(G);
>
> DisplayCompTreeNodes (G: Leaves:=true);
node = 2
parent = 1
depth = 1
scalar = 1
info = leaf, GrpAb, cyclic group, order 12
fast verify = true
----------
node = 4
parent = 3
depth = 2
scalar = 1
info = leaf, GrpAb, cyclic group, order 4
fast verify = true
----------
node = 7
parent = 6
depth = 4
scalar = 12
info = leaf, GrpAb, cyclic group, order 24
fast verify = true
----------
node = 8
parent = 6
depth = 4
scalar = 2
info = leaf, GrpMat, almost simple, <"A", 1, 25>
fast verify = true
----------
node = 9
parent = 5
depth = 3
scalar = 1
info = leaf, GrpMat, almost simple, <"A", 1, 25>
fast verify = true
----------
Next the correctness of the composition tree is verified. In order
to demonstrate what is going on, various pieces of the verification
process will be examined. Firstly, the nice group H for G and its
associated SLP group, is set up; observe that H = G. After checking
that verification can be carried out quickly, the verification is
actually performed.
> H := CompositionTreeNiceGroup(G);
> W := CompositionTreeSLPGroup(G);
>
> CompositionTreeFastVerification(G);
true
>
> f, R := CompositionTreeVerify(G);
At this point correctness has been verified. To show what verification
actually involves, the relations R on the generators of H will be
explicitly evaluated. This step has already been performed by
CompositionTreeVerify and is shown here just for demonstration
purposes.
> Set(Evaluate(R, [H.i:i in [1..Ngens(H)]]));
{
[ 1 0 0 0]
[ 0 1 0 0]
[ 0 0 1 0]
[ 0 0 0 1]
}
Knowing that the composition tree is correct, the order of G
is printed.
> CompositionTreeOrder(G);
11681280000
Express the element g of G as a SLP on the generators of the nice
group H.
> g := Random(G);
> f, w := CompositionTreeElementToWord(G, g);
> Evaluate(w, [H.i:i in [1..Ngens(H)]]) eq g;
true
Rewrite the SLP in terms of the user-supplied generators for G.
> tau := CompositionTreeNiceToUser(G);
> tau;
Mapping from: GrpSLP: W to SLPGroup(5)
Images of elements of W under tau lie in WordGroup(G).
> v := tau(w);
> Evaluate (v, [G.i : i in [1..Ngens(G)]]) eq g;
true
Test a random element of the generic group for G for membership.
(The generic group will be the general linear group GL(4, 5 2).)
> x := Random(Generic(G));
> f, w := CompositionTreeElementToWord(G, x);
> f;
false
Finally, we construct a normal series for G and locate a random
element within this series.
> CS, _, _, _, flag := CompositionTreeSeries(G);
> "Series is composition series? ", flag;
Series is composition series? true
> "Length is ", #CS;
Length is 10
>
> g := Random(G);
> CompositionTreeFactorNumber(G, g);
10
In this example, we choose a maximal subgroup of the linear group
SL(10, 28) and compute its composition tree.
> X := ClassicalMaximals ("L", 10, 2^8);
> G := X[1];
>
> T := CompositionTree (G);
>
> DisplayCompTreeNodes (G: Leaves:=true, NonTrivial:=true);
node = 6
parent = 5
depth = 5
scalar = 1
info = leaf, GrpAb, cyclic group, order 255
fast verify = true
----------
node = 9
parent = 8
depth = 5
scalar = 1
info = leaf, GrpMat, almost simple, <"A", 8, 256>
fast verify = true
----------
node = 13
parent = 12
depth = 3
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 15
parent = 14
depth = 4
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 17
parent = 16
depth = 5
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 19
parent = 18
depth = 6
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 21
parent = 20
depth = 7
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
----------
node = 23
parent = 22
depth = 8
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 25
parent = 24
depth = 9
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 27
parent = 26
depth = 10
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
node = 29
parent = 28
depth = 11
scalar = 1
info = leaf, GrpPC, abelian group, order 256
fast verify = true
----------
We now set up the nice group H for G and its associated SLP group;
observe that H = G.
> H := CompositionTreeNiceGroup(G);
> "# of generators of H is ", Ngens(H);
# of generators of H is 77
> W := CompositionTreeSLPGroup(G);
After checking that correctness of the composition tree can be verified
quickly, we perform verification.
> CompositionTreeFastVerification(G);
true
> f, R := CompositionTreeVerify(G);
Evaluate the relations on the generators of H.
> Set (Evaluate (R, [H.i:i in [1..Ngens (H)]]));
{
[1 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 1]
}
Express the element g of G as a SLP on the generators of the nice group H.
Then rewrite the SLP in terms of user generators for G.
> g := Random (G);
> f, w := CompositionTreeElementToWord (G, g);
> Evaluate (w, [H.i:i in [1..Ngens (H)]]) eq g;
true
>
> tau := CompositionTreeNiceToUser (G);
> tau;
Mapping from: GrpSLP: W to SLPGroup(4)
>
> v := tau (w);
> Evaluate (v, [G.i : i in [1..Ngens (G)]]) eq g;
true
Next test a random element of the generic group of G for membership
of G.
> x := Random (Generic (G));
> f, w := CompositionTreeElementToWord (G, x);
> f;
false
Finally, we construct a normal series for G.
> CS, _, _, _, flag := CompositionTreeSeries (G);
> "Series is composition series? ", flag;
Series is composition series? true
> "Length is ", #CS;
Length is 78
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|