SSL grp.gi Sprache: unbekannt

#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Thomas Breuer, Frank Celler, Bettina Eick, Heiko Theißen.
##
## Copyright of GAP belongs to its developers, whose names are too numerous
## to list here. Please refer to the COPYRIGHT file for details.
##
## SPDX-License-Identifier: GPL-2.0-or-later
##
## This file contains generic methods for groups.
##

#############################################################################
##
#M IsFinitelyGeneratedGroup( <G> ) . . test if a group is finitely generated
##
InstallImmediateMethod( IsFinitelyGeneratedGroup,
 IsGroup and HasGeneratorsOfGroup,
 function( G )
 if IsFinite( GeneratorsOfGroup( G ) ) then
 return true;
 fi;
 TryNextMethod();
 end );

#############################################################################
##
#M IsCyclic( <G> ) . . . . . . . . . . . . . . . . test if a group is cyclic
##
# This used to be an immediate method. It was replaced by an ordinary
# method since the flag is typically set when creating the group.
InstallMethod( IsCyclic, true, [IsGroup and HasGeneratorsOfGroup], 0,
 function( G )
 if Length( GeneratorsOfGroup( G ) ) = 1 then
 return true;
 else
 TryNextMethod();
 fi;
 end );

InstallMethod( IsCyclic,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local a;

 # if <G> has a generator list of length 1 then <G> is cyclic
 if HasGeneratorsOfGroup( G ) and Length( GeneratorsOfGroup(G) ) = 1 then
 a:=GeneratorsOfGroup(G)[1];
 if CanEasilyCompareElements(a) and not IsOne(a) then
 SetMinimalGeneratingSet(G,GeneratorsOfGroup(G));
 fi;
 return true;

 # if <G> is not commutative it is certainly not cyclic
 elif not IsCommutative( G ) then
 return false;

 # if <G> is finite, test if the -th powers of the generators
 # generate a subgroup of index for all prime divisors 
 elif IsFinite( G ) then
 return ForAll( PrimeDivisors( Size( G ) ),
 p -> Index( G, SubgroupNC( G,
 List( GeneratorsOfGroup( G ),g->g^p)) ) = p );

 # otherwise test if the abelian invariants are that of $Z$
 else
 return AbelianInvariants( G ) = [ 0 ];
 fi;
 end );

InstallMethod( Size,
 "for a cyclic group",
 [ IsGroup and IsCyclic and HasGeneratorsOfGroup and CanEasilyCompareElements ],
 {} -> -RankFilter(HasGeneratorsOfGroup),
function(G)
 local gens;
 if HasMinimalGeneratingSet(G) then
 gens:=MinimalGeneratingSet(G);
 else
 gens:=GeneratorsOfGroup(G);
 fi;
 if Length(gens) = 1 and gens[1] <> One(G) then
 SetMinimalGeneratingSet(G,gens);
 return Order(gens[1]);
 elif Length(gens) <= 1 then
 SetMinimalGeneratingSet(G,[]);
 return 1;
 fi;
 TryNextMethod();
end);

InstallMethod( MinimalGeneratingSet,"finite cyclic groups",true,
 [ IsGroup and IsCyclic and IsFinite ],
 {} -> RankFilter(IsFinite and IsPcGroup),
function ( G )
local g;
 if IsTrivial(G) then return []; fi;
 g:=Product(IndependentGeneratorsOfAbelianGroup(G),One(G));
 Assert( 1, Index(G,Subgroup(G,[g])) = 1 );
 return [g];
end);

#############################################################################
##
#M MinimalGeneratingSet(<G>) . . . . . . . . . . . . . for groups
##
InstallMethod(MinimalGeneratingSet,"test solvable and 2-generator noncyclic",
 true, [IsGroup and IsFinite],0,
function(G)
 if not HasIsSolvableGroup(G) and IsSolvableGroup(G) and
 CanEasilyComputePcgs(G) then
 # discovered solvable -- redo
 return MinimalGeneratingSet(G);
 elif not IsSolvableGroup(G) then
 if IsGroup(G) and (not IsCyclic(G)) and HasGeneratorsOfGroup(G)
 and Length(GeneratorsOfGroup(G)) = 2 then
 return GeneratorsOfGroup(G);
 fi;
 fi;
 TryNextMethod();
end);

#############################################################################
##
#M MinimalGeneratingSet(<G>)
##
InstallOtherMethod(MinimalGeneratingSet,"fallback method to inform user",true,
 [IsObject],0,
function(G)
 if IsGroup(G) and IsSolvableGroup(G) then
 TryNextMethod();
 else
 Error(
 "`MinimalGeneratingSet' currently assumes that the group is solvable, or\n",
 "already possesses a generating set of size 2.\n",
 "In general, try `SmallGeneratingSet' instead, which returns a generating\n",
 "set that is small but not of guaranteed smallest cardinality");
 fi;
end);

InstallOtherMethod(MinimalGeneratingSet,"finite groups",true,
 [IsGroup and IsFinite],0,
function(g)
local r,i,j,u,f,q,n,lim,sel,nat,ok,mi;
 if not HasIsSolvableGroup(g) and IsSolvableGroup(g) and
 CanEasilyComputePcgs(g) then
 return MinimalGeneratingSet(g);
 fi;
 # start at rank 2/abelian rank
 n:=AbelianInvariants(g);
 if Length(n)>0 then
 r:=Maximum(List(Set(List(n,SmallestPrimeDivisor)),
 x->Number(n,y->y mod x=0)));
 else r:=0; fi;
 r:=Maximum(r,2);
 n:=false;
 repeat
 if Length(GeneratorsOfGroup(g))=r then
 return GeneratorsOfGroup(g);
 fi;
 for i in [1..10^r] do
 u:=SubgroupNC(g,List([1..r],x->Random(g)));
 if Size(u)=Size(g) then return GeneratorsOfGroup(u);fi; # found
 od;
 f:=FreeGroup(r);
 ok:=false;
 if not IsSolvableGroup(g) then
 if n=false then
 n:=ShallowCopy(NormalSubgroups(g));
 if IsPerfectGroup(g) then
 # all perfect groups of order <15360 *are* 2-generated
 lim:=15360;
 else
 # all groups of order <8 *are* 2-generated
 lim:=8;
 fi;
 n:=Filtered(n,x->IndexNC(g,x)>=lim and Size(x)>1);
 SortBy(n,x->-Size(x));
 mi:=MinimalInclusionsGroups(n);
 fi;
 i:=1;
 while i<=Length(n) do
 ok:=false;
 # is factor randomly r-generated?
 q:=2^r;
 while ok=false and q>0 do
 u:=n[i];
 for j in [1..r] do
 u:=ClosureGroup(u,Random(g));
 od;
 ok:=Size(u)=Size(g);
 q:=q-1;
 od;

 if not ok then
 # is factor a nonsplit extension with minimal normal -- if so rank
 # stays the same, no new test

 # minimal overnormals
 sel:=List(Filtered(mi,x->x[1]=i),x->x[2]);
 if Length(sel)>0 then
 nat:=NaturalHomomorphismByNormalSubgroupNC(g,n[i]);
 for j in sel do
 if not ok then
 # nonsplit extension (so pre-images will still generate)?
 ok:=0=Length(
 ComplementClassesRepresentatives(Image(nat),Image(nat,n[j])));
 fi;
 od;
 fi;
 fi;

 if not ok then
 q:=GQuotients(f,g/n[i]:findall:=false);
 if Length(q)=0 then
 # fail in quotient
 i:=Length(n)+10;
 Info(InfoGroup,2,"Rank ",r," fails in quotient\n");
 fi;
 fi;

 i:=i+1;
 od;

 fi;
 if n=false or i<=Length(n)+1 then
 # still try group
 q:=GQuotients(f,g:findall:=false);
 if Length(q)>0 then return List(GeneratorsOfGroup(f),
 x->ImagesRepresentative(q[1],x)) ;fi; # found

 fi;
 r:=r+1;
 until false;
end);

