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