|
#############################################################################
##
## This file is part of GAP, a system for computational discrete algebra.
## This file's authors include Frank Celler.
##
## 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 the methods for polycyclic generating systems of pc
## groups.
##
#############################################################################
##
#R IsUnsortedPcgsRep
##
DeclareRepresentation( "IsUnsortedPcgsRep", IsPcgsDefaultRep, [] );
#############################################################################
##
#R IsSortedPcgsRep
##
## the pc sequence is in different depth in the same order as the sorting
## pcgs (so in particular depths are the same).
DeclareRepresentation( "IsSortedPcgsRep", IsUnsortedPcgsRep, [] );
#############################################################################
##
#M PcgsByPcSequenceNC( <fam>, <pcs> )
##
#############################################################################
InstallMethod( PcgsByPcSequenceNC,
"elements family by rws with defining pcgs",
true,
[ IsElementsFamilyByRws and HasDefiningPcgs,
IsHomogeneousList ],
0,
function( efam, pcs )
local rws, pfa, pcgs, pag, id, g, dg, i, new,
ord,codepths,pagpow,sorco;
# quick check
if not IsIdenticalObj( efam, ElementsFamily(FamilyObj(pcs)) ) then
Error( "elements family of <pcs> does not match <efam>" );
fi;
# check if it is the defining sequence
rws := efam!.rewritingSystem;
pfa := DefiningPcgs(efam);
if List( pcs, UnderlyingElement ) = GeneratorsOfRws(rws) then
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs and IsFamilyPcgs,
efam,
pcs,[]);
SetRelativeOrders(pcgs,RelativeOrders(rws));
#T We should not use `InducedPcgs' because `PcgsByPcSequence' is guaranteed
#T to return a new, noninduced pcgs each time! AH
# otherwise check if we can used an induced system
# elif IsSSortedList( List( pcs, x -> DepthOfPcElement(pfa,x) ) ) then
# pcgs := InducedPcgsByPcSequenceNC( pfa, pcs );
# make an unsorted pcgs
else
# sort the elements according to the depth wrt pfa
pag := [];
new := [];
ord := [];
id := One(pcs[1]);
for i in [ Length(pcs), Length(pcs)-1 .. 1 ] do
g := pcs[i];
dg := DepthOfPcElement( pfa, g );
while g <> id and IsBound(pag[dg]) do
g := ReducedPcElement( pfa, g, pag[dg] );
dg := DepthOfPcElement( pfa, g );
od;
if g <> id then
pag[dg] := g;
new[dg] := i;
ord[i] := RelativeOrderOfPcElement( pfa, g );
fi;
od;
if not IsHomogeneousList(ord) then
Error("not all relative orders given");
fi;
if IsSSortedList(new) and Length(new)=Length(pfa) then
# we have the same sequence, same depths, just changed by
# multiplying elements of a lower level
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs and IsSortedPcgsRep,
efam,
pcs,[] );
else
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs and IsUnsortedPcgsRep,
efam,
pcs,[] );
fi;
pcgs!.sortedPcSequence := pag;
pcgs!.newDepths := new;
pcgs!.sortingPcgs := pfa;
# Precompute the leading coeffs and the powers of pag up to the
# relative order
pagpow:=[];
sorco:=[];
for i in [1..Length(pag)] do
if IsBound(pag[i]) then
pagpow[i]:=
List([1..RelativeOrderOfPcElement(pfa,pag[i])-1],j->pag[i]^j);
sorco[i]:=LeadingExponentOfPcElement(pfa,pag[i]);
fi;
od;
pcgs!.sortedPcSeqPowers:=pagpow;
pcgs!.sortedPcSequenceLeadCoeff:=sorco;
# codepths[i]: the minimum pcgs-depth that can be implied by pag-depth i
codepths:=[];
for dg in [1..Length(new)] do
g:=Length(new)+1;
for i in [dg..Length(new)] do
if IsBound(new[i]) and new[i]<g then
g:=new[i];
fi;
od;
codepths[dg]:=g;
od;
pcgs!.minimumCodepths:=codepths;
SetRelativeOrders( pcgs, ord );
if IsSortedPcgsRep(pcgs) then
pcgs!.inversePowers:=
List([1..Length(pfa)],i->(1/sorco[i]) mod ord[i]);
fi;
fi;
# that it
return pcgs;
end );
#############################################################################
InstallMethod( PcgsByPcSequenceNC,
"elements family by rws",
true,
[ IsElementsFamilyByRws,
IsHomogeneousList ],
0,
function( efam, pcs )
local pcgs, rws;
# quick check
if not IsIdenticalObj( efam, ElementsFamily(FamilyObj(pcs)) ) then
Error( "elements family of <pcs> does not match <efam>" );
fi;
# check if it is the defining sequence
rws := efam!.rewritingSystem;
if List( pcs, UnderlyingElement ) = GeneratorsOfRws(rws) then
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs and IsFamilyPcgs,
efam,
pcs,[]);
SetRelativeOrders(pcgs,RelativeOrders(rws));
# make an ordinary pcgs
else
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs,
efam,
pcs,[] );
fi;
# that it
return pcgs;
end );
#############################################################################
InstallMethod( PcgsByPcSequenceNC,
"elements family by rws, empty sequence",
true,
[ IsElementsFamilyByRws,
IsList and IsEmpty ],
0,
function( efam, pcs )
local pcgs, rws;
# construct a pcgs
pcgs := PcgsByPcSequenceCons(
IsPcgsDefaultRep,
IsPcgs,
efam,
pcs,[] );
# check if it is the defining sequence
rws := efam!.rewritingSystem;
if 0 = NumberGeneratorsOfRws(rws) then
SetIsFamilyPcgs( pcgs, true );
SetRelativeOrders( pcgs, [] );
fi;
# that it
return pcgs;
end );
#############################################################################
##
#M PcgsByPcSequence( <fam>, <pcs> )
##
#############################################################################
InstallMethod( PcgsByPcSequence,
true,
[ IsElementsFamilyByRws,
IsHomogeneousList ],
0,
function( efam, pcs )
#T 96/09/26 fceller do some checks
return PcgsByPcSequenceNC( efam, pcs );
end );
#############################################################################
InstallMethod( PcgsByPcSequence,
true,
[ IsElementsFamilyByRws,
IsList and IsEmpty ],
0,
function( efam, pcs )
#T 96/09/26 fceller do some checks
return PcgsByPcSequenceNC( efam, pcs );
end );
#############################################################################
##
#M SiftedPcElement( <fam-pcgs>, <elm> )
##
InstallMethod( SiftedPcElement, "family pcgs", IsCollsElms,
[ IsPcgs and IsFamilyPcgs, IsMultiplicativeElementWithInverse ], 0,
function(p,x)
return OneOfPcgs(p);
end);
#############################################################################
##
#M DepthOfPcElement( <fam-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement,
"family pcgs",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws ],
0,
function( pcgs, elm )
local rep;
rep := ExtRepOfObj( UnderlyingElement(elm) );
if 0 = Length(rep) then
return Length(pcgs)+1;
else
return rep[1];
fi;
end );
#############################################################################
##
#M ExponentsOfPcElement( <fam-pcgs>, <elm> )
##
InstallMethod( ExponentsOfPcElement,
"family pcgs",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws ],
0,
function( pcgs, elm )
local exp, rep, i;
exp := ListWithIdenticalEntries( Length( pcgs ), 0 );
rep := ExtRepOfObj( UnderlyingElement(elm) );
for i in [ 1, 3 .. Length(rep)-1 ] do
exp[rep[i]] := rep[i+1];
od;
return exp;
end );
#############################################################################
##
#M LeadingExponentOfPcElement( <fam-pcgs>, <elm> )
##
InstallMethod( LeadingExponentOfPcElement,
"family pcgs",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws ],
0,
function( pcgs, elm )
local rep;
rep := ExtRepOfObj( UnderlyingElement(elm) );
if 0 = Length(rep) then
return fail;
else
return rep[2];
fi;
end );
# methods for `PcElementByExponent' that use the family pcgs directly
#############################################################################
##
#M PcElementByExponentsNC( <family pcgs>, <list> )
##
InstallMethod( PcElementByExponentsNC, "family pcgs", true,
[ IsPcgs and IsFamilyPcgs, IsRowVector and IsCyclotomicCollection ], 0,
function( pcgs, list )
#Assert(1,ForAll(list,i->i>=0));
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),list);
end );
InstallMethod( PcElementByExponentsNC, "family pcgs, FFE", true,
[ IsPcgs and IsFamilyPcgs, IsRowVector and IsFFECollection ], 0,
function( pcgs, list )
list:=IntVecFFE(list);
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),list);
end );
InstallOtherMethod( PcElementByExponentsNC, "family pcgs, index", true,
[ IsPcgs and IsFamilyPcgs, IsRowVector and IsCyclotomicCollection,
IsRowVector and IsCyclotomicCollection ], 0,
function( pcgs,ind, list )
local l;
l:=ShallowCopy(pcgs!.zeroVector);
l{ind}:=list;
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),l);
end );
InstallOtherMethod( PcElementByExponentsNC, "family pcgs, basisind, FFE", true,
[ IsPcgs and IsFamilyPcgs, IsRowVector and IsCyclotomicCollection,
IsRowVector and IsFFECollection ], 0,
function( pcgs,ind, list )
local l;
l:=ShallowCopy(pcgs!.zeroVector);
l{ind}:=IntVecFFE(list);
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),l);
end );
#############################################################################
##
#M PcElementByExponentsNC( <family pcgs induced>, <list> )
##
InstallMethod( PcElementByExponentsNC, "subset induced wrt family pcgs", true,
[ IsPcgs and IsParentPcgsFamilyPcgs and IsSubsetInducedPcgsRep
and IsPrimeOrdersPcgs, IsRowVector and IsCyclotomicCollection ], 0,
function( pcgs, list )
local exp;
#Assert(1,ForAll(list,i->i>=0));
exp:=ShallowCopy(pcgs!.parentZeroVector);
exp{pcgs!.depthsInParent}:=list;
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),exp);
end);
InstallOtherMethod( PcElementByExponentsNC,
"subset induced wrt family pcgs, index", true,
[ IsPcgs and IsParentPcgsFamilyPcgs and IsSubsetInducedPcgsRep
and IsPrimeOrdersPcgs, IsRowVector and IsCyclotomicCollection,
IsRowVector and IsCyclotomicCollection ], 0,
function( pcgs, ind,list )
local exp;
#Assert(1,ForAll(list,i->i>=0));
exp:=ShallowCopy(pcgs!.parentZeroVector);
exp{pcgs!.depthsInParent{ind}}:=list;
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),exp);
end);
#############################################################################
##
#M PcElementByExponentsNC( <family pcgs induced>, <list> )
##
InstallMethod( PcElementByExponentsNC,
"subset induced wrt family pcgs, FFE", true,
[ IsPcgs and IsParentPcgsFamilyPcgs and IsSubsetInducedPcgsRep
and IsPrimeOrdersPcgs,
IsRowVector and IsFFECollection ], 0,
function( pcgs, list )
local exp;
list:=IntVecFFE(list);
exp:=ShallowCopy(pcgs!.parentZeroVector);
exp{pcgs!.depthsInParent}:=list;
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),exp);
end);
InstallOtherMethod( PcElementByExponentsNC,
"subset induced wrt family pcgs, FFE,index", true,
[ IsPcgs and IsParentPcgsFamilyPcgs and IsSubsetInducedPcgsRep
and IsPrimeOrdersPcgs, IsRowVector and IsCyclotomicCollection,
IsRowVector and IsFFECollection ], 0,
function( pcgs,ind, list )
local exp;
list:=IntVecFFE(list);
exp:=ShallowCopy(pcgs!.parentZeroVector);
exp{pcgs!.depthsInParent{ind}}:=list;
return ObjByVector(TypeObj(OneOfPcgs(pcgs)),exp);
end);
#############################################################################
##
#M ExponentsConjugateLayer( <mpcgs>,<elm>,<e> )
##
# this algorithm does not compute any conjugates but only looks them up and
# adds vectors mod p.
InstallGlobalFunction(DoExponentsConjLayerFampcgs,function(p,m,e,c)
local d,q,l,i,j,k,n,g,v,res;
c:=ExtRepOfObj(c);
d:=m!.depthsInParent;
q:=RelativeOrders(m)[1];
l:=Length(d);
e:=ExponentsOfPcElement(p,e){d}; # exponent vector
for i in [1,3..Length(c)-1] do
g:=c[i];
if g<d[1] then
for j in [1..c[i+1]] do
# conjugate the vector once by summing the conjugates in each entry
res:=ShallowCopy(m!.zeroVector);
for k in [1..l] do
if e[k]>0 then
v:=ExponentsOfConjugate(p,d[k],g);
for n in [1..l] do
res[n]:=(res[n]+e[k]*v[d[n]]) mod q;
od;
fi;
od;
e:=res;
od;
fi;
od;
return e;
end);
InstallMethod( ExponentsConjugateLayer,"subset induced pcgs",
IsCollsElmsElms,
[ IsTailInducedPcgsRep and IsParentPcgsFamilyPcgs,
IsMultiplicativeElementWithInverse,IsMultiplicativeElementWithInverse],0,
function(m,e,c)
local a,p;
p:=ParentPcgs(m);
# need to test whether pcgs is normal in parent -- otherwise fail
if not IsBound(m!.expConjNormalInParent) then
a:=Difference([1..Length(p)],m!.depthsInParent);
m!.expConjNormalInParent:=ForAll(p,x->ForAll(m,
y->ForAll(ExponentsOfPcElement(p,y^x){a},IsZero)));
#Print("Tested eligibility for cheap test ",m!.expConjNormalInParent,"\n");
fi;
if m!.expConjNormalInParent=false then
TryNextMethod();
fi;
return DoExponentsConjLayerFampcgs(p,m,e,c);
end);
#############################################################################
##
#M CanonicalPcElement( <igs>, <8bits-word> )
##
InstallMethod( CanonicalPcElement,
"tail induced pcgs, 8bits word",
IsCollsElms,
[ IsInducedPcgs and IsTailInducedPcgsRep and IsParentPcgsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep ],
0,
function( pcgs, elm )
return 8Bits_HeadByNumber( elm, pcgs!.tailStart );
end );
#############################################################################
##
#M DepthOfPcElement( <8bits-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement,
"family pcgs (8 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep ],
0,
8Bits_DepthOfPcElement );
#############################################################################
##
#M ExponentOfPcElement( <8bits-pcgs>, <elm> )
##
InstallMethod( ExponentOfPcElement,
"family pcgs (8bits)",IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep,
IsPosInt ],
0,
8Bits_ExponentOfPcElement );
#############################################################################
##
#M ExponentsOfPcElement( <8bits-pcgs>, <elm> )
##
InstallMethod( ExponentsOfPcElement, "family pcgs/8 bit",IsCollsElms,
[ IsPcgs and IsFamilyPcgs, Is8BitsPcWordRep ], 0,
8Bits_ExponentsOfPcElement);
#function ( pcgs, elm )
# local exp, rep, i;
# exp := ListWithIdenticalEntries( Length( pcgs ), 0 );
# rep := 8Bits_ExtRepOfObj( elm );
# for i in [ 1, 3 .. Length( rep ) - 1 ] do
# exp[rep[i]] := rep[i + 1];
# od;
# return exp;
#end);
#############################################################################
##
#M ExponentsOfPcElement( <8bits-pcgs>, <elm>,<range> )
##
InstallOtherMethod( ExponentsOfPcElement, "family pcgs/8 bit",IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs, Is8BitsPcWordRep,IsList ], 0,
function( pcgs, elm,range )
return 8Bits_ExponentsOfPcElement(pcgs,elm){range};
end);
#local exp, rep, i,rp,lr;
# lr:=Length(range);
# exp := ListWithIdenticalEntries( lr, 0 );
# rep := 8Bits_ExtRepOfObj(elm);
# rp:=1; # position in range
# # assume the ext rep is always ordered.
# for i in [ 1, 3 .. Length(rep)-1 ] do
# # do we have to get up through the range?
# while rp<=lr and range[rp]<rep[i] do
# rp:=rp+1;
# od;
# if rp>lr then
# break; # we have reached the end of the range
# fi;
# if rep[i]=range[rp] then
# exp[rp] := rep[i+1];
# rp:=rp+1;
# fi;
# od;
# return exp;
#end );
#############################################################################
##
#M HeadPcElementByNumber( <8bits-pcgs>, <8bits-word>, <num> )
##
InstallMethod( HeadPcElementByNumber, "family pcgs (8bits)",
IsCollsElmsX, [ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep, IsInt ], 0,
function( pcgs, elm, pos )
return 8Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M CleanedTailPcElement( <8bits-pcgs>, <8bits-word>, <num> )
##
InstallMethod( CleanedTailPcElement, "family pcgs (8bits)",
IsCollsElmsX, [ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep, IsInt ], 0,
function( pcgs, elm, pos )
return 8Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M LeadingExponentOfPcElement( <8bits-pcgs>, <elm> )
##
InstallMethod( LeadingExponentOfPcElement,
"family pcgs (8 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is8BitsPcWordRep ],
0,
8Bits_LeadingExponentOfPcElement );
#############################################################################
##
#M CanonicalPcElement( <igs>, <16bits-word> )
##
InstallMethod( CanonicalPcElement,
"tail induced pcgs, 16bits word",
IsCollsElms,
[ IsInducedPcgs and IsTailInducedPcgsRep and IsParentPcgsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep ],
0,
function( pcgs, elm )
return 16Bits_HeadByNumber( elm, pcgs!.tailStart );
end );
#############################################################################
##
#M DepthOfPcElement( <16bits-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement,
"family pcgs (16 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep ],
0,
16Bits_DepthOfPcElement );
#############################################################################
##
#M ExponentOfPcElement( <16bits-pcgs>, <elm> )
##
InstallMethod( ExponentOfPcElement,
"family pcgs (16bits)",IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep,
IsPosInt ],
0,
16Bits_ExponentOfPcElement );
#############################################################################
##
#M ExponentsOfPcElement( <16bits-pcgs>, <elm> )
##
InstallMethod( ExponentsOfPcElement, "family pcgs/16 bit",IsCollsElms,
[ IsPcgs and IsFamilyPcgs, Is16BitsPcWordRep ], 0,
16Bits_ExponentsOfPcElement);
#############################################################################
##
#M ExponentsOfPcElement( <16bits-pcgs>, <elm>,<range> )
##
InstallOtherMethod( ExponentsOfPcElement, "family pcgs/16 bit",IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs, Is16BitsPcWordRep,IsList ],
0,
function( pcgs, elm,range )
return 16Bits_ExponentsOfPcElement(pcgs,elm){range};
end );
#############################################################################
##
#M HeadPcElementByNumber( <16bits-pcgs>, <16bits-word>, <num> )
##
InstallMethod( HeadPcElementByNumber,
"family pcgs (16bits)",
IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep,
IsInt ],
0,
function( pcgs, elm, pos )
return 16Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M CleanedTailPcElement( <16bits-pcgs>, <16bits-word>, <num> )
##
InstallMethod( CleanedTailPcElement,
"family pcgs (16bits)",
IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep,
IsInt ],
0,
function( pcgs, elm, pos )
return 16Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M LeadingExponentOfPcElement( <16bits-pcgs>, <elm> )
##
InstallMethod( LeadingExponentOfPcElement,
"family pcgs (16 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is16BitsPcWordRep ],
0,
16Bits_LeadingExponentOfPcElement );
#############################################################################
##
#M CanonicalPcElement( <igs>, <32bits-word> )
##
InstallMethod( CanonicalPcElement,
"tail induced pcgs, 32bits word",
IsCollsElms,
[ IsInducedPcgs and IsTailInducedPcgsRep and IsParentPcgsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep ],
0,
function( pcgs, elm )
return 32Bits_HeadByNumber( elm, pcgs!.tailStart-1 );
end );
#############################################################################
##
#M DepthOfPcElement( <32bits-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement,
"family pcgs (32 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep ],
0,
32Bits_DepthOfPcElement );
#############################################################################
##
#M ExponentOfPcElement( <32bits-pcgs>, <elm> )
##
InstallMethod( ExponentOfPcElement,
"family pcgs (32bits)",
IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep,
IsPosInt ],
0,
32Bits_ExponentOfPcElement );
#############################################################################
##
#M ExponentsOfPcElement( <32bits-pcgs>, <elm> )
##
InstallMethod( ExponentsOfPcElement, "family pcgs/32 bit",IsCollsElms,
[ IsPcgs and IsFamilyPcgs, Is32BitsPcWordRep ], 0,
32Bits_ExponentsOfPcElement);
#############################################################################
##
#M ExponentsOfPcElement( <32bits-pcgs>, <elm>,<range> )
##
InstallOtherMethod( ExponentsOfPcElement, "family pcgs/32 bit",IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs, Is32BitsPcWordRep,IsList ], 0,
function( pcgs, elm,range )
return 32Bits_ExponentsOfPcElement(pcgs,elm){range};
end);
#############################################################################
##
#M HeadPcElementByNumber( <32bits-pcgs>, <32bits-word>, <num> )
##
InstallMethod( HeadPcElementByNumber,
"family pcgs (32bits)",
IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep,
IsInt ],
0,
function( pcgs, elm, pos )
return 32Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M CleanedTailPcElement( <32bits-pcgs>, <32bits-word>, <num> )
##
InstallMethod( CleanedTailPcElement,
"family pcgs (32bits)",
IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep,
IsInt ],
0,
function( pcgs, elm, pos )
return 32Bits_HeadByNumber( elm, pos );
end );
#############################################################################
##
#M LeadingExponentOfPcElement( <32bits-pcgs>, <elm> )
##
InstallMethod( LeadingExponentOfPcElement,
"family pcgs (32 bits)",
IsCollsElms,
[ IsPcgs and IsFamilyPcgs,
IsMultiplicativeElementWithInverseByRws and Is32BitsPcWordRep ],
0,
32Bits_LeadingExponentOfPcElement );
#############################################################################
##
#M ExponentsOfConjugate( <pcgs>, <i>, <j> )
##
InstallMethod( ExponentsOfConjugate,"family pcgs: look up",true,
[ IsPcgs and IsFamilyPcgs, IsPosInt,IsPosInt], 0,
function( pcgs, i, j )
if not IsBound(pcgs!.conjugates[i][j]) then
pcgs!.conjugates[i][j]:=ExponentsOfPcElement(pcgs,pcgs[i]^pcgs[j]);
fi;
return pcgs!.conjugates[i][j];
end );
#############################################################################
##
#M ExponentsOfRelativePower( <pcgs>, <i> )
##
InstallMethod( ExponentsOfRelativePower,"family pcgs: look up",true,
[ IsPcgs and IsFamilyPcgs, IsPosInt], 0,
function( pcgs, i )
if not IsBound(pcgs!.powers[i]) then
# happens rarely!
return ExponentsOfPcElement(pcgs,pcgs[i]^RelativeOrders(pcgs)[i]);
else
return pcgs!.powers[i];
fi;
end );
#############################################################################
##
#M CleanedTailPcElement( <family pcgs>, <elm>,<dep> )
##
InstallMethod( CleanedTailPcElement, "family pcgs", IsCollsElmsX,
[ IsPcgs and IsFamilyPcgs, IsMultiplicativeElementWithInverse, IsPosInt ],
0,
function( pcgs, elm,dep )
elm:=ExponentsOfPcElement(pcgs,elm);
elm{[dep..Length(elm)]}:= 0*[dep..Length(elm)];
return PcElementByExponentsNC(pcgs,elm);
end);
#############################################################################
##
#M DepthOfPcElement( <unsorted-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement, "unsorted pcgs", IsCollsElms,
[ IsPcgs and IsUnsortedPcgsRep, IsObject ], 0,
function( pcgs, elm )
local pfa, pcs, new, dep, id, dg;
if not IsBound(pcgs!.sortingPcgs) then TryNextMethod();fi;
pfa := pcgs!.sortingPcgs;
pcs := pcgs!.sortedPcSequence;
new := pcgs!.newDepths;
dep := Length(pcgs)+1;
id := OneOfPcgs(pcgs);
# if <elm> is the identity return the composition length plus one
if elm = id then
return Length(pcgs)+1;
fi;
# sift element through the sorted system
while elm <> id do
dg := DepthOfPcElement( pfa, elm );
if IsBound(pcs[dg]) then
elm := ReducedPcElement( pfa, elm, pcs[dg] );
if new[dg] < dep then
dep := new[dg];
fi;
else
Error( "<elm> must lie in group defined by <pcgs>" );
fi;
od;
return dep;
end );
#############################################################################
##
#M DepthOfPcElement( <sorted-pcgs>, <elm> )
##
InstallMethod( DepthOfPcElement, "sorted pcgs", IsCollsElms,
[ IsPcgs and IsSortedPcgsRep, IsObject ], 0,
function( pcgs, elm )
return DepthOfPcElement(pcgs!.sortingPcgs,elm);
end );
#############################################################################
##
#M ExponentOfPcElement( <unsorted-pcgs>, <elm>, <pos> )
##
InstallMethod( ExponentOfPcElement, "unsorted pcgs", IsCollsElmsX,
[ IsPcgs and IsUnsortedPcgsRep, IsObject, IsPosInt ], 0,
function( pcgs, elm, pos )
local pfa, pcs, new, dep, id, g, dg, ll, lr, ord,
led,pcsl,relords,pcspow,codepths,step;
id := OneOfPcgs(pcgs);
# if <elm> is the identity return the null
if elm = id then
return 0;
fi;
if not IsBound(pcgs!.sortingPcgs) then TryNextMethod();fi;
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
pcs := pcgs!.sortedPcSequence;
pcsl:= pcgs!.sortedPcSequenceLeadCoeff;
pcspow := pcgs!.sortedPcSeqPowers;
new := pcgs!.newDepths;
codepths:=pcgs!.minimumCodepths;
# sift element through the sorted system
step:=0; # the index in pcgs up to which we have already computed exponents
while elm <> id do
#compute the next depth `dep' at which we have an exponent in pcgs.
g := elm;
dep := Length(pcgs)+1;
while g <> id do
# do this by stepping down in pag
dg := DepthOfPcElement( pfa, g );
if codepths[dg]>dep then
# once we have reached pfa-depth dg, we cannot achieve `dep'
# any longer. So we may stop the descent through pfa here
g:=id;
elif IsBound(pcs[dg]) then
ll := LeadingExponentOfPcElement( pfa, g );
#lr := LeadingExponentOfPcElement( pfa, pcs[dg]);
lr := pcsl[dg]; # precomputed value
#ord := RelativeOrderOfPcElement( pfa, g );
# the relative order is of course the rel. ord. in pfa
# at depth dg.
ord:=relords[dg];
ll := (ll/lr mod ord);
#g := LeftQuotient( pcs[dg]^ll, g );
g := LeftQuotient( pcspow[dg][ll], g ); #precomputed
if new[dg] < dep then
dep := new[dg];
led := ll;
if dep<=step+1 then
# this is the minimum possible pcgs-depth at this
# point
g:=id;
fi;
fi;
else
Error( "<elm> must lie in group defined by <pcgs>" );
fi;
od;
step:=dep;
if dep = pos then
return led;
fi;
#elm := LeftQuotient( pcgs[dep]^led, elm );
elm := LeftQuotientPowerPcgsElement( pcgs,dep,led, elm );
od;
return 0;
end );
#############################################################################
##
#M ExponentOfPcElement( <sorted-pcgs>, <elm>,<pos> )
##
InstallMethod( ExponentOfPcElement, "sorted pcgs", IsCollsElmsX,
[ IsPcgs and IsSortedPcgsRep, IsObject,IsPosInt ], 0,
function( pcgs, elm,pos )
local pfa,relords,invpow,step,e,p,pcspow;
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
invpow := pcgs!.inversePowers;
pcspow := pcgs!.sortedPcSeqPowers;
for step in [1..pos] do
e:=ExponentOfPcElement(pfa,elm,step);
p:=(e*invpow[step]) mod relords[step];
if e<>0 and step<pos then
elm:=LeftQuotient(pcspow[step][p],elm);
fi;
od;
return p;
end);
#############################################################################
##
#M ExponentsOfPcElement( <unsorted-pcgs>, <elm> )
##
InstallMethod( ExponentsOfPcElement,
"unsorted pcgs",
IsCollsElms,
[ IsPcgs and IsUnsortedPcgsRep,
IsObject ],
0,
function( pcgs, elm )
local pfa, pcs, new, dep, id, exp, g, dg, ll, lr, ord,
led,pcsl,relords,pcspow,codepths,step;
id := OneOfPcgs(pcgs);
exp := ListWithIdenticalEntries(Length(pcgs),0);
# if <elm> is the identity return the null vector
if elm = id then
return exp;
fi;
if not IsBound(pcgs!.sortingPcgs) then TryNextMethod();fi;
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
pcs := pcgs!.sortedPcSequence;
pcsl:= pcgs!.sortedPcSequenceLeadCoeff;
pcspow := pcgs!.sortedPcSeqPowers;
new := pcgs!.newDepths;
codepths:=pcgs!.minimumCodepths;
# sift element through the sorted system
step:=0; # the index in pcgs up to which we have already computed exponents
while elm <> id do
#compute the next depth `dep' at which we have an exponent in pcgs.
g := elm;
dep := Length(pcgs)+1;
while g <> id do
# do this by stepping down in pag
dg := DepthOfPcElement( pfa, g );
if codepths[dg]>dep then
# once we have reached pfa-depth dg, we cannot achieve `dep'
# any longer. So we may stop the descent through pfa here
g:=id;
elif IsBound(pcs[dg]) then
ll := LeadingExponentOfPcElement( pfa, g );
#lr := LeadingExponentOfPcElement( pfa, pcs[dg]);
lr := pcsl[dg]; # precomputed value
#ord := RelativeOrderOfPcElement( pfa, g );
# the relative order is of course the rel. ord. in pfa
# at depth dg.
ord:=relords[dg];
ll := (ll/lr mod ord);
#g := LeftQuotient( pcs[dg]^ll, g );
g := LeftQuotient( pcspow[dg][ll], g ); #precomputed
if new[dg] < dep then
dep := new[dg];
led := ll;
if dep<=step+1 then
# this is the minimum possible pcgs-depth at this
# point
g:=id;
fi;
fi;
else
Error( "<elm> must lie in group defined by <pcgs>" );
fi;
od;
exp[dep] := led;
step:=dep;
#elm := LeftQuotient( pcgs[dep]^led, elm );
elm := LeftQuotientPowerPcgsElement( pcgs,dep,led, elm );
od;
return exp;
end );
#############################################################################
##
#M ExponentsOfPcElement( <unsorted-pcgs>, <elm>, <range> )
##
InstallOtherMethod( ExponentsOfPcElement,
"unsorted pcgs/range",
IsCollsElmsX,
[ IsPcgs and IsUnsortedPcgsRep,
IsObject,IsList ],
0,
function( pcgs, elm,range )
local pfa, pcs, new, dep, id, exp, g, dg, ll, lr, ord,
led,pcsl,max,step,codepths,pcspow,relords;
id := OneOfPcgs(pcgs);
exp := ListWithIdenticalEntries(Length(pcgs),0);
# if <elm> is the identity return the null vector
if elm = id or Length(range)=0 then
return exp{range};
fi;
if not IsBound(pcgs!.sortingPcgs) then TryNextMethod();fi;
max:=Maximum(range);
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
pcs := pcgs!.sortedPcSequence;
pcsl:= pcgs!.sortedPcSequenceLeadCoeff;
pcspow := pcgs!.sortedPcSeqPowers;
new := pcgs!.newDepths;
codepths:=pcgs!.minimumCodepths;
# sift element through the sorted system
step:=0; # the index in pcgs up to which we have already computed exponents
while elm <> id do
#compute the next depth `dep' at which we have an exponent in pcgs.
g := elm;
dep := Length(pcgs)+1;
while g <> id do
# do this by stepping down in pag
dg := DepthOfPcElement( pfa, g );
if codepths[dg]>dep then
# once we have reached pfa-depth dg, we cannot achieve `dep'
# any longer. So we may stop the descent through pfa here
g:=id;
elif IsBound(pcs[dg]) then
ll := LeadingExponentOfPcElement( pfa, g );
#lr := LeadingExponentOfPcElement( pfa, pcs[dg]);
lr := pcsl[dg]; # precomputed value
#ord := RelativeOrderOfPcElement( pfa, g );
# the relative order is of course the rel. ord. in pfa
# at depth dg.
ord:=relords[dg];
ll := (ll/lr mod ord);
#g := LeftQuotient( pcs[dg]^ll, g );
g := LeftQuotient( pcspow[dg][ll], g ); #precomputed
if new[dg] < dep then
dep := new[dg];
led := ll;
if dep<=step+1 then
# this is the minimum possible pcgs-depth at this
# point
g:=id;
fi;
fi;
else
Error( "<elm> must lie in group defined by <pcgs>" );
fi;
od;
exp[dep] := led;
step:=dep;
if dep>=max then
# we have found all exponents, may stop
break;
fi;
#elm := LeftQuotient( pcgs[dep]^led, elm );
elm := LeftQuotientPowerPcgsElement( pcgs,dep,led, elm );
od;
return exp{range};
end);
#############################################################################
##
#M ExponentsOfPcElement( <sorted-pcgs>, <elm> )
##
BindGlobal( "ExpPcElmSortedFun", function( pcgs, elm,ran )
local exp,pfa,relords,invpow,max,step,e,p,pcspow;
exp := [];
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
invpow := pcgs!.inversePowers;
pcspow := pcgs!.sortedPcSeqPowers;
if ran=true then
max:=Length(pfa);
elif Length(ran)=0 then
return [];
else
max:=Maximum(ran);
fi;
for step in [1..max] do
e:=ExponentOfPcElement(pfa,elm,step);
p:=(e*invpow[step]) mod relords[step];
Add(exp,p);
if e<>0 and step<max then
elm:=LeftQuotient(pcspow[step][p],elm);
fi;
od;
if ran<>true then
return exp{ran};
else
return exp;
fi;
end );
InstallMethod( ExponentsOfPcElement, "sorted pcgs", IsCollsElms,
[ IsPcgs and IsSortedPcgsRep, IsObject ], 0,
function(pcgs,elm)
return ExpPcElmSortedFun(pcgs,elm,true);
end);
InstallOtherMethod( ExponentsOfPcElement, "sorted pcgs/range", IsCollsElmsX,
[ IsPcgs and IsSortedPcgsRep, IsObject,IsList ], 0,
ExpPcElmSortedFun);
#############################################################################
##
#M LeadingExponentOfPcElement( <unsorted-pcgs>, <elm> )
##
InstallMethod( LeadingExponentOfPcElement,
"unsorted pcgs",
IsCollsElms,
[ IsPcgs and IsUnsortedPcgsRep,
IsObject ],
0,
function( pcgs, elm )
local pfa, pcs, new, dep, id, dg, ll, lr, ord, led,pcsl,
relords,pcspow,codepths;
id := OneOfPcgs(pcgs);
# if <elm> is the identity return fail
if elm = id then
return fail;
fi;
if not IsBound(pcgs!.sortingPcgs) then TryNextMethod();fi;
pfa := pcgs!.sortingPcgs;
relords:=RelativeOrders(pfa);
pcs := pcgs!.sortedPcSequence;
pcsl:= pcgs!.sortedPcSequenceLeadCoeff;
pcspow := pcgs!.sortedPcSeqPowers;
new := pcgs!.newDepths;
codepths:=pcgs!.minimumCodepths;
dep := Length(pcgs)+1;
# sift element through the sorted system
while elm <> id do
# do this by stepping down in pag
dg := DepthOfPcElement( pfa, elm );
if codepths[dg]>dep then
# once we have reached pfa-depth dg, we cannot achieve `dep'
# any longer. So we may stop the descent through pfa here
elm:=id;
elif IsBound(pcs[dg]) then
ll := LeadingExponentOfPcElement( pfa, elm );
#lr := LeadingExponentOfPcElement( pfa, pcs[dg]);
lr := pcsl[dg]; # precomputed value
#ord := RelativeOrderOfPcElement( pfa, elm );
# the relative order is of course the rel. ord. in pfa
# at depth dg.
ord:=relords[dg];
ll := (ll/lr mod ord);
#elm := LeftQuotient( pcs[dg]^ll, elm);
elm := LeftQuotient( pcspow[dg][ll], elm ); #precomputed
if new[dg] < dep then
dep := new[dg];
led := ll;
fi;
else
Error( "<elm> must lie in group defined by <pcgs>" );
fi;
od;
return led;
end );
#############################################################################
##
#M ExponentOfPcElement( <sorted-pcgs>, <elm>,<pos> )
##
InstallMethod( LeadingExponentOfPcElement, "sorted pcgs", IsCollsElms,
[ IsPcgs and IsSortedPcgsRep, IsObject ], 0,
function( pcgs, elm )
local d;
d:=DepthOfPcElement(pcgs!.sortingPcgs,elm);
return (LeadingExponentOfPcElement(pcgs!.sortingPcgs,elm)
*pcgs!.inversePowers[d]) mod RelativeOrders(pcgs)[d];
end);
#############################################################################
##
#M CleanedTailPcElement( <sorted pcgs>, <elm>,<dep> )
##
InstallMethod( CleanedTailPcElement, "sorted pcgs - defer to sorting pcgs",
IsCollsElmsX,
[IsPcgs and IsSortedPcgsRep,IsMultiplicativeElementWithInverse,IsPosInt],0,
function( pcgs, elm,dep )
return CleanedTailPcElement(pcgs!.sortingPcgs,elm,dep);
end);
#############################################################################
##
#M Order( <obj> ) . . . . . . . . . . . . . . . . . . order of a pc-element
##
#############################################################################
InstallMethod( Order,
"method for a pc-element",
HasDefiningPcgs,
[ IsMultiplicativeElementWithOne ], 3,
function( g )
local pcgs, rorders, one, ord, d, rord;
pcgs := DefiningPcgs( FamilyObj( g ) );
rorders := RelativeOrders( pcgs );
one := g^0;
ord := 1;
if IsPrimeOrdersPcgs( pcgs ) then
while g <> one do
d := DepthOfPcElement( pcgs, g );
rord := rorders[ d ];
ord := ord * rord;
g := g^rord;
od;
else
while g <> one do
d := DepthOfPcElement( pcgs, g );
if not IsBound( rorders[d] ) or rorders[ d ] = 0 then
return infinity;
fi;
rord := rorders[ d ];
rord := rord / Gcd( ExponentOfPcElement( pcgs, g, d ), rord );
ord := ord * rord;
g := g^rord;
od;
fi;
return ord;
end );
#############################################################################
InstallMethod( PrimePowerComponents, "method for a pc element",
HasDefiningPcgs, [ IsMultiplicativeElementWithOne ], 0,
function( el )
local pcgs, g,ord,cord,ppc,q,r,gcd,p1,p2,i,j,e1,pows,exps,rord;
pcgs := DefiningPcgs( FamilyObj( el ) );
if not IsPrimeOrdersPcgs( pcgs ) then
TryNextMethod(); # don't bother with optimizing the other case
fi;
g:=el;
ord := 1;
exps:=[];
pows:=[];
# first get the order and remember the powers computed
rord:=RelativeOrderOfPcElement(pcgs,g);
while rord>1 do
ord := ord * rord;
g := g^rord;
Add(exps,ord);
Add(pows,g);
rord:=RelativeOrderOfPcElement(pcgs,g);
od;
if ord=1 then
return [g];
fi;
g:=el;
ppc:=[];
cord:=Collected(Factors(Integers,ord));
for i in [1..Length(cord)-1] do
q:=cord[i][1]^cord[i][2];
r:=ord/q;
gcd:=Gcdex(q,r);
p2:=gcd.coeff1*q mod ord;
p1:=gcd.coeff2*r mod ord;
# try to find the powers
j:=Length(exps);
e1:=false;
while e1=false and j>0 do
if IsInt(p1/exps[j]) then
e1:=pows[j]^(p1/exps[j]);
fi;
j:=j-1;
od;
if e1=false then
if Length(exps)>0 then
# compose from the exponents in exps:
e1:=OneOfPcgs(pcgs);
while p1>1 and ForAny(exps,i->i<p1 and i^3>p1) do
j:=First([Length(exps),Length(exps)-1..1],i->exps[i]<p1
and exps[i]^3>p1);
q:=QuoInt(p1,exps[j]);
e1:=e1*pows[j]^q;
p1:=p1 mod exps[j];
od;
e1:=e1*g^p1;
else
e1:=g^p1;
fi;
fi;
Add(ppc,e1);
ord:=r; # new order
# try to find the powers
j:=Length(exps);
e1:=false;
while e1=false and j>0 do
if IsInt(p2/exps[j]) then
q:=p2/exps[j];
e1:=pows[j]^q;
# the remaining powers in case they can be used
r:=Filtered([j..Length(exps)],k->IsInt(exps[k]/p2));
pows:=pows{r};
exps:=exps{r}/p2;
Assert(1,ForAll([1..Length(exps)],x->e1^exps[x]=pows[x]));
fi;
j:=j-1;
od;
if e1=false then
if Length(exps)>0 then
# compose from the exponents in exps;
e1:=OneOfPcgs(pcgs);
while p2>1 and ForAny(exps,i->i<p2 and i^3>p2) do
j:=First([Length(exps),Length(exps)-1..1],i->exps[i]<p2
and exps[i]^3>p2);
q:=QuoInt(p2,exps[j]);
e1:=e1*pows[j]^q;
p2:=p2 mod exps[j];
od;
e1:=e1*g^p2;
else
e1:=g^p2;
fi;
exps:=[]; # we can't use any of the precomputed powers
fi;
g:=e1;
od;
Add(ppc,g);
return ppc;
end );
[ Dauer der Verarbeitung: 0.43 Sekunden
(vorverarbeitet)
]
|
