Deciding Virtual Properties of Linear Groups

In this section, K is a finite degree extension of 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.

We describe algorithms to decide various "virtual" properties of a finitely generated linear group over an infinite field. Details of the algorithms can be found in [DFO11].

IsSolubleByFinite(G : parameters) : GrpMat -> BoolElt

    Presentation: MonStgElt             Default: "CT"

    OrderLimit: RngIntElt               Default: 10^{15}

    Small: RngIntElt                    Default: 10^6

    NeedChangeOfBasis: BoolElt          Default: false

This function takes as input a finitely generated matrix group G over K, and tests whether G is soluble-by-finite. If so, it returns true, otherwise false. Note that currently the function is valid only for p>n if K has characteristic p>0.

The algorithm first constructs a congruence homomorphism, then a presentation for the congruence image, and finally evaluates its relations to obtain normal generators for the congruence kernel. For further details, see [DFO11, Section 3.2].

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 NeedChangeOfBasis is true, then a change-of-basis matrix is computed and recorded which explictly exhibits G as a group of block lower-triangular matrices.

IsPolycyclicByFinite(G : parameters) : GrpMat -> BoolElt

    Presentation: MonStgElt             Default: "CT"

    OrderLimit: RngIntElt               Default: 10^{15}

    Small: RngIntElt                    Default: 10^6

This function takes as input a finitely generated matrix group G over Z, and tests whether G is polycyclic-by-finite. If so, it returns true, otherwise false. See [DFO11, Section 3.2] for details.

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.

IsNilpotentByFinite(G : parameters) : GrpMat -> BoolElt

    Presentation: MonStgElt             Default: "CT"

    OrderLimit: RngIntElt               Default: 10^{15}

    Small: RngIntElt                    Default: 10^6

This function takes as input a finitely generated matrix group G over K, and tests whether G is nilpotent-by-finite. If so, it returns true, otherwise false. Here K must currently be Q, a number field, or an (algebraic) function field with a single indeterminate.

The algorithm first constructs a congruence homomorphism, then a presentation for the congruence image, and finally evaluates its relations to obtain normal generators for the congruence kernel. Further details of the algorithm can be found in [DFO11, Section 5.2].

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.

IsAbelianByFinite(G : parameters) : GrpMat -> BoolElt

    Presentation: MonStgElt             Default: "CT"

    OrderLimit: RngIntElt               Default: 10^{15}

    Small: RngIntElt                    Default: 10^6

This function takes as input a finitely generated matrix group G over K, and tests whether G is abelian-by-finite. If so, it returns true, otherwise false. As before, K must currently be Q, a number field, or an (algebraic) function field with a single indeterminate.

The algorithm first constructs a congruence homomorphism, then a presentation for the congruence image, and finally evaluates its relations to obtain normal generators for the congruence kernel. Further details of the algorithm can be found in [DFO11, Section 5.2].

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.

IsCentralByFinite(G : parameters) : GrpMat -> BoolElt

    Presentation: MonStgElt             Default: "CT"

    OrderLimit: RngIntElt               Default: 10^{15}

    Small: RngIntElt                    Default: 10^6

    CompletelyReducible: BoolElt        Default: false

This function takes as input a finitely generated matrix group G over a field K, and tests whether G is central-by-finite. If so, it returns true, otherwise false. Here K is (a finite degree extension of) F(x₁, ..., x_m), where F is Q or a number field.

The algorithm first constructs a congruence homomorphism, then a presentation for the congruence image, and finally evaluates its relations to obtain normal generators for the congruence kernel. Further details of the algorithm can be found in [DFO11, Section 5.3].

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 CompletelyReducible is set to true then we use a more efficient algorithm to test whether G is central-by-finite.