Aschbacher Reduction

Introduction

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 [Aschbacher, 1984]:

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

(i)

\(G\) acts reducibly on \(V\);

(ii)

\(G\) acts semilinearly over an extension field of \(K\);

(iii)

\(G\) acts imprimitively on \(V\);

(iv)

\(G\) preserves a nontrivial tensor-product decomposition of \(V\);

(v)

\(G\) has a normal subgroup \(N\), acting absolutely irreducibly on \(V\), which is an extraspecial \(p\)-group or 2-group of symplectic type;

(vi)

\(G\) preserves a tensor-induced decomposition of \(V\);

(vii)

\(G\) acts (modulo scalars) linearly over a proper subfield of \(K\);

(viii)

\(G\) contains a classical group in its natural action over \(K\);

(ix)

\(G\) is almost simple modulo scalars.

The philosophy underpinning the research program is to attempt to decide that \(G\) lies in at least one of the above categories, and to calculate the associated isomorphism or decomposition explicitly. 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.

Primitivity

Let \(G\) be a subgroup of \({\operatorname{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 = V_1 \oplus V_2 \oplus \ldots \oplus V_r\]

where \(V_1,\ldots, V_r\) are permuted by \(G\). In such a case, each block \(V_i\) has the same dimension or size, and we have the block system \(\{V_1, \ldots, V_r\}\). 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 [Holt et al., 1996].

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

IsPrimitive(G: parameters): GrpMat -> BoolElt

BlockSizes: [RngIntElt]                    Default: []

Given a matrix group \(G\) defined over a finite field, this intrinsic returns true if \(G\) is primitive, false if \(G\) is not primitive, or "unknown" if no decision can be reached.

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.

ImprimitiveBasis(G): GrpMat -> SeqEnum

Given a matrix group \(G\) defined over a finite field which is imprimitive, this intrinsic returns the change-of-basis matrix which exhibits the block structure for \(G\).

Blocks(G): GrpMat -> SeqEnum

Given a matrix group \(G\) defined over a finite field which is imprimitive, this intrinsic returns the blocks of imprimitivity of \(G\).

BlocksImage(G): GrpMat -> GrpPerm

Given a matrix group \(G\) defined over a finite field which is imprimitive, this intrinsic returns the group induced by the action of \(G\) on the system of imprimitivity.

ImprimitiveAction(G, g): GrpMat, GrpMatElt -> GrpPermElt

Given a matrix group \(G\) defined over a finite field which is imprimitive and an element \(g\) of \(G\), this intrinsic returns action of \(g\) on blocks of imprimitivity as a permutation.

Example: Is Primitive (ex-cc4edb)

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

> MG := GL (4, 7);
> PG := Sym (3);
> G := WreathProduct (MG, PG);
>
> IsPrimitive (G);
false

Run in calculatorCopy input

We investigate the block system for \(G\).

> B := Blocks (G);
> B;
> #B;
3
> B[1];
Vector space of degree 12, dimension 4 over GF(7)
Generators:
(0 0 0 0 1 0 0 0 0 0 0 0)
(0 0 0 0 0 1 0 0 0 0 0 0)
(0 0 0 0 0 0 1 0 0 0 0 0)
(0 0 0 0 0 0 0 1 0 0 0 0)
Echelonized basis:
(0 0 0 0 1 0 0 0 0 0 0 0)
(0 0 0 0 0 1 0 0 0 0 0 0)
(0 0 0 0 0 0 1 0 0 0 0 0)
(0 0 0 0 0 0 0 1 0 0 0 0)

Run in calculatorCopy input

Now we obtain a permutation representation of \(G\) in its action on the blocks.

> P := BlocksImage (G);
> P;
Permutation group P acting on a set of cardinality 3
    (1, 2, 3)
    (2, 3)
> g := G.4 * G.3;
> ImprimitiveAction (G, g);
(1, 2)

Run in calculatorCopy input

Semilinearity

Let \(G\) be a subgroup of \({\operatorname{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 \({\operatorname{GL}}(d/e,q^e)\), for \(e>1\), and a \(d \times d\) matrix \(C\) acts as multiplication by a scalar \(\lambda\) (a field generator of \({\bf F}_{q^e}\)) 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 = gC^{i}\), that is, \(g\) corresponds to the field automorphism \(\lambda \rightarrow \lambda^{i}\). If so, we have a map from \(G\) to the (cyclic) group \({\rm Aut}(GF(q^e))\), and \(C\) centralises the kernel of this map, which thus lies in \({\operatorname{GL}}(d,q^e)\).

Theoretical details of the algorithm used may be found in Holt, Leedham-Green, O’Brien and Rees [Holt et al., 1996].

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

IsSemiLinear(G): GrpMat -> BoolElt

Given a matrix group \(G\) defined over a finite field, this intrinsic returns true if \(G\) is semilinear, false if \(G\) is not semilinear, or "unknown" if no decision can be reached.

DegreeOfFieldExtension(G): GrpMat -> RngIntElt

Let \(G\) be a subgroup of \(K = {\operatorname{GL}}(d, q)\). The intrinsic returns the degree \(e\) of the extension field of \(F_q\) over which \(G\) is semilinear.

CentralisingMatrix(G): GrpMat -> AlgMatElt

Let \(G\) be a semilinear subgroup of \(K = {\operatorname{GL}}(d, q)\). The intrinsic returns the matrix \(C\) which centralises the normal subgroup of \(G\) which acts linearly over the extension field of \(F_q\).

FrobeniusAutomorphisms(G): GrpMat -> SeqEnum

Let \(G\) be a semilinear subgroup of \(K = {\operatorname{GL}}(d, q)\) and let \(C\) be the corresponding centralising matrix. The intrinsic returns a sequence \(S\) of positive integers, one for each generator \(g_i\) of \(G\). The element \(S[i]\) is the least positive integer such that \(g_i^{-1} C g_i = C^{S[i]}\).

WriteOverLargerField(G): GrpMat -> GrpMat, GrpAb, SeqEnum

Let \(G\) be a semilinear subgroup of \({\operatorname{GL}}(d, q)\) with extension degree \(e\). This intrinsic returns:

(i)

The normal subgroup \(N\) of the matrix group \(G\) which is the kernel of the map from \(G\) to \(C_e\); this subgroup acts linearly over the extension field of \(K\) and is precisely the centraliser of \(C\) in \(G\).

(ii)

A cyclic group \(E\) of order \(e\) which is isomorphic to \(G/N\).

(iii)

A sequence of images of the generators of \(G\) in \(E\).

Example: Semilinearity (ex-0459a8)

We analyse a semilinear group.

> P := GL(6,3);
> g1 := P![0,1,0,0,0,0,-1,0,0,0,0,0,
>          0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1];
> g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1,
>          -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0];
> g3 := P![1,0,0,0,0,0,0,-1,0,0,0,0,
>          0,0,1,0,0,0,0,0,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,-1];
> G := sub <P | g1, g2, g3 >;
>
> 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);

Run in calculatorCopy input

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

> K.1;
[0 1 0 0 0 0]
[2 0 0 0 0 0]
[0 0 1 0 0 0]
[0 0 0 1 0 0]
[0 0 0 0 1 0]
[0 0 0 0 0 1]

Run in calculatorCopy input

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

> E;
Abelian Group isomorphic to Z/2
Defined on 1 generator
Relations:
    2*E.1 = 0
>
> phi;
[ 0, 0, E.1 ]

Run in calculatorCopy input

Tensor Products

Let \(G\) be a subgroup of \({\operatorname{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\otimes W\) if there is an isomorphism of \(V\) onto \(U\otimes W\) such that the induced image of \(G\) in \({\operatorname{GL}}(U\otimes W)\) lies in \({\operatorname{GL}}(U) \circ {\operatorname{GL}}(W)\).

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

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

IsTensor(G: parameters): GrpMat -> BoolElt

Factors: [SeqEnum]                    Default: []

Given a matrix group \(G\) defined over a finite field, this intrinsic returns true if \(G\) preserves a non-trivial tensor decomposition, false if \(G\) is does not preserve a tensor decomposition, or "unknown" if no decision can be reached.

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

TensorBasis(G): GrpMat -> GrpMatElt

Given a matrix group \(G\) defined over a finite field that admits a tensor decomposition, this intrinsic returns the change-of-basis matrix which exhibits the tensor decomposition of \(G\).

TensorFactors(G): GrpMat -> GrpMat, GrpMat

Given a matrix group \(G\) defined over a finite field that admits a tensor decomposition, this intrinsic returns two groups which are the tensor factors of \(G\).

IsProportional(X, k): Mtrx, RngIntElt -> BoolElt, Tup

Given a matrix group \(G\) defined over a finite field that admits a tensor decomposition, this intrinsic returns true if and only if the matrix \(X\) is composed of \(k \times k\) blocks which differ only by scalars. If this is indeed the case, the tensor decomposition of \(X\) is also returned.

Example: Tensor (ex-8c10fc)

We define a subgroup of \(GL(6, 3)\) which admits a non-trivial tensor decomposition.

> P := GL(6, 3);
>
> g := P![ 0, 1, 1, 2, 1, 0, 2, 2, 1, 2, 1, 1, 1, 0, 2, 1, 2, 2, 1, 2, 2,
>          2, 2, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 2, 2 ];
>
> h := P![ 1, 0, 2, 1, 1, 2, 0, 0, 2, 0, 0, 2, 2, 0, 1, 0, 2, 1, 2, 1, 2,
>          2, 1, 1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 2, 1, 2 ];
>
> G := sub< P | g, h >;
> IsTensor(G);
true
> C := TensorBasis(G);

Run in calculatorCopy input

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

> G.1^C;
[0 0 2 0 2 0]
[0 0 2 2 2 2]
[2 0 0 0 2 0]
[2 2 0 0 2 2]
[0 0 0 0 1 0]
[0 0 0 0 1 1]
>

Run in calculatorCopy input

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

> IsProportional(G.1^C, 2);
true
<
 [2 0]
 [2 2],

 [0 1 1]
 [1 0 1]
 [0 0 2]
>

Run in calculatorCopy input

Finally, we display the tensor factors.

> A := TensorFactors(G);
> A[1];
MatrixGroup(2, GF(3))
Generators:
    [1 2]
    [2 2]

    [2 0]
    [2 2]
> A[2];
MatrixGroup(3, GF(3))
Generators:
    [0 1 0]
    [1 2 1]
    [1 2 0]

    [0 1 1]
    [1 0 1]
    [0 0 2]

Run in calculatorCopy input

Tensor-induced Groups

Let \(G\) be a subgroup of \({\operatorname{GL}}(d, K)\), where \(K = {\bf F}_{q}\) and \(q = p^e\) for some prime \(p\), and let \(V\) be the natural \(K[G]\)-module. Assume that \(d\) has a proper factorisation as \(u^r\). We say that \(G\) is tensor-induced if \(G\) preserves a decomposition of \(V\) as

\[U_1 \otimes U_2 \otimes \cdots \otimes U_r\]

where each \(U_i\) has dimension \(u > 1\), \(r > 1\), and the set of \(U_i\) is permuted by \(G\). If \(G\) is tensor-induced, then there is a homomorphism of \(G\) into the symmetric group \(S_r\).

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

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

IsTensorInduced(G : parameters): GrpMat -> BoolElt

InducedDegree: RngIntElt                    Default: "All"

Given a matrix group \(G\) defined over a finite field, return true if \(G\) is tensor-induced, false if \(G\) is not tensor-induced, and "unknown" if no decision can be reached.

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.

TensorInducedBasis(G): GrpMat -> GrpMatElt

Given a matrix group \(G\) defined over a finite field that is tensor-induced, this intrinsic returns the change-of-basis matrix which exhibits that \(G\) is tensor-induced.

TensorInducedPermutations(G): GrpMat -> SeqEnum

Given a matrix group \(G\) defined over a finite field that is tensor-induced, this intrinsic returns a sequence whose \(i\)-th entry is the homomorphic image of \(G.i\) in \(S_r\).

TensorInducedAction(G, g): GrpMat, GrpMatElt -> GrpPermElt

Given a matrix group \(G\) defined over a finite field that is tensor-induced, this intrinsic returns the tensor-induced action of the element \(g \in G\).

Example: Tensor Induced (ex-1ef8b8)

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

> G := GL(2, 3);
> S := Sym(3);
> G := TensorWreathProduct(G, S);
> IsTensorInduced(G);
true

Run in calculatorCopy input

We next recover the permutations.

> TensorInducedPermutations(G);
[
    Id(S),
    Id(S),
    (1, 2, 3),
    (1, 2)
]

Run in calculatorCopy input

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.

> C := TensorInducedBasis(G);
> x := G.1^C;
> x;
[2 0 0 0 0 0 0 0]
[0 2 0 0 0 0 0 0]
[0 0 2 0 0 0 0 0]
[0 0 0 2 0 0 0 0]
[1 0 0 0 1 0 0 0]
[0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0]
[0 0 0 1 0 0 0 1]

Run in calculatorCopy input

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

> IsProportional(x, 2);
true
<[2 0]
[0 2], [1 0 0 0]
[0 1 0 0]
[2 0 2 0]
[0 2 0 2]>
> IsProportional(x, 4);
true
<[2 0 0 0]
[0 2 0 0]
[0 0 2 0]
[0 0 0 2], [1 0]
[2 2]>

Run in calculatorCopy input

Normalisers of Extraspecial \(r\)-groups and Symplectic 2-groups

Let \(G \leq GL(d, q)\), where \(d=r^m\) for some prime \(r\). If \(G\) is contained in the normaliser of an \(r\)-group \(R\), of order either \(r^{2m+1}\) or \(2^{2m+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 [Niemeyer, 2005] 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".

IsExtraSpecialNormaliser(G): GrpMat -> BoolElt

Given a matrix group \(G\) defined over a finite field, the intrinsic returns true if \(G\) normalises an extraspecial \(r\)-group or 2-group of symplectic type, false if \(G\) is known not to normalise an extraspecial \(r\)-group or a 2-group of symplectic type, or "unknown" if it cannot reach a conclusion.

ExtraSpecialParameters(G): GrpMat -> [RngIntElt, RngIntElt]

Given a matrix group \(G\) defined over a finite field that is known to normalise an extraspecial \(r\)-group or 2-group of symplectic type, this intrinsic returns a sequence of two integers, \(r\) and \(n\), where the extraspecial or symplectic subgroup \(R\) normalised by \(G\) has order \(r^{n}\).

ExtraSpecialGroup(G): GrpMat -> GrpMat

Given a matrix group \(G\) defined over a finite field that is known to normalise an extraspecial \(r\)-group or 2-group of symplectic type, this intrinsic returns the extraspecial or symplectic subgroup normalised by \(G\).

ExtraSpecialNormaliser(G): GrpMat -> SeqEnum

Given a matrix group \(G\) defined over a finite field that is known to normalise an extraspecial \(r\)-group or 2-group of symplectic type, this intrinsic returns the action of the generators of \(G\) on its normal extraspecial or symplectic subgroup as a sequence of matrices, each of degree \(2r\), one for each generator of \(G\).

ExtraSpecialAction(G, g): GrpMat, GrpMatElt -> GrpMatElt

Given a matrix group \(G\) defined over a finite field that is known to normalise an extraspecial \(r\)-group or 2-group of symplectic type, this intrinsic returns a matrix of degree \(2r\) describing the action of element \(g\) on the extraspecial or symplectic group normalised by \(G\).

ExtraSpecialBasis(G): GrpMat -> GrpMatElt

Given a matrix group \(G\) defined over a finite field, which is the odd prime degree case of \(G\) normalising an extraspecial \(r\)-group or 2-group of symplectic type, this intrinsic returns the change-of-basis matrix which conjugates the normal extraspecial subgroup into a “nice” representation, generated by a diagonal and a permutation matrix.

Example: Extra Special Normaliser (ex-2adbb0)

For this example we construct a subgroup \(G\) of \({\operatorname{GL}}(7, 8)\) that normalises an extraspecial \(r\)-group or \(2\)-group of symplectic type.

> F:=GF(8);
> P:=GL(7,F);
> w := PrimitiveElement(F);
> g1:=P![
> w,0,w^2,w^5,0,w^3,w,w,1,w^6,w^3,0,w^4,w,w^2,w^6,w^4,1,w^3,w^3,w^5,
> w^6,w,w^3,1,w^5,0,w^4,1,w^6,w^3,w^6,w^3,w^2,w^2,w^3,w^6,w^6,w^4,1,w^2,w^4,
> w^5,w^4,w^2,w^6,1,w^5,w ];
> g2:=P![w^3,w^4,w^2,w^6,w,w,w^3,w^3,w^4,w,w,w^2,w^3,w^3,w,w^3,w^5,w,1,w^3,w,
> 0,w^2,w^6,w,w^5,1,w,w^6,0,w^3,0,w^4,w,w^5,w^3,w^3,1,w^3,w^5,w^5,w^3,
> w^4,w^6,w,w^6,w^4,w^4,0 ];
> g3:=P![w^5,w^6,w^2,w,w,w^4,w^6,w^6,w^6,w,w^6,w,1,w^3,w,w^6,w^2,w,w^6,w^3,w^6,
> w^2,w^6,w^6,w^3,w,w^6,w^5,0,w^4,w^6,w^6,w,w^2,0,w,w^3,w^5,w^2,w^3,w^4,w^6,
> 0,w^3,w,w^3,w^4,w^3,1];
> gens := [g1,g2,g3];
> G := sub< P | gens >;
> IsExtraSpecialNormaliser(G);
true

Run in calculatorCopy input

So \(G\) has the desired normaliser property.

> ExtraSpecialParameters (G);
[ 7, 3 ]
> N:=ExtraSpecialNormaliser(G);
> N;
[
    [3 4]
    [1 4],

    [4 3]
    [0 2],

    [1 0]
    [0 1]
]

Run in calculatorCopy input

Writing Representations over Subfields

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

IsOverSmallerField(G : parameters): GrpMat -> BoolElt, GrpMat

Scalars  : BoolElt                      Default: false
Algorithm: MonStgElt                    Default: "GLO"

Given an absolutely irreducible matrix group \(G\) defined over a finite field \(K\), this intrinsic decides whether or not \(G\) has an equivalent representation over a subfield of \(K\). If so, it returns true and the representation over the smallest possible subfield, otherwise it returns false. If the optional argument Scalars is true then decide whether or \(G\) modulo scalars has an equivalent representation over a subfield of \(K\). If the optional argument Algorithm is set to "GH", then the non-scalar case uses the original Glasby and Howlett algorithm. The default is the Glasby, Leedham-Green and O’Brien algorithm, specified by "GLO".

IsOverSmallerField(G, k : parameters): GrpMat -> BoolElt, GrpMat

Scalars  : BoolElt                      Default: false
Algorithm: MonStgElt                    Default: "GLO"

Given an absolutely irreducible matrix group \(G\) defined over a finite field \(K\), and a positive integer \(k\) which is a proper divisor of the degree of \(K\), this intrinsic decides whether or not \(G\) has an equivalent representation over a proper subfield of \(K\) having degree \(k\) over the prime field. If so, it returns true and the representation over this subfield, else it returns false. If the optional argument Scalars is true then it decides whether or not \(G\) modulo scalars has an equivalent representation over a degree \(k\) subfield of \(K\). If the optional argument Algorithm is set to "GH", then the non-scalar case uses the original Glasby and Howlett algorithm. The default is the Glasby, Leedham-Green and O’Brien algorithm, specified by "GLO".

SmallerField(G): GrpMat -> FLdFin

Given an absolutely irreducible matrix group \(G\) defined over a finite field \(K\), which can be written over a proper subfield of \(K\) (possibly modulo scalars), return the subfield.

SmallerFieldBasis(G): GrpMat -> GrpMatElt

Given an absolutely irreducible matrix group \(G\) defined over a finite field \(K\), which can be written over a proper subfield of \(K\) (possibly modulo scalars), return the change of basis matrix for \(G\) which rewrites \(G\) over the smaller field.

SmallerFieldImage(G, g): GrpMat, GrpMatElt -> GrpMatElt

Given an absolutely irreducible matrix group \(G\) defined over a finite field \(K\), which can be written over a proper subfield of \(K\) (possibly modulo scalars), return the image of \(g \in G\) in the group defined over the subfield.

Example: Is Over Smaller Field (ex-3b0781)

We define a subgroup of \({\operatorname{GL}}(3, 8)\) which can be written over \({\bf F}_{2}\).

> G := GL (2, GF (3, 2));
> H := GL (2, GF (3, 8));
> K := sub < H | G.1, G.2 >;
> K;
MatrixGroup(2, GF(3^8))
Generators:
    [ $.1^820        0]
    [       0        1]

    [       2        1]
    [       2        0]
> flag, M := IsOverSmallerField (K);
> flag;
true
> M;
MatrixGroup(2, GF(3^2))
Generators:
    [$.1^7 $.1^2]
    [    1     2]

    [$.1^7 $.1^6]
    [$.1^2 $.1^5]
> F := GF(3, 4);
> G := MatrixGroup<2, F | [ F.1^52, F.1^72, F.1^32, 0 ],
>                                [ 1, 0, F.1^20, 2 ] >;
> flag, X := IsOverSmallerField (G);
> flag;
false

Run in calculatorCopy input

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

> flag, X := IsOverSmallerField (G: Scalars := true);
> flag;
true
> X;
MatrixGroup(2, GF(3))
Generators:
    [2 1]
    [1 0]

    [2 1]
    [1 1]
> SmallerField (G);
Finite field of size 3
> SmallerFieldBasis (G);
[F.1^33 F.1^23]
[F.1^43 F.1^63]
> g := G.1 * G.2^2; g;
[F.1^52 F.1^72]
[F.1^32      0]
> SmallerFieldImage (G, g);
[1 2]
[2 0]

Run in calculatorCopy input

WriteOverSmallerField(G, F): GrpMat, FldFin -> GrpMat, Map

Given a group \(G\) of \(d \times d\) matrices over a finite field \(E\) having degree \(e\) and a subfield \(F\) of \(E\) having degree \(f\), write the matrices of \(G\) as \(de/f\) by \(de/f\) matrices over \(F\) and return the group and the isomorphism.

Example: Write Over Smaller Field (ex-c2e1e0)

We define the group \({\operatorname{GL}}(2, 4)\) and then rewrite in over \({\bf F}_{2}\) as a degree 4 matrix group.

> G := GL(2, 4);
> H := WriteOverSmallerField(G, GF(2));
> H;
MatrixGroup(4, GF(2))
Generators:
    [0 1 0 0]
    [1 1 0 0]
    [0 0 1 0]
    [0 0 0 1]

    [1 0 1 0]
    [0 1 0 1]
    [1 0 0 0]
    [0 1 0 0]

Run in calculatorCopy input

Decompositions with Respect to a Normal Subgroup

SearchForDecomposition(G, S): GrpMat, [GrpMatElt] -> BoolElt

Given a matrix group \(G\) defined over a finite field and a sequence \(S\) of elements of \(G\), this intrinsic first constructs the normal closure \(N\) of \(S\) in \(G\). It then seeks to decide whether or not \(G\), with respect to \(N\), has a decomposition corresponding to one of the categories (ii)–(vi) in the theorem of Aschbacher stated at the beginning of this section. Theoretical details of the algorithms used may be found in Holt, Leedham-Green, O’Brien, and Rees [Holt et al., 1996]. In summary, it tests for one of the following possibilities:

(ii)

\(G\) acts semilinearly over an extension field \(L\) of \(K\), and \(N\) acts linearly over \(L\);

(iii)

\(G\) acts imprimitively on \(V\) and \(N\) fixes each block of imprimitivity;

(iv)

\(G\) preserves a tensor product decomposition \(U \otimes W\) of \(V\), where \(N\) acts as scalar matrices on \(U\);

(v)

\(N\) acts absolutely irreducibly on \(V\) and is an extraspecial \(p\)-group for some prime \(p\), or a 2-group of symplectic type;

(vi)

\(G\) preserves a tensor-induced decomposition \(V = \otimes ^mU\) of \(V\) for some \(m>1\), where \(N\) acts absolutely irreducibly on \(V\) and fixes each of the \(m\) factors. If one of the listed decompositions is found, then the function reports the type found and returns true; if no decomposition is found with respect to \(N\), then the function returns false. The answer provided by the function is conclusive for decompositions of types (ii)–(v), but a negative answer for (vi) is not necessarily conclusive. 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).

Accessing the Decomposition Information

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.

Example: Decompose (ex-14d37b)

We begin with an example where no decomposition exists.

> G := GL(4, 5);
> SearchForDecomposition (G, [G.1]);
Smash: No decomposition found
false

Run in calculatorCopy input

The second example is of an imprimitive decomposition.

> M := GL (4, 7);
> P := Sym (3);
> G := WreathProduct (M, P);
> SearchForDecomposition (G, [G.1, G.2]);
Smash: G is imprimitive
true
> IsPrimitive (G);
false
> BlocksImage (G);
Permutation group acting on a set of cardinality 3
    Id($)
    Id($)
    (1, 2, 3)
    (1, 2)

Run in calculatorCopy input

The third example admits a semilinear decomposition.

> P := GL(6,3);
> g1 := P![0,1,0,0,0,0,-1,0,0,0,0,0,
>          0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,0,1];
> g2 := P![-1,0,0,0,1,0,0,-1,0,0,0,1,
>          -1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0,0,0,0,0,-1,0,0];
> g3 := P![1,0,0,0,0,0,0,-1,0,0,0,0,
>          0,0,1,0,0,0,0,0,0,-1,0,0,0,0,0,0,1,0,0,0,0,0,0,-1];
> G := sub <P | g1, g2, g3 >;
>
> 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 ]

Run in calculatorCopy input

The fourth example admits a tensor product decomposition.

> F := GF(5);
> G := GL(5, F);
> H := GL(3, F);
> P := GL(15, F);
> A := MatrixAlgebra (F, 5);
> B := MatrixAlgebra (F, 3);
> g1 := A!G.1; g2 := A!G.2;  g3 := A!Identity(G);
> h1 := B!H.1; h2 := B!H.2; h3 := B!Identity(H);
> w := TensorProduct (g1, h3);
> x := TensorProduct (g2, h3);
> y := TensorProduct (g3, h1);
> z := TensorProduct (g3, h2);
> G := sub < P | w, x, y, z>;
> SearchForDecomposition (G, [G.1, G.2]);
Smash: G is a tensor product
true
> IsTensor (G);
true
> TensorBasis (G);
[1 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 0]
[4 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 4 0 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 4 0 1 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 4 0 1]
[0 0 0 0 0 0 0 0 0 4 0 1 0 0 0]
[1 4 4 0 0 0 0 0 0 0 0 0 0 0 0]
[0 0 0 1 4 4 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 1 4 4 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 1 4 4]
[0 0 0 0 0 0 0 0 0 1 4 4 0 0 0]

Run in calculatorCopy input

Our fifth example is of a tensor-induced decomposition.

> M := GL (3, GF(2));
> P := Sym (3);
> G := TensorWreathProduct (M, P);
> SearchForDecomposition (G, [G.1]);
Smash: G is tensor induced
true
>
> IsTensorInduced (G);
true
> TensorInducedPermutations (G);
[ Id(P), Id(P), (1, 3, 2), (1, 3) ]

Run in calculatorCopy input

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

> F := GF(5);
> P := GL(4,F);
> g1 := P![ 1,0,0,0,0,4,0,0,2,0,2,3,3,0,4,3];
> g2 := P![ 4,0,0,1,2,4,4,0,1,0,1,2,0,0,0,1];
> g3 := P![ 4,0,1,1,0,1,0,0,0,1,3,4,0,4,3,2];
> g4 := P![ 2,0,4,3,4,4,2,4,0,1,3,4,4,2,0,1];
> g5 := P![ 1,1,3,4,0,0,3,4,2,0,0,4,3,1,3,4];
> g6 := P![ 2,0,0,0,0,2,0,0,0,0,2,0,0,0,0,2];
> G := sub < P | g1, g2, g3, g4, g5, g6 >;
> SearchForDecomposition (G, [G.4]);
Smash: G is normaliser of symplectic 2-group
true
> IsExtraSpecialNormaliser (G);
true
> ExtraSpecialParameters (G);
[2, 6]
> g := G.1 * G.2;
> ExtraSpecialAction(G, g);
[0 1 0 0]
[1 1 0 0]
[0 1 1 1]
[1 1 1 0]

Run in calculatorCopy input