#############################################################################
##
#M IsElementaryAbelian(<G>) . . . . . test if a group is elementary abelian
##
InstallMethod( IsElementaryAbelian,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local i, # loop
 p; # order of one generator of <G>

 # if <G> is not commutative it is certainly not elementary abelian
 if not IsCommutative( G ) then
 return false;

 # if <G> is trivial it is certainly elementary abelian
 elif IsTrivial( G ) then
 return true;

 # if <G> is infinite it is certainly not elementary abelian
 elif HasIsFinite( G ) and not IsFinite( G ) then
 return false;

 # otherwise compute the order of the first nontrivial generator
 else
 # p := Order( GeneratorsOfGroup( G )[1] );
 i:=1;
 repeat
 p:=Order(GeneratorsOfGroup(G)[i]);
 i:=i+1;
 until p>1; # will work, as G is not trivial

 # if the order is not a prime <G> is certainly not elementary abelian
 if not IsPrime( p ) then
 return false;

 # otherwise test that all other nontrivial generators have order 
 else
 return ForAll( GeneratorsOfGroup( G ), gen -> gen^p = One( G ) );
 fi;

 fi;
 end );

#############################################################################
##
#M IsPGroup( <G> ) . . . . . . . . . . . . . . . . . is a group a p-group ?
##

# The following helper function makes use of the fact that for any given prime
# p, any (possibly infinite) nilpotent group G is a p-group if and only if any
# generating set of G consists of p-elements (i.e. elements whose order is a
# power of p). For finite G this is well-known. The general case follows from
# e.g. 5.2.6 in "A Course in the Theory of Groups" by Derek J.S. Robinson,
# since it holds in the case were G is abelian, and since being a p-group is
# a property inherited by quotients and extensions.
BindGlobal( "IS_PGROUP_FOR_NILPOTENT",
 function( G )
 local p, gen, ord;

 p := fail;
 for gen in GeneratorsOfGroup( G ) do
 ord := Order( gen );
 if ord = infinity then
 return false;
 elif ord > 1 then
 if p = fail then
 p := SmallestRootInt( ord );
 if not IsPrimeInt( p ) then
 return false;
 fi;
 else
 if ord <> p^PValuation( ord, p ) then
 return false;
 fi;
 fi;
 fi;
 od;
 if p = fail then
 return true;
 fi;

 SetPrimePGroup( G, p );
 return true;
 end);

# The following helper function uses the well-known fact that a finite group
# is a p-group if and only if its order is a prime power.
BindGlobal( "IS_PGROUP_FROM_SIZE",
 function( G )
 local s, p;

 s:= Size( G );
 if s = 1 then
 return true;
 elif s = infinity then
 return fail; # cannot say anything about infinite groups
 fi;
 p := SmallestRootInt( s );
 if not IsPrimeInt( p ) then
 return false;
 fi;

 SetPrimePGroup( G, p );
 return true;
 end);

InstallMethod( IsPGroup,
 "generic method (check order of the group or of generators if nilpotent)",
 [ IsGroup ],
 function( G )

 # We inspect orders of group generators if the group order is not yet
 # known *and* the group knows to be nilpotent or is abelian;
 # thus an `IsAbelian' test may be forced (which can be done via comparing
 # products of generators) but *not* an `IsNilpotent' test.
 if HasSize( G ) and IsFinite( G ) then
 return IS_PGROUP_FROM_SIZE( G );
 elif ( HasIsNilpotentGroup( G ) and IsNilpotentGroup( G ) )
 or IsAbelian( G ) then
 return IS_PGROUP_FOR_NILPOTENT( G );
 elif IsFinite( G ) then
 return IS_PGROUP_FROM_SIZE( G );
 fi;
 TryNextMethod();
 end );

InstallMethod( IsPGroup,
 "for nilpotent groups",
 [ IsGroup and IsNilpotentGroup ],
 function( G )

 if HasSize( G ) and IsFinite( G ) then
 return IS_PGROUP_FROM_SIZE( G );
 else
 return IS_PGROUP_FOR_NILPOTENT( G );
 fi;
 end );

#############################################################################
##
#M IsPowerfulPGroup( <G> ) . . . . . . . . . . is a group a powerful p-group ?
##
InstallMethod( IsPowerfulPGroup,
 "use characterisation of powerful p-groups based on rank ",
 [ IsGroup and HasRankPGroup and HasComputedOmegas ],
 function( G )
 local p;
 if (IsTrivial(G)) then
 return true;
 else
 p:=PrimePGroup(G);
 # We use the less known characterisation of powerful p groups
 # for p>3 by Jon Gonzalez-Sanchez, Amaia Zugadi-Reizabal
 # can be found in 'A characterization of powerful p-groups'
 if (p>3) then
 return RankPGroup(G)=Log(Order(Omega(G,p)),p);
 else
 TryNextMethod();
 fi;
 fi;
 end);

InstallMethod( IsPowerfulPGroup,
 "generic method checks inclusion of commutator subgroup in agemo subgroup",
 [ IsGroup ],
 function( G )
 local p;
 if IsPGroup( G ) = false then
 return false;
 elif IsTrivial(G) then
 return true;

 else

 p:=PrimePGroup(G);
 if p = 2 then
 return IsSubgroup(Agemo(G,2,2),DerivedSubgroup( G ));
 else
 return IsSubgroup(Agemo(G,p), DerivedSubgroup( G ));
 fi;
 fi;
 end);

#############################################################################
##
#M IsRegularPGroup( <G> ) . . . . . . . . . . is a group a regular p-group ?
##
InstallMethod( IsRegularPGroup,
 [ IsGroup ],
function( G )
local p, hom, reps, as, a, b, ap, bp, ab, ap_bp, ab_p, g, h, H, N;

 if not IsPGroup(G) then
 return false;
 fi;

 p:=PrimePGroup(G);
 if p = 2 then
 # see [Hup67, Satz III.10.3 a)]
 return IsAbelian(G);
 elif p = 3 and DerivedLength(G) > 2 then
 # see [Hup67, Satz III.10.3 b)]
 return false;
 elif Size(G) <= p^p then
 # see [Hal34, Corollary 14.14], [Hall, p. 183], [Hup67, Satz III.10.2 b)]
 return true;
 elif NilpotencyClassOfGroup(G) < p then
 # see [Hal34, Corollary 14.13], [Hall, p. 183], [Hup67, Satz III.10.2 a)]
 return true;
 elif IsCyclic(DerivedSubgroup(G)) then
 # see [Hup67, Satz III.10.2 c)]
 return true;
 elif Exponent(G) = p then
 # see [Hup67, Satz III.10.2 d)]
 return true;
 elif p = 3 and RankPGroup(G) = 2 then
 # see [Hup67, Satz 10.3 b)]: at this point we know that the derived
 # subgroup is not cyclic, hence G is not regular
 return false;
 elif Size(G) < p^p * Size(Agemo(G,p)) then
 # see [Hal36, Theorem 2.3], [Hup67, Satz III.10.13]
 return true;
 elif Index(DerivedSubgroup(G), Agemo(DerivedSubgroup(G),p)) < p^(p-1) then
 # see [Hal36, Theorem 2.3], [Hup67, Satz III.10.13]
 return true;
 fi;

 # We now use Proposition 2 from A. Mann, "Regular p-groups. II", 1972, DOI
 # 10.1007/BF02764891, which states: If N is a central elementary abelian
 # subgroup of order p^2, such that G/M is regular for all M with 1<M<N, then
 # G is regular. The reverse implication also holds as all sections of a
 # regular p-group are again regular.
 #
 # Such a subgroup exists if and only if the center of G is not cyclic.
 #
 # As a heuristic, we only apply this criterion if the index of the center in
 # G is not too small, as otherwise a brute force search is faster.
 #
 # Note: the book Y. Berkovich, "Groups of Prime Power Order, Volume 1", 2008
 # states a stronger version of this as Corollary 7.7, where it is basically
 # claimed that it suffices to check just two subgroups M of N. This result
 # is attributed to the above paper by Mann, but I can't find it in there,
 # and it also simply is wrong: for example, the direct product of
 # SmallGroup(3^5,22) and SmallGroup(3^5,22) has a center of order p^2 = 9,
 # which contains four subgroups M of order p = 3. For two of those the
 # corresponding quotient G/M is regular, and for the other two it is not.
 H := Center(G);
 if not IsCyclic(H) and Index(G, H) > 250 then
 if Size(H) = p^2 then
 N := H;
 else
 N := Group(Filtered(Pcgs(H), g -> Order(g) = p){[1,2]});
 fi;
 Assert(0, Size(N) = p^2);
 Assert(0, IsElementaryAbelian(N));
 reps := MinimalNormalSubgroups(N);
 Info( InfoGroup, 2, "IsRegularPGroup: using Mann criterion, |G| = ", Size(G),
 ", |reps| = ", Length(reps));
 return ForAll(reps, M -> IsRegularPGroup(G/M));
 fi;

 # Fallback to actually check the defining criterion, i.e.:
 # for all a,b in G, we must have that a^p*b^p/(a*b)^p in (<a,b>')^p

 # It suffices to pick 'a' among conjugacy class representatives.
 # Moreover, if 'a' is central then the criterion automatically holds.
 # For z,z'\in Z(G), the criterion holds for (a,b) iff it holds for (az,bz').
 # We thus choose 'a' among lifts of conjugacy class representatives in G/Z(G).
 hom := NaturalHomomorphismByNormalSubgroup(G, Center(G));
 reps := ConjugacyClasses(Image(hom));
 reps := List(reps, Representative);
 reps := Filtered(reps, g -> not IsOne(g));
 reps := List(reps, g -> PreImagesRepresentative(hom, g));

 as := List(reps, a -> [a,a^p]);

 for b in Image(hom) do
 b := PreImagesRepresentative(hom, b);
 bp := b^p;
 for a in as do
 ap := a[2]; a := a[1];
 # if a and b commute the regularity condition automatically holds
 ab := a*b;
 if ab = b*a then continue; fi;

 # regularity is also automatic if a^p * b^p = (a*b)^p
 ap_bp := ap * bp;
 ab_p := ab^p;
 if ap_bp = ab_p then continue; fi;

 # if the subgroup generated H by a and b is itself regular, we are also
 # done. However we don't use recursion here, as it is too expensive.
 # we just check the direct definition, with a twist to avoid Agemo
 g := ap_bp / ab_p;
 h := Comm(a,b)^p;
 # clearly h is in Agemo(DerivedSubgroup(Group([a,b])), p), so if g=h or
 # g=h^-1 then the regularity condition is satisfied
 if g = h or IsOne(g*h) then continue; fi;
 H := Subgroup(G, [a,b]);
 N := NormalClosure(H, [h]);
 # To follow the definition of regular precisely we should now check if g
 # is in A:=Agemo(DerivedSubgroup(H), p). Clearly h=[a,b]^p and all its
 # conjugates are contained in A, and so N is a subgroup of A. But it
 # could be a *proper* subgroup. Alas, if G is regular, then also H is
 # regular, and from [Hup67, Hauptsatz III.10.5.b)] we conclude A = N and
 # the test g in N will succeed. If on the other hand G is not regular,
 # then H may also be not regular, and then N might be too small. But
 # that is fine (and even beneficial), because that just means we might
 # reach the 'return false' faster.
 if not g in N then
 return false;
 fi;
 od;
 od;
 return true;

end);

