Monte Carlo Algorithms for Subgroups

CentraliserOfInvolution(G, g : parameters): GrpMat, GrpMatElt -> GrpMat

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]. 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, []

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]. 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

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

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

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

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] and it uses NormalSubgroupRandomElement.

Example: Is Probably Perfect (ex-00c3d9)

We illustrate IsProbablyPerfect with a subgroup of \(GU(4, 9)\).

> G := GU(4, 9);
> N := sub<G | (G.1, G.2)>;

Run in calculatorCopy input

The generators of \(N\) have been chosen to be a normal generating set for the derived group of \(G\).

> 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

Run in calculatorCopy input

We now consider \(SO(7, 5)\) and \(\Omega(7, 5)\).

> G := SO(7, 5);
> IsProbablyPerfect(G);
false
> G := Omega(7, 5);
> IsProbablyPerfect(G);
true

Run in calculatorCopy input