%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  schunck.tex              CRISP documentation           Burkhard H\"ofling
%%
%%  @(#)$Id: schunck.tex,v 1.12 2006/09/13 17:44:16 gap Exp $
%%
%%  Copyright (C) 2000, Burkhard H\"ofling, Mathematisches Institut,
%%  Friedrich Schiller-Universit\"at Jena, Germany
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Chapter{Schunck classes and formations}

In principle, any group class can be created as generic (group) class,
followed by setting the required properties and attributes described in the
preceding chapters. For certain standard kinds of group classes, there are additional
functions available to accomplish this task, which are described in this and the
following chapter.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creating Schunck classes}\null

\index{Schunck class!creating}

A class $\cal C$ of finite groups is a *Schunck class* if a finite group
$G$ belongs to $\cal C$ if and only if all its primitive factor groups
belong to $\cal C$. In particular, a Schunck class is nonempty and closed
with respect to factor groups. By definition, a Schunck class $\cal C$ is
determined by the primitive groups which it contains (the basis of $\cal C$),
or by the primitive groups not in $\cal C$ but all of whose proper factor
groups belong to $\cal C$ (the boundary of $\cal C$).

\>SchunckClass(<rec>) O

returns a Schunck class defined by the information stored in the record
<rec>. Note that it is the user's responsibility to ensure that <rec> really
defines a Schunck class. <rec> may have the following components: `\\in',
`proj', `bound', `char', and `name'. The values bound to these entries, if
present, are stored, respectively, in the attributes `MemberFunction', 
`ProjectorFunction', `BoundaryFunction', `Characteristic', and `Name'.
Please refer to "MemberFunction", 
"ProjectorFunction", "BoundaryFunction", "Characteristic", and "ref:Name"
for the meaning of these attributes.

At least one of the attributes `MemberFunction', `ProjectorFunction', or
`BoundaryFunction' must be present in order to be able to compute
with a Schunck class. 

\beginexample
gap> nilp := SchunckClass (rec (bound := G -> not IsCyclic (G),
>        name := "class of all nilpotent groups"));
class of all nilpotent groups
gap> DihedralGroup (8) in nilp;
true
gap> SymmetricGroup (3) in nilp;
false
\endexample

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Attributes and operations for Schunck classes}\null

\index{Schunck class!attributes of}
\index{Schunck class!operations for}
\index{attributes!of Schunck class}
\index{operations!for Schunck class!}

In addition to the attributes and operations for generic group classes,
for Schunck classes also the following are available:

\>Boundary(<class>) A

computes the boundary of <class>, i.~e., the class of all
primitive groups which do not belong to <class> but whose proper
factor groups do. The result is a group class. 

\>Basis(<class>) A

The basis of <class> consists of the primitive solvable 
groups in <class>. The result is a group class. 

\>Projector(<grp>, <class>) O

This function returns a <class>-projector of <grp>.
Note that, at present, methods are only available for finite
solvable groups <grp>, or when <class> has an attribute `ProjectorFunction'.

A subgroup 
$H$ of the group $G$ is a <class>-projector of $G$ if $H N/N$ is
<class>-maximal in $G/N$ for all normal subgroups $N$ of~$G$. A subgroup $H$
of $G$ is <class>-maximal in $G$ if $H$ belongs to <class>, and there is no
subgroup $L$ of $G$ which contains $H$ and lies in <class>. Note that if
<class> consists of finite solvable groups, then <class>-projectors exist in
every finite solvable group if and only if <class> is a Schunck class, and in
this case all <class>-projectors of
$G$ are conjugate. See \cite{DH92}, III,~3.21.

\beginexample
gap> H := SchunckClass (rec (bound := G -> Size (G) = 6));
SchunckClass (bound:=function( G ) ... end)
gap> Size (Projector (GL(2,3), H)); 
16 
gap> # H-projectors coincide with Sylow subgroups
gap> U := SchunckClass (rec ( # class of all supersolvable groups
>    bound := G -> not IsPrimeInt ( Size (Socle (G)))
> )); 
SchunckClass (bound:=function( G ) ... end)
gap> Size (Projector (SymmetricGroup (4), U));
6 
gap> # the projectors are the point stabilizers
\endexample

\>CoveringSubgroup(<grp>, <class>) O

A subgroup $H$ of $G$ is a <class>-covering subgroup of $G$ if $H$ is a
<class>-projector of $L$ for every subgroup $L$ with $H \leq L \leq G$.
Note that projectors and covering subgroups coincide for Schunck classes of
finite solvable groups. At present, methods are only available for finite
solvable groups <grp>.

