Quelle util.gi
Sprache: unbekannt
|
|
#############################################################################
##
## util.gi CRISP Burkhard Höfling
##
## Copyright © 2000-2003, 2005, 2015 Burkhard Höfling
##
#############################################################################
##
#M CentralizesLayer(<list>, <mpcgs>)
##
InstallMethod(CentralizesLayer, "generic method", IsIdenticalObj,
[IsListOrCollection, IsModuloPcgs], 0,
function(l, mpcgs)
local len, i, x, exp, j;
len := Length(mpcgs);
for i in [1..len] do
for x in l do
exp := ExponentsConjugateLayer(mpcgs, mpcgs[i], x);
if exp[i] <> 1 then
return false;
fi;
for j in [1..len] do
if exp[j] <> 0 and i <> j then
return false;
fi;
od;
od;
od;
return true;
end);
InstallMethod(CentralizesLayer, "for empty list", true,
[IsListOrCollection and IsEmpty, IsModuloPcgs], 0,
ReturnTrue);
#############################################################################
##
#M PrimePowerGensPcSequence(<grp>)
##
InstallMethod(PrimePowerGensPcSequence,
"for group which can easily compute a pcgs", true,
[IsGroup and CanEasilyComputePcgs], 0,
function(G)
local pcgs, primes, gens, x, o, qr, r, p, f, pos, len;
primes := [];
gens := [];
len := 0;
pcgs := Pcgs(G);
for x in pcgs do
o := Order(x);
p := RelativeOrderOfPcElement(pcgs, x);
# we are looking for the p-part of x
qr := [o, 0];
repeat
r := qr[1];
qr := QuotientRemainder(Integers, r, p);
until qr[2] <> 0;
pos := PositionSorted(primes, p);
if pos <= Length(primes) and primes[pos] = p then
Add(gens[pos], x^r);
else #insert a new prime
Add(primes, p, pos);
Add(gens, [x^r], pos);
len := len + 1;
fi;
od;
return rec(primes := primes, generators := gens, pcgs := pcgs);
end);
#############################################################################
##
#M PrimePowerGensPcSequence(<grp>)
##
InstallMethod(PrimePowerGensPcSequence, "for group with special pcgs", true,
[IsGroup and HasSpecialPcgs], 0,
function(G)
local pcgs, primes, gens, x, o, qr, r, p, f, pos, len;
primes := [];
gens := [];
len := 0;
pcgs := SpecialPcgs(G);
# elements already have prime power order
for x in pcgs do
p := RelativeOrderOfPcElement(pcgs, x);
pos := PositionSorted(primes, p);
if pos <= Length(primes) and primes[pos] = p then
Add(gens[pos], x);
else #insert a new prime
Add(primes, p, pos);
Add(gens, [x], pos);
len := len + 1;
fi;
od;
return rec(primes := primes, generators := gens, pcgs := pcgs);
end);
############################################################################
##
#M IsNilpotentGroup
##
InstallMethod(IsNilpotentGroup, "for pcgs computable group", true,
[IsGroup and IsFinite and CanEasilyComputePcgs], 0,
function(G)
local pseq, i, j;
if HasSpecialPcgs(G) then
TryNextMethod();
fi;
pseq := PrimePowerGensPcSequence(G);
for i in [1..Length(pseq.generators)] do
for j in [i+1..Length(pseq.generators)] do
if ForAny(pseq.generators[i], x ->
ForAny(pseq.generators[j], y -> x^y <> x)) then
return false;
fi;
od;
od;
return true;
end);
############################################################################
##
#M NormalGeneratorsOfNilpotentResidual
##
InstallMethod(NormalGeneratorsOfNilpotentResidual, "for pcgs computable group",
true,
[IsGroup and IsFinite and CanEasilyComputePcgs],
0,
function(G)
local pgens, gens, i, j, x, y, c, id;
id := One(G);
gens := [];
pgens := PrimePowerGensPcSequence(G);
for i in [1..Length(pgens.generators)] do
for j in [i+1..Length(pgens.generators)] do
for x in pgens.generators[i] do
for y in pgens.generators[j] do
c := Comm(x, y);
if c <> id then
Add(gens, c);
fi;
od;
od;
od;
od;
return gens;
end);
############################################################################
##
#M NormalGeneratorsOfNilpotentResidual
##
InstallMethod(NormalGeneratorsOfNilpotentResidual,
"generic method - use lower central series",
true,
[IsGroup],
0,
function(G)
local lcs;
lcs := LowerCentralSeries(G);
return GeneratorsOfGroup(lcs[Length(lcs)]);
end);
###################################################################################
##
#F CompositionSeriesElAbFactorUnderAction(<act>, <M>, <N>)
##
## computes a <act>-composition series of the elementary abelian normal section M/N,
## i.e. a list M = N_0 > N_1 > ... > N_r = N of subgroups of <grp> such that
## there is no <grp>-invariant subgroup between N_i and N_{i+1}.
##
InstallGlobalFunction("CompositionSeriesElAbFactorUnderAction",
function(act, M, N)
local m;
m := Pcgs(M) mod InducedPcgs(Pcgs(M), N);
return List(PcgsCompositionSeriesElAbModuloPcgsUnderAction(act, m),
s -> SubgroupByPcgs(M, s));
end);
###################################################################################
##
#F PcgsCompositionSeriesElAbModuloPcgsUnderAction(<act>, <sec>)
##
## computes a series of pcgs representing a <act>-composition series of the elementary
## abelian normal section M/N, represented by the modulo pcgs <sec>.
## i.e. a list M = N_0 > N_1 > ... > N_r = N of subgroups of N such that
## there is no <grp>-invariant subgroup between N_i and N_{i+1}.
##
InstallGlobalFunction("PcgsCompositionSeriesElAbModuloPcgsUnderAction",
function(act, pcgs)
local ppcgs, bas, bases, mats, p, one, new, ser, b, v, gens, num,
y, len, depth, ddepth, pos, dp, t0, t;
num := NumeratorOfModuloPcgs(pcgs);
if Length(pcgs) = 0 then
return [num];
elif Length(pcgs) = 1 then
return [num, DenominatorOfModuloPcgs(pcgs)];
fi;
ppcgs := ParentPcgs(num);
p := RelativeOrderOfPcElement(pcgs, pcgs[1]);
if IsGroup(act) then
act := GeneratorsOfGroup(act);
fi;
if Length(act) = 0 then
bases := IdentityMat(Length(pcgs), GF(p));
bas := List([1..Length(bases)], i -> bases{[i..Length(bases)]});
Add(bas, []);
else
one := One(GF(p));
mats := List(act, a ->
List(pcgs, x -> ExponentsOfPcElement(pcgs, x^a)*one));
bas := [];
t0 := Runtime();
bases := MTX.BasesCompositionSeries(GModuleByMats(mats, GF(p)));
t := Runtime() - t0;
for b in bases do
new := MutableCopyMat(b);
TriangulizeMat(new);
Add(bas, new);
od;
fi;
Sort(bas, function(a, b) return Length(a) > Length(b); end);
ser := [];
ddepth := List(DenominatorOfModuloPcgs(pcgs),
y -> DepthOfPcElement(ppcgs, y));
for b in bas do
gens := List(DenominatorOfModuloPcgs(pcgs));
len := Length(gens);
depth := ShallowCopy(ddepth);
for v in Reversed(b) do
y := PcElementByExponentsNC(pcgs, v);
dp := DepthOfPcElement(ppcgs, y);
pos := PositionSorted(depth, dp);
while pos <= len and dp = depth[pos] do
y := ReducedPcElement(ppcgs, y, gens[pos]);
dp := DepthOfPcElement(ppcgs, y);
pos := PositionSorted(depth, dp);
od;
Add(gens, y, pos);
Add(depth, dp, pos);
len := len + 1;
od;
Add(ser, InducedPcgsByPcSequenceNC(ppcgs, gens));
od;
return ser;
end);
###################################################################################
##
#M ChiefSeries(<grp>)
##
InstallMethod(ChiefSeries,
"for pcgs computable group refining PcgsElementaryAbelianSeries",
true, [IsGroup and CanEasilyComputePcgs], 1,
function(G)
local gens, pcgs, inds, elabser, i, ser;
pcgs := PcgsElementaryAbelianSeries(G);
inds := IndicesEANormalSteps(pcgs);
elabser := List(inds,
i -> InducedPcgsByPcSequence(pcgs, pcgs{[i..Length(pcgs)]}));
ser := [];
for i in [1..Length(elabser)-1] do
Append(ser,
PcgsCompositionSeriesElAbModuloPcgsUnderAction(
pcgs{[1..inds[i]-1]}, elabser[i] mod elabser[i+1]));
Unbind(ser[Length(ser)]);
od;
ser := List(ser, p -> SubgroupByPcgs(G, p));
Add(ser, TrivialSubgroup(G));
return ser;
end);
###################################################################################
##
#M CompositionSeriesUnderAction(<act>, <grp>)
##
InstallMethod(CompositionSeriesUnderAction, "for soluble group",
true,
[IsListOrCollection, IsGroup and IsSolvableGroup], 0,
function(act, G)
local gens, pcgs, inds, elabser, i, ser;
if IsGroup(act) then
act := ShallowCopy(GeneratorsOfGroup(act));
fi;
for i in [1..Length(act)] do
if FamilyObj(act[i]) = FamilyObj(One(G)) then
act[i] := ConjugatorAutomorphism(G, act[i]);
fi;
od;
pcgs := PcgsElementaryAbelianSeries(G);
if pcgs = fail then
TryNextMethod();
fi;
# InvariantElementaryAbelianSeries with four arguments seems to be buggy
# elabser := List(InvariantElementaryAbelianSeries(G, act, TrivialSubgroup(G), true),
# S -> InducedPcgs(pcgs, S));
elabser := List(InvariantElementaryAbelianSeries(G, act),
S -> InducedPcgs(pcgs, S));
ser := [];
for i in [1..Length(elabser)-1] do
Append(ser,
PcgsCompositionSeriesElAbModuloPcgsUnderAction(
act, elabser[i] mod elabser[i+1]));
Unbind(ser[Length(ser)]);
od;
ser := List(ser, p -> SubgroupByPcgs(G, p));
Add(ser, TrivialSubgroup(G));
return ser;
end);
###################################################################################
##
#M CompositionSeriesUnderAction(<act>, <grp>)
##
CRISP_RedispatchOnCondition(CompositionSeriesUnderAction,
"redispatch if group is finite or soluble",
true,
[IsListOrCollection, IsGroup],
[, IsFinite and IsSolvableGroup], # no conditions on first argument
0);
###################################################################################
##
#F PcgsElementaryAbelianSeriesFromPrimeOrdersPcgs
##
InstallGlobalFunction("PcgsElementaryAbelianSeriesFromPrimeOrdersPcgs",
function(pcgs)
local ro, p, new, i, nsteps, j, k, n, d,
npcgs, dpcgs, der, depths, x, m;
if IsPcgsElementaryAbelianSeries(pcgs) then
return pcgs;
fi;
ro := RelativeOrders( pcgs );
i := 1;
nsteps := [1];
while i <= Length(pcgs) do
p := ro[i];
n := DepthOfPcElement(pcgs, pcgs[i]^p);
j := i + 1;
while j < n do
if ro[j] = p then
d := DepthOfPcElement(pcgs, pcgs[j]^p);
if d < n then
n := d;
fi;
d := Minimum(List([i..j-1], k ->
DepthOfPcElement(pcgs, Comm(pcgs[j], pcgs[k]))));
if d < n then
n := d;
fi;
j := j + 1;
else
n := j;
fi;
od;
# now find smallest normal subgroup of the series containing
# the previously computed group
j := 1;
while i < n and j < n do
k := n;
while i < n and k <= Length(pcgs) do
d := DepthOfPcElement(pcgs, Comm(pcgs[k], pcgs[j]));
if d < n then
n := d;
fi;
k := k + 1;
od;
j := j + 1;
od;
if n < i then
Error("internal error: PcgsElementaryAbelianSeriesFromPrimeOrdersPcgs, wrong depth");
elif n = i then # no abelian normal section found - change pcgs
Info(InfoPcGroup, 2, "changing pcgs");
npcgs := InducedPcgsByPcSequenceNC(pcgs, pcgs{[i..Length(pcgs)]});
der := DerivedSubgroup(GroupOfPcgs(npcgs));
dpcgs := InducedPcgs(pcgs, der);
m := npcgs mod dpcgs;
dpcgs := List(dpcgs);
depths := List(dpcgs, x -> DepthOfPcElement(pcgs, x));
for x in Reversed(m) do
# elements may already be contained in the subgroup, so don't check return values'
AddPcElementToPcSequence(pcgs, dpcgs, depths, x^p);
od;
dpcgs := CanonicalPcgs(
InducedPcgsByPcSequenceNC(pcgs, dpcgs));
m := npcgs mod dpcgs;
pcgs := PcgsByPcSequenceNC(FamilyObj(pcgs[1]),
Concatenation(pcgs{[1..i-1]}, m, dpcgs));
ro := Concatenation(ro{[1..i-1]}, RelativeOrders(m), RelativeOrders(dpcgs));
SetRelativeOrders(pcgs, ro );
Info(InfoPcGroup, 2, "changing pcgs from ",i," ",pcgs);
n := n + Length(m);
else
Info(InfoPcGroup, 2, "normal step found at ",n);
fi;
Add(nsteps, n);
i := n;
od;
SetIsPcgsElementaryAbelianSeries(pcgs, true);
SetIndicesEANormalSteps(pcgs, nsteps);
return pcgs;
end);
###################################################################################
##
#M PcgsElementaryAbelianSeries
##
InstallMethod(PcgsElementaryAbelianSeries, "CRISP method for pc group",
true,
[IsPcGroup and IsFinite],
1, # this makes the priority higher than the(slow) library method which uses SpecialPcgs
function(G)
local pcgs;
pcgs := Pcgs(G);
if not IsPrimeOrdersPcgs(pcgs) then
TryNextMethod();
fi;
return PcgsElementaryAbelianSeriesFromPrimeOrdersPcgs(pcgs);
end);
###################################################################################
##
#M PcgsElementaryAbelianSeries
##
InstallMethod(PcgsElementaryAbelianSeries, "for pc group with parent group", true,
[IsPcGroup and IsFinite and HasParent],
1, # this makes the priority higher than the(slow) library method which uses SpecialPcgs
function(G)
local P, pcgs, ppcgs, depths, pinds, inds, i, j;
P := Parent(G);
if HasPcgsElementaryAbelianSeries(P) then
ppcgs := PcgsElementaryAbelianSeries(P);
pcgs := CanonicalPcgs(InducedPcgs(ppcgs, G));
# now find an elementary abelian series
depths := List(pcgs, x -> DepthOfPcElement(ppcgs, x));
pinds := IndicesEANormalSteps(ppcgs);
inds := [];
i := 1;
for j in [1..Length(depths)] do
if depths[j] >= pinds[i] then
Add(inds, j);
repeat
i := i + 1;
until depths[j] < pinds[i];
fi;
od;
Add(inds, Length(pcgs)+1);
SetIsPcgsElementaryAbelianSeries(pcgs, true);
SetIndicesEANormalSteps(pcgs, inds);
return pcgs;
else
TryNextMethod();
fi;
end);
###################################################################################
##
#M PcgsElementaryAbelianSeries
##
InstallMethod(PcgsElementaryAbelianSeries, "finite group", true,
[IsGroup and IsFinite], 0,
function(G)
if not IsSolvableGroup(G) then
Error("The group <G> must be soluble");
elif IsPrimeOrdersPcgs(Pcgs(G)) then
return PcgsElementaryAbelianSeriesFromPrimeOrdersPcgs(Pcgs(G));
else
TryNextMethod();
fi;
end);
###################################################################################
##
#M PcgsElementaryAbelianSeries
##
InstallMethod(PcgsElementaryAbelianSeries, "for group with parent group", true,
[IsGroup and HasParent], 0,
function(G)
local P, pcgs, ppcgs, pinds, depths, inds, i, j;
P := Parent(G);
if HasPcgsElementaryAbelianSeries(P) then
ppcgs := PcgsElementaryAbelianSeries(P);
pcgs := CanonicalPcgs(InducedPcgs(ppcgs, G));
depths := List(pcgs, x -> DepthOfPcElement(ppcgs, x));
pinds := IndicesEANormalSteps(ppcgs);
inds := [];
i := 1;
for j in [1..Length(depths)] do
if depths[j] >= pinds[i] then
Add(inds, j);
repeat
i := i + 1;
until depths[j] < pinds[i];
fi;
od;
Add(inds, Length(pcgs)+1);
SetIsPcgsElementaryAbelianSeries(pcgs, true);
SetIndicesEANormalSteps(pcgs, inds);
return pcgs;
else
TryNextMethod();
fi;
end);
#############################################################################
##
#M SiftedPcElementWrtPcSequence(<pcgs>, <seq>, <depths>, <x>)
##
## sifts an element x through a list seq of elements resembling a Pcgs,
## reducing x if it has the same depth as an element in seq
##
InstallMethod(SiftedPcElementWrtPcSequence, "generic method",
function(fpcgs, fseq, fdepths, fx) return IsIdenticalObj(fpcgs, fseq) and
IsIdenticalObj(fseq, CollectionsFamily(fx));
end,
[IsPcgs, IsListOrCollection, IsList, IsMultiplicativeElementWithInverse], 0,
function(pcgs, seq, depths, x)
local d, pos;
d := DepthOfPcElement(pcgs, x);
pos := PositionSorted(depths, d);
while pos <= Length(depths) and depths[pos] = d do
x := ReducedPcElement(pcgs, x, seq[pos]);
d := DepthOfPcElement(pcgs, x);
pos := PositionSorted(depths, d);
od;
return x;
end);
#############################################################################
##
#M SiftedPcElementWrtPcSequence(<pcgs>, <seq>, <depths>, <x>)
##
InstallMethod(SiftedPcElementWrtPcSequence, "method for an empty collection",
function(a,b,c, d) return
IsIdenticalObj(a, CollectionsFamily(d));
end,
[IsPcgs, IsListOrCollection and IsEmpty, IsList, IsMultiplicativeElementWithInverse],
0,
function(pcgs, seq, depths, x)
return x;
end);
#############################################################################
##
#M AddPcElementToPcSequence(<pcgs>, <seq>, <depths>, <x>)
##
InstallMethod(AddPcElementToPcSequence, "generic method",
function(fpcgs, fseq, fdepths, fx) return IsIdenticalObj(fpcgs, fseq) and
IsIdenticalObj(fseq, CollectionsFamily(fx));
end,
[IsPcgs, IsListOrCollection, IsList, IsMultiplicativeElementWithInverse], 0,
function(pcgs, seq, depths, x)
local d, pos, len;
d := DepthOfPcElement(pcgs, x);
pos := PositionSorted(depths, d);
len := Length(depths);
while pos <= len and depths[pos] = d do
x := ReducedPcElement(pcgs, x, seq[pos]);
d := DepthOfPcElement(pcgs, x);
pos := PositionSorted(depths, d);
od;
if d > Length(pcgs) then
return false;
fi;
Add(seq, x, pos);
Add(depths, d, pos);
return true;
end);
#############################################################################
##
#M AddPcElementToPcSequence(<pcgs>, <seq>, <depths>, <x>)
##
InstallMethod(AddPcElementToPcSequence, "method for an empty collection",
function(a,b,d, c) return
IsIdenticalObj(a, CollectionsFamily(c));
end,
[IsPcgs, IsListOrCollection and IsEmpty, IsList and IsEmpty, IsMultiplicativeElementWithInverse],
0,
function(pcgs, seq, depths, x)
local d;
d := DepthOfPcElement(pcgs, x);
if d > Length(pcgs) then
return false;
fi;
depths[1] := d;
seq[1] := x;
return true;
end);
#############################################################################
##
#M CRISP_SmallGeneratingSet(<G>)
##
InstallMethod(CRISP_SmallGeneratingSet, "subset of pcgs",
[IsGroup and CanEasilyComputePcgs],
function(G)
local H, gens, g;
H := TrivialSubgroup(G);
gens := [];
for g in Pcgs(G) do
if not g in H then
Add(gens, g);
H := ClosureGroup(H,g);
if Size(H)=Size(G) then
return gens;
elif Length(gens)>Length(GeneratorsOfGroup(G)) then
TryNextMethod();
fi;
fi;
od;
Error("G is not generated by pcgs");
end);
#############################################################################
##
#M CRISP_SmallGeneratingSet(<G>)
##
InstallMethod(CRISP_SmallGeneratingSet, "use generators",
[IsGroup], GeneratorsOfGroup);
#############################################################################
##
#M CRISP_SmallGeneratingSet(<G>)
##
InstallMethod(CRISP_SmallGeneratingSet, "use SmallGeneratingSet",
[IsGroup and HasSmallGeneratingSet], SUM_FLAGS, SmallGeneratingSet);
############################################################################
##
#E
##
[ zur Elbe Produktseite wechseln0.31Quellennavigators
Analyse erneut starten
]
|
2026-04-02
|
