%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %W frattext.tex GrpConst documentation Bettina Eick %% %H $Id: frattext.tex,v 1.9 1999/11/07 19:28:45 gap Exp $ %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Chapter{The Frattini Extension Method} \index{The Frattini Extension Method} This is a method to construct up to isomorphism the soluble groups of a given order. The main function `FrattiniExtensionMethod' to construct groups is described in Section "The Main Frattini Extension Function". The construction process consists of two parts which can be addressed separately. In the first step a list of possible candidates for the Frattini factors of the desired groups is determined up to isomorphism. See Section "The Construction of Frattini Free Groups" for the corresponding functions. In the second step the determined candidates are considered one after the other and for each candidate a list of extensions is computed. See Section "The Determination of Frattini Extensions" for the available functions. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Main Frattini Extension Function} \index{The Main Frattini Extension Function} \> FrattiniExtensionMethod( <order> ) F \> FrattiniExtensionMethod( <order>, <uncoded> ) F \> FrattiniExtensionMethod( <order>, <flags> ) F \> FrattiniExtensionMethod( <order>, <flags>, <uncoded> ) F First we describe the *input* of the function. The <order> is the size of the desired groups. The optional input <uncoded> is a boolean which determines the output format. If it is true, then pc groups are returned. Otherwise, if it is false or not given, then code records describing pc groups are returned (see `PcGroupCodeRec'). The optional input <flags> is a record which is used to restrict the construction process to groups with certain properties only. This record consists of any of the following entries: \beginitems `nilpotent' & must be `true'. Only nilpotent groups are constructed. `nonnilpot' & must be `true'. Only non-nilpotent groups are constructed. `supersol' & must be `true'. Only supersoluble groups are constructed. `nonsupsol' & must be `true'. Only non-supersoluble groups are constructed. `pnormal' & must be a list of primes. Only groups with normal Sylow $p$-subgroup for all $p$ in the given list are constructed. `nonpnorm' & must be a list of primes. Only groups without normal Sylow $p$-subgroup for all $p$ in the given list are constructed. \enditems If a particular entry is not set, then no restriction on the groups is assumed. The default is an empty record of flags. Any combination of flags is possible. However, not all combinations make sense; For example, if `nilpotent' and `nonnilpotent' are both true, then the algorithm will return the empty list. If `nonnilpot' is true and `pnormal' is the list $[3]$, then the non-nilpotent groups whose Sylow 3-subgroup is normal will be computed. The *output* of the function is usually a list of pc groups or code records depending on <uncoded>. However, it may happen that the output list contains not only pc groups or codes, but also lists of pc groups or codes. This means that the groups in such a sublist are probably non-isomorphic, but the algorithm did not do a final verification, since this would be time-consuming. If desired, then the user might do a verification using the function `DistinguishGroups' described below. Moreover, it might be worth noting that the groups in such sublists of the output list are always reduced by the random isomorphism test (see the Section on `Random Isomorphism Testing' in the reference manual). Hence the probability that there are still isomorphisms between groups in this list is less than $2^{-100}$. \beginexample gap> flags := rec( nonnilpot := true, pnormal := [3] ); rec( nonnilpot := true, pnormal := [ 3 ] ) gap> grps := FrattiniExtensionMethod( 24, flags, true ); [ <pc group with 4 generators>, <pc group with 4 generators>, <pc group with 4 generators>, <pc group with 4 generators>, <pc group with 4 generators>, <pc group with 4 generators>, <pc group with 4 generators> ] gap> List( last, IdGroup ); [ [ 24, 1 ], [ 24, 5 ], [ 24, 8 ], [ 24, 6 ], [ 24, 7 ], [ 24, 4 ], [ 24, 14 ] ] gap> FrattiniExtensionMethod( 8 ); [ rec( code := 323, order := 8, isFrattiniFree := false, first := [ 1, 1, 2 ], socledim := [ 1 ], extdim := [ 2, 2 ], isUnique := true ), rec( code := 34, order := 8, isFrattiniFree := false, first := [ 1, 1, 3 ], socledim := [ 1, 1 ], extdim := [ 2 ], isUnique := true ), rec( code := 36, order := 8, isFrattiniFree := false, first := [ 1, 1, 3 ], socledim := [ 1, 1 ], extdim := [ 2 ], isUnique := true ), rec( code := 2343, order := 8, isFrattiniFree := false, first := [ 1, 1, 3 ], socledim := [ 1, 1 ], extdim := [ 2 ], isUnique := true ), rec( code := 0, order := 8, isFrattiniFree := true, first := [ 1, 1, 4 ], socledim := [ 1, 1, 1 ], extdim := [ ], isUnique := true ) ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Construction of Frattini Free Groups} \index{The Construction of Frattini Free Groups} A finite group is called *Frattini free* if it has a trivial Frattini subgroup. As candidates for the Frattini factors of the groups of size <order>, we compute Frattini free groups of suitable size dividing <order>. \>FrattiniFactorCandidates( <order>, <flags> ) F \>FrattiniFactorCandidates( <order>, <flags>, <uncoded> ) F The input is similar to the input for the function `FrattiniExtensionMethod'. The output is a list of candidates for the Frattini factors of the desired groups, i.e. the groups of size <order> possibly restricted by <flags>. By default the groups are returned as codes which may be changed using the boolean <uncoded>. Note that the computed list is always reduced to isomorphism type representatives. Moreover, it might happen that some of the Frattini free groups are not realised as Frattini factors of a group of size <order>. However, in practice this is a very rare case. Furthermore, note that for this part of the Frattini extension method the restriction to the positive properties `nilpotent', `supersol' and `pnormal' in the flags record will reduce the amount of computation considerably, while the negative properties do not have such a major influence on the efficiency of this method. \beginexample gap> flags := rec( nonsupsol := true ); rec( nonsupsol := true ) gap> FrattiniFactorCandidates( 24, flags, true ); [ <pc group with 4 generators>, <pc group with 3 generators>, <pc group with 4 generators> ] gap> List(last, IdGroup); [ [ 24, 12 ], [ 12, 3 ], [ 24, 13 ] ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{The Determination of Frattini Extensions} \index{The Determination of Frattini Extensions} A group $H$ is a *Frattini extension* of a group $G$ if there exists a normal subgroup $N$ of $H$ such that $H/N \cong G$ and $N \leq \phi(H)$ holds. Clearly, each finite group can be obtained as a Frattini extension of a Frattini free group. \> FrattiniExtensions( <code/group>, <order> ) F \> FrattiniExtensions( <code/group>, <order>, <uncoded> ) F Here the default input is a Frattini free group described by a code and the size <order> of the groups which shall be constructed. Alternatively, one can input a Frattini free group as pc group. Moreover, it is possible to give a list of codes or pc groups at once. The flag <uncoded> changes the output format to pc groups instead of codes as above. The output of this function is similar to the output of the function `FrattiniExtensionMethod'. \beginexample gap> G := SmallGroup( 24, 12 ); <pc group of size 24 with 4 generators> gap> FrattiniSubgroup(G); Group([ ]) gap> FrattiniExtensions( G, 48, true ); [ <pc group with 5 generators>, <pc group with 5 generators>, <pc group with 5 generators> ] gap> List( last, IdGroup); [ [ 48, 29 ], [ 48, 30 ], [ 48, 28 ] ] gap> cand := FrattiniFactorCandidates( 6, rec() ); [ rec( code := 25, order := 6, isFrattiniFree := true, first := [ 1, 2, 3 ], socledim := [ 1 ], extdim := [ ], isUnique := true ), rec( code := 1, order := 6, isFrattiniFree := true, first := [ 1, 1, 3 ], socledim := [ 1, 1 ], extdim := [ ], isUnique := true ) ] gap> FrattiniExtensions( cand, 12 ); [ rec( code := 6442, order := 12, isFrattiniFree := false, first := [ 1, 2, 3 ], socledim := [ 1 ], extdim := [ 2 ], isUnique := true ), rec( code := 266, order := 12, isFrattiniFree := false, first := [ 1, 1, 3 ], socledim := [ 1, 1 ], extdim := [ 2 ], isUnique := true ) ] \endexample %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Verifying non-isomorphism} The output of the functions `FrattiniExtensionMethod' or `FrattiniExtensions' might contain sublists of groups. That means, that the groups contained in sublists could not be distinguished up to isomorphism by the Frattini extension method. However, the groups have gone through the random isomorphism test and hence it is likely that they are not isomorphic. Here we provide a tool that can be used to try to prove that these groups are non-isomorphic. This is not done automatically within the Frattini extension method, since it might be time consuming and many users might not be interested in a complete verification of non-isomorphism. To distinguish groups we compute invariants of the given groups. Clearly, if the invariants differ, then we obtain that the corresponding groups are not isomorphic. However, the converse is not true and hence we might not succeed to distinguish all non-isomorphic groups in a given list. See \cite{BE99} for a description of the used invariants. \> DistinguishGroups( <list>, <bool> ) F The function `DistinguishGroups' takes as input <list> a list as described for the output of `FrattiniExtensions'. It returns a similar list, where the sublists contained in <list> are split up. There are two levels to operate the function `DistinguishGroups' which are controlled by the second input parameter <bool> of the function. If <bool> is `false', then only few invariants are computed, if it is `true', then we try also the more complicated invariants. Clearly, if <bool> is `false', then the result is obtained faster, but if <bool> is `true', then we might distinguish more groups. If `DistinguishGroups' fails to split up the input list completely, then a user might use the general purpose function `IsomorphismGroups' to prove the non-isomorphism between the remaining groups. However, this might be a time consuming computation.