|
#############################################################################
##
#W upext.gi GrpConst Bettina Eick
#W Hans Ulrich Besche
##
#############################################################################
##
#F GroupOfInnerAutomorphismSpecial( G, A )
##
InstallGlobalFunction( GroupOfInnerAutomorphismSpecial,
function( G, A )
local gens, autos, g, imgs, inn;
gens := GeneratorsOfGroup( G );
autos := [];
for g in gens do
imgs := List( gens, x -> x^g );
inn := GroupHomomorphismByImagesNC( G, G, gens, imgs );
Add( autos, inn );
od;
return SubgroupNC( A, autos );
end );
#############################################################################
##
#F AutomorphismGroupSpecial(G)
##
## Characteristic direct products are a special case.
##
BindGlobal( "AutomorphismGroupSpecial", function(G)
local N, C, U,
AN, AC, gensN, gensC, idN, idC, gens, autos, aut, imgs, auto,
cls, tups, subl, tup, ext, tmp, cl, imgtup, n, orb, g, max, k,
i, I, A, img, t, len, all, vec, done, o;
if HasAutomorphismGroup( G ) then
return AutomorphismGroup( G );
fi;
# get char classes of G
N := PerfectResiduum( G );
C := Centralizer( G, N );
U := Intersection( N, C );
# catch the direct product case
if Size(C) > 1 and Size(N) > 1 and Size(U) = 1 and
Size(N)*Size(C)=Size(G) then
Info( InfoGrpCon, 3, " Aut: compute aut group - direct product case");
AN := AutomorphismGroup(N);
AC := AutomorphismGroup(C);
gensN := GeneratorsOfGroup( N );
gensC := GeneratorsOfGroup( C );
gens := Concatenation(gensN, gensC);
autos := [];
for aut in GeneratorsOfGroup( AN ) do
imgs := List( gensN, x -> Image(aut, x) );
Append( imgs, gensC );
auto := GroupHomomorphismByImagesNC( G,G,gens,imgs );
Add( autos, auto );
od;
for aut in GeneratorsOfGroup( AC ) do
imgs := ShallowCopy( gensN );
Append( imgs, List( gensC, x -> Image(aut, x) ) );
auto := GroupHomomorphismByImagesNC( G,G,gens,imgs );
Add( autos, auto );
od;
A := Group( autos, IdentityMapping(G) );
SetIsFinite( A, true );
SetIsAutomorphismGroup( A, true );
SetAutomorphismGroup( G, A );
return A;
fi;
Info( InfoGrpCon, 3, " Aut: compute aut group - general case ");
return AutomorphismGroup( G );
end );
#############################################################################
##
#F DirectSplitting( G, N )
##
BindGlobal( "DirectSplitting", function( G, N )
local C, U, cl, norm;
C := Centralizer( G, N );
U := Intersection( C, N );
if Size(C)*Size(N)/Size(U) <> Size(G) then
return [G];
fi;
if Size(U) = 1 then return [G, C]; fi;
if IsSolvableGroup( U ) then
cl := ComplementClassesRepresentatives( C, U );
cl := Filtered( cl, x -> IsNormal(G,x) );
if Length(cl)>0 then
return [G, cl[1]];
else
return [G];
fi;
fi;
norm := NormalSubgroups( C );
norm := Filtered(norm, x -> Size(x) = Size(C)/Size(U) );
norm := Filtered(norm, x -> Size(Intersection(U,N)) = 1 );
if Length(norm)>0 then
return [G, norm[1]];
else
return [G];
fi;
end );
#############################################################################
##
#F RandomIsomorphismTestUEM( G, H )
##
BindGlobal( "RandomIsomorphismTestUEM", function( G, H )
local cocl, cocr, size, ngens, size_inner, elms, poses, pos, qual, i, j,
gens1, gens2, f, tpos, tqual, len_classes;
cocl := List( [ G, H ], CocGroup );
cocr := DiffCocList( cocl, false );
if cocr[ Length( cocr ) ] <> fail then
Info( InfoRandIso, 2, "RandomIsomorphismTestUEM distinguishs groups" );
return false;
fi;
size := Size( G );
ngens := Length( SmallGeneratingSet( G ) );
size_inner := size / Size( Center( G ) );
cocl := List( cocl, x -> List( x, Concatenation ) );
len_classes := List( cocl[ 1 ], Length );
elms := Concatenation( cocl[ 1 ] );
poses := Concatenation( List( [ 1 .. Length( len_classes ) ],
x -> List( [ 1 .. len_classes[ x ] ], y -> x ) ) );
SortParallel( elms, poses );
pos := fail;
qual := size ^ ngens;
for i in [ 1 .. 1000 ] do
gens1 := List( [ 1 .. ngens ], x -> Random( AsList( G ) ) );
tpos := List( gens1, x -> poses[ Position( elms, x ) ] );
tqual := Product( len_classes{ tpos } );
if ( tqual >= size_inner ) and ( tqual < qual ) and
( Size( Group( gens1 ) ) = size ) then
pos := tpos;
qual := tqual;
fi;
od;
if pos = fail then
Info( InfoRandIso, 1, "RandomIsomorphismTestUEM: ",
" no generating system found" );
return fail;
fi;
Info( InfoRandIso, 3, "RandomIsomorphismTestUEM: ", qual,
" generating system candidates" );
j := 0;
f := 0;
cocl := List( cocl, x -> x{ pos } );
while true do
j := j + 1;
repeat
gens1 := List( cocl[ 1 ], Random );
f := f + 1;
if j + f > 10000 then
Info( InfoRandIso, 2,
"RandomIsomorphismTestUEM failed to decide" );
return fail;
fi;
until Size( Group( gens1 ) ) = size;
repeat
gens2 := List( cocl[ 2 ], Random );
f := f + 1;
if j + f > 10000 then
Info( InfoRandIso, 2,
"RandomIsomorphismTestUEM failed to decide" );
return fail;
fi;
until Size( Group( gens2 ) ) = size;
if GroupHomomorphismByImages( G, H, gens1, gens2 ) <> fail then
Info( InfoRandIso, 2, "RandomIsomorphismTestUEM ",
"found isomorphism" );
return true;
fi;
if j mod 50 = 0 then
Info( InfoRandIso, 5, "RandomIsomorphismTestUEM: ", j,
" loops without isomorphism" );
fi;
od;
end );
#############################################################################
##
#F IsomorphismTest( G, H )
##
BindGlobal( "IsomorphismTest", function( G, H )
local homG, homH, dirG, dirH, res, i;
# the factor
Info( InfoGrpCon, 4, " Iso: test isomorphism on groups of size ",Size(G));
homG := NaturalHomomorphismByNormalSubgroupNC( G, PerfectResiduum(G) );
homH := NaturalHomomorphismByNormalSubgroupNC( H, PerfectResiduum(H) );
if IdGroup( Image( homG ) ) <> IdGroup( Image( homH ) ) then
return false;
fi;
# check for direct splittings
dirG := DirectSplitting( G, PerfectResiduum(G) );
dirH := DirectSplitting( H, PerfectResiduum(H) );
if Length( dirG ) <> Length( dirH ) then
return false;
elif Length( dirG ) = 2 then
return true;
fi;
# lets make some random tests
for i in [ 1 .. 3 ] do
res := RandomIsomorphismTestUEM( G, H );
if res in [ true, false ] then
return res;
fi;
od;
# the final test - both groups are not direct splittings
return not IsBool( IsomorphismGroups( G, H ) );
end );
#############################################################################
##
#F ReducedList( size, list )
##
BindGlobal( "ReducedList", function( size, list )
local rem, types, G, new, i, H, iso, g, h;
if Length( list ) <= 1 then return list; fi;
rem := [1..Length(list)];
types := [];
while Length(rem) > 0 do
g := list[rem[1]];
G := Group( g, () );
SetSize( G, size );
new := [rem[1]];
Add( types, g );
# compute isomorphic copies
for i in [2..Length(rem)] do
h := list[rem[i]];
H := Group( h, () );
SetSize( H, size );
iso := IsomorphismTest( G, H );
if iso then
Add( new, rem[i] );
fi;
od;
# delete them from rem
rem := Difference( rem, new );
od;
return types;
end );
#############################################################################
##
#F IsomorphismClasses( size, list )
##
BindGlobal( "IsomorphismClasses", function( size, list )
local sub, fin, G, f, j, i, g, finger;
if Length( list ) <= 1 then return list ; fi;
Info( InfoGrpCon, 3," Iso: test isom on ", Length(list)," groups ");
Assert(0, size = Size( Group( list[1], () ) ));
if ID_AVAILABLE(size) <> fail then
finger := IdGroup;
else
finger := FingerprintFF;
fi;
# first compute fingerprints
sub := [];
fin := [];
for i in [1..Length(list)] do
if InfoLevel(InfoGrpCon) >= 3 then
Print("\r", "#I computing fingerprint ", i, "/", Length(list), "\c");
fi;
g := list[i];
G := Group( g, () );
SetSize( G, size );
f := finger( G );
j := Position( fin, f );
if IsBool( j ) then
Add( sub, [g] );
Add( fin, f );
else
Add( sub[j], g );
fi;
od;
if InfoLevel(InfoGrpCon) >= 3 then
Print("\r");
fi;
SortBy( sub, Length );
Info( InfoGrpCon, 3, " Iso: split up in sublists of length ",
List( sub, Length ) );
# now reduce
for i in [1..Length(sub)] do
Info( InfoGrpCon, 3, " Iso: start sublist ", i ,"/", Length(sub),
" of length ", Length(sub[i]) );
sub[i] := ReducedList( size, sub[i] );
od;
sub := Concatenation( sub );
Info( InfoGrpCon, 3, " Iso: reduced to ",Length(sub)," groups" );
return sub;
end );
#############################################################################
##
#F CyclicExtensionByTuple( G, p, aut, n )
##
InstallGlobalFunction( CyclicExtensionByTuple,
function( G, p, aut, n )
local d, gens, base, g, x, m, i, c, shift, shifts, k, l, H, new, N;
# all shifting perms
gens := GeneratorsOfGroup( G );
d := LargestMovedPointPerms( gens );
shifts := List( [1..p], x -> MappingPermListList( [1..d],
[(x-1)*d+1..x*d] ) );
# the base
base := [];
for g in gens do
x := g;
m := g;
for i in [1..p-1] do
m := Image( aut, m );
x := x * (m^shifts[i+1]);
od;
Add( base, x );
od;
# the cyclic extension
x := n^shifts[p];
shift := [];
for i in [1..p] do
k := RemInt( i, p );
for l in [1..d] do
shift[(i-1)*d+l] := k*d+l;
od;
od;
shift := PermList( shift );
shift := x^-1 * shift;
Add( base, shift );
H := Group( base, () );
if not Size(H) = Size(G)*p then
Error("wrong up ext \n");
fi;
H := Image( SmallerDegreePermutationRepresentation( H : cheap ) );
return SmallGeneratingSet( H );
end );
#############################################################################
##
#F ConjugatingElement( G, inn )
##
BindGlobal( "ConjugatingElement", function( G, inn )
local elm, C, g, h, n, gens, imgs, i;
elm := Identity( G );
C := G;
gens := GeneratorsOfGroup( G );
imgs := List( gens, x -> Image( inn, x ) );
for i in [1..Length(gens)] do
g := gens[i];
h := imgs[i];
n := RepresentativeAction( C, g, h );
elm := elm * n;
C := Centralizer( C, g^n );
gens := List( gens, x -> x ^ n );
od;
return elm;
end );
#############################################################################
##
#F CyclicExtensions( G, p )
##
InstallGlobalFunction( CyclicExtensions,
function( G, p )
local A, I, iso, PA, PI, cl, res, a, h, e, m, C, fix, f, H, F, hom;
# compute automorphisms group and inner autos
A := AutomorphismGroupSpecial( G:nogensyssearch );
I := GroupOfInnerAutomorphismSpecial( G, A );
# compute perm reps
iso := IsomorphismPermGroup( A );
#iso := ActionHomomorphism( A, AsList(G) );
PA := Image( iso );
PI := Image( iso, I );
hom := NaturalHomomorphismByNormalSubgroup( PA, PI );
F := Image( hom );
# compute rational classes of elements with a^p in PI
cl := RationalClasses( F );
cl := List( cl, x -> Representative( x ) );
cl := Filtered( cl, x -> x^p = Identity( F ) );
cl := List( cl, x -> PreImagesRepresentative( hom, x ) );
# for each rep compute elements of G corresponding to a^p
res := [];
for a in cl do
h := PreImagesRepresentative( iso, a );
e := h^p;
m := ConjugatingElement( G, e );
C := Centre( G );
fix := Filtered( RightCoset( C, m ), x -> Image(h,x) = x );
# compute extensions
for f in fix do
H := CyclicExtensionByTuple( G, p, h, f );
Add( res, H );
od;
od;
Info( InfoGrpCon, 2, " found ",Length(res)," extensions ");
return List( res, x -> Group(x, ()) );
end );
#############################################################################
##
#F UpwardsExtensions( P, stepsize )
##
InstallGlobalFunction( UpwardsExtensions,
function( P, stepsize )
local div, grps, size, i, d, r, pr, G, p, ext, j, gens, A, n, k;
# the trivial stuff
if stepsize = 1 then return [[P]]; fi;
# start loop
div := DivisorsInt( stepsize );
grps := List( div, x -> [] );
if IsList( P ) then
size := Gcd( List( P, Size ) );
for i in [ 1 .. Length( P ) ] do
Add( grps[ Position( div, Size( P[ i ] ) / size ) ],
SmallGeneratingSet( P[ i ] ) );
od;
elif IsGroup( P ) then
grps[1] := [SmallGeneratingSet(P)];
size := Size(P);
fi;
for i in [1..Length(div)-1] do
d := div[i];
r := stepsize/d;
pr := Set( FactorsInt( r ) );
Info( InfoGrpCon, 1, "extend groups of size ", d*size,
" by primes ",pr );
n := Length( grps[i] );
# extend each group in turn
for k in [1..n] do
Info( InfoGrpCon, 1, " start group ",k," of ",n );
G := Group( grps[i][k], () );
for p in pr do
Info( InfoGrpCon, 1," start prime ",p);
ext := CyclicExtensions( G, p );
ext := List( ext, x -> GeneratorsOfGroup( x ) );
j := Position( div, d * p );
Append( grps[j], ext );
od;
od;
# reduce to isomorphism classes
Info( InfoGrpCon, 2, "Iso: reduce to isomorphism clasess \n");
grps[i+1] := IsomorphismClasses( div[i+1] * size, grps[i+1] );
od;
Info( InfoGrpCon, 1, "extensions for steps ",div );
# go back to groups
for i in [1..Length(div)] do
grps[i] := List( grps[i], x -> Group(x,()) );
od;
return grps;
end );
[ Dauer der Verarbeitung: 0.33 Sekunden
(vorverarbeitet)
]
|