\>BoundaryFunction(<grpclass>)                                  A

This attribute stores a function <func> which has been set by the 
user to define <grpclass>, either as an argument to `SchunckClass', 
`SaturatedFormation', or `FittingFormation' (see "SchunckClass", 
"SaturatedFormation", or "FittingFormation"), or has been set directly
(see "ref:Setter"). <func> must be a function taking one argument.
If the argument is a finite solvable group $G$ having attributes 
`Socle' and `SocleComplement' (see Section "Additional attributes for 
primitive solvable groups" below), <func> must  return `true' if $G$ 
is in the boundary of <grpclass>, and `false' if $G$ belongs to 
<grpclass>. The behaviour for arguments which are not primitive 
solvable groups, or which  belong neither to <grpclass> nor to the 
boundary of <grpclass> need not be defined. Note that 
`BoundaryFunction' should *not* be used to test whether a given group 
belongs to the boundary of <grpclass>. `Boundary' and/or `Basis' (see 
"Boundary" and "Basis"), which are defined independently of the way 
<grpclass> is defined.


\>ProjectorFunction(<grpclass>) A

If bound, `ProjectorFunction' stores a function <func> supplied by the
user as part of the definition of <grpclass>. <func> must be a function
taking a group
$G$ as the only argument, and returns a <grpclass>-projector of $G$.  Note that
`Projector' (see "Projector"),
rather than `ProjectorFunction', should be used by the user to compute
<grpclass>-projectors.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Additional attributes for primitive solvable groups}\null

\index{primitive solvable group!attributes of}
\index{attributes!of primitive solvable group}

A finite group $G$ is *primitive* if it has a faithful primitive permutation 
representation, or equivalently, if it has a maximal subgroup $M$ with trivial 
core. If $G$ is solvable, $M$ complements the unique minimal normal subgroup
$N$ of $G$. Therefore $N$ is the socle as well as the Fitting subgroup of
<grp>.


\>IsPrimitiveSolvable(<grp>) P

returns true if <grp> is primitive and solvable, and false otherwise.


\>SocleComplement(<grp>) A

If present, this attribute stores a complement of the socle of <grp>.
Currently, there is only a method available for `SocleComplement'
if <grp> has the property `IsPrimitiveSolvable'.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Creating formations}\null

\index{formations!creating}

A nonempty group class is a  formation if it is closed with respect to factor
groups and residually closed. A saturated formation is, of course, a
formation which is saturated. Note that by the
Gasch\accent127utz-Lubeseder-Schmid theorem (see e.~g. \cite{DH92}, IV,
4.6), every saturated formation is a local formation. Moreover, every
saturated formation is a Schunck class. Therefore a saturated formation
admits the operations `Boundary', `Basis', and `Projector'.


\>OrdinaryFormation(<rec>) O

creates a formation from the record <rec>. Note that it is the user's responsibility to ensure that <rec> really
defines a formation. <rec> may have components `\\in',
`res', `char', and `name', whose values are stored in the attributes
`MemberFunction', `ResidualFunction', `Characteristic', and
`Name', respectively, of the new formation. See "MemberFunction", "ResidualFunction",
"Characteristic", and "ref:Name", respectively, for the meaning of these attributes.


The following example shows how to construct the formations of all groups of 
derived length at most $3$ and of all groups of exponent dividing $6$.

\beginexample
gap> der3 := OrdinaryFormation (rec (
>    res := G -> DerivedSubgroup (DerivedSubgroup (DerivedSubgroup (G)))
> ));
OrdinaryFormation (res:=function( G ) ... end)
gap> SymmetricGroup (4) in der3;
true
gap> GL (2,3) in der3;
false
gap> exp6 := OrdinaryFormation (rec (
>    \in := G -> 6 mod Exponent (G) = 0,
>    char := [2,3]));
OrdinaryFormation (in:=function( G ) ... end)
\endexample

\>SaturatedFormation(<rec>) O

creates a saturated formation from the record <rec>. Note that it is the user's
responsibility to ensure that <rec> really defines a saturated formation. <rec> may have
any components admissible for formations (see "OrdinaryFormation") or Schunck classes
(see "SchunckClass"), that is, `\\in', `res', `char', `proj', `bound', `locdef', and
`name',  whose values, if bound, are stored in the attributes `MemberFunction',
`ResidualFunction', `Characteristic',  `ProjectorFunction', `BoundaryFunction',
`LocalDefinitionFunction', and `Name', respectively.  Please refer to "MemberFunction", 
"ResidualFunction", "Characteristic",  "ProjectorFunction", "BoundaryFunction",
"LocalDefinitionFunction",  and "ref:Name" for the meaning of these attributes.

