The LMG functions#

The LMG (large matrix group) functions are designed to provide a user-friendly interface to the CompositionTree package, and thereby enable the user to carry out a limited range of structural calculations in a matrix group that is too large for the use of BSGS methods.

By default, these methods have a small probability of failing or even of returning incorrect results. For most examples, at the cost of some extra time, the user can ensure that the computed results are verified as correct by calling LMGInitialise with the Verify flag on the group \(G\) before calling any of the other functions. (Once CompositionTree or any of the LMG functions has been called on a group, further calls of LMGInitialise will have no effect.)

Let \(G\) be a matrix group over a finite field. On the first call of any of the LMG functions on \(G\), Magma decides whether it will use BSGS or Composition Tree based methods on \(G\). It does this by carrying out a quick calculation to decide whether any of the basic orbit lengths would be larger than a constant LMGSchreierBound, which is set to 40000 by default, but can be changed by the user. If all basic orbit lengths are at most LMGSchreierBound, then BSGS methods are used on \(G\), and the LMG functions are executed using the corresponding standard Magma functions. Otherwise, Composition Tree methods are used, starting with a call of CompositionTree\((G)\).

Composition Tree methods are also used if the user calls CompositionTree on the group before using th LMG functions, or if the user calls LMGInitialize with the Al option set to "CompositionTree".

SetVerbose("LMG", n) with \(n=1,2\) or 3 will provide increasing levels of information on the progress of the functions.

SetLMGSchreierBound(n): RngIntElt#: Set the constant LMGSchreierBound to \(n\).

LMGInitialize(G : parameters): GrpMat#

LMGInitialise(G : parameters): GrpMat#

Al                 : MonStgElt                    Default: ""
Verify             : BoolElt                      Default: false
RandomSchreierBound: RngIntElt                    Default: LMGSchreierBound

