Testing Finiteness

In this section, K is a finite degree extension of the field F(x₁, ..., x_m), where F is Q, a number field, or a finite field. Also m ≥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 GL(n, K). If G is finite then the function returns true, otherwise false. The function is an implementation of algorithms from [DFO13b], [DF09], [DFO09], [DF08].

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 [DF09] (resp. [DFO09]) 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 [DF08, 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 GL(n, K). If the function succeeds, then it returns true and an isomorphic copy of G in GL(n, GF(q)) where q is a prime power; otherwise it returns false. A description of the method used is in [DFO13b, Section 4.3]. If char K > 0, then GF(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 [DF09] (resp. [DFO09]) 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 ... 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 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.