There are also functions `FittingFormation' and `SaturatedFittingFormation' to create
Fitting formations and saturated Fitting formations; see
 "FittingFormation" and "SaturatedFittingFormation" below for details. 

The following example shows how to construct the saturated formations of all finite
nilpotent groups and of all nilpotent-by-abelian groups whose order is not divisible by a
prime congruent 3 mod 4, and whose $2$-chief factors are central. In the first case, we
choose $f(p) = (1)$ for all primes $p$, so that the $f(p)$-residual of $G$ is generated
by a generating set of $G$ (see "LocalDefinitionFunction" below). In the second example,
we let $f(2) = 1$, if $p \equiv 3 \pmod 4$, we define $f(p) = {\cal A}$, the class of
all finite abelian groups, and set
$f(p) =
\emptyset$ otherwise.

\beginexample
gap> nilp := SaturatedFormation (rec (
>      locdef := function (G, p)
>          return GeneratorsOfGroup (G);
>      end));
SaturatedFormation (locdef:=function( G, p ) ... end)
gap> form := SaturatedFormation (rec (
>    locdef := function (G, p)
>        if p = 2 then
>           return GeneratorsOfGroup (G);
>        elif p mod 4 = 3 then
>           return GeneratorsOfGroup (DerivedSubgroup (G));
>        else
>           return fail;
>        fi;
>     end));
SaturatedFormation (locdef:=function( G, p ) ... end)
gap> Projector (GL(2,3), form);
Group([ [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3)^0 ] ], 
  [ [ Z(3)^0, Z(3) ], [ 0*Z(3), Z(3)^0 ] ], 
  [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ])
\endexample

\>FormationProduct(<form1>, <form2>) O

The formation product <prod> of two formations <form1> and <form2> 
consists  of the groups $G$ such that the <form2>-residual of $G$ belongs to
<form1>. The product <prod> is again a formation. If <form1>
and <form2> are saturated formations, the result is a saturated
formation. The same is true if the characteristic of <form2> is contained in
that of <form1>. This is automatically recognised if the characteristic of
<form1> is `AllPrimes' (see "AllPrimes"). In all other cases, you
will have to set the attribute `IsSaturated' manually, if applicable. Note
that in general it is not possible for {\CRISP} to determine if two classes
are contained in each other.

\beginexample
gap> nilp := SaturatedFormation (rec (\in := IsNilpotent, name := "nilp"));
nilp
gap> FormationProduct (nilp, der3); # no characteristic known
FormationProduct (nilp, OrdinaryFormation (res:=function( G ) ... end))
gap> HasIsSaturated (last);HasCharacteristic (nilp);
false
false
gap> SetCharacteristic (nilp, AllPrimes);
gap> FormationProduct (nilp, der3); # try with characteristic
FormationProduct (nilp, OrdinaryFormation (res:=function( G ) ... end))
gap> IsSaturated (last);
true
\endexample


\>FittingFormationProduct(<fitform1>, <fitform2>) O

If <fitform1> and <fitform2>  are Fitting formations, the formation product
equals the Fitting product (see "FittingProduct") of <fitform1> and
<fitform2>, which, in turn, equals the class product of <fitform1> and
<fitform2>. The latter consists of all groups <G> having a  normal subgroup
<N> in <fitform1> such that $<G>/<N>$ belongs to <fitform2>.

Note that if <fitform1> and <fitform2> are Fitting formations, then 
`FormationProduct(<fitform1>, <fitform2>)', `FittingProduct(<fitform1>,
<fitform2>)' and `FittingFormationProduct(<fitform1>, <fitform2>)' all
return the same mathematical object (but distinct GAP objects), which is,
again, a Fitting formation.


\beginexample
gap> nilp := FittingFormation (rec (\in := IsNilpotent, name := "nilp"));;
gap> FormationProduct (nilp, nilp);
FittingFormationProduct (nilp, nilp)
gap> FittingProduct (nilp, nilp);
FittingFormationProduct (nilp, nilp)
gap> FittingFormationProduct (nilp, nilp);
FittingFormationProduct (nilp, nilp)
\endexample


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Attributes and operations for formations}\null

