|
#############################################################################
##
## 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 <p>-th powers of the generators
# generate a subgroup of index <p> for all prime divisors <p>
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 <p>
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>, <p>[, <n>] ) . . . . . . . . . . . omega of a <p>-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 <p>-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
--> --------------------
[ Konzepte0.56Was zu einem Entwurf gehört
Wie die Entwicklung von Software durchgeführt wird
]
|
