# 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` ```magma 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)$. ```magma > 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 ``` 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! ```magma > 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 ``` Note that, for large classical groups, the socle-star factors are represented projectively. ```magma > 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 ``` 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` ```magma 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` ```magma 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. ```magma > 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 ```