# Properties of an FP-Group In this section intrinsics for providing information about the global properties of an fp-group are described. ## Cardinality A very basic requirement is to determine whether a given fp-group $G$ is finite or infinite. Unfortunately, this is a problem for which there is no general solution. Instead, an intrinsic `Order` is provided which attempts to prove that the group is finite and a second intrinsic `IsInfiniteFPGroup` is provided which attempts to prove that the group is infinite. If both fail to produce a result then no conclusion can be drawn. We assume that the group is finite and try to prove that this assumption is true using coset enumeration and other techniques. ### `Order(G: parameters): GrpFP -> RngIntElt` ### `FactoredOrder(G: parameters): GrpFP -> [ ]` Given an fp-group $G$, this function attempts to determine the order of $G$ or to prove that $G$ is infinite. If a finite order can be computed, the function `Order` returns the order as a positive integer, whereas the function `FactoredOrder` returns a sequence of prime power factors. The function `FactoredOrder` reports an error in all other cases, whereas the function `Order` returns the object `Infinity`, if $G$ can be shown to be infinite and returns a value of 0 if neither a finite value for the group order nor a proof for the infinity of $G$ can be obtained. No conclusions can be drawn from a return value 0 of `Order`. In addition to the parameters controlling possibly invoked coset enumerations, there exist some other parameters controlling the strategy used by the functions `Order` and `FactoredOrder`. These parameters are described below. ### `Example: Order11 (ex-134948)` We use the function [`Order`](#function-grpfp-1-order) without any parameters to compute the order of the group $$ G =\,\, . $$ ```magma > G := FPGroup; > G; Finitely presented group G on 2 generators Relations x^8 = Id(G) y^7 = Id(G) (x * y)^2 = Id(G) (x^-1 * y)^3 = Id(G) > Order(G); 10752 ``` The strategy employed by the functions `Order` and `FactoredOrder` may involve trying to obtain information on certain subgroups of $G$. Whether or not an attempt is made to construct a presentation for a subgroup arising in the course of the computation by means of Reidemeister-Schreier rewriting, is controlled by three parameters: ```magma UseRewrite: BoolElt Default: true MinIndex : RngIntElt Default: 10 MaxIndex : RngIntElt Default: 1000 ``` If `UseRewrite` is set to `false`, attempts to construct presentations for subgroups are not made. Otherwise, `MinIndex` and `MaxIndex` specify for subgroups of which index range Reidemeister-Schreier rewriting is done. The following strategy is used for trying to determine the order of $G$. **(1)** Check whether $G$ is free. If so, $G$ is either trivial or infinite. **(2)** Check whether the presentation for $G$ is deficient (i.e. whether the number of relations is smaller than the number of generators). If it is, $G$ is infinite. **(3)** Check the subgroups of $G$ with known order. If such a subgroup is known to be infinite or if we can compute its index in G, we’re done. **(4)** Try to compute the index of $G$ in a supergroup of known order. (An infinite supergroup in which $G$ has finite index proves $G$ to be infinite.) **(5)** Try to enumerate the cosets of the trivial subgroup in $G$. **(6)** Check the subgroups of known or easily computable index in $G$. If we can compute the order of such a subgroup or prove that it is infinite, we’re done. **(7)** Try to enumerate the cosets of some subgroups occurring “naturally” in the presentation of $G$. **(8)** Check the supergroups in which $G$ has known or easily computable index. If we can compute the order of a supergroup or prove that it is infinite, we’re done. **(9)** Try to rewrite $G$ w.r.t. some supergroup and to enumerate the cosets of the trivial subgroup using the resulting presentation. Steps requiring coset enumeration in $G$ or a supergroup of $G$ are skipped, if no relations are known for this group. Steps involving Reidemeister-Schreier rewriting may be skipped according to the values of the parameters mentioned above. Experienced users can control the behaviour of coset enumerations which may be invoked by the functions `Order` and `FactoredOrder` with a wide range of parameters. Both functions – in addition to the parameters mentioned above – accept the same parameters as the function [`CosetEnumerationProcess`](subgroup-general.md#function-grpfp-cosetenumerationprocess) in Subsec. [Interactive Coset Enumeration](subgroup-general.md#coset-enumeration). The intrinsic `IsInfiniteFPGroup` attempts to prove that an fp-group is infinite by finding a subgroup that has an infinite abelian section. ### `IsInfiniteFPGroup(G : parameters): GrpFP -> BoolElt` Given a finitely-presented group $G$, the function attempts to establish that $G$ is infinite. If it succeeds it returns `true`. Otherwise it returns `false` meaning that the tests it has made don’t prove the group to be infinite. This does not imply that the group is likely to be finite. The code searches for epimorphisms $\phi$ of $G$ and uses the Holt-Plesken cohomological criterion, as implemented in the intrinsic `HasPositiveH1Dimension`, to test for non-finiteness of the kernel of $\phi$. The version in this release works best on groups $G$ which are perfect or which have small abelian quotients. It will be extended to handle groups which have larger soluble quotients in a subsequent release. At present epimorphisms are sought using four techniques that are described elsewhere in this chapter: L2-quotient, Simple Quotient, Low Index Subgroups and Low Index Normal Subgroups. The intrinsic has corresponding parameters `L2Quot`, `SimQuot`, `LISub` and `LINSub` that allow the user to control the types of epimorphisms to be used. The default is for all four methods to be employed – however, the user can turn any of them off by setting the appropriate parameter to `false`. A verbose flag `InfGrp` will provide some information about progress. The application of the Holt-Plesken theorem to an epimorphism $\phi$ requires a knowledge of the $QH$ modules, where $H$ is the image of $\phi$. A database containing such modules for ATLAS groups of degree up to 1000 is available as an optional download. The serious user of `IsInfiniteFPGroup` is strongly advised to have this database available as it can save a great deal of runtime. ### `Example: Prove Inf1 (ex-fea44f)` Consider the following one-relator quotient group of the triangle group $\langle 2, 3, 7 \rangle$: $$ \langle x,y | x^2, y^3, (xy)^7, (x,y)^{12} \rangle $$ ```magma > SetVerbose("InfGrp", 2); > G := FPGroup; > inf := IsInfiniteFPGroup(G); > L2Q SEARCH commencing: L2Q SEARCH Considering L2Qs with degrees in the interval [1, 1000] SIMPLE QUOTIENT Commence searching interval [60, 10000]: Found epi onto PSL(2, 7) of order 168 and degree 8: 0.000 secs. Found epi onto PSL(2, 13) of order 1092 and degree 14: 0.060 secs. SIMPLE QUOTIENT Search of interval [60, 10000] unsuccessful: 2 epis, 0.610 secs. NORMAL SUBGROUPS Search of indices [1, 1000] commencing: NORMAL SUBGROUPS Search of [1, 1000] unsuccessful: 1 + 0 subgroups, 0.200 secs. SUBGRP SEARCH of indices [1, 25] commencing: SUBGRP SEARCH of [1, 25] was unsuccessful: 8 + 8 subgroups, 0.990 secs. SIMPLE QUOTIENT Commence searching interval [20001, 100000]: SIMPLE QUOTIENT Search of interval [20001, 100000] unsuccessful: 0 epis, 0.620 secs. NORMAL SUBGROUPS Search of indices [1001, 10000] commencing: NORMAL SUBGROUPS Search of [1001, 10000] unsuccessful: 0 + 0 subgroups, 0.960 secs. SUBGRP SEARCH of indices [26, 50] commencing: SUBGRP SEARCH of [26, 50] was unsuccessful: 8 + 8 subgroups, 1.460 secs. SIMPLE QUOTIENT Commence searching interval [100001, 1000000]: Found epi onto J_2 of order 604800 and degree 100: 1.300 secs. For 4950-dim ex_sq of perm module, dim of H^1/Z is 1: 1.050 secs. SIMPLE QUOTIENT Search of interval [100001, 1000000] successful: 1 epis, 2.430 secs. > inf; true ``` So the group $G$ has the simple group $J_2$ as quotient and the rational representation corresponding to the exterior square of $J_2$’s degree 100 permutation module lifted to $G$ has first cohomology group of dimension 1. So $G$ is infinite by an application of the Holt-Plesken theorem. ### `HasPositiveH1Dimension(G, phi : parameters): GrpFP, HomGrp -> BoolElt` Given a finitely-presented group $G$ and an epimorphism $\phi$ of $G$ onto a permutation group $H$, this intrinsic returns `true` if some ${{\mathbb{Q}}}H$-module, where ${{\mathbb{Q}}}$ is the field of the rationals, lifts to a ${{\mathbb{Q}}}G$-module whose first cohomology group is non-trivial. By a result of Holt and Plesken this shows that $G$ is infinite. The ${{\mathbb{Q}}}H$-modules are obtained in three ways. The first consists of ${{\mathbb{Q}}}H$-modules that are easily obtainable from the permutation representation of $H$. The second method is to systematically construct the ${{\mathbb{Q}}}H$-modules of $H$ while the third source is the Magma database of rational representations of small simple groups. Parameters allow the user to specify which of these methods are used (see below). The parameter `ESLimit` allows the user to place a limit on the dimension of exterior squares for which the Holt-Plesken test will be applied. If the parameter `CmpIrrs` is set to `true` then Magma will construct rational irreducible representations for $H$ if they are not present in the database. If the parameter `DBIrrs` is set to `true` then Magma will use those irreducible modules for $H$ that are available in the Rational Representations Database. Setting both `CmpIrrs` and `DBIrrs` to `false` specifies that the test should be applied only to the permutation module and its exterior square. There are two signatures for this intrinsic where the second has a third argument needed by the intrinsic `IsInfiniteFPGroup`. Note that this version is only intended to be called internally. For all other uses the two-argument version should be used. ## Small Cancellation Conditions ### `SmallCancellationConditions(G): GrpFP -> RngIntElt, RnIntElt, FldRatElt)` ```magma Print : RngIntElt Default: 0 involgens: BoolElt Default: false ``` This functions calculates the values for which the small cancellation conditions $T(i)$, $C(j)$ and $C'(k)$ are satisfied by the presentation $G$. It returns $i,j,k'$, where $T(i)$, $C(j)$, and $C'(k)$ are satisfied for all $k > k'$. If the parameter `involgens` is set `true` then edges labelled by involutory generators $x$ in a van Kampen diagram for $G$ are regarded as undirected, and are not regarded as pieces of the relator $x^2$. ### `Example: Small Cancel (ex-2f799a)` ```magma > G := FPGroup< x,y | x^6, y^6, (x*y)^5, (x,y)^3 >; > SmallCancellationConditions(G); This presentation satisfies T( 3 ). This presentation satisfies C( 5 ). This presentation satisfies C'(k) for all k > 1/5 . 3 5 1/5 ``` ## Largeness ### `IsLarge(G, L, U:parameters): GrpFP, RngIntElt, RngIntElt -> BoolElt, GrpFP` ```magma Simplify : BoolElt Default: true MaxExponent: RngIntElt Default: 100000 TimeLimit : RngIntElt Default: 10 ``` Attempt to show that $G$ has a subgroup with homomorphic image the free group of rank 2. If successful return `true`, plus a subgroup witness to this property. If not successful, return `false`. Note that `false` does not imply that $G$ doesn’t have the stated property, just that no such subgroup has been found. The witness group returned has a finite index subgroup with the free group of rank 2 as a homomorphic image. The algorithm will consider subgroups of $G$ with index $h$ having $L\le h\le U$. We attempt to decide if G is large by calculating the (multivariable) Alexander polynomial of those subgroups $H$ of $G$ having index $h$ in the given range, and also subgroups of H having index up to $2h$ in $G$. Controls simplification of subgroup presentations. If the abelian torsion of subgroup $H$ is greater than `MaxExponent` we do not rewrite to obtain a presentation of $H$. If, in computing low index subgroups of a finite index subgroup $H$ of $G$, the low-index subgroup calculation takes more than `TimeLimit` in seconds, then abort without trying to find more subgroups of $H$.