#############################################################################
##
#M PrimePGroup . . . . . . . . . . . . . . . . . . . . . prime of a p-group
##
InstallMethod( PrimePGroup,
 "generic method, check the order of a nontrivial generator",
 [ IsPGroup and HasGeneratorsOfGroup ],
function( G )
local gen, s;
 if IsTrivial( G ) then
 return fail;
 fi;
 for gen in GeneratorsOfGroup( G ) do
 s := Order( gen );
 if s <> 1 then
 break;
 fi;
 od;
 return SmallestRootInt( s );
end );

InstallMethod( PrimePGroup,
 "generic method, check the group order",
 [ IsPGroup ],
function( G )
local s;
 # alas, the size method might try to be really clever and ask for the size
 # again...
 if IsTrivial(G) then
 return fail;
 fi;
 s:= Size( G );
 if s = 1 then
 return fail;
 fi;
 return SmallestRootInt( s );
end );

RedispatchOnCondition (PrimePGroup, true,
 [IsGroup],
 [IsPGroup], 0);

#############################################################################
##
#M IsNilpotentGroup( <G> ) . . . . . . . . . . test if a group is nilpotent
##
#T InstallImmediateMethod( IsNilpotentGroup, IsGroup and HasSize, 10,
#T function( G )
#T G:= Size( G );
#T if IsInt( G ) and IsPrimePowerInt( G ) then
#T return true;
#T fi;
#T TryNextMethod();
#T end );
#T This method does *not* fulfill the condition to be immediate,
#T factoring an integer may be expensive.
#T (Can we install a more restrictive method that *is* immediate,
#T for example one that checks only small integers?)

InstallMethod( IsNilpotentGroup,
 "if group size can be computed and is a prime power",
 [ IsGroup and CanComputeSize ], 25,
 function ( G )
 local s;

 s := Size ( G );
 if IsInt( s ) and IsPrimePowerInt( s ) then
 SetIsPGroup( G, true );
 SetPrimePGroup( G, SmallestRootInt( s ) );
 return true;
 elif s = 1 then
 SetIsPGroup( G, true );
 return true;
 elif s <> infinity then
 SetIsPGroup( G, false );
 fi;
 TryNextMethod();
 end );

InstallMethod( IsNilpotentGroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local S; # lower central series of <G>

 # compute the lower central series
 S := LowerCentralSeriesOfGroup( G );

 # <G> is nilpotent if the lower central series reaches the trivial group
 return IsTrivial( Last(S) );
 end );

#############################################################################
##
#M IsPerfectGroup( <G> ) . . . . . . . . . . . . test if a group is perfect
##
InstallImmediateMethod( IsPerfectGroup,
 IsGroup and HasIsAbelian and IsSimpleGroup,
 0,
 grp -> not IsAbelian( grp ) );

InstallMethod( IsPerfectGroup, "for groups having abelian invariants",
 [ IsGroup and HasAbelianInvariants ],
 grp -> Length( AbelianInvariants( grp ) ) = 0 );

InstallMethod( IsPerfectGroup,
 "method for finite groups",
 [ IsGroup and IsFinite ],
function(G)
 if not CanComputeIndex(G,DerivedSubgroup(G)) then
 TryNextMethod();
 fi;
 return Index( G, DerivedSubgroup( G ) ) = 1;
end);

InstallMethod( IsPerfectGroup, "generic method for groups",
 [ IsGroup ],
 G-> IsSubset(DerivedSubgroup(G),G));

#############################################################################
##
#M IsSporadicSimpleGroup( <G> )
##
InstallMethod( IsSporadicSimpleGroup,
 "for a group",
 [ IsGroup ],
 G -> IsFinite( G )
 and IsSimpleGroup( G )
 and IsomorphismTypeInfoFiniteSimpleGroup( G ).series = "Spor" );

#############################################################################
##
#M IsSimpleGroup( <G> ) . . . . . . . . . . . . . test if a group is simple
##
InstallMethod( IsSimpleGroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local C, # one conjugacy class of <G>
 g; # representative of <C>

 if IsTrivial( G ) then
 return false;
 fi;

 # loop over the conjugacy classes
 for C in ConjugacyClasses( G ) do
 g := Representative( C );
 if g <> One( G )
 and NormalClosure( G, SubgroupNC( G, [ g ] ) ) <> G
 then
 return false;
 fi;
 od;

 # all classes generate the full group
 return true;
 end );

#############################################################################
##
#P IsAlmostSimpleGroup( <G> )
##
## Since the outer automorphism groups of finite simple groups are solvable,
## a finite group <A>G</A> is almost simple if and only if the last member
## in the derived series of <A>G</A> is a simple group <M>S</M> (which is
## then necessarily nonabelian) such that the centralizer of <M>S</M> in
## <A>G</A> is trivial.
##
## (We could detect whether the given group is an extension of a group of
## prime order by some automorphisms, as follows.
## If the derived series ends with the trivial group then take the previous
## member of the series, and check whether it has prime order and is
## self-centralizing.)
##
InstallMethod( IsAlmostSimpleGroup,
 "for a group",
 [ IsGroup ],
 function( G )
 local der;

 if IsAbelian( G ) then
 # Exclude simple groups of prime order.
 return false;
 elif IsSimpleGroup( G ) then
 # Nonabelian simple groups are almost simple.
 return true;
 elif not IsFinite( G ) then
 TryNextMethod();
 fi;

 der:= DerivedSeriesOfGroup( G );
 der:= Last(der);
 if IsTrivial( der ) then
 return false;
 fi;
 return IsSimpleGroup( der ) and IsTrivial( Centralizer( G, der ) );
 end );

#############################################################################
##
#P IsQuasisimpleGroup( <G> )
##
InstallMethod( IsQuasisimpleGroup,
 "for a group",
 [ IsGroup ],
 G -> IsPerfectGroup( G ) and IsSimpleGroup( G / Centre( G ) ) );

