[Up] [Previous] [Next] [Index]

4 The Frattini Extension Method

Sections

  1. The Main Frattini Extension Function
  2. The Construction of Frattini Free Groups
  3. The Determination of Frattini Extensions
  4. Verifying non-isomorphism

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.

4.1 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:

    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.

    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.

    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 ) ]
    

    4.2 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.

    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 ] ]
    

    4.3 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 congG and N leqphi(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.

    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 ) ]
    

    4.4 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 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.

    [Up] [Previous] [Next] [Index]

    grpconst manual
    Mai 2012