Testing Finiteness

In this section, \(K\) is a finite degree extension of the field \(F(x_1, \ldots, x_m)\), where \(F\) is \(Q\), a number field, or a finite field. Also \(m \geq 0\) if char \(F = 0\), and \(m > 0\) otherwise.

IsFinite(G : parameters): GrpMat -> BoolElt, RngIntElt

NumberRandom  : RngIntElt                    Default: 10
Presentation  : MonStgElt                    Default: "CT"
Small         : RngIntElt                    Default: 10^6
OrderLimit    : RngIntElt                    Default: 10^15
Algebra       : BoolElt                      Default: true
Nilpotent     : BoolElt                      Default: false
UseCongruence : BoolElt                      Default: false
DetermineOrder: BoolElt                      Default: false
Prime         : RngintElt                    Default: 3

Let \(G\) be a finitely generated subgroup of \({\operatorname{GL}}(n, K)\). If \(G\) is finite then the function returns true, otherwise false. The function is an implementation of algorithms from [Detinko and Flannery, 2008, Detinko and Flannery, 2009, Detinko et al., 2009, Detinko et al., 2013].

The algorithm first tests whether NumberRandom random elements of \(G\) have finite order.

If the optional parameter Algebra is true and \(K\) is a function field of characteristic zero (resp. positive characteristic), then we use the “algebra algorithm” of [Detinko and Flannery, 2009] (resp. [Detinko et al., 2009]) to decide finiteness.

Otherwise, we prove that \(G\) is finite by first constructing a congruence homomorphism, then a presentation for the congruence image, and finally evaluates its relations to obtain normal generators for the congruence kernel. If char \(K = 0\), then the kernel should be trivial, otherwise the kernel is unipotent.

The optional parameter Presentation is used to dictate how the presentation is constructed. If its value is “CT”, then we use the presentation provided by CompositionTreeVerify. If its value is “PC” and the image is soluble, then we use a PC-presentation provided by LMGSolubleRadical. If its value is “FP” then we use the presentation provided by FPGroup or FPGroupStrong. If the order of the congruence image is less than the value of the optional argument Small, then we use FPGroup to construct the presentation; if it is less than the value of the optional argument OrderLimit, then we use FPGroupStrong to construct the presentation; otherwise we use the presentation provided by CompositionTreeVerify.

If \(K\) is \(Q\) or a number field and UseCongruence is true, then use congruence homomorphism machinery to decide; otherwise use default algorithm.

If \(G\) is known to be nilpotent then by setting the optional parameter Nilpotent to true, the function will call a special procedure for testing finiteness of nilpotent groups (see [Detinko and Flannery, 2008, Section 4.3]).

If the optional parameter DetermineOrder is set to true, and \(G\) is finite, then the function returns the order of \(G\). This may sometimes be more expensive than deciding finiteness.

The optional parameter Prime applies if \(K\) has characteristic 0: if Prime is positive, then it is a lower bound for the characteristic of the congruence image; if it is 0 then the function constructs a congruence image defined over a field of characteristic 0.

IsomorphicCopy(G : parameters): GrpMat -> BoolElt, GrpMat, HomGrp

Presentation       : MonStgElt                    Default: "CT"
Small              : RngIntElt                    Default: 10^6
OrderLimit         : RngIntElt                    Default: 10^15
Verify             : BoolElt                      Default: false
Algebra            : BoolElt                      Default: false
StartDegree        : RngIntElt                    Default: 1
EndDegree          : RngIntElt                    Default: 5
CompletelyReducible: BoolElt                      Default: false

The input is a finite subgroup \(G\) of \({\operatorname{GL}}(n, K)\). If the function succeeds, then it returns true and an isomorphic copy of \(G\) in \({\operatorname{GL}}(n,{\bf F}_{q})\) where \(q\) is a prime power; otherwise it returns false. A description of the method used is in [Detinko et al., 2013, Section 4.3]. If char \(K > 0\), then \({\bf F}_{q}\) has the same characteristic. Note that the function always succeeds if \(K\) has zero characteristic.

If the optional parameter Algebra is true and \(K\) is a function field of characteristic zero (resp. positive characteristic), then we use the “algebra algorithm” of [Detinko and Flannery, 2009] (resp. [Detinko et al., 2009]) to construct an isomorphic copy.

Otherwise we prove that a congruence homomorphism is an isomorphism by constructing a presentation for the congruence image and evaluating its relations to obtain normal generators for the congruence kernel.

The optional parameter Presentation is used to dictate how the presentation is constructed. If its value is “CT”, then we use the presentation provided by CompositionTreeVerify. If its value is “PC” and the image is soluble, then we use a PC-presentation provided by LMGSolubleRadical. If its value is “FP” then we use the presentation provided by FPGroup or FPGroupStrong. If the order of the congruence image is less than the value of the optional argument Small, then we use FPGroup to construct the presentation; if it is less than the value of the optional argument OrderLimit, then we use FPGroupStrong to construct the presentation; otherwise we use the presentation provided by CompositionTreeVerify.

If the optional parameter Verify is set to true then we first check whether \(G\) is finite.

If the characteristic of the coefficient field \(F\) is positive, then we investigate extensions of \(F\) in the range StartDegree \(\ldots\) EndDegree.

If the optional parameter CompletelyReducible is set to true then we use a more efficient algorithm to construct the isomorphic copy.

Order(G : parameters): GrpMat -> RngIntElt

Verify       : BoolElt                    Default: false
UseCongruence: BoolElt                    Default: false

Given a finite subgroup \(G\) of \({\operatorname{GL}}(n,K)\), the function returns the order of \(G\) by applying IsomorphicCopy to \(G\).

If the optional parameter Verify is set to true, then we first check that \(G\) is finite.

If \(K\) is \(Q\) or a number field and UseCongruence is true, then use congruence homomorphism machinery to decide; otherwise use default algorithm.