#############################################################################
##
#M IsSolvableGroup( <G> ) . . . . . . . . . . . test if a group is solvable
##
## By the Feit–Thompson odd order theorem, every group of odd order is
## solvable.
##
## Now suppose G is a group of order 2m, with m odd. Let G act on itself from
## the right, yielding a monomorphism \phi:G \to Sym(G). G contains an
## involution h; then \phi(h) decomposes into a product of m disjoint
## transpositions, hence sign(\phi(h)) = -1. Hence the kernel N of the
## composition x \mapsto sign(\phi(x)) is a normal subgroup of G of index 2,
## hence |N| = m.
##
## By the odd order theorem, N is solvable, and so is G. Thus the order of
## any non-solvable finite group is a multiple of 4.
##
## By Burnside's theorem, every group of order p^a q^b is solvable. If a
## group of such order is not already caught by the reasoning above, then
## it must have order 2^a q^b with a>1.
##
InstallImmediateMethod( IsSolvableGroup, IsGroup and HasSize, 10,
 function( G )
 local size;
 size := Size( G );
 if IsInt( size ) and size mod 4 <> 0 then
 return true;
 fi;
 TryNextMethod();
 end );

InstallMethod( IsSolvableGroup,
 "if group size is known and is not divisible by 4 or p^a q^b",
 [ IsGroup and HasSize ], 25,
 function( G )
 local size;
 size := Size( G );
 if IsInt( size ) then
 if size mod 4 <> 0 then
 return true;
 else
 size := size/4;
 while size mod 2 = 0 do
 size := size/2;
 od;
 if size = 1 then
 SetIsPGroup( G, true );
 SetPrimePGroup( G, 2 );
 return true;
 elif IsPrimePowerInt( size ) then
 return true;
 fi;
 fi;
 fi;
 TryNextMethod();
 end );

InstallMethod( IsSolvableGroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local S, # derived series of <G>
 isAbelian, # true if <G> is abelian
 isSolvable; # true if <G> is solvable

 # compute the derived series of <G>
 S := DerivedSeriesOfGroup( G );

 # the group is solvable if the derived series reaches the trivial group
 isSolvable := IsTrivial( Last(S) );

 # set IsAbelian filter
 isAbelian := isSolvable and Length( S ) <= 2;
 Assert(3, IsAbelian(G) = isAbelian);
 SetIsAbelian(G, isAbelian);

 return isSolvable;
 end );

#############################################################################
##
#M IsSupersolvableGroup( <G> ) . . . . . . test if a group is supersolvable
##
## Note that this method automatically sets `SupersolvableResiduum'.
## Analogously, methods for `SupersolvableResiduum' should set
## `IsSupersolvableGroup'.
##
InstallMethod( IsSupersolvableGroup,
 "generic method for groups",
 [ IsGroup ],
 function( G )
 if IsNilpotentGroup( G ) then
#T currently the nilpotency test is much cheaper than the test below,
#T so we force it!
 return true;
 fi;
 return IsTrivial( SupersolvableResiduum( G ) );
 end );

#############################################################################
##
#M IsPolycyclicGroup( <G> ) . . . . . . . . . test if a group is polycyclic
##
InstallMethod( IsPolycyclicGroup,
 "generic method for groups", true, [ IsGroup ], 0,

 function ( G )

 local d;

 if IsFinite(G) then return IsSolvableGroup(G); fi;
 if not IsSolvableGroup(G) then return false; fi;
 d := DerivedSeriesOfGroup(G);
 return ForAll([1..Length(d)-1],i->Index(d[i],d[i+1]) < infinity
 or IsFinitelyGeneratedGroup(d[i]/d[i+1]));
 end );

#############################################################################
##
#M IsTrivial( <G> ) . . . . . . . . . . . . . . test if a group is trivial
##
InstallMethod( IsTrivial,
 [ IsGroup ],
 G -> ForAll( GeneratorsOfGroup( G ), gen -> gen = One( G ) ) );

#############################################################################
##
#M AbelianInvariants( <G> ) . . . . . . . . . abelian invariants of a group
##
InstallMethod( AbelianInvariants,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local H, p, l, r, i, j, gns, inv, ranks, g, cmm;

 if not IsFinite(G) then
 if HasIsCyclic(G) and IsCyclic(G) then
 return [ 0 ];
 fi;
 TryNextMethod();
 elif IsTrivial( G ) then
 return [];
 fi;

 gns := GeneratorsOfGroup( G );
 inv := [];
 # the parent of this will be G
 cmm := DerivedSubgroup(G);
 for p in PrimeDivisors( Size( G ) ) do
 ranks := [];
 repeat
 H := cmm;
 for g in gns do
 #NC is safe
 H := ClosureSubgroupNC( H, g ^ p );
 od;
 r := Size(G) / Size(H);
 Info( InfoGroup, 2,
 "AbelianInvariants: |<G>| = ", Size( G ),
 ", |<H>| = ", Size( H ) );
 G := H;
 gns := GeneratorsOfGroup( G );
 if r <> 1 then
 Add( ranks, Length(Factors(Integers,r)) );
 fi;
 until r = 1;
 Info( InfoGroup, 2,
 "AbelianInvariants: <ranks> = ", ranks );
 if 0 < Length(ranks) then
 l := List( [ 1 .. ranks[1] ], x -> 1 );
 for i in ranks do
 for j in [ 1 .. i ] do
 l[j] := l[j] * p;
 od;
 od;
 Append( inv, l );
 fi;
 od;

 Sort( inv );
 return inv;
 end );

InstallMethod( AbelianRank ,"generic method for groups", [ IsGroup ],0,
function(G)
local a,r;
 a:=AbelianInvariants(G);
 r:=Number(a,IsZero);
 a:=Filtered(a,x->not IsZero(x));
 if Length(a)=0 then return r; fi;
 a:=List(Set(a,SmallestRootInt),p->Number(a,x->x mod p=0));
 return r+Maximum(a);
end);

#############################################################################
##
#M IsInfiniteAbelianizationGroup( <G> )
##
InstallMethod( IsInfiniteAbelianizationGroup,"generic method for groups",
[ IsGroup ], G->0 in AbelianInvariants(G));

#############################################################################
##
#M AsGroup( <D> ) . . . . . . . . . . . . . . . domain <D>, viewed as group
##
InstallMethod( AsGroup, [ IsGroup ], 100, IdFunc );

InstallMethod( AsGroup,
 "generic method for collections",
 [ IsCollection ],
 function( D )
 local M, gens, m, minv, G, L;

 if IsGroup( D ) then
 return D;
 fi;

 # Check that the elements in the collection form a nonempty semigroup.
 M:= AsMagma( D );
 if M = fail or not IsAssociative( M ) then
 return fail;
 fi;
 gens:= GeneratorsOfMagma( M );
 if IsEmpty( gens ) or not IsGeneratorsOfMagmaWithInverses( gens ) then
 return fail;
 fi;

 # Check that this semigroup contains the inverses of its generators.
 for m in gens do
 minv:= Inverse( m );
 if minv = fail or not minv in M then
 return fail;
 fi;
 od;

 D:= AsSSortedList( D );
 G:= TrivialSubgroup( GroupByGenerators( gens ) );
 L:= ShallowCopy( D );
 SubtractSet( L, AsSSortedList( G ) );
 while not IsEmpty(L) do
 G := ClosureGroupDefault( G, L[1] );
 SubtractSet( L, AsSSortedList( G ) );
 od;
 if Length( AsList( G ) ) <> Length( D ) then
 return fail;
 fi;
 G := GroupByGenerators( GeneratorsOfGroup( G ), One( D[1] ) );
 SetAsSSortedList( G, D );
 SetIsFinite( G, true );
 SetSize( G, Length( D ) );

 # return the group
 return G;
 end );

#############################################################################
##
#M ChiefSeries( <G> ) . . . . . . . . delegate to `ChiefSeriesUnderAction'
##
InstallMethod( ChiefSeries,
 "method for a group (delegate to `ChiefSeriesUnderAction')",
 [ IsGroup ],
 G -> ChiefSeriesUnderAction( G, G ) );

#############################################################################
##
#M RefinedSubnormalSeries( <ser>,<n> )
##
InstallGlobalFunction("RefinedSubnormalSeries",function(ser,sub)
local new,i,c;
 new:=[];
 i:=1;
 if not IsSubset(ser[1],sub) then
 sub:=Intersection(ser[1],sub);
 fi;
 while i<=Length(ser) and IsSubset(ser[i],sub) do
 Add(new,ser[i]);
 i:=i+1;
 od;
 while i<=Length(ser) and not IsSubset(sub,ser[i]) do
 c:=ClosureGroup(sub,ser[i]);
 if Size(Last(new))>Size(c) then
 Add(new,c);
 fi;
 if Size(Last(new))>Size(ser[i]) then
 Add(new,ser[i]);
 fi;
 sub:=Intersection(sub,ser[i]);
 i:=i+1;
 od;
 if Size(sub)<Size(Last(new)) and i<=Length(ser) and Size(sub)>Size(ser[i]) then
 Add(new,sub);
 fi;
 while i<=Length(ser) do
 Add(new,ser[i]);
 i:=i+1;
 od;
 Assert(1,ForAll([1..Length(new)-1],x->Size(new[x])<>Size(new[x+1])));
 return new;
end);

