#############################################################################
##
#W rcwagrp.gi GAP4 Package `RCWA' Stefan Kohl
##
## This file contains implementations of methods and functions for computing
## with rcwa groups over
##
## - the ring Z of the integers, over
## - the ring Z^2, over
## - the semilocalizations Z_(pi) of the ring of integers, and over
## - the polynomial rings GF(q)[x] in one variable over a finite field.
##
## See the definitions given in the file rcwamap.gd.
##
#############################################################################
#############################################################################
##
#S Implications between the categories of rcwa groups. /////////////////////
##
#############################################################################
InstallTrueMethod( IsGroup, IsRcwaGroup );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverZOrZ_pi );
InstallTrueMethod( IsRcwaGroupOverZOrZ_pi, IsRcwaGroupOverZ );
InstallTrueMethod( IsRcwaGroupOverZOrZ_pi, IsRcwaGroupOverZ_pi );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverZxZ );
InstallTrueMethod( IsRcwaGroup, IsRcwaGroupOverGFqx );
#############################################################################
##
#S Implications of `IsRcwaGroup'. //////////////////////////////////////////
##
#############################################################################
InstallTrueMethod( CanComputeSizeAnySubgroup, IsRcwaGroup );
InstallTrueMethod( KnowsHowToDecompose,
IsRcwaGroup and HasGeneratorsOfGroup );
#############################################################################
##
#M IsWholeFamily . . . . . . . . . . . . . for an rcwa group -- return false
##
InstallMethod( IsWholeFamily,
"for an rcwa group -- return false (RCWA)", true,
[ IsRcwaGroup ], 0, ReturnFalse );
#############################################################################
##
#S Rcwa groups and lists of generators. ////////////////////////////////////
##
#############################################################################
#############################################################################
##
#M IsGeneratorsOfMagmaWithInverses( <l> ) . . . for a list of rcwa mappings
##
## Tests whether all rcwa mappings in the list <l> belong to the same
## family and are bijective, hence generate a group.
##
InstallMethod( IsGeneratorsOfMagmaWithInverses,
"for lists of rcwa mappings (RCWA)", true,
[ IsListOrCollection ], 0,
function ( l )
if ForAll(l,IsRcwaMapping)
then return Length(Set(List(l,FamilyObj))) = 1
and ForAll(l,IsBijective);
else TryNextMethod(); fi;
end );
#############################################################################
##
#M AssignGeneratorVariables( <G> ) . . for rcwa groups with at most 8 gen's
##
## This method assigns the generators of <G> to global variables a, b, ... .
## As all functions which assign anything one-letter global variables, it is
## for interactive use only, and should not be called from inside code.
##
InstallMethod( AssignGeneratorVariables,
"for rcwa groups with at most 8 generators (RCWA)",
true, [ IsRcwaGroup ], 0,
function ( G )
local gens, names, name, i;
gens := GeneratorsOfGroup(G);
if Length(gens) > 8 then TryNextMethod(); fi;
names := "abcdefgh";
for i in [1..Length(gens)] do
name := names{[i]};
if IsBoundGlobal(name) then
if IsReadOnlyGlobal(name)
then Error("variable ",name," is read-only"); fi;
UnbindGlobal(name);
Info(InfoWarning,1,"The global variable ",name,
" has been overwritten.");
fi;
BindGlobal(name,gens[i]);
MakeReadWriteGlobal(name);
od;
Print("The following global variables have been assigned: ");
for i in [1..Length(gens)] do
Print(names{[i]});
if i < Length(gens) then Print(", "); fi;
od;
Print("\n");
end );
#############################################################################
##
#S Conversion of rcwa groups between standard and sparse representation. ///
##
#############################################################################
#############################################################################
##
#M SparseRepresentation( <G> ) . . . . . . . . . . . for rcwa groups over Z
##
InstallMethod( SparseRepresentation,
"for rcwa groups over Z (RCWA)",
true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,
function ( G )
local G_sparse;
G_sparse := GroupByGenerators(List(GeneratorsOfGroup(G),SparseRep));
if HasIsTame(G) then SetIsTame(G_sparse,IsTame(G)); fi;
if HasModulusOfRcwaMonoid(G)
then SetModulusOfRcwaMonoid(G_sparse,ModulusOfRcwaMonoid(G)); fi;
if HasSize(G) then SetSize(G_sparse,Size(G)); fi;
if HasIsAbelian(G) then SetIsAbelian(G_sparse,IsAbelian(G)); fi;
if HasIsPGroup(G) then
SetIsPGroup(G_sparse,IsPGroup(G));
if HasPrimePGroup(G) then SetPrimePGroup(G_sparse,PrimePGroup(G)); fi;
fi;
if HasIsSolvableGroup(G)
then SetIsSolvableGroup(G_sparse,IsSolvableGroup(G)); fi;
if HasIsPerfectGroup(G)
then SetIsPerfectGroup(G_sparse,IsPerfectGroup(G)); fi;
if HasIsSimpleGroup(G)
then SetIsSimpleGroup(G_sparse,IsSimpleGroup(G)); fi;
if IsNaturalCTP_Z(G)
then SetFilterObj(G_sparse,IsNaturalCTP_Z); fi;
return G_sparse;
end );
#############################################################################
##
#M StandardRepresentation( <G> ) . . . . . . . . . . for rcwa groups over Z
##
InstallMethod( StandardRepresentation,
"for rcwa groups over Z (RCWA)",
true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,
function ( G )
local G_standard;
G_standard := GroupByGenerators(List(GeneratorsOfGroup(G),StandardRep));
if HasIsTame(G) then SetIsTame(G_standard,IsTame(G)); fi;
if HasModulusOfRcwaMonoid(G)
then SetModulusOfRcwaMonoid(G_standard,ModulusOfRcwaMonoid(G)); fi;
if HasSize(G) then SetSize(G_standard,Size(G)); fi;
if HasIsAbelian(G) then SetIsAbelian(G_standard,IsAbelian(G)); fi;
if HasIsPGroup(G) then
SetIsPGroup(G_standard,IsPGroup(G));
if HasPrimePGroup(G) then SetPrimePGroup(G_standard,PrimePGroup(G)); fi;
fi;
if HasIsSolvableGroup(G)
then SetIsSolvableGroup(G_standard,IsSolvableGroup(G)); fi;
if HasIsPerfectGroup(G)
then SetIsPerfectGroup(G_standard,IsPerfectGroup(G)); fi;
if HasIsSimpleGroup(G)
then SetIsSimpleGroup(G_standard,IsSimpleGroup(G)); fi;
if IsNaturalCTP_Z(G)
then SetFilterObj(G_standard,IsNaturalCTP_Z); fi;
return G_standard;
end );
#############################################################################
##
#S Methods for `View', `Print', `Display' etc. /////////////////////////////
##
#############################################################################
#############################################################################
##
#M ViewObj( <G> ) . . . . . . . . . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( ViewObj,
"for rcwa groups (RCWA)", true,
[ IsRcwaGroup and HasGeneratorsOfGroup ], 0,
function ( G )
local NrGens, RingString, gens, g, cl, i;
RingString := RingToString(Source(One(G)));
if IsTrivial(G) then
Print("Trivial rcwa group over ",RingString);
elif IsRcwaGroupOverZ(G) and Length(GeneratorsOfGroup(G)) <=6
and ForAll(GeneratorsOfGroup(G),IsClassTransposition)
then
gens := GeneratorsOfGroup(G);
Print("<");
for i in [1..Length(gens)] do
g := gens[i];
cl := TransposedClasses(g);
Print("(",Residue(cl[1]),"(",Mod(cl[1]),"),",
Residue(cl[2]),"(",Mod(cl[2]),"))");
if i < Length(gens) then Print(","); fi;
od;
Print(">");
else
Print("<");
if HasIsTame(G) and not (HasSize(G) and IsInt(Size(G)))
then if IsTame(G) then Print("tame "); else Print("wild "); fi; fi;
NrGens := Length(GeneratorsOfGroup(G));
Print("rcwa group over ",RingString," with ",NrGens," generator");
if NrGens > 1 then Print("s"); fi;
if not (HasIsTame(G) and not IsTame(G)) then
if HasIdGroup(G)
then Print(", of isomorphism type ",IdGroup(G));
elif HasSize(G)
then Print(", of order ",Size(G)); fi;
fi;
Print(">");
fi;
end );
#############################################################################
##
#M ViewObj( <G> ) . . . . . . . . . for rcwa groups without known generators
##
InstallMethod( ViewObj,
"for rcwa groups without known generators (RCWA)",
true, [ IsRcwaGroup ], 0,
function ( G )
Print("<");
if HasIsTame(G)
then if IsTame(G) then Print("tame "); else Print("wild "); fi; fi;
Print("rcwa group over ",RingToString(Source(One(G))));
if HasElementTestFunction(G)
then Print(", with membership test"); fi;
if not HasGeneratorsOfGroup(G)
then Print(", without known generators"); fi;
Print(">");
end );
#############################################################################
##
#M ViewString( <G> ) . . . for groups generated by class transpositions of Z
##
InstallMethod( ViewString,
"for a group generated by class transpositions of Z",
true, [ IsRcwaGroupOverZ and HasGeneratorsOfGroup ], 0,
function ( G )
local gens, s, g, gs, cl;
gens := GeneratorsOfGroup(G);
if not ForAll(gens,IsClassTransposition) then TryNextMethod(); fi;
s := "<";
for g in gens do
cl := TransposedClasses(g);
gs := Concatenation(List(["(",Residue(cl[1]),"(",Mod(cl[1]),"),",
Residue(cl[2]),"(",Mod(cl[2]),"))"],
String));
if s <> "<" then s := Concatenation(s,","); fi;
s := Concatenation(s,gs);
od;
s := Concatenation(s,">");
return s;
end );
#############################################################################
##
#M ViewObj( <RG> ) . . . . . . . . . . . . . for group rings of rcwa groups
##
InstallMethod( ViewObj,
"for group rings of rcwa groups (RCWA)",
ReturnTrue, [ IsGroupRing ], 100,
function ( RG )
local R, G;
R := LeftActingDomain(RG); G := UnderlyingMagma(RG);
if not IsRcwaGroup(G) or R <> Source(One(G)) then TryNextMethod(); fi;
Print(RingToString(R)," "); ViewObj(G);
end );
#############################################################################
##
#M Print( <G> ) . . . . . . . . . . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( PrintObj,
"for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,
function ( G )
Print( "Group( ", GeneratorsOfGroup( G ), " )" );
end );
#############################################################################
##
#M Display( <G> ) . . . . . . . . . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( Display,
"for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,
function ( G )
local RingString, g, prefix;
RingString := RingToString(Source(One(G)));
if IsTrivial(G)
then Print("Trivial rcwa group over ",RingString);
if ValueOption("NoLineFeed") <> true then Print("\n"); fi;
else prefix := false;
if HasIsTame(G) and not (HasSize(G) and IsInt(Size(G))) then
if IsTame(G) then Print("\nTame "); else Print("\nWild "); fi;
prefix := true;
fi;
if prefix then Print("rcwa "); else Print("\nRcwa "); fi;
Print("group over ",RingString);
if not (HasIsTame(G) and not IsTame(G)) then
if HasIdGroup(G) then Print(" of isomorphism type ",IdGroup(G));
elif HasSize(G) then Print(" of order ",Size(G)); fi;
fi;
Print(", generated by\n\n[\n");
for g in GeneratorsOfGroup(G) do Display(g); od;
Print("]\n\n");
fi;
end );
#############################################################################
##
#M LaTeXStringRcwaGroup( <G> ) . . . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( LaTeXStringRcwaGroup,
"for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,
function ( G )
local s, g;
s := "\\langle ";
for g in GeneratorsOfGroup(G) do
if s <> "\\langle " then Append(s,", "); fi;
Append(s,LaTeXStringRcwaMapping(g));
od;
Append(s," \\rangle");
return s;
end );
#############################################################################
##
#S The trivial rcwa groups. ////////////////////////////////////////////////
##
#############################################################################
#############################################################################
##
#V TrivialRcwaGroupOverZ . . . . . . . . . . . . . trivial rcwa group over Z
#V TrivialRcwaGroupOverZxZ . . . . . . . . . . . trivial rcwa group over Z^2
##
BindGlobal( "TrivialRcwaGroupOverZ", Group( IdentityRcwaMappingOfZ ) );
BindGlobal( "TrivialRcwaGroupOverZxZ", Group( IdentityRcwaMappingOfZxZ ) );
#############################################################################
##
#M TrivialSubmagmaWithOne( <G> ). . . . . . . . . . . . . . for rcwa groups
##
InstallMethod( TrivialSubmagmaWithOne,
"for rcwa groups (RCWA)", true, [ IsRcwaGroup ], 0,
function ( G )
local triv;
triv := Group(One(G));
SetParentAttr(triv,G);
return triv;
end );
#############################################################################
##
#S The construction of the groups RCWA(R) of all rcwa permutations of R. ///
##
#############################################################################
#############################################################################
##
#M RCWACons( IsRcwaGroup, Integers ) . . . . . . . . . . . . . . . RCWA( Z )
##
## Returns the group which is formed by all bijective rcwa mappings of Z.
##
InstallMethod( RCWACons,
"natural RCWA(Z) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsIntegers ], 0,
function ( filter, R )
local G, id;
id := IdentityRcwaMappingOfZ;
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZ and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, IdentityRcwaMappingOfZ );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalRCWA );
SetFilterObj( G, IsNaturalRCWA_Z );
SetModulusOfRcwaMonoid( G, 0 );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, TrivialRcwaGroupOverZ );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
SetIsPerfectGroup( G, false );
SetIsSimpleGroup( G, false );
SetRepresentative( G, RcwaMapping( [ [ -1, 0, 1 ] ] ) );
SetName( G, "RCWA(Z)" );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M RCWACons( IsRcwaGroup, Integers^2 ) . . . . . . . . . . . . . RCWA( Z^2 )
##
## Returns the group which is formed by all bijective rcwa mappings of Z^2.
##
InstallMethod( RCWACons,
"natural RCWA(Z^2) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsRowModule ], 0,
function ( filter, R )
local G, id;
if not IsZxZ( R ) then TryNextMethod( ); fi;
id := IdentityRcwaMappingOfZxZ;
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZxZ and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, id );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalRCWA );
SetFilterObj( G, IsNaturalRCWA_ZxZ );
SetModulusOfRcwaMonoid( G, [ [ 0, 0 ], [ 0, 0 ] ] );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, TrivialRcwaGroupOverZxZ );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
SetRepresentative( G, RcwaMapping( R, [ [ 1, 0 ], [ 0, 1 ] ],
[ [ [ 0, 0 ], [ [ [ -1, 0 ], [ 0, -1 ] ], [ 0, 0 ], 1 ] ] ] ) );
SetName( G, "RCWA(Z^2)" );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M RCWACons( IsRcwaGroup, Z_pi( <pi> ) ) . . . . . . . . . . RCWA( Z_(pi) )
##
## Returns the group which is formed by all bijective rcwa mappings
## of Z_(pi).
##
InstallMethod( RCWACons,
"natural RCWA(Z_(pi)) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsZ_pi ], 0,
function ( filter, R )
local G, pi, id;
pi := NoninvertiblePrimes( R );
id := RcwaMapping( pi, [ [1,0,1] ] ); IsOne( id );
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZ_pi
and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, id );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalRCWA );
SetFilterObj( G, IsNaturalRCWA_Z_pi );
SetModulusOfRcwaMonoid( G, 0 );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetCentre( G, Group( id ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
SetRepresentative( G, -id );
SetName( G, Concatenation( "RCWA(", ViewString(R), ")" ) );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M RCWACons( IsRcwaGroup, PolynomialRing( GF( <q> ), 1 ) ) RCWA( GF(q)[x] )
##
## Returns the group which is formed by all bijective rcwa mappings
## of GF(q)[x].
##
InstallMethod( RCWACons,
"natural RCWA(GF(q)[x]) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsUnivariatePolynomialRing ], 0,
function ( filter, R )
local G, q, id, rep;
q := Size( CoefficientsRing( R ) );
id := RcwaMapping( q, One(R), [ [1,0,1] * One(R) ] ); IsOne( id );
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverGFqx
and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, id );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalRCWA );
SetFilterObj( G, IsNaturalRCWA_GFqx );
SetModulusOfRcwaMonoid( G, Zero( R ) );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, Group( id ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
rep := ClassTransposition(SplittedClass(R,q){[1..2]});
SetRepresentative( G, rep );
SetName( G, Concatenation( "RCWA(GF(", String(q), ")[",
String(IndeterminatesOfPolynomialRing(R)[1]),"])" ) );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#F RCWA( <R> ) . . . . . . . . . . . . . . . . . . . . . . . . . . RCWA( R )
##
InstallGlobalFunction( RCWA, R -> RCWACons( IsRcwaGroup, R ) );
#############################################################################
##
#S The construction of the groups CT(R) ////////////////////////////////////
#S generated by all class transpositions. //////////////////////////////////
##
#############################################################################
#############################################################################
##
#M CTCons( IsRcwaGroup, Integers ) . . . . . . . . . . . . . . . . . CT( Z )
##
## Returns the simple group which is generated
## by the set of all class transpositions of Z.
##
InstallMethod( CTCons,
"natural CT(Z) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsIntegers ], 0,
function ( filter, R )
local G, id;
id := IdentityRcwaMappingOfZ;
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZ and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, SparseRep( IdentityRcwaMappingOfZ ) );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalCT );
SetFilterObj( G, IsNaturalCT_Z );
SetModulusOfRcwaMonoid( G, 0 );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, SparseRep( TrivialRcwaGroupOverZ ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
SetIsPerfectGroup( G, true );
SetIsSimpleGroup( G, true );
SetRepresentative( G, SparseRep( ClassTransposition(0,2,1,2) ) );
SetSupport( G, Integers );
SetName( G, "CT(Z)" );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M CTCons( IsRcwaGroup, <P>, Integers ) . . . . . . . . . . . . . CT( P, Z )
##
## Returns the group which is generated by the set of all
## class transpositions of Z which interchange residue classes whose
## moduli have only prime factors in the finite set <P>.
## In case 2 is an element of <P>, this group is simple.
##
InstallMethod( CTCons,
"natural CT(Z) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsList, IsIntegers ], 0,
function ( filter, P, R )
local G, id;
if not ForAll(P,IsPosInt) or not ForAll(P,IsPrimeInt)
then TryNextMethod(); fi;
if P = [] then return TrivialRcwaGroupOverZ; fi;
id := IdentityRcwaMappingOfZ;
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZ and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, SparseRep( IdentityRcwaMappingOfZ ) );
SetFilterObj( G, IsNaturalCTP_Z );
SetModulusOfRcwaMonoid( G, 0 );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetPrimeSet( G, P );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, true );
SetCentre( G, SparseRep( TrivialRcwaGroupOverZ ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
if 2 in P then
SetIsPerfectGroup( G, true );
SetIsSimpleGroup( G, true );
fi;
SetRepresentative( G, SparseRep(ClassTransposition(0,P[1],1,P[1])) );
SetSupport( G, Integers );
SetName( G, Concatenation( "CT_", String(P), "(Z)" ) );
SetStructureDescription( G, Name( G ) );
if P = [2] then # Higman-Thompson group / Thompson's group V
SetGeneratorsOfGroup(G,List([[0,2,1,2],[1,2,2,4],[0,2,1,4],[1,4,2,4]],
c->SparseRep(ClassTransposition(c))));
elif P = [3] then
SetGeneratorsOfGroup(G,List([[0,3,1,3],[1,3,2,3],[2,9,3,9],[5,9,6,9],
[2,3,3,9]],
c->SparseRep(ClassTransposition(c))));
elif P = [2,3] then
SetGeneratorsOfGroup(G,List([[0,2,1,2],[0,3,1,3],[1,3,2,3],
[0,2,1,4],[0,2,5,6],[0,3,1,6]],
c->SparseRep(ClassTransposition(c))));
fi;
return G;
end );
#############################################################################
##
#M CTCons( IsRcwaGroup, Integers^2 ) . . . . . . . . . . . . . . . CT( Z^2 )
##
## Returns the group which is generated by
## the set of all class transpositions of Z^2.
##
InstallMethod( CTCons,
"natural CT(Z^2) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsRowModule ], 0,
function ( filter, R )
local G, id;
if not IsZxZ(R) then TryNextMethod(); fi;
id := IdentityRcwaMappingOfZxZ;
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZxZ and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, IdentityRcwaMappingOfZxZ );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalCT );
SetFilterObj( G, IsNaturalCT_ZxZ );
SetModulusOfRcwaMonoid( G, [ [ 0, 0 ], [ 0, 0 ] ] );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, TrivialRcwaGroupOverZxZ );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
SetIsPerfectGroup( G, true );
SetIsSimpleGroup( G, true );
SetRepresentative( G, ClassTransposition([0,0],[[1,0],[0,2]],
[0,1],[[1,0],[0,2]]) );
SetSupport( G, R );
SetName( G, "CT(Z^2)" );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M CTCons( IsRcwaGroup, Z_pi( <pi> ) ) . . . . . . . . . . . . CT( Z_(pi) )
##
## Returns the group which is generated by
## the set of all class transpositions of Z_(pi).
##
InstallMethod( CTCons,
"natural CT(Z_(pi)) (RCWA)", ReturnTrue,
[ IsRcwaGroup, IsZ_pi ], 0,
function ( filter, R )
local G, pi, id, rep;
pi := NoninvertiblePrimes( R );
id := RcwaMapping( pi, [ [1,0,1] ] ); IsOne( id );
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverZ_pi
and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, id );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalCT );
SetFilterObj( G, IsNaturalCT_Z_pi );
SetModulusOfRcwaMonoid( G, 0 );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetCentre( G, Group( id ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
rep := ClassTransposition(AllResidueClassesModulo(R,pi[1]){[1..2]});
SetRepresentative( G, rep );
SetSupport( G, R );
SetName( G, Concatenation( "CT(", ViewString(R), ")" ) );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#M CTCons( IsRcwaGroup, PolynomialRing( GF( <q> ), 1 ) ) . . CT( GF(q)[x] )
##
## Returns the group which is generated by
## the set of all class transpositions of GF(q)[x].
##
InstallMethod( CTCons,
"natural CT(GF(q)[x]) (RCWA)", true,
[ IsRcwaGroup, IsUnivariatePolynomialRing ], 0,
function ( filter, R )
local G, q, id, rep;
q := Size( CoefficientsRing( R ) );
id := RcwaMapping( q, One(R), [ [1,0,1] * One(R) ] ); IsOne( id );
G := Objectify( NewType( FamilyObj( Group( id ) ),
IsRcwaGroupOverGFqx
and IsAttributeStoringRep ),
rec( ) );
SetIsTrivial( G, false );
SetOne( G, id );
SetFilterObj( G, IsNaturalRCWA_OR_CT );
SetFilterObj( G, IsNaturalCT );
SetFilterObj( G, IsNaturalCT_GFqx );
SetModulusOfRcwaMonoid( G, Zero( R ) );
SetMultiplier( G, infinity );
SetDivisor( G, infinity );
SetIsFinite( G, false );
SetSize( G, infinity );
SetIsFinitelyGeneratedGroup( G, false );
SetCentre( G, Group( id ) );
SetIsAbelian( G, false );
SetIsSolvableGroup( G, false );
rep := ClassTransposition(SplittedClass(R,q){[1..2]});
SetRepresentative( G, rep );
SetSupport( G, R );
SetName( G, Concatenation( "CT(GF(", String(q), ")[",
String(IndeterminatesOfPolynomialRing(R)[1]),"])" ) );
SetStructureDescription( G, Name( G ) );
return G;
end );
#############################################################################
##
#F CT( <R> ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CT(R)
##
InstallGlobalFunction( CT,
function ( arg )
local P, R;
if Length(arg) = 1 then
R := arg[1];
return CTCons( IsRcwaGroup, R );
elif Length(arg) = 2 then
P := arg[1];
R := arg[2];
return CTCons( IsRcwaGroup, P, R );
else Error("usage: CT( [ <P>, ], <R> )"); fi;
end );
#############################################################################
##
#M Display( <G> ) . . . . . . . . . . . . . . . . . . for RCWA(R) and CT(R)
##
InstallMethod( Display,
"for RCWA(R) and CT(R) (RCWA)", true,
[ IsNaturalRCWA_OR_CT ], 0,
function ( G ) Print( Name( G ), "\n" ); end );
#############################################################################
##
#S The membership- / subgroup test for RCWA(R) and CT(R). //////////////////
##
#############################################################################
#############################################################################
##
#M \in( <g>, RCWA( <R> ) ) . . . . . . . . . for an rcwa mapping and RCWA(R)
##
InstallMethod( \in,
"for an rcwa mapping and RCWA(R) (RCWA)", ReturnTrue,
[ IsRcwaMapping, IsNaturalRCWA ], 100,
function ( g, RCWA_R )
return FamilyObj(g) = FamilyObj(One(RCWA_R)) and IsBijective(g);
end );
#############################################################################
##
#M \in( <g>, CT( <R> ) ) . . . . . . . . . . . for an rcwa mapping and CT(R)
##
InstallMethod( \in,
"for an rcwa mapping and CT(R) (RCWA)", ReturnTrue,
[ IsRcwaMapping, IsNaturalCT ], 100,
function ( g, CT_R )
local R, numres;
if FamilyObj(g) <> FamilyObj(One(CT_R)) or not IsBijective(g)
then return false; elif IsOne(g) then return true; fi;
R := Support(CT_R);
if IsIntegers(R) or IsZ_pi(R) then
if not IsClassWiseOrderPreserving(g) then return false; fi;
if IsIntegers(R) and not IsSignPreserving(g) then return false; fi;
if Minimum([0..Mod(g)-1]^g) < 0
or Maximum([-Mod(g)..-1]^g) >= 0
then return false; fi;
elif IsZxZ(R) then
numres := AbsInt(DeterminantMat(Modulus(g)));
if not IsClassWiseOrderPreserving(g)
or not ForAll(Coefficients(g),c->IsUpperTriangularMat(c[1]))
or not ForAll(Coefficients(g),c->c[1][1][1] > 0)
or not ForAll(Cartesian([0..numres-1],[-numres..numres]),
t->t^g*[1,0]>=0)
then return false; fi;
fi;
if ForAll(FactorizationIntoCSCRCT(g),
gi -> IsClassTransposition(gi)
or IsPrimeSwitch(gi) or IsPrimeSwitch(gi^-1))
then return true; fi;
TryNextMethod();
end );
#############################################################################
##
#M \in( <g>, CT( <P>, Integers ) ) . . for an rcwa mapping of Z and CT_P(Z)
##
InstallMethod( \in,
"for an rcwa mapping and CT_P(Z) (RCWA)", ReturnTrue,
[ IsRcwaMappingOfZ, IsNaturalCTP_Z ], 100,
function ( g, CTP_Z )
local R, numres;
if not IsClassWiseOrderPreserving(g) or not IsSignPreserving(g)
or not IsSubset(PrimeSet(CTP_Z),PrimeSet(g))
then return false; fi;
if ForAll( FactorizationIntoCSCRCT(g),
gi -> ( IsClassTransposition(gi)
or IsPrimeSwitch(gi) or IsPrimeSwitch(gi^-1) )
and IsSubset( PrimeSet(CTP_Z), PrimeSet(gi) ) )
then return true; fi;
TryNextMethod();
end );
#############################################################################
##
#M IsSubset( RCWA( <R> ), G ) . . . . . . . . for RCWA(R) and an rcwa group
##
InstallMethod( IsSubset,
"for RCWA(R) and an rcwa group (RCWA)", ReturnTrue,
[ IsNaturalRCWA, IsRcwaGroup ], SUM_FLAGS,
function ( RCWA_R, G )
return FamilyObj(One(RCWA_R)) = FamilyObj(One(G));
end );
#############################################################################
##
#M IsSubset( CT( Integers ), G ) . . . . for CT(Z) and an rcwa group over Z
##
InstallMethod( IsSubset,
"for CT(Z) and an rcwa group over Z (RCWA)", ReturnTrue,
[ IsNaturalCT_Z, IsRcwaGroupOverZ and HasGeneratorsOfGroup ], SUM_FLAGS,
function ( CT_Z, G )
if not IsClassWiseOrderPreserving(G)
or ForAny(GeneratorsOfGroup(G),g->Determinant(g)<>0)
or Minimum(Ball(G,0,4,OnPoints)) < 0
then return false; fi;
return ForAll(GeneratorsOfGroup(G),g->g in CT_Z);
end );
#############################################################################
##
#M IsSubset( CT( <R> ), G ) . . . . . . . . . . for CT(R) and an rcwa group
##
InstallMethod( IsSubset,
"for CT(R) and an rcwa group (RCWA)", ReturnTrue,
[ IsNaturalCT, IsRcwaGroup and HasGeneratorsOfGroup ], 100,
function ( CT_R, G )
if FamilyObj(One(G)) <> FamilyObj(One(CT_R)) then return false; fi;
return ForAll(GeneratorsOfGroup(G),g->g in CT_R);
end );
#############################################################################
##
#M IsSubset( CT( <R> ), RCWA( <R> ) ) . . . . . . . . for CT(R) and RCWA(R)
##
## Note that it is currently not known e.g. whether
## CT(GF(2)[x]) = RCWA(GF(2)[x]) or not.
##
InstallMethod( IsSubset,
"for CT(R) and RCWA(R) (RCWA)", ReturnTrue,
[ IsNaturalCT, IsNaturalRCWA ], SUM_FLAGS,
function ( CT_R, RCWA_R )
if FamilyObj(One(CT_R)) <> FamilyObj(One(RCWA_R)) then return false; fi;
if IsRcwaGroupOverZOrZ_pi(RCWA_R) then return false; fi;
if not IsTrivial(Units(CoefficientsRing(Source(One(RCWA_R)))))
then return false; fi;
Error("sorry - this is still an open question!");
return fail;
end );
#############################################################################
##
#S Counting / enumerating certain elements of RCWA(R) and CT(R). ///////////
##
#############################################################################
#############################################################################
##
#V NrElementsOfCTZWithGivenModulus
##
## The numbers of elements of CT(Z) of given order m <= 24, subject to the
## conjecture that CT(Z) is the setwise stabilizer of N_0 in RCWA(Z).
##
BindGlobal( "NrElementsOfCTZWithGivenModulus",
[ 1, 1, 17, 238, 4679, 115181, 3482639, 124225680, 5114793582, 238618996919,
12441866975999, 716985401817362, 45251629386163199, 3104281120750130159,
229987931693135611303, 18301127616460012222080, 1556718246822087917567999,
140958365897067252175843218, 13537012873511994353270783999,
1374314160482820530097944198162, 147065220260069766956421116517343,
16544413778663040175990602280223999, 1951982126641242370890486633922559999,
241014406219744996673035312579811441520 ] );
#############################################################################
##
#F AllElementsOfCTZWithGivenModulus( m ) . elements of CT(Z) with modulus m
##
## Assumes the conjecture that CT(Z) is the setwise stabilizer of the
## nonnegative integers in RCWA(Z).
##
InstallGlobalFunction( AllElementsOfCTZWithGivenModulus,
function ( m )
local elems, source, ranges, range, perms, g;
if not IsPosInt(m) then
Error("usage: AllElementsOfCTZWithGivenModulus( <m> ) ",
"for a positive integer m\n");
fi;
if m = 1 then return [ IdentityRcwaMappingOfZ ]; fi;
source := AllResidueClassesModulo(Integers,m);
ranges := PartitionsIntoResidueClasses(Integers,m);
perms := AsList(SymmetricGroup(m));
elems := [];
for range in ranges do
for g in perms do
Add(elems,RcwaMapping(source,Permuted(range,g)));
od;
od;
return Filtered(Set(elems),elm->Mod(elm)=m);
end );
#############################################################################
##
#S Factoring elm's of RCWA(R) into class shifts/reflections/transpositions.
##
#############################################################################
#############################################################################
##
#M Factorization( RCWA( <R> ), <g> ) . for RCWA( R ) and an element thereof
##
InstallMethod( Factorization,
"into class shifts / reflections / transpositions (RCWA)",
IsCollsElms, [ IsNaturalRCWA, IsRcwaMapping ], 0,
function(RCWA_R,g) return FactorizationIntoCSCRCT(g); end );
#############################################################################
##
#M Factorization( CT( <R> ), <g> ) . . . for CT( R ) and an element thereof
##
InstallMethod( Factorization,
"into class shifts / reflections / transpositions (RCWA)",
IsCollsElms, [ IsNaturalCT, IsRcwaMapping ], 0,
function( CT_R, g )
if g in CT_R then return FactorizationIntoCSCRCT(g);
else return fail; fi;
end );
#############################################################################
##
#S Decomposing elements of CT(Z). //////////////////////////////////////////
##
#############################################################################
#############################################################################
##
#A DecompositionIntoPermutationalAndOrderPreservingElement( <g> )
##
InstallMethod( DecompositionIntoPermutationalAndOrderPreservingElement,
"for elements of CT(Z) (RCWA)", true, [ IsRcwaMappingOfZ ], 0,
function ( g )
local a, b, cls, P, q;
if not IsBijective(g) or not IsSignPreserving(g)
then TryNextMethod(); fi;
q := Product(PrimeSet(g));
cls := AllResidueClassesModulo(Mod(g));
SortParallel(List(cls,cl->CoefficientsQadic(Residue(cl),q)),cls);
P := cls^g;
SortParallel(List(P,cl->CoefficientsQadic(Residue(cl),q)),P);
b := RcwaMapping(cls,P);
a := g/b;
return [ a, b ];
end );
############################################################################
##
#S The epimorphisms RCWA(Z) -> C2 and RCWA+(Z) -> (Z,+). ///////////////////
##
#############################################################################
#############################################################################
##
#M Sign( <f> ) . . . . . . . . . . . for rcwa mappings of Z in standard rep.
##
InstallMethod( Sign,
"for rcwa mappings of Z in standard rep. (RCWA)",
true, [ IsRcwaMappingOfZInStandardRep ], 0,
function ( f )
local m, c, sgn, r, ar, br, cr;
if not IsBijective(f) then return fail; fi;
m := Modulus(f); c := Coefficients(f);
sgn := 0;
for r in [0..m-1] do
ar := c[r+1][1]; br := c[r+1][2]; cr := c[r+1][3];
sgn := sgn + br/AbsInt(ar);
if ar < 0 then sgn := sgn + (m - 2*r); fi;
od;
sgn := (-1)^(sgn/m);
return sgn;
end );
#############################################################################
##
#M Sign( <f> ) . . . . . . . . . . . . for rcwa mappings of Z in sparse rep.
##
InstallMethod( Sign,
"for rcwa mappings of Z in sparse rep. (RCWA)",
true, [ IsRcwaMappingOfZInSparseRep ], 0,
function ( f )
local sgn, c, r, m, a, b;
if not IsBijective(f) then return fail; fi;
sgn := 0;
for c in f!.coeffs do
r := c[1]; m := c[2]; a := c[3]; b := c[4];
sgn := sgn + b/(m*AbsInt(a));
if a < 0 then sgn := sgn + (m - 2*r)/m; fi;
od;
sgn := (-1)^sgn;
return sgn;
end );
#############################################################################
##
#M Determinant( <f> ) . . . . . . . for rcwa mappings of Z in standard rep.
##
InstallMethod( Determinant,
"for rcwa mappings of Z in standard rep. (RCWA)",
true, [ IsRcwaMappingOfZInStandardRep ], 0,
function ( f )
if Mult(f) = 0 then return fail; fi;
return Sum(List(Coefficients(f),c->c[2]/AbsInt(c[1])))/Modulus(f);
end );
#############################################################################
##
#M Determinant( <f> ) . . . . . . . . for rcwa mappings of Z in sparse rep.
##
InstallMethod( Determinant,
"for rcwa mappings of Z in sparse rep. (RCWA)",
true, [ IsRcwaMappingOfZInSparseRep ], 0,
function ( f )
if Mult(f) = 0 then return fail; fi;
return Sum(List(Coefficients(f),c->c[4]/AbsInt(c[3]*c[2])));
end );
#############################################################################
##
#M Determinant( <f>, <S> ) . for rcwa mappings on unions of residue classes
##
InstallOtherMethod( Determinant,
"for rcwa mappings on unions of residue classes (RCWA)",
true, [ IsRcwaMappingOfZInStandardRep,
IsResidueClassUnionOfZ ], 0,
function ( f, S )
local m, c, r, cl;
m := Modulus(f); c := Coefficients(f);
return Sum(List([1..m],
r->Density(Intersection(S,ResidueClass(Integers,m,r-1)))
*c[r][2]/AbsInt(c[r][1])));
end );
#############################################################################
##
#M Determinant( <f>, <S> ) . for rcwa mappings on unions of residue classes
##
InstallOtherMethod( Determinant,
"for rcwa mappings on unions of residue classes (RCWA)",
true, [ IsRcwaMappingOfZInSparseRep,
IsResidueClassUnionOfZ ], 0,
function ( f, S )
return Sum(List(f!.coeffs,
c -> Density(Intersection(S,ResidueClass(c[1],c[2])))
* c[4]/AbsInt(c[3])));
end );
#############################################################################
##
#M SignInOddCTPZ( <g> ) . . . . . . . . for elements of CT_P(Z), 2 \notin P
##
InstallMethod( SignInOddCTPZ,
"for elements of CT_P(Z) where P does not contain 2 (RCWA)",
true, [ IsRcwaMappingOfZ ], 0,
function ( g )
local factors;
if not IsBijective(g) or not IsSignPreserving(g) or 2 in PrimeSet(g)
then TryNextMethod(); fi;
factors := DecompositionIntoPermutationalAndOrderPreservingElement(g);
return SignPerm(Permutation(factors[1],AllResidueClassesModulo(Mod(g))));
end );
#############################################################################
##
#S Generating random elements of RCWA(R), CT(R) and other rcwa groups. /////
##
#############################################################################
#############################################################################
##
#M Random( RCWA( Integers ) ) . . . . . . . . a `random' element of RCWA(Z)
##
InstallMethod( Random,
"for RCWA(Z) (RCWA)", true, [ IsNaturalRCWA_Z ], SUM_FLAGS,
function ( RCWA_Z )
local result, ClassTranspositions, ClassShifts, ClassReflections,
maxmodct, maxmodcscr, noct, nocs, nocr, genfactors, classes,
tame, integralpairs, g, i;
tame := ValueOption("IsTame") = true;
noct := GetOption("NumberOfCTs",Random([0..2]),IsInt);
nocs := GetOption("NumberOfCSs",Random([0..3]),IsInt);
nocr := GetOption("NumberOfCRs",Random([0..3]),IsInt);
maxmodcscr := GetOption("ModulusBoundForCSCRs",6,IsPosInt);
maxmodct := GetOption("ModulusBoundForCTs",14,IsPosInt);
if maxmodct <> CLASS_PAIRS_LARGE[1] then
MakeReadWriteGlobal("CLASS_PAIRS_LARGE");
CLASS_PAIRS_LARGE := [maxmodct,ClassPairs(maxmodct)];
MakeReadOnlyGlobal("CLASS_PAIRS_LARGE");
fi;
classes := Combinations([1..maxmodcscr],2)-1;
ClassTranspositions := List([1..noct],i->Random(CLASS_PAIRS[2]));
if Random([1..4]) = 1
then Add(ClassTranspositions,Random(CLASS_PAIRS_LARGE[2])); fi;
ClassShifts := List([1..nocs],i->Random(classes));
ClassReflections := List([1..nocr],i->Random(classes));
ClassTranspositions := List(ClassTranspositions,ClassTransposition);
ClassShifts := List(ClassShifts,t->ClassShift(t)^Random([-1,1]));
ClassReflections := List(ClassReflections,ClassReflection);
genfactors := Concatenation(ClassTranspositions,ClassShifts,
ClassReflections);
result := Product(genfactors);
if result = 1 then result := One(RCWA_Z); fi;
if not tame then SetFactorizationIntoCSCRCT(result,genfactors); fi;
if tame then
integralpairs := Filtered(CLASS_PAIRS[2],t->t[2]=t[4]);
g := One(RCWA_Z);
for i in [1..Random([1..3])] do
g := g * ClassTransposition(Random(integralpairs));
od;
result := g^result;
SetIsTame(result,true);
SetOrder(result,Order(g));
fi;
IsBijective(result);
return result;
end );
#############################################################################
##
#M Random( RCWA( <R> ) ) . . . . . . . . . . . a `random' element of RCWA(R)
##
InstallMethod( Random,
"for RCWA(R) (RCWA)", true, [ IsNaturalRCWA ], 0,
function ( RCWA_R )
return Random( CT( Support( RCWA_R ) ) );
end );
#############################################################################
##
#M Random( CT( Integers ) ) . . . . . . . . . . a `random' element of CT(Z)
##
InstallMethod( Random,
"for CT(Z) (RCWA)", true, [ IsNaturalCT_Z ], SUM_FLAGS,
function ( CT_Z )
local noct;
noct := GetOption("NumberOfCTs",RootInt(Random([0..125]),3),IsInt);
return Random(RCWA(Integers):NumberOfCTs:=noct,NumberOfCSs:=0,
NumberOfCRs:=0);
end );
#############################################################################
##
#M Random( CT( <R> ) ) . . . . . . . . . . . . . a `random' element of CT(R)
##
InstallMethod( Random,
"for CT(R) (RCWA)", true, [ IsNaturalCT ], 0,
function ( CT_R )
local result, R, tame, noct, ClassTranspositions,
classpairs, integralpairs, maxm, x, g, i;
if IsNaturalCT_Z(CT_R) # For CT(Z) there is a better method available.
then TryNextMethod(); fi;
R := Support(CT_R);
tame := ValueOption("IsTame") = true;
noct := ValueOption("NumberOfCTs");
if noct = fail then if not tame then noct := RootInt(Random([0..100]),3);
else noct := Random([0..2]); fi; fi;
if IsZ_pi(R) then
maxm := Maximum(NoninvertiblePrimes(R));
maxm := Maximum(maxm,Minimum(NoninvertiblePrimes(R))^2);
classpairs := List(ClassPairs(R,maxm),
t->[ResidueClass(R,t[2],t[1]),
ResidueClass(R,t[4],t[3])]);
elif IsFiniteFieldPolynomialRing(R) then
x := IndeterminatesOfPolynomialRing(R)[1];
classpairs := ClassPairs(R,x^3);
fi;
ClassTranspositions := List([1..noct],i->Random(classpairs));
ClassTranspositions := List(ClassTranspositions,ClassTransposition);
result := Product(ClassTranspositions);
if result = 1 then result := One(CT_R); fi;
if not tame
then SetFactorizationIntoCSCRCT(result,ClassTranspositions); fi;
if tame then
integralpairs := Filtered(classpairs,t->t[2]=t[4]);
g := One(CT_R);
for i in [1..Random([1..3])] do
g := g * ClassTransposition(Random(integralpairs));
od;
result := g^result;
SetIsTame(result,true);
SetOrder(result,Order(g));
fi;
IsBijective(result);
return result;
end );
#############################################################################
##
#M Random( <G>, <n> ) . . for finitely generated rcwa group and word length
##
InstallOtherMethod( Random,
"for rcwa group and word length (RCWA)",
ReturnTrue, [ IsRcwaGroup, IsPosInt ], 0,
function ( G, n )
local gens, g, gi, last_gi, i;
if not HasGeneratorsOfGroup(G) or Length(GeneratorsOfGroup(G)) <= 1
then TryNextMethod(); fi;
if ForAll(GeneratorsOfGroup(G),g->HasIsClassTransposition(g)
and IsClassTransposition(g))
then gens := GeneratorsOfGroup(G);
else gens := Set(GeneratorsAndInverses(G)); fi;
g := One(G); last_gi := One(G);
for i in [1..n] do
repeat gi := Random(gens); until gi <> last_gi^-1;
g := g * gi;
last_gi := gi;
od;
return g;
end );
#############################################################################
##
#S The action of RCWA(R) and CT(R) on R. ///////////////////////////////////
##
#############################################################################
#############################################################################
##
#M RepresentativeActionOp( RCWA( <R> ), <n1>, <n2>, <act> )
##
InstallMethod( RepresentativeActionOp,
"for RCWA(Z) and two integers (RCWA)", ReturnTrue,
[ IsNaturalRCWA, IsInt, IsInt, IsFunction ], 0,
function ( RCWA_R, n1, n2, act )
local R;
if act <> OnPoints then TryNextMethod(); fi;
R := Support(RCWA_R);
if Characteristic(R) = 0
then return ClassShift(R)^(n2-n1);
else return RcwaMapping(R,One(R),[[One(R),n2-n1,One(R)]]); fi;
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA(Integers), <l1>, <l2>, <act> )
##
InstallMethod( RepresentativeActionOp,
"for RCWA(Z) and two k-tuples of integers (RCWA)", ReturnTrue,
[ IsNaturalRCWA_Z, IsList, IsList, IsFunction ], 0,
function ( RCWA_Z, l1, l2, act )
local g, range, perm, exp, points, n;
points := Union(l1,l2);
if not IsSubset(Integers,points) then return fail; fi;
range := [1..Maximum(points)-Minimum(points)+1]; n := Length(range);
exp := -Minimum(points)+1;
perm := RepresentativeAction(SymmetricGroup(n),l1+exp,l2+exp,act);
if perm = fail then return fail; fi;
g := RcwaMapping(perm,range);
return g^(ClassShift(0,1)^-exp);
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA( <R> ), <S1>, <S2>, <act> )
##
## Returns an rcwa mapping <g> of <R> which maps <S1> to <S2>.
## The sets <S1> and <S2> must be unions of residue classes of <R>.
## The argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
"for RCWA(R) and two residue class unions (RCWA)",
ReturnTrue,
[ IsNaturalRCWA, IsResidueClassUnion,
IsResidueClassUnion, IsFunction ], 0,
function ( RCWA_R, S1, S2, act )
local Refine, Refinement, R, S, C, g;
Refinement := function ( cls, lng )
local m, splitcl, parts;
while Length(cls) <> lng do
m := Minimum(List(cls,Modulus));
splitcl := First(cls,cl->Modulus(cl)=m); RemoveSet(cls,splitcl);
parts := SplittedClass(splitcl,SizeOfSmallestResidueClassRing(R));
if Length(parts) > lng - Length(cls) + 1 then return fail; fi;
cls := Union(cls,parts);
od;
return cls;
end;
Refine := function ( S )
if Length(S[1]) > Length(S[2])
then S[2] := Refinement(S[2],Length(S[1]));
elif Length(S[2]) > Length(S[1])
then S[1] := Refinement(S[1],Length(S[2])); fi;
end;
R := Support(RCWA_R);
if not IsSubset(R,S1) or not IsSubset(R,S2) then return fail; fi;
S := List([S1,S2],AsUnionOfFewClasses);
C := List([S1,S2],Si->AsUnionOfFewClasses(Difference(R,Si)));
Refine(S); Refine(C);
if fail in S or fail in C then return fail; fi;
g := RcwaMapping(Concatenation(S[1],C[1]),Concatenation(S[2],C[2]));
return g;
end );
#############################################################################
##
#M RepresentativeActionOp( CT( <R> ), <S1>, <S2>, <act> )
##
## Returns an element <g> of CT(<R>) which maps <S1> to <S2>.
## The sets <S1> and <S2> must be unions of residue classes of <R>.
## The argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
"for CT(R) and two residue class unions (RCWA)",
ReturnTrue,
[ IsNaturalCT, IsResidueClassUnion,
IsResidueClassUnion, IsFunction ], 0,
function ( CT_R, S1, S2, act )
local Refine, Refinement, R, S, D1, D2, length, factors, g;
Refinement := function ( cls, lng )
local m, splitcl, parts;
while Length(cls) <> lng do
m := Minimum(List(cls,Modulus));
splitcl := First(cls,cl->Modulus(cl)=m); RemoveSet(cls,splitcl);
parts := SplittedClass(splitcl,SizeOfSmallestResidueClassRing(R));
if Length(parts) > lng - Length(cls) + 1 then return fail; fi;
cls := Union(cls,parts);
od;
return cls;
end;
Refine := function ( S )
local maxlength, i;
maxlength := Maximum(List(S,Length));
for i in [1..Length(S)] do
if Length(S[i]) < maxlength
then S[i] := Refinement(S[i],maxlength); fi;
od;
end;
R := Support(CT_R);
if not IsSubset(R,S1) or not IsSubset(R,S2) then return fail; fi;
if IsSubset(S2,S1) then D1 := Difference(S2,S1);
else D1 := Difference(R,S1); fi;
D2 := Difference(R,Union(D1,S2));
S := List([S1,D1,D2,S2],AsUnionOfFewClasses);
Refine(S); if fail in S then return fail; fi;
length := Length(S[1]);
factors := List([1..3],
i->List([1..length],
j->ClassTransposition(S[i][j],S[i+1][j])));
factors := Flat(factors);
g := Product(Flat(factors));
SetFactorizationIntoCSCRCT(g,factors);
return g;
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA( Integers ), <P1>, <P2>, <act> )
##
## Returns an rcwa mapping <g> which maps the partition <P1> to the
## partition <P2> and which is
##
## - affine on the elements of <P1>, if the option `IsTame' is not set
## and all elements of both partitions <P1> and <P2> are single residue
## classes, and
##
## - tame, if the option `IsTame' is set.
##
## The arguments <P1> and <P2> must be partitions of Z into equally many
## disjoint residue class unions, and the argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
"for RCWA(Z) and two class partitions (RCWA)", true,
[ IsNaturalRCWA_Z, IsList, IsList, IsFunction ], 100,
function ( RCWA_Z, P1, P2, act )
local SplitClass, g, tame, m, c, P, min, minpos, Phat, Buckets, b,
k, ri, mi, rtildei, mtildei, ar, br, cr, r, i, j;
SplitClass := function ( i, j )
local mods, pos, m, r, mtilde, r1, r2, j2, pos2;
mods := List(Buckets[i][j],Modulus);
m := Minimum(mods);
pos := Position(mods,m);
r := Residues(Buckets[i][j][pos])[1];
mtilde := 2*m; r1 := r; r2 := r + m;
Buckets[i][j] := Union(Difference(Buckets[i][j],[Buckets[i][j][pos]]),
[ResidueClass(Integers,mtilde,r1),
ResidueClass(Integers,mtilde,r2)]);
j2 := Filtered([1..k],
j->Position(Buckets[3-i][j],
ResidueClass(Integers,m,r))<>fail)[1];
pos2 := Position(Buckets[3-i][j2],ResidueClass(Integers,m,r));
Buckets[3-i][j2] := Union(Difference( Buckets[3-i][j2],
[Buckets[3-i][j2][pos2]]),
[ResidueClass(Integers,mtilde,r1),
ResidueClass(Integers,mtilde,r2)]);
end;
if Length(P1) <> Length(P2)
or not ForAll(P1,IsResidueClassUnionOfZ)
or not ForAll(P2,IsResidueClassUnionOfZ)
or [Union(List(P1,IncludedElements)),Union(List(P1,ExcludedElements)),
Union(List(P2,IncludedElements)),Union(List(P2,ExcludedElements))]
<> [[],[],[],[]]
or Sum(List(P1,Density)) <> 1 or Sum(List(P2,Density)) <> 1
or Union(P1) <> Integers or Union(P2) <> Integers
then TryNextMethod(); fi;
if not ForAll(P1,IsResidueClass) or not ForAll(P2,IsResidueClass) then
P1 := List(P1,AsUnionOfFewClasses);
P2 := List(P2,AsUnionOfFewClasses);
P := [P1,P2];
for j in [1..Length(P1)] do
if Length(P[1][j]) <> Length(P[2][j]) then
if Length(P[1][j]) < Length(P[2][j]) then i := 1; else i := 2; fi;
repeat
min := Minimum(List(P[i][j],Modulus));
minpos := Position(List(P[i][j],Modulus),min);
P[i][j][minpos] := SplittedClass(P[i][j][minpos],2);
P[i][j] := Flat(P[i][j]);
until Length(P[1][j]) = Length(P[2][j]);
fi;
od;
P1 := Flat(P[1]); P2 := Flat(P[2]);
fi;
if ValueOption("IsTame") <> true then
g := RcwaMapping(P1,P2);
else
k := Length(P1);
m := Lcm(List(Union(P1,P2),Modulus));
P := [P1,P2];
Phat := List([0..m-1],r->ResidueClass(Integers,m,r));
Buckets := List([1..2],i->List([1..k],j->Filtered(Phat,
cl->Residues(cl)[1] mod Modulus(P[i][j]) =
Residues(P[i][j])[1])));
repeat
for i in [1..k] do
b := [Buckets[1][i],Buckets[2][i]];
if Length(b[2]) > Length(b[1]) then
for j in [1..Length(b[2])-Length(b[1])] do
SplitClass(1,i);
od;
elif Length(b[1]) > Length(b[2]) then
for j in [1..Length(b[1])-Length(b[2])] do
SplitClass(2,i);
od;
fi;
od;
until ForAll([1..k],i->Length(Buckets[1][i]) = Length(Buckets[2][i]));
g := RcwaMapping(Flat(Buckets[1]),Flat(Buckets[2]));
SetIsTame(g,true); SetRespectedPartition(g,Set(Flat(Buckets[1])));
fi;
return g;
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA( <R> ), <P1>, <P2>, <act> )
##
## Returns an rcwa mapping <g> which maps the partition <P1> to the
## partition <P2> and which is affine on the elements of <P1>.
##
## The arguments <P1> and <P2> must be partitions of <R> into equally
## many residue classes, and the argument <act> is ignored.
##
InstallMethod( RepresentativeActionOp,
"for RCWA(<R>) and two class partitions (RCWA)", true,
[ IsNaturalRCWA, IsList, IsList, IsFunction ], 0,
function ( RCWA_R, P1, P2, act )
local R, g;
R := Support(RCWA_R);
if Length(P1) <> Length(P2)
or not ForAll(Union(P1,P2),IsResidueClass)
or not ForAll(Union(P1,P2),cl->IsSubset(R,cl))
or not ForAll([P1,P2],P->Sum(List(P,Density))=1)
or not ForAll([P1,P2],P->Union(P) = R)
then TryNextMethod(); fi;
return RcwaMapping(P1,P2);
end );
#############################################################################
##
#S Conjugacy of elements in RCWA(R) and CT(R). /////////////////////////////
##
#############################################################################
#############################################################################
##
#M IsConjugate( RCWA( Integers ), <f>, <g> )
##
## This method checks whether the `standard conjugates' of <f> and <g> are
## equal, if the mappings are tame, and looks for different lengths of short
## cycles otherwise. The latter will often not terminate. In particular this
## is the case if <f> and <g> are conjugate.
##
InstallMethod( IsConjugate,
"for two rcwa mappings of Z, in RCWA(Z) (RCWA)",
true, [ IsNaturalRCWA_Z, IsRcwaMappingOfZ,
IsRcwaMappingOfZ ], 0,
function ( RCWA_Z, f, g )
local maxlng;
if f = g then return true; fi;
if Order(f) <> Order(g) or IsTame(f) <> IsTame(g) then return false; fi;
if IsTame(f) then
return StandardConjugate(f) = StandardConjugate(g);
else
maxlng := 2;
repeat
if Collected(List(ShortCycles(f,maxlng),Length))
<> Collected(List(ShortCycles(g,maxlng),Length))
then return false; fi;
maxlng := maxlng * 2;
until false;
fi;
end );
#############################################################################
##
#M IsConjugate( RCWA( Z_pi( <pi> ) ), <f>, <g> )
##
## This method makes only trivial checks. It cannot confirm conjugacy
## unless <f> and <g> are equal.
##
InstallMethod( IsConjugate,
"for two rcwa mappings of Z_(pi) in RCWA(Z_(pi)) (RCWA)",
ReturnTrue, [ IsNaturalRCWA_Z_pi,
IsRcwaMappingOfZ_pi, IsRcwaMappingOfZ_pi ], 0,
function ( RCWA_Z_pi, f, g )
local maxlng;
if not f in RCWA_Z_pi or not g in RCWA_Z_pi then return fail; fi;
if f = g then return true; fi;
if Order(f) <> Order(g) or IsTame(f) <> IsTame(g) then return false; fi;
maxlng := 2;
repeat
if Collected(List(ShortCycles(f,maxlng),Length))
<> Collected(List(ShortCycles(g,maxlng),Length))
then return false; fi;
maxlng := maxlng * 2;
until false;
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA( Integers ), <f>, <g>, <act> )
##
## This method is for tame rcwa mappings of Z under the conjugation action
## of RCWA(Z). It returns an rcwa mapping <h> such that <f>^<h> = <g> in
## case such a mapping exists and fail otherwise. The action <act> must be
## `OnPoints'.
##
InstallMethod( RepresentativeActionOp,
"for RCWA(Z) and two tame rcwa mappings of Z (RCWA)", true,
[ IsNaturalRCWA_Z, IsRcwaMappingOfZ, IsRcwaMappingOfZ,
IsFunction ], 0,
function ( RCWA_Z, f, g, act )
if act <> OnPoints then TryNextMethod(); fi;
if f = g then return One(f); fi;
if not ForAll([f,g],IsTame) then TryNextMethod(); fi;
if Order(f) <> Order(g) then return fail; fi;
if StandardConjugate(f) <> StandardConjugate(g) then return fail; fi;
return StandardizingConjugator(f) * StandardizingConjugator(g)^-1;
end );
#############################################################################
##
#M RepresentativeActionOp( RCWA( Integers ), <f>, <g>, <act> )
##
## This method is for tame rcwa mappings of Z under the conjugation action
## of RCWA(Z). It covers the special case of products of the same numbers of
## class shifts, inverses of class shifts, class reflections and class
## transpositions, each, whose supports are pairwise disjoint and do not
## entirely cover Z up to a finite complement.
##
InstallMethod( RepresentativeActionOp,
"for RCWA(Z) and products of disjoint CS/CR/CT (RCWA)", true,
[ IsNaturalRCWA_Z, IsRcwaMappingOfZ, IsRcwaMappingOfZ,
IsFunction ], 100,
function ( RCWA_Z, f, g, act )
local RefinedPartition, Sorted, maps, facts, P, l, sigma, i;
RefinedPartition := function ( P, k )
local l, mods, min, pos;
P := ShallowCopy(P); l := Length(P);
while l < k do
mods := List(P,Modulus);
min := Minimum(mods);
pos := Position(mods,min);
P[pos] := SplittedClass(P[pos],2);
P := Flat(P);
l := l + 1;
od;
return P;
end;
Sorted := l -> [Filtered(l,fact->IsClassShift(fact)
or IsClassShift(fact^-1)),
Filtered(l,IsClassReflection),
Filtered(l,IsClassTransposition)];
if act <> OnPoints then TryNextMethod(); fi;
if f = g then return One(f); fi;
if not ForAll([f,g],IsTame) then TryNextMethod(); fi;
if Order(f) <> Order(g) then return fail; fi;
maps := [f,g];
facts := List(maps,FactorizationIntoCSCRCT);
if Length(facts[1]) <> Length(facts[2])
or 1 in List(maps,map->Density(Support(map)))
or ForAny([1..2],i->Density(Support(maps[i]))
<> Sum(List(facts[i],fact->Density(Support(fact)))))
or not ForAll(Union(facts),
fact -> IsClassShift(fact) or IsClassShift(fact^-1)
or IsClassReflection(fact)
or IsClassTransposition(fact))
then TryNextMethod(); fi;
facts := List(facts,Sorted);
if List(facts[1],Length) <> List(facts[2],Length)
then TryNextMethod(); fi;
P := List(maps,
map->AsUnionOfFewClasses(Difference(Integers,Support(map))));
l := Maximum(List(P,Length));
for i in [1..2] do
if l > Length(P[i]) then P[i] := RefinedPartition(P[i],l); fi;
od;
for i in [1..2] do
Append(P[i],Flat(List(Flat(facts[i]),
fact->Filtered(LargestSourcesOfAffineMappings(fact),
cl->Intersection(Support(fact),cl)<>[]))));
od;
sigma := RcwaMapping(P[1],P[2]);
for i in [1..Length(facts[1][1])] do
--> --------------------
--> maximum size reached
--> --------------------
