|
#############################################################################
##
#W nilpotency.gi NilMat Alla Detinko
#W Bettina Eick
#W Dane Flannery
##
##
## This file contains methods to check whether a given matrix group over
## GF(q) or Q is nilpotent. The methods for groups over Q need Polenta. The
## group needs to be finitely generated.
##
#############################################################################
##
## Some helpers
##
BindGlobal( "PLength", function(a,p)
return Length(Filtered(Factors(a), x -> x = p));
end );
BindGlobal( "PrimeFactors", function(list)
local prm;
prm := Flat(List(list, Factors));
prm := Set(prm);
return Filtered(prm, x -> x <> 1);
end );
BindGlobal( "PAndPrimePart", function( elm, q )
local o, f, a, b, g;
o := Order(elm);
f := Factors(o);
a := Product(Filtered(f, x -> x in q));
b := Product(Filtered(f, x -> not x in q));
g := Gcdex(a,b);
return [elm^(g.coeff2*b), elm^(g.coeff1*a)];
end );
BindGlobal( "IsCentralElement", function(H,a)
local h;
for h in GeneratorsOfGroup(H) do
if h*a <> a*h then return false; fi;
od;
return true;
end );
BindGlobal( "IsCentralSubgroup", function(H,U)
local h, a;
for h in GeneratorsOfGroup(H) do
for a in GeneratorsOfGroup(U) do
if h*a <> a*h then return false; fi;
od;
od;
return true;
end );
BindGlobal( "GroupsCommute", function(S,U)
local s, u, a, b;
s := GeneratorsOfGroup(S);
u := GeneratorsOfGroup(U);
for a in s do
for b in u do
if not a*b = b*a then return false; fi;
od;
od;
return true;
end );
BindGlobal( "OrbitStabGens", function(G, v)
local g, h, l, orb, trs, stb, c, i, w, j, U, s;
# set up
g := GeneratorsOfGroup(G);
h := List(g, x -> x^-1);
l := Length(g);
# set up for orbit-stab computation
orb := [v];
trs := [One(G)];
stb := [];
c := 0;
while c < Length(orb) do
c := c+1;
for i in [1..l] do
w := h[i]*orb[c]*g[i];
j := Position(orb, w);
if IsBool(j) then
Add(orb, w);
Add(trs, trs[c]*g[i]);
else
s := trs[c]*g[i]*trs[j]^-1;
if s <> One(G) then AddSet(stb, s); fi;
fi;
od;
od;
# that is it
U := GroupByGenerators(stb);
U!.index := Length(orb);
return U;
end );
BindGlobal( "MakeMatGroup", function(n, F, gens)
local s, one;
s := Filtered(gens, x -> x <> x^0);
s := Set(s);
s := List(s, x -> ImmutableMatrix(F, x));
one := IdentityMat(n, F);
return GroupByGenerators(s, one);
end );
#############################################################################
##
#F IsCompletelyReducibleNilpotentMatGroup(G)
##
InstallGlobalFunction( IsCompletelyReducibleNilpotentMatGroup, function(G)
local J, g;
J := JordanSplitting(G);
g := GeneratorsOfGroup(J[2]);
return ForAll( g, x -> x = One(G) );
end );
#############################################################################
##
#F ClassLimit(n,F) . . . . . . . . . an upper bound for the nilpotency class
##
## The function returns an upper bound for the nilpotency class of a
## nilpotent subgroup of GL(n,F). The field F needs to be finite or Q
## (otherwise the function returns fail).
##
InstallGlobalFunction( ClassLimit, function(n, F)
local p, q, t, f, m, s;
p := Characteristic(F);
# in char 0 the class limit is easy to obtain
if F = Rationals then return Int(3*n/2); fi;
# otherwise the field needs to be finite for our methods
if not IsFinite(F) then return fail; fi;
# get relevant primes
f := [];
for t in [2..n] do
if t <> p and IsPrimeInt(t) then
if ForAny([1..n], x -> IsInt((Size(F)^x - 1)/t)) then
Add( f, t );
fi;
fi;
od;
# loop over relevant primes
m := 1;
for t in f do
s := PLength(Size(F)-1,t);
m := Maximum(m, t*s - s + 1);
od;
# that's it
return n*m;
end );
#############################################################################
##
#F SecondCentralElement(G, H, l) . . . . . . . . .an element in Z_2(H) \ Z(H)
##
## The function returns an element in Z_2(H) which is not in Z(H). The
## function assumes that H is a nilpotent normal subgroup of G (it may return
## fail otherwise). The integer l is an upper bound to the nilpotency class
## of H.
##
BindGlobal( "SecondCentralElement", function(G, H, l)
local h, g, a, b, i, c;
# find initial element and check that H is non-abelian
h := GeneratorsOfGroup(H);
g := GeneratorsOfGroup(G);
a := First(h, x -> not IsCentralElement(H,x));
if IsBool(a) then return fail; fi;
# find second central element
i := 0;
c := 0;
while i < Length(g) do
i := i+1;
b := Comm(g[i],a);
if not IsCentralElement(H,b) then
a := b;
i := 0;
c := c+1;
if c > l then return fail; fi;
fi;
od;
return a;
end );
#############################################################################
##
#F NonCentralAbelian(H, a) . . non-central abelian subgroup of H containing a
##
## The function returns a non-central abelian subgroup of H containing the
## element a. The element a is the result of SecondCentralElement. The
## abelian subgroup is generated by two elements.
##
## Note: This function is not currently used.
##
BindGlobal( "NonCentralAbelian", function(H,a)
local h, b, c;
h := GeneratorsOfGroup(H);
for b in h do
c := Comm(b,a);
if c <> One(H) then
return Subgroup(H, [a,c]);
fi;
od;
return fail;
end );
#############################################################################
##
#F AbelianNormalSeries(G, l) . . . . . . a normal series with abelian factors
##
## The function returns a normal series with abelian factors of G. The group
## G has to be non-abelian and nilpotent (otherwise the function may return
## fail). The integer l is a limit to the nilpotency class of G.
##
InstallGlobalFunction( AbelianNormalSeries, function(G, l)
local n, p, C, s, c, a;
# set up
n := DimensionOfMatrixGroup(G);
p := Characteristic(G);
# initialise series
C := G;
s := [C];
# loop
c := 0;
while not IsAbelian(C) do
# increase counter -- check that c <= n-1
c := c+1;
if c > n-1 then return fail; fi;
# get relevant element
Info(InfoNilMat, 3, " - ",c,"the second central element ");
a := SecondCentralElement(G,C,l);
if IsBool(a) then return fail; fi;
C := OrbitStabGens(C, a);
Add(s, C);
Info(InfoNilMat, 3, " - centralizer has index ",C!.index);
if IsInt(C!.index/p) then return fail; fi;
od;
return s;
end );
#############################################################################
##
#A IsUnipotentMatGroup(G)
##
InstallMethod( IsUnipotentMatGroup, true, [IsMatrixGroup], 0,
function(G)
local F, n, g, V, U;
if HasIsTrivial(G) and IsTrivial(G) then return true; fi;
F := FieldOfMatrixGroup(G);
n := DimensionOfMatrixGroup(G);
g := List(GeneratorsOfGroup(G), x -> x - x^0);
U := IdentityMat(n, F);
repeat
V := U;
U := BaseMat(Concatenation(List(g, x -> V*x)));
until Length(V) = Length(U) or Length(U) = 0;
return (Length(U) = 0);
end );
#############################################################################
##
#A JordanSplitting(G) . . . . . . . . . . . . . . . the Jordan decomposition
##
## The function returns the Jordan decomposition of G as a list of two groups
## [S,U]. If G is nilpotent, then G = S x U, the group U is unipotent and S is
## semisimple.
##
InstallMethod( JordanSplitting, true, [IsMatrixGroup], 0,
function(G)
local g, F, n, d, S, U;
# set up
g := GeneratorsOfGroup(G);
F := FieldOfMatrixGroup(G);
n := DimensionOfMatrixGroup(G);
# split every generator
d := List(g, JordanDecomposition);
# create new groups
S := MakeMatGroup( n, F, ShallowCopy(List(d, x -> x[1])) );
U := MakeMatGroup( n, F, List(d, x -> (x[2] * x[1]^-1) + One(G)) );
return [S, U];
end );
#############################################################################
##
#A PiPrimarySplitting(G) . . . . . . . . . . . . . .the pi-primary splitting
##
## Let pi be the set of primes in the range [1..dim(G)].
## This function returns a list [B,C] of subgroups of G with G = BC.
##
## If G is nilpotent, then G = B x C,
## C is the product of all Sylow p-subgroups with p > n, and
## B is the product of all remaining Sylow subgroups.
## Further, if G is nilpotent, then C is central in G.
##
## The group G needs to be a matrix group over a finite field.
##
InstallMethod( PiPrimarySplitting, true, [IsMatrixGroup], 0,
function(G)
local F, n, q, s, B, C;
# set up
F := FieldOfMatrixGroup(G);
n := DimensionOfMatrixGroup(G);
q := Filtered([1..n], IsPrimeInt);
# check
if not IsFinite(F) then TryNextMethod(); fi;
# split every generator
s := List(GeneratorsOfGroup(G), x -> PAndPrimePart(x,q));
# generate groups
B := MakeMatGroup(n, F, List(s, x -> x[1]));
C := MakeMatGroup(n, F, List(s, x -> x[2]));
return [B,C];
end );
#############################################################################
##
#F SylowSubgroupOfNilpotentMatGroupFF(G, g, p)
##
## The function returns a Sylow p-subgroup of G where G is a nilpotent matrix
## group over GF(q). The list g has to be a polycyclic sequence for G.
##
BindGlobal( "SylowSubgroupOfNilpotentMatGroupFF", function(G, g, p)
local F, n, s, U;
F := FieldOfMatrixGroup(G);
n := DimensionOfMatrixGroup(G);
s := List(g, x -> PAndPrimePart(x,[p])[1]);
U := MakeMatGroup( n, F, s );
SetIsPGroup(U, true);
SetPrimePGroup(U, p);
return U;
end );
#############################################################################
##
#F PcGensBySeries(G, s)
##
## The function returns a polycyclic sequence for G using the abelian normal
## series s of G.
##
BindGlobal( "PcGensBySeries", function(G, s)
local b, i;
b := ShallowCopy(GeneratorsOfGroup(s[Length(s)]));
for i in Reversed([1..Length(s)-1]) do
Append(b, Filtered(GeneratorsOfGroup(s[i]), x -> not (x in b)));
od;
return b;
end );
#############################################################################
##
#F IsNilpotentMatGroupFF(G, l) . . . . . . . . . . . . .check nilpotency of G
##
## The function returns true if G is nilpotent and false otherwise. The
## group G is a subgroup of GL(n,F), where F is a finite field, and the
## integer l is an upper bound to the nilpotency class of G.
##
BindGlobal( "IsNilpotentMatGroupFF", function(G, l)
local p, n, J, S, U, P, B, C, s, o, r, b, syl, q, W, V;
Info( InfoNilMat, 1, "start testing nilpotency ");
p := Characteristic(G);
n := DimensionOfMatrixGroup(G);
# catch a trivial case
if Length(GeneratorsOfGroup(G)) = 1 then return true; fi;
# compute Jordan splitting
Info( InfoNilMat, 1, "determine Jordan decomposition G <= <S,U>");
J := JordanSplitting(G);
S := J[1];
U := J[2];
Info( InfoNilMat, 1, "checking Jordan decomposition ");
Info( InfoNilMat, 2, " - checking [S,U] = 1 ");
if not GroupsCommute(S,U) then return false; fi;
Info( InfoNilMat, 2, " - checking that U is unipotent ");
if not IsUnipotentMatGroup(U) then return false; fi;
# it remains to consider S
Info( InfoNilMat, 1, "determine pi-primary decomposition S = <B,C>");
P := PiPrimarySplitting(S);
B := P[1];
C := P[2];
Info( InfoNilMat, 1, "checking pi-primary decomposition ");
Info( InfoNilMat, 2, " - check that pi-part C is central ");
if not IsCentralSubgroup(S, C) then return false; fi;
Info( InfoNilMat, 2, " - check wether pi'-part B is abelian ");
if IsAbelian(B) then return true; fi;
# compute series through B
Info( InfoNilMat, 1, "compute abelian normal series of B with limit ",l);
s := AbelianNormalSeries(B, l);
if IsBool(s) then return false; fi;
Info( InfoNilMat, 2, " - found series of length ",Length(s));
# check the prime factors of |B|
o := PrimeFactors(List(s{[2..Length(s)]}, x -> x!.index));
r := PrimeFactors(List(GeneratorsOfGroup(s[Length(s)]), Order));
o := Union(o,r);
Info( InfoNilMat, 1, "B has prime factors ",o);
if ForAny(r, x -> IsInt(x/p)) then return false; fi;
if ForAny(o, x -> x > n) then return false; fi;
# pick up polycyclic generators for B (perhaps more)
b := PcGensBySeries(B, s);
Info( InfoNilMat, 1, "B has ",Length(b)," pc gens ");
# now we leave the Detinko-Flannery paper and do a simple final check
# if B is nilpotent, then we construct its Sylow subgroups
# and note that they commute
# if B is not nilpotent, then we construct supergroups of the
# Sylow subgroups and they will not commute
syl := [];
for q in o do
Info( InfoNilMat, 1, "determine Sylow ",q,"-subgroup of B");
W := SylowSubgroupOfNilpotentMatGroupFF(B, b, q);
for V in syl do
if not GroupsCommute(W,V) then return false; fi;
od;
Add( syl, W);
od;
SetSylowSystem(B, syl);
return true;
end );
#############################################################################
##
## IsNilpotentMatGroupRN( G ) . . . . . .nilpotency testing for groups over Q
##
## The function returns true if G is nilpotent and false otherwise. The
## group G is a subgroup of GL(n,Q) and the integer l is an upper bound to
## the nilpotency class of G.
##
BindGlobal( "IsNilpotentMatGroupRN", function(G, l)
local n, g, d, S, U, s, p, t, pcgs, kern, K;
n := DimensionOfMatrixGroup(G);
g := GeneratorsOfGroup(G);
if Length(g) = 1 then return true; fi;
# first split by Jordan Decomposition
d := List(g, JordanDecomposition);
S := GroupByGenerators(List(d, x -> x[1]));
U := GroupByGenerators(List(d, x -> x[2]*x[1]^-1 + One(G)));
# check [S,U] = 1 and IsUnipotent(U)
if not GroupsCommute(S,U) then return false; fi;
if not IsUnipotentMatGroup(U) then return false; fi;
if IsAbelian(S) then return true; fi;
# consider S using Polenta
s := GeneratorsOfGroup(S);
p := DetermineAdmissiblePrime(s);
# check image of congruence hom
t := InducedByField(s, GF(p));
if not IsNilpotentMatGroupFF(GroupByGenerators(t),l) then
return false;
fi;
# get kernel of congruence hom
pcgs := CPCS_finite_word( t, n+2 );
kern := POL_NormalSubgroupGeneratorsOfK_p( pcgs, s );
kern := Filtered(kern, x -> not x = One(G));
if Length(kern) = 0 then return true; fi;
# check that the kernel is central
K := GroupByGenerators(kern);
if not IsCentralSubgroup(S, K) then return false; fi;
# that's it
return true;
end );
#############################################################################
##
#F IsNilpotentMatGroup( G ) . . . . nilpotency testing a la Flannery-Detinko
##
InstallGlobalFunction( IsNilpotentMatGroup, function(G)
local F, p, l, n;
F := FieldOfMatrixGroup(G);
n := DimensionOfMatrixGroup(G);
# get class limit
l := ClassLimit(n, F);
# choose case
if IsFinite(F) then
return IsNilpotentMatGroupFF(G, l);
fi;
if F = Rationals then
return IsNilpotentMatGroupRN(G, l);
fi;
# otherwise there is no method
return fail;
end );
##
## need to install this method with high value, as otherwise for the
## finite field case GAP determines a permutation group and tests
## nilpotency of that.
##
InstallMethod( IsNilpotentGroup, [IsFFEMatrixGroup], NICE_FLAGS, IsNilpotentMatGroup );
InstallMethod( IsNilpotentGroup, [IsCyclotomicMatrixGroup], NICE_FLAGS,
function(G)
if IsRationalMatrixGroup(G) then
return IsNilpotentMatGroup(G);
fi;
TryNextMethod();
end );
[ Dauer der Verarbeitung: 0.31 Sekunden
(vorverarbeitet)
]
|