#############################################################################
##
#M CommutatorFactorGroup( <G> ) . . . . commutator factor group of a group
##
InstallMethod( CommutatorFactorGroup,
 "generic method for groups",
 [ IsGroup ],
 function( G )
 G:= FactorGroupNC( G, DerivedSubgroup( G ) );
 SetIsAbelian( G, true );
 return G;
 end );

############################################################################
##
#M MaximalAbelianQuotient(<group>)
##
InstallMethod(MaximalAbelianQuotient,
 "not fp group",
 [ IsGroup ],
 function( G )
 if IsSubgroupFpGroup( G ) then
 TryNextMethod();
 fi;
 return NaturalHomomorphismByNormalSubgroupNC(G,DerivedSubgroup(G));
#T Here we know that the image is abelian, and this information may be
#T useful later on.
#T However, the image group of the homomorphism may be not stored yet,
#T so we do not attempt to set the `IsAbelian' flag for it.
end );

#############################################################################
##
#M CompositionSeries( <G> ) . . . . . . . . . . . composition series of <G>
##
InstallMethod( CompositionSeries,
 "using DerivedSubgroup",
 [ IsGroup and IsFinite ],
function( grp )
 local der, series, i, comp, low, elm, pelm, o, p, x,
 j, qelm;

 # this only works for solvable groups
 if HasIsSolvableGroup(grp) and not IsSolvableGroup(grp) then
 TryNextMethod();
 fi;
 der := DerivedSeriesOfGroup(grp);
 if not IsTrivial(Last(der)) then
 TryNextMethod();
 fi;

 # build up a series
 series := [ grp ];
 for i in [ 1 .. Length(der)-1 ] do
 comp := [];
 low := der[i+1];
 while low <> der[i] do
 repeat
 elm := Random(der[i]);
 until not elm in low;
 for pelm in PrimePowerComponents(elm) do
 o := Order(pelm);
 p := Factors(o)[1];
 x := LogInt(o,p);
 for j in [ x-1, x-2 .. 0 ] do
 qelm := pelm ^ ( p^j );
 if not qelm in low then
 Add( comp, low );
 low:= ClosureGroup( low, qelm );
 fi;
 od;
 od;
 od;
 Append( series, Reversed(comp) );
 od;

 return series;

end );

InstallMethod( CompositionSeries,
 "for simple group", true, [IsGroup and IsSimpleGroup], 100,
 S->[S,TrivialSubgroup(S)]);

InstallMethod(CompositionSeriesThrough,"intersection/union",IsElmsColls,
 [IsGroup and IsFinite,IsList],0,
function(G,normals)
local cs,i,j,pre,post,c,new,rev;
 cs:=CompositionSeries(G);
 # find normal subgroups not yet in
 normals:=Filtered(normals,x->not x in cs);
 # do we satisfy by sheer dumb luck?
 if Length(normals)=0 then return cs;fi;

 SortBy(normals,x->-Size(x));
 # check that this is a valid series
 Assert(0,ForAll([2..Length(normals)],i->IsSubset(normals[i-1],normals[i])));

 # Now move series through normals by closure/intersection
 for j in normals do
 # first in cs that does not contain j
 pre:=PositionProperty(cs,x->not IsSubset(x,j));
 # first contained in j.
 post:=PositionProperty(cs,x->Size(j)>=Size(x) and IsSubset(j,x));

 # if j is in the series, then pre>post. pre=post impossible
 if pre<post then
 # so from pre to post-1 needs to be changed
 new:=cs{[1..pre-1]};

 rev:=[j];
 i:=post-1;
 repeat
 if not IsSubset(Last(rev),cs[i]) then
 c:=ClosureGroup(cs[i],j);
 if Size(c)>Size(Last(rev)) then
 # proper down step
 Add(rev,c);
 fi;
 fi;
 i:=i-1;
 # at some point this must reach j, then no further step needed
 until Size(c)=Size(cs[pre-1]) or i<pre;
 Append(new,Filtered(Reversed(rev),x->Size(x)<Size(cs[pre-1])));

 i:=pre;
 repeat
 if not IsSubset(cs[i],Last(new)) then
 c:=Intersection(cs[i],j);
 if Size(c)<Size(Last(new)) then
 # proper down step
 Add(new,c);
 fi;
 fi;
 i:=i+1;
 until Size(c)=Size(cs[post]);
 fi;
 cs:=Concatenation(new,cs{[post+1..Length(cs)]});
 od;
 return cs;
end);

#############################################################################
##
#M ConjugacyClasses( <G> )
##

#############################################################################
##
#M ConjugacyClassesMaximalSubgroups( <G> )
##

##############################################################################
##
#M DerivedLength( <G> ) . . . . . . . . . . . . . . derived length of a group
##
InstallMethod( DerivedLength,
 "generic method for groups",
 [ IsGroup ],
 G -> Length( DerivedSeriesOfGroup( G ) ) - 1 );

##############################################################################
##
#M HirschLength( <G> ) . . . . .hirsch length of a polycyclic-by-finite group
##
InstallMethod( HirschLength,
 "generic method for finite groups",
 [ IsGroup and IsFinite ],
 G -> 0 );

#############################################################################
##
#M DerivedSeriesOfGroup( <G> ) . . . . . . . . . . derived series of a group
##
InstallMethod( DerivedSeriesOfGroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local S, # derived series of <G>, result
 lastS, # last element of S
 D; # derived subgroups

 # print out a warning for infinite groups
 if (HasIsFinite(G) and not IsFinite( G ))
 and not (HasIsPolycyclicGroup(G) and IsPolycyclicGroup( G )) then
 Info( InfoWarning, 1,
 "DerivedSeriesOfGroup: may not stop for infinite group <G>" );
 fi;

 # compute the series by repeated calling of `DerivedSubgroup'
 S := [ G ];
 lastS := G;
 Info( InfoGroup, 2, "DerivedSeriesOfGroup: step ", Length(S) );
 D := DerivedSubgroup( G );

 while
 (not HasIsTrivial(lastS) or
 not IsTrivial(lastS)) and
 (
 (not HasIsPerfectGroup(lastS) and
 not HasAbelianInvariants(lastS) and D <> lastS) or
 (HasIsPerfectGroup(lastS) and not IsPerfectGroup(lastS))
 or (HasAbelianInvariants(lastS)
 and Length(AbelianInvariants(lastS)) > 0)
 ) do
 Add( S, D );
 lastS := D;
 Info( InfoGroup, 2, "DerivedSeriesOfGroup: step ", Length(S) );
 D := DerivedSubgroup( D );
 od;

 # set filters if the last term is known to be trivial
 if HasIsTrivial(lastS) and IsTrivial(lastS) then
 SetIsSolvableGroup(G, true);
 if Length(S) <=2 then
 Assert(3, IsAbelian(G));
 SetIsAbelian(G, true);
 fi;
 fi;

 # set IsAbelian filter if length of derived series is more than 2
 if Length(S) > 2 then
 Assert(3, not IsAbelian(G));
 SetIsAbelian(G, false);
 fi;

 # return the series when it becomes stable
 return S;
 end );

#############################################################################
##
#M DerivedSubgroup( <G> ) . . . . . . . . . . . derived subgroup of a group
##
InstallMethod( DerivedSubgroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local D, # derived subgroup of <G>, result
 gens, # group generators of <G>
 i, j, # loops
 comm; # commutator of two generators of <G>

 # find the subgroup generated by the commutators of the generators
 D := TrivialSubgroup( G );
 gens:= GeneratorsOfGroup( G );
 for i in [ 2 .. Length( gens ) ] do
 for j in [ 1 .. i - 1 ] do
 comm := Comm( gens[i], gens[j] );
 #NC is safe (init with Triv)
 D := ClosureSubgroupNC( D, comm );
 od;
 od;

 # return the normal closure of <D> in <G>
 D := NormalClosure( G, D );
 if D = G then D := G; fi;
 return D;
 end );