It is not normally necessary to call this function but, by setting the optional parameters, it can be used to initialise \(G\) for LMG computations with a different value of LMGSchreierBound or, by setting Al to be "CompositionTree" (or "CT" or "RandomSchreier" (or "RS"), to force the use of either Composition Tree or BSGS methods on \(G\).

If the Verify flag is set, then an attempt will be made to verify the correctness of the computed BSGS or Composition Tree. This will make the initialisation process slower, and for some groups the increased memory requirements will make verification impractical. In that case, a warning message is displayed.

LMGOrder(G): GrpMat[FldFin] -> RngIntElt#: Given a matrix group \(G\) defined over a finite field, this intrinsic returns the order of \(G\).

LMGFactoredOrder(G): GrpMat[FldFin] -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, this intrinsic returns the factored order of \(G\).

LMGIsIn(G, x): GrpMat, GrpMatElt -> BoolElt, GrpSLPElt#: Given a matrix group \(G\) defined over a finite field \({\mathbb{F}}_q\), and an element \(x\) of the generic overgroup GL\((n,q)\) of \(G\); if \(x \in G\) then the intrinsic returns true and the corresponding element of WordGroup(G); and false otherwise.

LMGIsSubgroup(G, H): GrpMat, GrpMat -> BoolElt#: Given a matrix group \(G\) defined over a finite field \({\mathbb{F}}_q\), and a subgroup \(H\) of the generic overgroup GL\((n,q)\) of \(G\), the intrinsic returns true if \(H \le G\) and false otherwise.

LMGEqual(G, H): GrpMat, GrpMat -> BoolElt#: Given a matrix groups \(G\) and \(H\) belonging to a common overgroup GL\((n,q)\), the intrinsic returns true if \(G\) and \(H\) are equal and false otherwise.

LMGIndex(G, H): GrpMat, GrpMat -> RngIntElt#: Given a matrix group \(G\) defined over a finite field, and a subgroup \(H\) of \(G\), the intrinsic returns the index of \(H\) in \(G\).

LMGIsNormal(G, H): GrpMat, GrpMat -> BoolElt#: Given a matrix group \(G\) defined over a finite field, and a subgroup \(H\) of \(G\), the intrinsic returns true if \(H\) is normal in \(G\) and false otherwise.

LMGNormalClosure(G, H): GrpMat, GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, and a subgroup \(H\) of \(G\), the intrinsic returns the normal closure of \(H\) in \(G\).

LMGDerivedGroup(G): GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the derived subgroup of \(G\).

LMGCommutatorSubgroup(G, H): GrpMat, GrpMat -> GrpMat#: Let \(g\) and \(H\) be subgroups of GL\((n,q)\). This intrinsic returns the commutator subgroup of \(G\) and \(H\) as a subgroup of GL\((n,q)\).

LMGIsSoluble(G): GrpMat -> BoolElt#
LMGIsSolvable(G): GrpMat -> BoolElt#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns true if \(G\) is soluble and false otherwise.

LMGIsNilpotent(G): GrpMat -> BoolElt#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns true if \(G\) is nilpotent and false otherwise.

LMGCompositionSeries(G): GrpMat[FldFin] -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a composition series for \(G\).

LMGCompositionFactors(G): GrpMat[FldFin] -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the composition factors of \(G\). The Handbook entry for CompositionFactors(G) of a finite group gives a detailed description of how to interpret the returned sequence.

LMGChiefSeries(G): GrpMat[FldFin] -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a chief series for \(G\).

LMGChiefFactors(G): GrpMat[FldFin] -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the chief factors \(G\). The Handbook entry for ChiefFactors(G) of a finite group gives a detailed description of how to interpret the returned sequence.

LMGUnipotentRadical(G): GrpMat -> GrpMat, GrpPC, Map#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the unipotent radical \(U\) of the matrix group \(G\). A group \(P\) of type GrpPC and an isomorphism \(U \rightarrow P\) are also returned.

LMGSolubleRadical(G): GrpMat -> GrpMat, GrpPC, Map#
LMGSolvableRadical(G): GrpMat -> GrpMat, GrpPC, Map#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the soluble radical \(S\) of \(G\). A group \(P\) of type GrpPC and an isomorphism \(S \rightarrow P\) are also returned.

LMGFittingSubgroup(G): GrpMat -> GrpMat, GrpPC, Map#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the Fitting subgroup \(S\) of \(G\). A group \(P\) of type GrpPC and an isomorphism \(S \rightarrow P\) are also returned.

LMGCentre(G): GrpMat -> GrpMat#
LMGCenter(G): GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the centre of \(G\).

LMGSylow(G, p): GrpMat, RngIntElt -> GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a Sylow \(p\)-subgroup of \(G\).

LMGSocleStar(G): GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the inverse image in \(G\) of the socle of \(G/S\), where \(S\) is the soluble radical of \(G\).

LMGSocleStarFactors(G): GrpMat -> SeqEnum, SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the simple direct factors of LMGSocleStar(G)/LMGSolubleRadical(G), which may be represented projectively for large classical groups. A list of maps from the factors to \(G\) is also returned.

LMGSocleStarAction(G): GrpMat -> Map, GrpPerm, GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the map \(\phi\) representing the conjugation action of \(G\) on the simple direct factors of LMGSocleStar(G)/LMGSolubleRadical(G). The image and kernel of \(\phi\) are also returned.

LMGSocleStarActionKernel(G): GrpMat -> GrpMat, GrpPC, Map#: Given a matrix group \(G\) defined over a finite field, this intrinsic returns three values. The first is the kernel of the conjugation action of \(G\) on the simple direct factors of LMGSocleStar(G)/LMGSolubleRadical(G). A group \(P\) of type GrpPC isomorphic to LMGSocleStarActionKernel(G)/LMGSocleStar(G) and the epimorphism \(G \rightarrow P\) are also returned.

LMGSocleStarQuotient(G): GrpMat -> GrpPerm, Map, GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the quotient group G/LMGSocleStar(G) represented as a permutation group, with associated epimorphism and kernel.

Example: LM Gex (ex-533478)#

We apply the LMG functions to a maximal subgroup of \({\operatorname{SL}}(12, 5)\).

> SetVerbose("LMG", 1);
> C := ClassicalMaximals("L", 12, 5);
> G := C[4];
> LMGFactoredOrder(G);
RandomSchreierBound is 40000
Using CompositionTree on this group
Composition tree computed
Composition series has length 40
Order of group is:  27845944957511377275508129969239234924316406250000000000000\\
0000000000000000000
[ <2, 32>, <3, 7>, <5, 66>, <7, 1>, <11, 1>, <13, 3>, <31, 3>, <71, 1>, <313,
1>, <19531, 1> ]
> LMGChiefFactors(G);
Classifying composition factors
Defined PCGroup of solvable radical
Computed PCGroup of SocleKernel/SocleStar
    G
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  A(3, 5)                = L(4, 5)
    *
    |  A(7, 5)                = L(8, 5)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(5) (32 copies)
    1
> D := LMGDerivedGroup(G);
RandomSchreierBound is 40000
Using CompositionTree on this group
Composition tree computed
Composition series has length 38
Order of group is:  69614862393778443188770324923098087310791015625000000000000\\
000000000000000000
> LMGIndex(G, D);
4
> SetVerbose("LMG", 0);
> LMGEqual( LMGDerivedGroup(D), D );
true
> S := LMGSolubleRadical(G);
> LMGFactoredOrder(S);
[ <2, 4>, <5, 32> ]
> LMGIsSoluble(G);
false
> LMGIsSoluble(S);
true
> LMGIsNilpotent(S);
false
> #LMGCentre(G);
4
> #LMGCentre(S);
4

Run in calculator

We carelessly used the standard Magma Order function in the above two commands, but it did not matter, because it was small. We will be more careful next time!

> F := LMGFittingSubgroup(G);
> LMGFactoredOrder( LMGCentre(F) );
[ <2, 2>, <5, 32> ]
> P := LMGSylow(G, 5);
> LMGFactoredOrder(P);
[ <5, 66> ]
> LMGEqual( D, LMGNormalClosure(G,P) );
true
> facs, maps := LMGSocleStarFactors(G);
> #facs;
2
> LMGChiefFactors(facs[1]);
    G
    |  A(7, 5)                = L(8, 5)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    1

Run in calculator

Note that, for large classical groups, the socle-star factors are represented projectively.

> I := sub< Generic(G) | [ facs[2].i @ maps[2] : i in [1..Ngens(facs[2])] ] >;
> LMGChiefFactors( LMGNormalClosure(G, I) );
    G
    |  A(3, 5)                = L(4, 5)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(2)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    *
    |  Cyclic(5) (4 copies)
    1

Run in calculator

The remaining functions in this section will work only if a permutation representation can be computed for \(G/L\), where \(L\) is the soluble radical of \(G\). Apart from LMGRadicalQuotient itself, they all operate by solving the problem first in \(G/L\) and then lifting the solution through elementary abelian layers of \(L\). Results are returned using the same formats as for other types of finite groups.

LMGRadicalQuotient(G): GrpMat -> GrpPerm, Map, GrpMat#

Given a matrix group \(G\) defined over a finite field, the intrinsic returns a permutation group \(P\) isomorphic to \(G/L\), where \(L\) is the soluble radical of \(G\). An epimorphism \(G \to P\) and its kernel \(L\) are also returned.

Of course, this will only work if \(G/L\) has such a representation of sufficiently small degree. This function is called implicitly as a first step in all of the remaining functions in this section.

LMGCentraliser(G, g): GrpMat, GrpMatElt -> GrpMat#
LMGCentralizer(G, g): GrpMat, GrpMatElt -> GrpMat#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the centraliser in the matrix group \(G\) of \(g \in G\).

LMGIsConjugate(G, g, h): GrpMat, GrpMatElt, GrpMatElt -> BoolElt, GrpMatElt#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns true if the elements \(g,h\) in \(G\) are conjugate. If so, a conjugating element will also be returned.

LMGClasses(G): GrpMat -> SeqEnum#
LMGConjugacyClasses(G): GrpMat -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns the conjugacy classes of \(G\).

LMGNormaliser(G, H): GrpMat, GrpMat -> GrpMat#
LMGNormalizer(G, H): GrpMat, GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, and a subgroup \(H\) of \(G\), the intrinsic returns the normaliser of \(H\) in \(G\).

LMGIsConjugate(G, H, K): GrpMat, GrpMat, GrpMat -> BoolElt, GrpMatElt#: Given a matrix group \(G\) defined over a finite field, and subgroups \(H\) and \(K\) of \(G\), the intrinsic returns true if the subgroups \(H\) and \(K\) are conjugate in \(G\). If so, a conjugating element will also be returned.

LMGMeet(G, H, K): GrpMat, GrpMat, GrpMat -> GrpMat#: Given a matrix group \(G\) defined over a finite field, and subgroups \(H\) and \(K\) of \(G\), the intrinsic returns their intersection.

LMGMaximalSubgroups(G): GrpMat -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a list of subgroup records defining representatives of the conjugacy classes of maximal subgroups of \(G\).

LMGNormalSubgroups(G): GrpMat -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a list of subgroup records defining the normal subgroups of \(G\).

LMGLowIndexSubgroups(G, n): GrpMat, RngIntElt -> SeqEnum#: Given a matrix group \(G\) defined over a finite field, the intrinsic returns a list of representatives of the conjugacy classes of subgroups of index at most \(n\) in \(G\).

LMGCosetAction(G, H : parameters): GrpMat, GrpMat -> Map, GrpPerm, GrpMat#

ker: BoolElt                    Default: true

Given a subgroup \(H\) of a matrix group \(G\) defined over a finite field, return the homomorphism \(f:G \to P\) defining the action of \(G\) by multiplication on the right cosets of \(H\) in \(G\). The image \(P\) (a permutation group) and the kernel of \(f\) are also returned.

If the optional parameter ker is set to false then the kernel of \(f\) is not computed.

A right transversal of \(H\) in \(G\), in which the ordering corresponds to the order on the points permuted by \(P\), is computed at the same time, and this can be accessed by calling LMGRightTransversal(G,H : ca:=f).

LMGCosetImage(G, H): GrpMat, GrpMat -> GrpPerm#: Given a subgroup \(H\) of a matrix group \(G\) defined over a finite field, return the image \(P\) of the homomorphism \(f:G \to P\) defining the action of \(G\) by multiplication on the right cosets of \(H\) in \(G\).

LMGCosetActionInverseImage(G, f, i): GrpMat, Map, RngIntElt -> GrpMatElt#: The map \(f\) should be the result of a call of LMGCosetAction on some subgroup of the matrix group \(G\). An element of \(g \in G\) for which \(1^{f(g)} = i\) is returned.

LMGRightTransversal(G, H : parameters): GrpMat, GrpMat -> SeqEnum#

ca: Map                    Default: 

Given a subgroup \(H\) of a matrix group \(G\) defined over a finite field, return a right transversal of \(H\) in \(G\). The optional parameter ca should be the map returned by LMGCosetAction(G,H), and if this option is used then the elements in the transversal will be ordered in the same way as the points permuted by the image of ca.

LMGIsPrimitive(G): GrpMat -> BoolElt#: Decide whether matrix group \(G\) defined over a finite field is primitive.

LMGCharacterTable(G : parameters): GrpMat -> SeqEnum#: Compute the character table of the matrix group \(G\), using LMG functions for the calculations within the group. The overall method is as for the standard CharacterTable command.

Example: LM Gex2 (ex-fa2be2)#

We apply the LMG classes and character table functions to the Dempwolff Group. We will use LMGInitialize to force use of the composition tree methods.

> G := MatrixGroup(ATLASGroup("25L52"));
> G:Minimal;
MatrixGroup(69, GF(2)) of order 2^15 * 3^2 * 5 * 7 * 31
> LMGInitialize(G:Al := "CT");
> LMGChiefFactors(G);
  G
  |  A(4, 2)                    = L(5, 2)
  *
  |  Cyclic(2) (5 copies)
  1
> time cl := LMGClasses(G);
#Warning: we will need to find a perm rep of the radical quotient!
#Found perm rep of the radical quotient of degree 31
Time: 0.750
> #cl;
41
> time X := LMGCharacterTable(G);
Time: 4.510
> {* Degree(x): x in X *};
{* 1, 30, 124, 155, 217, 248, 280, 315^^6, 465^^4, 496,
651^^3, 744^^2, 868, 930^^3, 960, 1024, 1240, 1488, 1736^^4,
1984, 3720^^3, 11160^^2 *}
> &+[d^2 : d in $1] eq #G;
true

Run in calculator