\index{formations!attributes for}
\index{formations!operations for}
\index{attributes!of formation}
\index{operations!for formation}

In addition to those available for generic group classes, formations also
admit the following attributes and operations. See also "Attributes and
operations for Schunck classes" for additional operations for saturated
formations. 

\>Residual(<grp>, <form>) O
\>Residuum(<grp>. <form>) O

return the <form>-residual (also called <form>-residuum) of the group <grp>.
This is the smallest normal subgroup <res> of <grp> such that $<grp>/<res>$ belongs to <form>.
Note that, unless <form> has an attribute `ResidualFunction', there are presently only methods
available for finite solvable groups.

\>ResidualFunction(<form>) A

This attribute is part of the definition of <form> supplied by the user. If
present, it must contain a function which computes the <form>-residual of a given group.
In general, such a residual only exists if <form> is residually closed; cf.
"IsResiduallyClosed". Note that `ResidualFunction', if present, is called by `Residual'
(see "Residual"). Therefore `Residual', which also works for formations without
`ResidualFunction', should be used by the user to compute <form>-residuals.

\>LocalDefinitionFunction(<form>) A

Let <form> be a saturated formation with local function~$f$. This attribute,
if present, stores a function <func> supplied by the user as part of the
definition of <form>. <func> must be a function taking two parameters, a group
$G$ and a prime $p$. If $p$ is in the characteristic of <form>, this
function must return a list <list> of elements of
$G$, such that the smallest normal subgroup of $G$ containing <list> is the
$f(p)$-residual of $G$. If $p$ is not in the characteristic of <form>, 
then `<func>($G$, $p$)' must return `fail' for any group $G$.
`LocalDefinitionFunction' is part of the definition of <form> and should not
be called by the user. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Functions for normal and characteristic subgroups}\null

\>NormalSubgroups(<grp>) A

{\CRISP} provides an improved method for `NormalSubgroups' (see
"ref:NormalSubgroups") for groups <grp> which are finite and  solvable.
This method simply calls `AllInvSgrsWithQPropUnderAction' with
$<act> = <grp>$, `ReturnTrue'
as <pretest> and `ReturnFail' as <test>. Note that, since
<pretest> always returns `true', <test> is never actually called.
This is usually significantly faster than the methods in the {\GAP} library.

\>CharacteristicSubgroups(<grp>) A

returns a list containing all characteristic subgroups of <grp>. 
`CharacteristicSubgroups' calls `AllInvSgrsWithQPropUnderAction'.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Low level functions for normal subgroups related to residuals}\null

\index{normal subgroups!with properties inherited by normal subgroups above}
\index{invariant normal subgroups!with properties inherited by normal subgroups above}
\index{factor groups!with properties inherited by factor groups}
\index{quotient groups!with properties inherited by quotients}

\>OneInvariantSubgroupMinWrtQProperty(<act>, <grp>, <pretest>, <test>, <data>) O

Let <act> be a list or group whose elements act on <grp> via the caret operator,
such that every subgroup of <grp> invariant under <act> is normal in <grp>. 
Assume that $\cal X$ is a set of <act>-invariant subgroups of <grp> containing <grp>, and
such that whenever
$M$ and $N$ are <act>-invariant subgroups with $M \in \cal X$ and $M$
contained in $N$, then also $N \in \cal X$. Then
`OneInvariantSubgroupMinWrtQProperty' computes an <act>-invariant subgroup $M \in \cal X$
such that no <act>-invariant subgroup of <grp> contained in $M$ belongs to $\cal X$. 
At present, there exist only methods for finite solvable groups <grp>.

The class $\cal X$ is described by two functions, <pretest> and <test>. 

<pretest> is a function taking four arguments, <U>, <V>, <R>, and <data>,
where <data> is just the argument passed to
`OneInvariantSubgroupMinWrtQProperty' (see below for examples). $<U>/<V>$ is a
chief factor of <grp>, and  <R> is an <act>-invariant subgroup of <grp> containing <U>
which is known to belong to
$\cal X$.

<pretest> may return the values `true', `false', or `fail'. If it returns 
`true', every <act>-invariant subgroup <N> of <grp> such that <V> is
contained in $N$ and $<R>/<N>$ is
$G$-isomorphic with $<U>/<V>$ must belong to $\cal X$. If it returns
`false', no such <act>-invariant subgroup~$N$ may belong to $\cal X$. 