InstallMethod( DerivedSubgroup,
 "for a group that knows it is perfect",
 [ IsGroup and IsPerfectGroup ],
 SUM_FLAGS, # this is better than everything else
 IdFunc );

InstallMethod( DerivedSubgroup,
 "for a group that knows it is abelian",
 [ IsGroup and IsAbelian ],
 SUM_FLAGS, # this is better than everything else
 TrivialSubgroup );

##########################################################################
##
#M DimensionsLoewyFactors( <G> ) . . . . . . dimension of the Loewy factors
##
InstallMethod( DimensionsLoewyFactors,
 "for a group (that must be a finite p-group)",
 [ IsGroup ],
 function( G )

 local p, J, x, P, i, s, j;

 # <G> must be a p-group
 if not IsPGroup( G ) then
 Error( "<G> must be a p-group" );
 fi;

 # get the prime and the Jennings series
 p := PrimePGroup( G );
 J := JenningsSeries( G );

 # construct the Jennings polynomial over the rationals
 x := Indeterminate( Rationals );
 P := One( x );
 for i in [ 1 .. Length(J)-1 ] do
 s := Zero( x );
 for j in [ 0 .. p-1 ] do
 s := s + x^(j*i);
 od;
 P := P * s^LogInt( Index( J[i], J[i+1] ), p );
 od;

 # the coefficients are the dimension of the Loewy series
 return CoefficientsOfUnivariatePolynomial( P );
 end );

#############################################################################
##
#M ElementaryAbelianSeries( <G> ) . . elementary abelian series of a group
##
InstallOtherMethod( ElementaryAbelianSeries,
 "method for lists",
 [ IsList and IsFinite],
 function( G )

 local i, A, f;

 # if <G> is a list compute an elementary series through a given normal one
 if not IsSolvableGroup( G[1] ) then
 return fail;
 fi;
 for i in [ 1 .. Length(G)-1 ] do
 if not IsNormal(G[1],G[i+1]) or not IsSubgroup(G[i],G[i+1]) then
 Error( "<G> must be normal series" );
 fi;
 od;

 # convert all groups in that list
 f := IsomorphismPcGroup( G[ 1 ] );
 A := ElementaryAbelianSeries(List(G,x->Image(f,x)));

 # convert back into <G>
 return List( A, x -> PreImage( f, x ) );
 end );

InstallMethod( ElementaryAbelianSeries,
 "generic method for finite groups",
 [ IsGroup and IsFinite],
 function( G )
 local f;

 # compute an elementary series if it is not known
 if not IsSolvableGroup( G ) then
 return fail;
 fi;

 # there is a method for pcgs computable groups we should use if
 # applicable, in this case redo
 if CanEasilyComputePcgs(G) then
 return ElementaryAbelianSeries(G);
 fi;

 f := IsomorphismPcGroup( G );

 # convert back into <G>
 return List( ElementaryAbelianSeries( Image( f )), x -> PreImage( f, x ) );
 end );

#############################################################################
##
#M ElementaryAbelianSeries( <G> ) . . elementary abelian series of a group
##
BindGlobal( "DoEASLS", function( S )
local N,I,i,L;

 N:=ElementaryAbelianSeries(S);
 # remove spurious factors
 L:=[N[1]];
 I:=N[1];
 i:=2;
 repeat
 while i<Length(N) and HasElementaryAbelianFactorGroup(I,N[i+1])
 and (IsIdenticalObj(I,N[i]) or not N[i] in S) do
 i:=i+1;
 od;
 I:=N[i];
 Add(L,I);
 until Size(I)=1;

 # return it.
 return L;
end );

InstallMethod( ElementaryAbelianSeriesLargeSteps,
 "remove spurious factors", [ IsGroup ],
 DoEASLS);

InstallOtherMethod( ElementaryAbelianSeriesLargeSteps,
 "remove spurious factors", [IsList],
 DoEASLS);

#############################################################################
##
#M Exponent( <G> ) . . . . . . . . . . . . . . . . . . . . . exponent of <G>
##
InstallMethod( Exponent,
 "generic method for finite groups",
 [ IsGroup and IsFinite ],
function(G)
 local exp, primes, p;
 exp := 1;
 primes := PrimeDivisors(Size(G));
 for p in primes do
 exp := exp * Exponent(SylowSubgroup(G, p));
 od;
 return exp;
end);

# ranked below the method for abelian groups
InstallMethod( Exponent,
 [ "IsGroup and IsFinite and HasConjugacyClasses" ],
 G-> Lcm(List(ConjugacyClasses(G), c-> Order(Representative(c)))) );

InstallMethod( Exponent,
 "method for finite abelian groups with generators",
 [ IsGroup and IsAbelian and HasGeneratorsOfGroup and IsFinite ],
 function( G )
 G:= GeneratorsOfGroup( G );
 if IsEmpty( G ) then
 return 1;
 fi;
 return Lcm( List( G, Order ) );
 end );

RedispatchOnCondition( Exponent, true, [IsGroup], [IsFinite], 0);

#############################################################################
##
#M FittingSubgroup( <G> ) . . . . . . . . . . . Fitting subgroup of a group
##
InstallMethod( FittingSubgroup, "for nilpotent group",
 [ IsGroup and IsNilpotentGroup ], SUM_FLAGS, IdFunc );

InstallMethod( FittingSubgroup,
 "generic method for finite groups",
 [ IsGroup and IsFinite ],
 function (G)
 if not IsTrivial( G ) then
 G := SubgroupNC( G, Filtered(Union( List( PrimeDivisors( Size( G ) ),
 p -> GeneratorsOfGroup( PCore( G, p ) ) ) ),
 p->p<>One(G)));
 Assert( 2, IsNilpotentGroup( G ) );
 SetIsNilpotentGroup( G, true );
 fi;
 return G;
 end);

RedispatchOnCondition( FittingSubgroup, true, [IsGroup], [IsFinite], 0);

#############################################################################
##
#M FrattiniSubgroup( <G> ) . . . . . . . . . . Frattini subgroup of a group
##
InstallMethod( FrattiniSubgroup, "method for trivial groups",
 [ IsGroup and IsTrivial ], IdFunc );

InstallMethod( FrattiniSubgroup, "for abelian groups",
 [ IsGroup and IsAbelian ],
function(G)
 local i, abinv, indgen, p, q, gen;

 gen := [ ];
 abinv := AbelianInvariants(G);
 indgen := IndependentGeneratorsOfAbelianGroup(G);
 for i in [1..Length(abinv)] do
 q := abinv[i];
 if q<>0 and not IsPrime(q) then
 p := SmallestRootInt(q);
 Add(gen, indgen[i]^p);
 fi;
 od;
 return SubgroupNC(G, gen);
end);

InstallMethod( FrattiniSubgroup, "for powerful p-groups",
 [ IsPGroup and IsPowerfulPGroup and HasComputedAgemos ],100,
function(G)
 local p;
#If the group is powerful and has computed agemos, then no work needs
#to be done, since FrattiniSubgroup(G)=Agemo(G,p) in this case
#by properties of powerful p-groups.
 p:=PrimePGroup(G);
 return Agemo(G,p);
end);

InstallMethod( FrattiniSubgroup, "for nilpotent groups",
 [ IsGroup and IsNilpotentGroup ],
function(G)
 local hom, Gf;

 hom := MaximalAbelianQuotient(G);
 Gf := Image(hom);
 SetIsAbelian(Gf, true);
 return PreImage(hom, FrattiniSubgroup(Gf));
end);

InstallMethod( FrattiniSubgroup, "generic method for groups",
 [ IsGroup ],
 0,
function(G)
local m;
 if IsTrivial(G) then
 return G;
 fi;
 if not HasIsSolvableGroup(G) and IsSolvableGroup(G) then
 return FrattiniSubgroup(G);
 fi;
 m := List(ConjugacyClassesMaximalSubgroups(G),C->Core(G,Representative(C)));
 m := Intersection(m);
 if HasIsFinite(G) and IsFinite(G) then
 Assert(2,IsNilpotentGroup(m));
 SetIsNilpotentGroup(m,true);
 fi;
 return m;
end);

