Composition Trees for Matrix Groups#

The Composition Tree Algorithm#

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 [Aschbacher, 1984] and constructive recognition algorithms for finite simple groups. The basic algorithms are described in [Leedham-Green, 2001, O'Brien, 2006, O'Brien, 2011] while some new ideas introduced in [Neunhöffer and Seress, 2006] are incorporated. A detailed account of the entire CompositionTree procedure appears in [B\accent 127a\accent 127arnhielm et al., 2015].

The algorithm for constructing a composition tree for a group \(G\) proceeds as follows.

(i)

Attempt to construct an effective homomorphism \(\phi : G \to G_1\), for some group \(G_1\). The homomorphism \(\phi\) is called a reduction of \(G\) since \(G_1\) 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 \(G_1\).

  2. Determine generators for \(G_0 := {\rm Ker}(\phi)\). This requires a rewriting algorithm for \(G_1\).

  3. Construct a composition tree for \(G_0\).

  4. Combine the composition trees for \(G_1\) and \(G_0\) to produce a composition tree for \(G\).

If \(G \leq {\operatorname{GL}}(d, q)\), then Aschbacher’s theorem [Aschbacher, 1984] is applied in Step (1). This requires algorithms that can decide whether \(G\) lies in a certain Aschbacher class, and to construct the corresponding \(\phi\). 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 = \langle X \rangle\) has been constructed, then a second list \(Y\) of nice generators are stored with \(G\). The group \(\langle Y \rangle\) 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, \ldots, 10\) may be used to print increasing levels of information on the progress of the functions.

Constructing the Composition Tree#

CompositionTree(G): GrpMat[FldFin] -> []#

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.

Example: Composition Tree (ex-009621)#

The minimum degree of a permutation representation of the sporadic simple group \(J_4\) is \(173,067,389\) while there is a matrix representation of degree \(112\) over the finite field \(F_2\). We extract this matrix representation of \(J_4\) 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

Run in calculator

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"

Run in calculator

CompositionTree(G : parameters): GrpMat[FldFin] -> []#
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.

CompositionTreeFastVerification(G): Grp -> BoolElt#

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.

CompositionTreeVerify(G): Grp -> BoolElt, []#

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

Example: Composition Tree Verify (ex-1c147a)#

We use the two methods of establishing correctness to verify the result of applying CompositionTree to a wreath product.

> U33 := MatrixGroup(AtlasGroup("U33"), 1);
> G := TensorWreathProduct( U33, Sym(3) );
> time G_Tree := CompositionTree(G);
Time: 26.620

Run in calculator

> G := TensorWreathProduct( U33, Sym(3) );
> time G_Tree := CompositionTree(G : Verify := true);
Time: 28.450

Run in calculator

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

Run in calculator

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.

Accessing the Composition Tree#

CompositionTreeOrder(G): Grp -> RngIntElt#

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

CompositionTreeNonAbelianFactors(G): Grp -> RngIntElt#

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.

DisplayCompTreeNodes(G : parameters): Grp#
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.

Example: Comp Tree J4 (ex-8acf9e)#

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 \(J_4\). The group \(J_4\) 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 \(J_4\) 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

Run in calculator

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

Run in calculator

From this information we deduce that structure of the subgroup is consistent with \(2^{1+12}.3.M_{22}.2\) which is the structure of the second largest maximal subgroup of \(J_4\).

CompositionTreeNiceGroup(G): Grp -> GrpMat[FldFin]#

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

CompositionTreeSLPGroup(G): Grp -> GrpSLP, Map#

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

CompositionTreeNiceToUser(G): Grp -> Map, []#

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.

CompositionTreeOrder(G): Grp -> RngIntElt#
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\).

CompositionTreeElementToWord(G, g): Grp, GrpElt -> BoolElt, GrpSLPElt#

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\in G\), return true and an SLP for \(g\) in the nice generators of \(G\), otherwise return false.

CompositionTreeNonAbelianFactors(G): GrpMat[FldFin] -> List#

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

CompositionTreeCBM(G): GrpMat[FldFin -> GrpMatElt#

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.

CompositionTreeReductionInfo(G, t): Grp, RngIntElt -> MonStgElt, Grp, Grp#

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.

CompositionTreeSeries(G): Grp -> SeqEnum, List, List, List, BoolElt, []#

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 = G_0 < G_1 < ... < G_k = G\).

  2. Maps \(G_i \mapsto S_i\), where \(S_i\) is the standard copy of \(G_i / G_{i-1}\), where \(i \geq 1\). The kernel of this map is \(G_{i-1}\). Observe that \(S_i\) may be the standard copy plus scalars \(Z\), and the map is then a homomorphism modulo scalars, so that the kernel is \((G_{i-1}.Z)/Z\).

  3. Maps \(S_i \mapsto G_i\).

  4. Maps \(S_i \mapsto\) WordGroup\((S_i)\).

  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.

CompositionTreeFactorNumber(G, g): Grp, GrpElt -> RngIntElt#

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 \(i\)th-term of the normal series returned by CompositionTreeSeries for \(G\).

HasCompositionTree(G): Grp -> BoolElt#

Given a matrix group \(G\) defined over a finite field, this intrinsic returns true if \(G\) has a composition tree and false otherwise.

CleanCompositionTree(G): Grp#

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

Example: Comp Tree1 (ex-0bfaff)#

A composition tree for the conformal orthogonal group \(G\) of plus type of degree \(4\) over \({\bf F}_{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
----------

Run in calculator

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

Run in calculator

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

Run in calculator

Knowing that the composition tree is correct, the order of \(G\) is printed.

> CompositionTreeOrder(G);
11681280000

Run in calculator

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

Run in calculator

Rewrite the SLP in terms of the user-supplied generators for \(G\).

> tau := CompositionTreeNiceToUser(G);
> tau;
Mapping from: GrpSLP: W to SLPGroup(5)

Run in calculator

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

Run in calculator

Test a random element of the generic group for \(G\) for membership. (The generic group will be the general linear group \({\operatorname{GL}}(4, 5^2)\).)

> x := Random(Generic(G));
> f, w := CompositionTreeElementToWord(G, x);
> f;
false

Run in calculator

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

Run in calculator

Example: Comp Tree2 (ex-b767f8)#

In this example, we choose a maximal subgroup of the linear group \(SL(10, 2^8)\) 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
----------

Run in calculator

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

Run in calculator

After checking that correctness of the composition tree can be verified quickly, we perform verification.

> CompositionTreeFastVerification(G);
true
> f, R := CompositionTreeVerify(G);

Run in calculator

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

Run in calculator

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

Run in calculator

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

Run in calculator

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

Run in calculator