An on-going international research project seeks to develop algorithms to explore the structure of groups having either large order or large degree. The approach relies on the following theorem of Aschbacher [Asc84]:

A matrix group G acting on the finite dimensional K[G]-module V over a finite field K satisfies at least one of the following conditions (which we have simplified slightly for brevity):

Groups in Category (i) can be recognised easily by means of the Meataxe functions described in the chapter on R-modules.

Groups which act irreducibly but not absolutely irreducibly on V fall theoretically into Category (ii), and furthermore act linearly over an extension field of K. In fact, absolute irreducibility can be tested using the built-in Magma functions and, by redefining their field to be an extension field L of K and reducing, they can be rewritten as absolutely irreducible groups of smaller dimension, but over L instead of K. We can therefore concentrate on absolutely irreducible matrix groups.

The CompositionTree package currently includes functions which seek to decide membership in all categories.

Let G be a subgroup of GL(d, q) and assume that G acts irreducibly on the underlying vector space V. Then G acts imprimitively on V if there is a non-trivial direct sum decomposition V = V1 direct-sum V2 direct-sum ... direct-sum Vr where V1, ..., Vr are permuted by G. In such a case, each block Vi has the same dimension or size, and we have the block system {V1, ..., Vr}. If no such system exists, then G is primitive.

Theoretical details of the algorithm used may be found in Holt, Leedham-Green, O'Brien, and Rees [HLGOR96b].

SetVerbose ("Smash", 1) will provide information on the progress of the algorithm.

If BlockSizes is supplied, then the search is restricted to systems of imprimitivity whose block sizes are given in the sequence BlockSizes only. Otherwise all valid sizes will be considered.

We construct an imprimitive group by taking the wreath product of GL(4, 7) with S3.

Let G be a subgroup of GL(d, q) and assume that G acts absolutely irreducibly on the underlying vector space V. Assume that a normal subgroup N of G embeds in GL(d/e, qe), for e>1, and a d x d matrix C acts as multiplication by a scalar λ(a field generator of GF(qe)) for that embedding.

We say that G acts as a semilinear group of automorphisms on the d/e-dimensional space if and only if, for each generator g of G, there is an integer i = i(g) such that Cg = gCi, that is, g corresponds to the field automorphism λ-> λi. If so, we have a map from G to the (cyclic) group ( Aut)(GF(qe)), and C centralises the kernel of this map, which thus lies in GL(d, qe).

Theoretical details of the algorithm used may be found in Holt, Leedham-Green, O'Brien and Rees [HLGOR96a].

SetVerbose ("SemiLinear", 1) will provide information on the progress of the algorithm.

We analyse a semilinear group.

; > > IsSemiLinear (G); true > DegreeOfFieldExtension (G); 2 > CentralisingMatrix (G); [2 2 0 0 0 0] [1 2 0 0 0 0] [0 0 2 2 0 0] [0 0 1 2 0 0] [0 0 0 0 2 2] [0 0 0 0 1 2] > FrobeniusAutomorphisms (G); [ 1, 1, 3 ] > K, E, phi := WriteOverLargerField (G);

The group K is the kernel of the homomorphism from G into E.

The return value E is the cyclic group of order e while phi gives the sequence of images of G.i in E.

Let G be a subgroup of GL(d, K), where K = GF(q), and let V be the natural K[G]-module. We say that G preserves a tensor decomposition of V as U tensor W if there is an isomorphism of V onto U tensor W such that the induced image of G in GL(U tensor W) lies in GL(U) GL(W).

Theoretical details of the algorithm used may be found in Leedham-Green and O'Brien [LGO97b], [LGO97a].

The verbose flag SetVerbose ("Tensor", 1) will provide information on the progress of the algorithm.

A sequence of valid dimensions for potential factors may be supplied using the parameter Factors. Then for each element [u, w] of the sequence Factors, the algorithm will search for decompositions of V as U tensor W, where U must have dimension u and W must have dimension w only. If this parameter is not set, then all valid factorisations will be considered.

So C is the change-of-basis matrix. If we conjugate G.1 by C, we obtain a visible Kronecker product.

We use the function IsProportional to verify that G.1C is a Kronecker product.