#############################################################################
##
#M JenningsSeries( <G> ) . . . . . . . . . . . jennings series of a p-group
##
InstallMethod( JenningsSeries,
 "generic method for groups",
 [ IsGroup ],
 function( G )

 local p, n, i, C, L;

 # <G> must be a p-group
 if not IsPGroup( G ) then
 Error( "<G> must be a p-group" );
 fi;

 # get the prime
 p := PrimePGroup( G );

 # and compute the series
 # (this is a new variant thanks to Laurent Bartholdi)
 L := [ G ];
 n := 2;
 while not IsTrivial(L[n-1]) do
 L[n] := ClosureGroup(CommutatorSubgroup(G,L[n-1]),
 List(GeneratorsOfGroup(L[QuoInt(n+p-1,p)]),x->x^p));
 n := n+1;
 od;
 return L;

 end );

#############################################################################
##
#M LowerCentralSeriesOfGroup( <G> ) . . . . lower central series of a group
##
InstallMethod( LowerCentralSeriesOfGroup,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local S, # lower central series of <G>, result
 C; # commutator subgroups

 # print out a warning for infinite groups
 if (HasIsFinite(G) and not IsFinite( G ))
 and not (HasIsNilpotentGroup(G) and IsNilpotentGroup( G )) then
 Info( InfoWarning, 1,
 "LowerCentralSeriesOfGroup: may not stop for infinite group <G>");
 fi;

 # compute the series by repeated calling of `CommutatorSubgroup'
 S := [ G ];
 Info( InfoGroup, 2, "LowerCentralSeriesOfGroup: step ", Length(S) );
 C := DerivedSubgroup( G );
 while C <> Last(S) do
 Add( S, C );
 Info( InfoGroup, 2, "LowerCentralSeriesOfGroup: step ", Length(S) );
 C := CommutatorSubgroup( G, C );
 od;

 # return the series when it becomes stable
 return S;
 end );

#############################################################################
##
#M NilpotencyClassOfGroup( <G> ) . . . . lower central series of a group
##
InstallMethod(NilpotencyClassOfGroup,"generic",[IsGroup],0,
function(G)
 if not IsNilpotentGroup(G) then
 Error("<G> must be nilpotent");
 fi;
 return Length(LowerCentralSeriesOfGroup(G))-1;
end);

#############################################################################
##
#M MaximalSubgroups( <G> )
##
InstallMethod(MaximalSubgroupClassReps,"default, catch dangerous options",
 true,[IsGroup],0,
function(G)
local a,m,i,l;
 # use ``try'' and set flags so that a known partial result is not used
 m:=TryMaximalSubgroupClassReps(G:
 cheap:=false,intersize:=false,inmax:=false,nolattice:=false);
 l:=[];
 for i in m do
 a:=SubgroupNC(G,GeneratorsOfGroup(i));
 if HasSize(i) then SetSize(a,Size(i));fi;
 Add(l,a);
 od;

 # now we know list is untained, store
 return l;

end);

# handle various options and flags
InstallGlobalFunction(TryMaximalSubgroupClassReps,
function(G)
local cheap,nolattice,intersize,attr,kill,i,flags,sup,sub,l;
 if HasMaximalSubgroupClassReps(G) then
 return MaximalSubgroupClassReps(G);
 fi;
 # the four possible options
 cheap:=ValueOption("cheap");
 if cheap=fail then cheap:=false;fi;
 nolattice:=ValueOption("nolattice");
 if nolattice=fail then nolattice:=false;fi;
 intersize:=ValueOption("intersize");
 if intersize=fail then intersize:=false;fi;
 #inmax:=ValueOption("inmax"); # should have no impact on validity of stored
 attr:=StoredPartialMaxSubs(G);
 # now find whether any stored information matches and which ones would be
 # superseded
 kill:=[];
 for i in [1..Length(attr)] do
 flags:=attr[i][1];
 # could use this stored result
 sup:=flags[3]=false or (IsInt(intersize) and intersize<=flags[3]);
 # would supersede the stored result
 sub:=intersize=false or (IsInt(flags[3]) and intersize>=flags[3]);
 sup:=sup and (cheap or not flags[1]);
 sub:=sub and (not cheap or flags[1]);
 sup:=sup and (nolattice or not flags[2]);
 sub:=sub and (not nolattice or flags[2]);
 if sup then return attr[i][2];fi; # use stored
 if sub then AddSet(kill,i);fi; # use stored
 od;
 l:=CalcMaximalSubgroupClassReps(G);
 Add(attr,Immutable([[cheap,nolattice,intersize],l]));
 # finally kill superseded ones (by replacing with last, which possibly was
 # just added)
 for i in Reversed(Set(kill)) do
 if i = Length(attr) then
 Remove(attr);
 else
 attr[i]:=Remove(attr);
 fi;
 od;
 return l;
end);

InstallMethod(StoredPartialMaxSubs,"set",true,[IsGroup],0,x->[]);

#############################################################################
##
#M NrConjugacyClasses( <G> ) . . no. of conj. classes of elements in a group
##
InstallImmediateMethod( NrConjugacyClasses,
 IsGroup and HasConjugacyClasses and IsAttributeStoringRep,
 0,
 G -> Length( ConjugacyClasses( G ) ) );

InstallMethod( NrConjugacyClasses,
 "generic method for groups",
 [ IsGroup ],
 G -> Length( ConjugacyClasses( G ) ) );

#############################################################################
##
#A IndependentGeneratorsOfAbelianGroup( <A> )
##
# to catch some trivial cases.
InstallMethod(IndependentGeneratorsOfAbelianGroup,"finite abelian group",
 true,[IsGroup and IsAbelian],0,
function(G)
local hom,gens;
 if not IsFinite(G) then
 TryNextMethod();
 fi;
 hom:=IsomorphismPermGroup(G);
 gens:=IndependentGeneratorsOfAbelianGroup(Image(hom,G));
 return List(gens,i->PreImagesRepresentative(hom,i));
end);

#############################################################################
##
#O IndependentGeneratorExponents( <G>, <g> )
##
InstallMethod(IndependentGeneratorExponents,IsCollsElms,
 [IsGroup and IsAbelian, IsMultiplicativeElementWithInverse],0,
function(G,elm)
local ind, pcgs, primes, pos, p, i, e, f, a, j;
 if not IsBound(G!.indgenpcgs) then
 ind:=IndependentGeneratorsOfAbelianGroup(G);
 pcgs:=[];
 primes:=[];
 pos:=[];
 for i in ind do
 Assert(1, IsPrimePowerInt(Order(i)));
 p:=SmallestRootInt(Order(i));
 Add(primes,p);
 Add(pos,Length(pcgs)+1);
 while not IsOne(i) do
 Add(pcgs,i);
 i:=i^p;
 od;
 od;
 Add(pos,Length(pcgs)+1);
 pcgs:=PcgsByPcSequence(FamilyObj(One(G)),pcgs);
 G!.indgenpcgs:=rec(pcgs:=pcgs,primes:=primes,pos:=pos,gens:=ind);
 else
 pcgs:=G!.indgenpcgs.pcgs;
 primes:=G!.indgenpcgs.primes;
 pos:=G!.indgenpcgs.pos;
 ind:=G!.indgenpcgs.gens;
 fi;
 e:=ExponentsOfPcElement(pcgs,elm);
 f:=[];
 for i in [1..Length(ind)] do
 a:=0;
 for j in [pos[i+1]-1,pos[i+1]-2..pos[i]] do
 a:=a*primes[i]+e[j];
 od;
 Add(f,a);
 od;
 return f;
end);

#############################################################################
##
#M Omega( <G>, [, <n>] ) . . . . . . . . . . . omega of a -group <G>
##
InstallMethod( Omega,
 [ IsGroup, IsPosInt ],
 function( G, p )
 return Omega( G, p, 1 );
 end );

InstallMethod( Omega,
 [ IsGroup, IsPosInt, IsPosInt ],
 function( G, p, n )
 local known;

 # <G> must be a -group
 if not IsPGroup(G) or PrimePGroup(G)<>p then
 Error( "Omega: <G> must be a p-group" );
 fi;

 known := ComputedOmegas( G );
 if not IsBound( known[ n ] ) then
 known[ n ] := OmegaOp( G, p, n );
 fi;
 return known[ n ];
 end );

InstallMethod( ComputedOmegas, [ IsGroup ], 0, G -> [ ] );

#############################################################################
##
#M SolvableRadical( <G> ) . . . . . . . . . . . solvable radical of a group
##
InstallMethod( SolvableRadical,
 "factor out Fitting subgroup",
 [IsGroup and IsFinite],
function(G)
 local F,f;
 F := FittingSubgroup(G);
 if IsTrivial(F) then return F; fi;
 f := NaturalHomomorphismByNormalSubgroupNC(G,F);
 return PreImage(f,SolvableRadical(Image(f)));
end);

