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