Finally, we display the tensor factors.

Let G be a subgroup of GL(d, K), where K = GF(q) and q = pe for some prime p, and let V be the natural K[G]-module. Assume that d has a proper factorisation as ur. We say that G is tensor-induced if G preserves a decomposition of V as U1 tensor U2 tensor ... tensor Ur where each Ui has dimension u > 1, r > 1, and the set of Ui is permuted by G. If G is tensor-induced, then there is a homomorphism of G into the symmetric group Sr.

Theoretical details of the algorithm used may be found in Leedham-Green and O'Brien [LGO02].

SetVerbose ("TensorInduced", 1) will provide information on the progress of the algorithm.

If the value of the parameter InducedDegree is set to r, then the algorithm will search for homomorphisms into the symmetric group of degree r only. Otherwise is will consider all valid degrees.

We illustrate the use of the functions for determining if a matrix group is tensor-induced.

We next recover the permutations.

Hence G.1 and G.2 are in the kernel of the homomorphism from G to S. We extract the change-of-basis matrix C and then conjugate G.1 by C, thereby obtaining a visible Kronecker product.

Finally, we verify that x = G.1C is a Kronecker product for each of 2 and 4.

Let G ≤GL(d, q), where d=rm for some prime r. If G is contained in the normaliser of an r-group R, of order either r2m + 1 or 22m + 2, then either R is extraspecial (in the first case), or R is a 2-group of symplectic type (that is, a central product of an extraspecial 2-group with the cyclic group of order 4).

If d = r is an odd prime, we use the Monte Carlo algorithm of Niemeyer [Nie05] to decide whether or not G normalises such a subgroup. Otherwise, the corresponding intrinsic IsExtraSpecialNormaliser searches for elements of the normal subgroup, and can only reach a negative conclusion in certain limited cases. If it cannot reach a conclusion it returns "unknown".

So G has the desired normaliser property.

The algorithm implemented by these functions is due to Glasby, Leedham-Green and O'Brien [GLGO05]. We also provide access to an earlier algorithm for the non-scalar case developed by Glasby and Howlett [GH97].

We now see if G has an equivalent representation modulo scalars.

We define the group GL(2, 4) and then rewrite in over GF(2) as a degree 4 matrix group.

In summary, it tests for one of the following possibilities:

Each test involves a decomposition of G with respect to the normal subgroup N (which may sometimes be trivial or scalar). In (ii), N is the subgroup of G acting linearly over the extension field irreducibly on V. In (iii), N is the subgroup which fixes each of the subspaces in the imprimitive decomposition of V. In (iv), it is the subgroup acting as scalar matrices on one of the factors in the tensor-product decomposition. In (v), N is already described, and in (vi), it is the subgroup fixing each of the factors in the tensor-induced decomposition (so N itself falls in Category (iv)).

If any one of these decompositions can be found, then it may be possible to obtain an explicit representation of G/N and hence reduce the study of G to a smaller problem. For example, in Category (iii), G/N acts as a permutation group on the subspaces in the imprimitive decomposition of V. Currently only limited facilities are provided to construct G/N.

Information about the progress of the algorithm can be output by setting the verbose flag SetVerbose ("Smash", 1).

The access functions described in the sections on Primitivity Testing, Semilinearity, Tensor Products, Tensor Induction, and Normalisers of extraspecial groups may be used to extract information about decompositions of type (ii), (iii), (iv), (v) and (vi). We illustrate such decompositions below.

We begin with an example where no decomposition exists.

The second example is of an imprimitive decomposition.

The third example admits a semilinear decomposition.

; > > SearchForDecomposition (G, [g1]); Smash: G is semilinear true > IsSemiLinear (G); true > DegreeOfFieldExtension (G); 2 > CentralisingMatrix (G); [2 2 0 0 0 0] [1 2 0 0 0 0] [0 0 2 2 0 0] [0 0 1 2 0 0] [0 0 0 0 2 2] [0 0 0 0 1 2] > FrobeniusAutomorphisms (G); [ 1, 1, 3 ]

The fourth example admits a tensor product decomposition.

Our fifth example is of a tensor-induced decomposition.

Our final example is of a normaliser of a symplectic group.