RedispatchOnCondition( SolvableRadical, true, [IsGroup], [IsFinite], 0);

InstallMethod( SolvableRadical,
 "solvable group is its own solvable radical",
 [ IsGroup and IsSolvableGroup ], 100,
 IdFunc );

#############################################################################
##
#M GeneratorsSmallest( <G> ) . . . . . smallest generating system of a group
##
InstallMethod( GeneratorsSmallest,
 "generic method for groups",
 [ IsGroup ],
 function ( G )
 local gens, # smallest generating system of <G>, result
 gen, # one generator of <gens>
 H; # subgroup generated by <gens> so far

 # start with the empty generating system and the trivial subgroup
 gens := [];
 H := TrivialSubgroup( G );

 # loop over the elements of <G> in their order
 for gen in EnumeratorSorted( G ) do

 # add the element not lying in the subgroup generated by the previous
 if not gen in H then
 Add( gens, gen );
 #NC is safe (init with Triv)
 H := ClosureSubgroupNC( H, gen );

 # it is important to know when to stop
 if Size( H ) = Size( G ) then
 return gens;
 fi;

 fi;

 od;

 if Size(G)=1 then
 # trivial subgroup case
 return [];
 fi;

 # well we should never come here
 Error( "panic, <G> not generated by its elements" );
 end );

#############################################################################
##
#M LargestElementGroup( <G> )
##
## returns the largest element of <G> with respect to the ordering `\<' of
## the elements family.
InstallMethod(LargestElementGroup,"use `EnumeratorSorted'",true,[IsGroup],
function(G)
 return EnumeratorSorted(G)[Size(G)];
end);

#############################################################################
##
#F SupersolvableResiduumDefault( <G> ) . . . . supersolvable residuum of <G>
##
## The algorithm constructs a descending series of normal subgroups with
## supersolvable factor group from <G> to its supersolvable residuum such
## that any subgroup that refines this series is normal in <G>.
##
## In each step of the algorithm, a normal subgroup <N> of <G> with
## supersolvable factor group is taken.
## Then its commutator factor group is constructed and decomposed into its
## Sylow subgroups.
## For each, the Frattini factor group is considered as a <G>-module.
## We are interested only in the submodules of codimension 1.
## For these cases, the eigenspaces of the dual submodule are calculated,
## and the preimages of their orthogonal spaces are used to construct new
## normal subgroups with supersolvable factor groups.
## If no eigenspace is found within one step, the residuum is reached.
##
## The component `ds' describes a series such that any composition series
## through `ds' from <G> down to the residuum is a chief series.
##
InstallGlobalFunction( SupersolvableResiduumDefault, function( G )
 local ssr, # supersolvable residuum
 ds, # component `ds' of the result
 gens, # generators of `G'
 gs, # small generating system of `G'
 p, # loop variable
 o, # group order
 size, # size of `G'
 s, # subgroup of `G'
 oldssr, # value of `ssr' in the last iteration
 dh, # nat. hom. modulo derived subgroup
 df, # range of `dh'
 fs, # list of factors of the size of `df'
 gen, # generators for the next candidate
 pp, # `p'-part of the size of `df'
 pu, # Sylow `p' subgroup of `df'
 tmp, # agemo generators
 ph, # nat. hom. onto Frattini quotient of `pu'
 ff, # Frattini factor
 ffsize, # size of `ff'
 pcgs, # PCGS of `ff'
 dim, # dimension of the vector space `ff'
 field, # prime field in char. `p'
 one, # identity in `field'
 idm, # identity matrix
 mg, # matrices of `G' action on `ff'
 vsl, # list of simult. eigenspaces
 nextvsl, # for next iteration
 matrix, # loop variable
 mat, #
 eigenvalue, # loop variable
 nullspace, # generators of the eigenspace
 space, # loop variable
 inter, # intersection
 tmp2, #
 v; #

 ds := [ G ];
 ssr := DerivedSubgroup( G );
 if Size( ssr ) < Size( G ) then
 ds[2]:= ssr;
 fi;

 if not IsTrivial( ssr ) then

 # Find a small generating system `gs' of `G'.
 # (We do *NOT* want to call `SmallGeneratingSet' here since
 # `MinimalGeneratingSet' is installed as a method for pc groups,
 # and for groups such as the Sylow 3 normalizer in F3+,
 # this needs more time than `SupersolvableResiduumDefault'.
 # Also the other method for `SmallGeneratingSet', which takes those
 # generators that cannot be omitted, is too slow.
 # The ``greedy'' type code below need not process all generators,
 # and it will be not too bad for pc groups.)
 gens := GeneratorsOfGroup( G );
 gs := [ gens[1] ];
 p := 2;
 o := Order( gens[1] );
 size := Size( G );
 repeat
 s:= SubgroupNC( G, Concatenation( gs, [ gens[p] ] ) );
 if o < Size( s ) then
 Add( gs, gens[p] );
 o:= Size( s );
 fi;
 p:= p+1;
 until o = size;

 # Loop until we reach the residuum.
 repeat

 # Remember the last candidate as `oldssr'.
 oldssr := ssr;
 ssr := DerivedSubgroup( oldssr );

 if Size( ssr ) < Size( oldssr ) then

 dh:= NaturalHomomorphismByNormalSubgroupNC( oldssr, ssr );

 # `df' is the commutator factor group `oldssr / ssr'.
 df:= Range( dh );
 SetIsAbelian( df, true );
 fs:= Factors(Integers, Size( df ) );

 # `gen' collects the generators for the next candidate
 gen := ShallowCopy( GeneratorsOfGroup( df ) );

 for p in Set( fs ) do

 pp:= Product( Filtered( fs, x -> x = p ) );

 # `pu' is the Sylow `p' subgroup of `df'.
 pu:= SylowSubgroup( df, p );

 # Remove the `p'-part from the generators list `gen'.
 gen:= List( gen, x -> x^pp );

 # Add the agemo_1 of the Sylow subgroup to the generators list.
 tmp:= List( GeneratorsOfGroup( pu ), x -> x^p );
 Append( gen, tmp );
 ph:= NaturalHomomorphismByNormalSubgroupNC( pu,
 SubgroupNC( df, tmp ) );

 # `ff' is the `p'-part of the Frattini factor group of `pu'.
 ff := Range( ph );
 ffsize:= Size( ff );
 if p < ffsize then

 # noncyclic case
 pcgs := Pcgs( ff );
 dim := Length( pcgs );
 field:= GF(p);
 one := One( field );
 idm := IdentityMat( dim, field );

 # `mg' is the list of matrices of the action of `G' on the
 # dual space of the module, w.r.t. `pcgs'.
 mg:= List( gs, x -> TransposedMat( List( pcgs,
 y -> one * ExponentsOfPcElement( pcgs, Image( ph,
 Image( dh, PreImagesRepresentative(
 dh, PreImagesRepresentative(ph,y) )^x ) ) )))^-1);
#T inverting is not necessary, or?
 mg:= Filtered( mg, x -> x <> idm );

 # `vsl' is a list of generators of all the simultaneous
 # eigenspaces.
 vsl:= [ idm ];
 for matrix in mg do

 nextvsl:= [];

 # All eigenvalues of `matrix' will be used.
 # (We expect `p' to be small, so looping over the nonzero
 # elements of the field is much faster than constructing and
 # factoring the characteristic polynomial of `matrix').
 mat:= matrix;
 for eigenvalue in [ 2 .. p ] do
 mat:= mat - idm;
 nullspace:= NullspaceMat( mat );
 if not IsEmpty( nullspace ) then
 for space in vsl do
 inter:= SumIntersectionMat( space, nullspace )[2];
 if not IsEmpty( inter ) then
 Add( nextvsl, inter );
 fi;
 od;
 fi;

 od;

 vsl:= nextvsl;

 od;

 # Now calculate the dual spaces of the eigenspaces.
 if IsEmpty( vsl ) then
 Append( gen, GeneratorsOfGroup( pu ) );
 else

 # `tmp' collects the eigenspaces.
 tmp:= [];
 for matrix in vsl do

 # `tmp2' will be the base of the dual space.
 tmp2:= [];
 Append( tmp, matrix );
 for v in NullspaceMat( TransposedMat( tmp ) ) do

 # Construct a group element corresponding to
--> --------------------

--> maximum size reached

--> --------------------

SSL grp.gi Sprache: unbekannt

[ Verzeichnis aufwärts0.55unsichere Verbindung Übersetzung europäischer Sprachen durch Browser ]