# Monte Carlo Algorithms for Subgroups ## `CentraliserOfInvolution(G, g : parameters): GrpMat, GrpMatElt -> GrpMat` ```magma Central : BoolElt Default: false NumberRandom : RngIntElt Default: 100 CompletionCheck: UserProgram Default: ``` Given an involution $g$ in $G$, this function returns the centraliser $C$ of $g$ in $G$ using an algorithm of John Bray [[Bray, 2000](../../references.md#cite-bray00)]. Since it is Monte Carlo, it may return only a subgroup of the centraliser. If `Central` is `true`, the projective centraliser of $g$ will be constructed: its elements commute with $g$ modulo the centre of $G$. The optional argument `CompletionCheck` is a function which can be used to determine when we have constructed the centraliser. It takes the following arguments: the parent group $G$; the proposed centraliser $C$; the involution $g$. By default, the algorithm completes when 20 generators have been found for the centraliser or when `NumberRandom` elements have been considered. ## `CentraliserOfInvolution(G, g, w : parameters): GrpMat, GrpMatElt, GrpSLPElt -> GrpMat, []` ```magma Randomiser : GrpRandProc Default: Central : BoolElt Default: false NumberRandom : RngIntElt Default: 100 CompletionCheck: UserProgram Default: ``` Given an involution $g$ in a matrix group $G$ together with a SLP $w$ corresponding to $g$, this function returns the centraliser $C$ of $g$ in $G$ and SLPs for the generators of $C$. The algorithm used is due to John Bray [[Bray, 2000](../../references.md#cite-bray00)]. Since it is Monte Carlo, it may return a proper subgroup of the centraliser. If `Central` is `true`, the projective centraliser of $g$ is constructed: its elements commute with $g$ modulo the centre of $G$. The parameter `Randomiser` specifies the random process that is to be used to construct the centraliser. By default `Randomiser` is the value returned by `RandomProcessWithWords (G)`. The SLP for $g$ must lie in the word group of this process. The optional argument `CompletionCheck` is a function which can be used to determine when we have constructed the centraliser. It takes four arguments: the parent group $G$; the proposed centraliser $C$; the involution $g$; and the list of the SLPs for the generators of $C$. By default, the algorithm completes when 20 generators have been found for the centraliser or when `NumberRandom` elements have been considered. ## `AreInvolutionsConjugate({G, x, wx, y,}{ wy : parameters}): GrpMat, GrpMatElt, GrpSLPElt, GrpMatElt, GrpSLPElt -> BoolElt, GrpMatElt, GrpSLPElt` ```magma Randomiser: GrpRandProc Default: MaxTries : RngIntElt Default: 100 ``` This Monte Carlo algorithm attempts to construct an element $c$ of the group $G$ which conjugates the involution $x$ to the involution $y$. The corresponding SLPs for $x$ and $y$ are $wx$ and $wy$ respectively. If such an element $c$ is found, then three values are returned: `true`, $c$ and the SLP for $c$. Otherwise, the boolean value `false` is returned. At most `MaxTries` random elements are considered. The parameter `Randomiser` specifies the random process to be used. By default `Randomiser` is the value returned by `RandomProcessWithWords (G)`. The SLPs for $x$ and $y$ must lie in the word group of this process and the SLP for $c$ will also lie in this word group. ## `NormalClosureMonteCarlo(G, H): GrpMat, GrpMat -> GrpMat` ## `NormalClosureMonteCarlo(G, H : parameters): GrpPerm, GrpPerm -> GrpMat` ```magma slpsH : [] Default: [] ErrorProb : FltRatElt Default: 9/10 SubgroupChainLength: RngIntElt Default: Degree(H) ``` This Monte Carlo algorithm constructs the normal closure $N$ of $H$ in $G$. If SLPs of the generators of $H$ in the generators of $G$ are supplied via the parameter `slpsH`, then the function also returns SLPs for the generators of $N$. The parameter `SubgroupChainLength` is used to specify an upper bound on the length of any subgroup chain in $H$. The probability that $N$ is a proper subgroup of the normal closure is bounded above by `ErrorProb`, assuming that `SubgroupChainLength` is correctly set. ## `DerivedGroupMonteCarlo(G : parameters): GrpMat -> GrpMat` ```magma Randomiser : GrpRandProc Default: NumberGenerators: RngIntElt Default: 10 MaxGenerators : RngIntElt Default: 100 ``` Given a matrix group $G$ defined over a finite field, this intrinsic returns the derived group of $G$, and a list of SLPs of its generators in the generators of $G$. The SLPs are elements of the word group of the random process. The algorithm is Monte Carlo and may return a proper subgroup of the derived group. The parameter `Randomiser` specifies the random process to be used. By default `Randomiser` is the value returned by `RandomProcessWithWords (G)`. At least `NumberGenerators` and at most `MaxGenerators` will be constructed for the derived group. ## `IsProbablyPerfect(G : parameters): Grp -> BoolElt` ```magma NumberRandom: RngIntElt Default: 100 ``` This intrinsic attempts to prove that a matrix or permutation group $G$ is perfect by establishing that its generators are in $G'$. Since it is Monte-Carlo, there is a small probability of error. If the function returns `true`, then $G$ is perfect; if it returns `false`, then $G$ might still be perfect. Each call considers `NumberRandom` random elements. The algorithm is due to Leedham-Green and O’Brien [[Leedham-Green and O'Brien, 2002](../../references.md#cite-crlg-eaob)] and it uses `NormalSubgroupRandomElement`. ## `Example: Is Probably Perfect (ex-00c3d9)` We illustrate `IsProbablyPerfect` with a subgroup of $GU(4, 9)$. ```magma > G := GU(4, 9); > N := sub; ``` The generators of $N$ have been chosen to be a normal generating set for the derived group of $G$. ```magma > IsProbablyPerfect(N); false > x := NormalSubgroupRandomElement(G, N); > x; [$.1^68 $.1^34 $.1^26 $.1^55] [$.1^23 $.1^78 $.1^16 $.1^72] [$.1^42 $.1^2 $.1^24 2] [$.1^11 $.1^66 $.1^13 $.1^29] > L := sub< G | N, x>; > IsProbablyPerfect(L); true ``` We now consider $SO(7, 5)$ and $\Omega(7, 5)$. ```magma > G := SO(7, 5); > IsProbablyPerfect(G); false > G := Omega(7, 5); > IsProbablyPerfect(G); true ```