<test> is a function taking three arguments, <S>, <R>, and <data>, where
data has been described above. <R> is a <act>-invariant subgroup of <grp> belonging to
$\cal X$, and $<R>/<S>$ is a chief factor of <grp>. The function must return
true if <S> belongs to $\cal X$, and false otherwise. 

Note that whenever `<test>(<S>, <R>, <data>)' is called, 
`<pretest>(<U>, <V>, <R>, <data>)' has been called before, and has returned
`fail', where  $<U>/<V>$ is a  chief factor which is <G>-isomorphic with
$<R>/<S>$. Thus <test> need not repeat tests which have been performed by
<pretest>. In particular, if <pretest> always returns `true' or `false',
<test> will never be called.

<data> is never used or changed by `OneInvariantSubgroupMinWrtQProperty', but
exists only as a means for passing additional information to or between
the functions <pretest> and <test>.

For example, if $\cal C$ is a group class which is closed with respect to
factor groups and $\cal X$ is the set of all <act>-invariant subgroups $N$ of <grp>
with $<grp>/N \in \cal C$, then $\cal X$ satisfies the above properties. In
particular, if $\cal C$ is a formation, then
`OneInvariantSubgroupMinWrtQProperty' will return the $\cal C$-residual of
<grp>.

The following example shows how to use `OneInvariantSubgroupMinWrtQProperty' to
compute the derived subgroup of a group $G$. (Note that in practise, this 
is not a particularly efficient way of computing the derived subgroup.)

\beginexample
gap> G := DirectProduct (SL(2,3), CyclicGroup (2));;
gap> data := rec (gens := GeneratorsOfGroup (G),
>    comms := List (Combinations (GeneratorsOfGroup (G), 2), 
>       x -> Comm (x[1],x[2])));;
gap> OneInvariantSubgroupMinWrtQProperty (
>    G, G,
>    function (U, V, R, data) # test if U/V is central in G
>        if ForAny (ModuloPcgs (U, V), y ->
>           ForAny (data.gens, x -> not Comm (x, y) in V)) then 
>           return false;
>        else
>           return fail;
>        fi;
>     end,
>     function (S, R, data)
>        return ForAll (data.comms, x -> x in S);
>     end,
>     data) = DerivedSubgroup (G); # compare results
true
\endexample       


\>AllInvariantSubgroupsWithQProperty(<act>, <grp>, <pretest>, <test>, <data>) O

`AllInvariantSubgroupsWithQProperty' returns a list consisting of all 
<act>-invariant subgroups in $\cal X$, where $\cal X$ is the class defined by <pretest>,
<test>, and <data>, as described for `OneInvariantSubgroupMinWrtQProperty' (see
"OneInvariantSubgroupMinWrtQProperty"). 
At present, there exist only methods for finite solvable groups <grp>.

\beginexample
gap> G := GL(2,3);
GL(2,3)
gap> normsWithSupersolvableFactorGroups :=
> AllInvSgrsWithQPropUnderAction (G, G, 
>    function (U, V, R, data)
>       return IsPrimeInt (Index (U, V));
>    end,
>    ReturnFail, # pretest is sufficient
>    fail); # no data required
[ GL(2,3), 
  Group([ [ [ Z(3)^0, Z(3) ], [ 0*Z(3), Z(3)^0 ] ], [ [ Z(3), Z(3)^0 ], 
          [ Z(3)^0, Z(3)^0 ] ], [ [ 0*Z(3), Z(3)^0 ], [ Z(3), 0*Z(3) ] ], 
      [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ]), 
  Group([ [ [ Z(3), Z(3)^0 ], [ Z(3)^0, Z(3)^0 ] ], 
      [ [ 0*Z(3), Z(3)^0 ], [ Z(3), 0*Z(3) ] ], 
      [ [ Z(3), 0*Z(3) ], [ 0*Z(3), Z(3) ] ] ]) ]
\endexample


\>OneNormalSubgroupMinWrtQProperty(<grp>, <pretest>, <test>, <data>) O

`OneNormalSubgroupMinWrtQProperty' is the same as 
`OneInvariantSubgroupMinWrtQProperty' (see
"OneInvariantSubgroupMinWrtQProperty"), where $<act> = <grp>$. 

\>AllNormalSubgroupsWithQProperty(<grp>, <pretest>, <test>, <data>) O

`AllNormalSubgroupsWithQProperty' is the same as 
`AllInvariantSubgroupsWithQProperty' (see
"AllInvariantSubgroupsWithQProperty"), where $<act> = <grp>$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
%%