GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it
#############################################################################
##
#W imf.gi GAP group library Volkmar Felsch
##
##
#Y Copyright (C) 1995, Lehrstuhl D für Mathematik, RWTH Aachen, Germany
#Y (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
##
## This file contains the library functions for the GAP library of
## irreducible maximal finite integral matrix groups.
##
#############################################################################
##
#F BaseShortVectors( <orbit> ) . . . . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "BaseShortVectors", function ( orbit )
local base, count, dim, i, j, nums, vector;
dim := Length( orbit[1] );
base := ListWithIdenticalEntries( dim, 0 );
nums := ListWithIdenticalEntries( dim, 0 );
count := 0;
i := 0;
while count < dim do
i := i + 1;
vector := orbit[i];
j := 0;
while j < dim do
j := j + 1;
if vector[j] <> 0 then
if nums[j] <> 0 then
vector := vector - vector[j] * base[j];
else
base[j] := vector / vector[j];
nums[j] := i;
count := count + 1;
j := dim;
fi;
fi;
od;
od;
base := List( nums, i -> orbit[i] );
return [ nums, base^-1 ];
end );
#############################################################################
##
#F DisplayImfInvariants( <dim>, <q> ) . . . . . . . . . . . . . . . . . . .
#F DisplayImfInvariants( <dim>, <q>, <z> ) . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "DisplayImfInvariants", function ( arg )
local dim, dims, hyphens, linelength, q, qq, z;
# load the imf main list if it is not yet available
if not IsBound( IMFList ) then
IMFLoad( 0 );
fi;
# get the arguments
dim := arg[1];
q := arg[2];
if Length( arg ) > 2 then
z := arg[3];
else
z := 1;
fi;
# get the range of dimensions to be handled
if dim = 0 then
dims := [ 1 .. IMFRec.maximalDimension ];
else
# check the given dimension for being in range
if dim < 0 or IMFRec.maximalDimension < dim then
Error( "dimension out of range" );
fi;
dims := [ dim ];
fi;
# loop over all dimensions in that range
for dim in dims do
# handle the cases q = 0 and q > 0 differently
if q = 0 then
linelength := Minimum( SizeScreen()[1], 76 );
hyphens := Concatenation( List( [ 1 .. linelength - 5 ],
i -> "-" ) );
# loop over the Q-classes of dimension dim
for qq in [ 1 .. IMFRec.numberQClasses[dim] ] do
# print a line of separators
Print( "#I ", hyphens, "\n" );
# check the Z-class number for being in range
if z < 0 or Length( IMFRec.bNumbers[dim][qq] ) < z then
Error( "Z-class number out of range" );
fi;
# display the specified Z-classes in the Q-class
DisplayImfReps( dim, qq, z );
od;
# print a line of separators
Print( "#I ", hyphens, "\n" );
else
# check the given Q-class number for being in range
if q < 1 or IMFRec.numberQClasses[dim] < q then
Error( "Q-class number out of range" );
fi;
# check the Z-class number for being in range
if z < 0 or Length( IMFRec.bNumbers[dim][q] ) < z then
Error( "Z-class number out of range" );
fi;
# display the specified Z-classes in the Q-class
DisplayImfReps( dim, q, z );
fi;
od;
end );
#############################################################################
##
#F DisplayImfReps( <dim>, <q>, <z> ) . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "DisplayImfReps", function ( dim, q, z )
local bound, degree, degs, eldivs, i, leng, mult, n, norm, qmax, size,
solvable, type, znums;
# get the position numbers of the groups to be handled
znums := IMFRec.bNumbers[dim][q];
if z = 0 then
z := 1;
bound := Length( znums );
else
bound := z;
fi;
# loop over the classes to be displayed
while z <= bound do
n := znums[z];
type := IMFList[dim].isomorphismType[n];
size := IMFList[dim].size[n];
solvable := IMFList[dim].isSolvable[n];
eldivs := IMFList[dim].elementaryDivisors[n];
degs := IMFList[dim].degrees[n];
norm := IMFList[dim].minimalNorm[n];
# print a class number
if IMFRec.repsAreZReps[dim] then
Print( "#I Z-class ", dim, ".", q, ".", z );
else
Print( "#I Q-class ", dim, ".", q );
fi;
# print solvability and group size
if solvable then
Print( ": Solvable, size = " );
else
Print( ": Size = " );
fi;
PrintFactorsInt( size );
Print( "\n" );
# print the isomorphism type
Print( "#I isomorphism type = " );
Print( type, "\n" );
# print the elementary divisors
Print( "#I elementary divisors = " );
Print( eldivs[1] );
if eldivs[2] > 1 then
Print( "^", eldivs[2] );
fi;
leng := Length( eldivs );
i := 3;
while i < leng do
Print( "*", eldivs[i] );
if eldivs[i+1] > 1 then
Print( "^", eldivs[i+1] );
fi;
i := i + 2;
od;
Print( "\n" );
# print the orbit size
Print( "#I orbit size = " );
if IsInt( degs ) then
Print( degs );
leng := 1;
else
leng := Length( degs );
i := 0;
while i < leng do
i := i + 1;
degree := degs[i];
mult := 1;
while i < leng and degs[i+1] = degree do
mult := mult + 1;
i := i + 1;
od;
if mult > 1 then Print( mult, "*" ); fi;
Print( degree );
if i < leng then Print( " + " ); fi;
od;
fi;
# print the minimal norm
Print( ", minimal norm = ", norm, "\n" );
# print a message if the group is not imf in Q
qmax := IMFRec.maximalQClasses[dim][q];
if qmax <> q then
Print( "#I not maximal finite in GL(", dim,
",Q), rational imf class is ", dim, ".", qmax, "\n" );
fi;
z := z + 1;
od;
end );
#############################################################################
##
#F ImfInvariants( <dim>, <q> ) . . . . . . . . . . . . . . . . . . . . . . .
#F ImfInvariants( <dim>, <q>, <z> ) . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfInvariants", function ( arg )
local dim, eldivs, flat, i, infrec, j, leng, n, q, qmax, sizes;
# check the arguments and get the position number of the class to be
# handled
n := ImfPositionNumber( arg );
dim := arg[1];
q := arg[2];
# get the size of the orbits of short vectors
sizes := IMFList[dim].degrees[n];
if IsInt( sizes ) then
sizes := [ sizes ];
fi;
# get the elementary divisors
flat := IMFList[dim].elementaryDivisors[n];
leng := Length( flat );
eldivs := [ ];
i := 1;
while i < leng do
for j in [ 1 .. flat[i+1] ] do
Add( eldivs, flat[i] );
od;
i := i + 2;
od;
# get the Q-class number of the corresponding rational imf class
qmax := IMFRec.maximalQClasses[dim][q];
# create the information record and return it
infrec := rec(
size := IMFList[dim].size[n],
isSolvable := IMFList[dim].isSolvable[n],
isomorphismType := IMFList[dim].isomorphismType[n],
elementaryDivisors := eldivs,
minimalNorm := IMFList[dim].minimalNorm[n],
sizesOrbitsShortVectors := sizes );
if qmax <> q then
infrec.maximalQClass := qmax;
fi;
return infrec;
end );
#############################################################################
##
#F IMFLoad( <dim> ) . . . . . . . . load a secondary file of the imf library
##
InstallGlobalFunction( "IMFLoad", function ( dim )
local d, maxdim, name;
# initialize the imf main list if it is not yet available
if not IsBound( IMFList ) then
name := "imf.grp";
Info( InfoImf, 2, "loading secondary file ", name );
if not ReadGrp( name, "imf" ) then
Error( "cannot load secondary file ", name );
fi;
fi;
# check whether we actually need to load a matrix file
if dim > 0 and not IsBound( IMFList[dim].matrices ) then
# load the file
if dim < 10 then
name := "imf1to9.grp";
else
name := Concatenation( "imf", String( dim ), ".grp" );
fi;
Info( InfoImf, 2, "loading secondary file ", name );
if not ReadGrp( name, "imf" ) then
Error( "cannot load secondary file ", name );
fi;
fi;
return;
end );
#############################################################################
##
#F ImfMatrixGroup( <dim>, <q> ) . . . . . . . . . . . . . . . . . . . . . .
#F ImfMatrixGroup( <dim>, <q>, <z> ) . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfMatrixGroup", function ( arg )
local degrees, dim, form, gens, i, imfM, j, M, mats, n, name, q, qmax,
reps, z;
# check the arguments and get the position number of the class to be
# handled
n := ImfPositionNumber( arg );
# get dimension, Q-class number, and Z-class number
dim := arg[1];
q := arg[2];
z := arg[3];
# load the appropriate imf matrix file if it is not yet available
if not IsBound( IMFList[dim].matrices ) then
IMFLoad( dim );
fi;
# construct the matrix group
mats := IMFList[dim].matrices[n];
gens := mats[2];
M := Group( gens, gens[1] * gens[1]^-1 );
# construct the group name
if IMFRec.repsAreZReps[dim] then
name := Concatenation( "ImfMatrixGroup(", String( dim ), ",",
String( q ), ",", String( z ), ")" );
else
name := Concatenation( "ImfMatrixGroup(", String( dim ), ",",
String( q ), ")" );
fi;
# get the associated Gram matrix
form := List( mats[1], ShallowCopy );
for i in [ 1 .. dim - 1 ] do
for j in [ i + 1 .. dim ] do
form[i][j] := form[j][i];
od;
od;
# get the representatives and sizes of the orbits of short vectors
reps := IMFList[dim].orbitReps[n];
degrees := IMFList[dim].degrees[n];
if IsInt( degrees ) then
degrees := [ degrees ];
reps := [ reps ];
fi;
# get the Q-class number of the corresponding rational imf class
qmax := IMFRec.maximalQClasses[dim][q];
# define an approriate imf record
imfM := rec( );
imfM.isomorphismType := IMFList[dim].isomorphismType[n];
imfM.elementaryDivisors := ElementaryDivisorsMat( form );
imfM.form := form;
imfM.minimalNorm := IMFList[dim].minimalNorm[n];
imfM.repsOrbitsShortVectors := reps;
imfM.sizesOrbitsShortVectors := degrees;
if qmax <> q then
imfM.maximalQClass := qmax;
fi;
# define some approriate group attributes
SetFilterObj( M, IsImfMatrixGroup );
SetName( M, name );
SetSize( M, IMFList[dim].size[n] );
SetIsSolvableGroup( M, IMFList[dim].isSolvable[n] );
SetImfRecord( M, imfM );
return M;
end );
#############################################################################
##
#F ImfNumberQClasses( <dim> ) . . . . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfNumberQClasses", function ( dim )
# load the imf main list if it is not yet available
if not IsBound( IMFList ) then
IMFLoad( 0 );
fi;
# check the given dimension for being in range
if dim < 0 or IMFRec.maximalDimension < dim then
Error( "dimension out of range" );
fi;
return IMFRec.numberQClasses[dim];
end );
#############################################################################
##
#F ImfNumberQQClasses( <dim> ) . . . . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfNumberQQClasses", function ( dim )
# load the imf main list if it is not yet available
if not IsBound( IMFList ) then
IMFLoad( 0 );
fi;
# check the given dimension for being in range
if dim < 0 or IMFRec.maximalDimension < dim then
Error( "dimension out of range" );
fi;
return IMFRec.numberQQClasses[dim];
end );
#############################################################################
##
#F ImfNumberZClasses( <dim>, <q> ) . . . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfNumberZClasses", function ( dim, q )
local num;
# load the imf main list if it is not yet available
if not IsBound( IMFList ) then
IMFLoad( 0 );
fi;
# check the dimension for being in range
if dim < 1 or IMFRec.maximalDimension < dim then
Error( "dimension out of range" );
fi;
# check the Q-class number for being in range
if q < 1 or IMFRec.numberQClasses[dim] < q then
Error( "Q-class number out of range" );
fi;
# return the number of class representatives in the given Q-class
return Length( IMFRec.bNumbers[dim][q] );
end );
#############################################################################
##
#F ImfPositionNumber( [ <dim>, <q> ] ) . . . . . . . . . . . . . . . . . . .
#F ImfPositionNumber( [ <dim>, <q>, <z> ] ) . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "ImfPositionNumber", function ( args )
local dim, n, q, z, znums;
# load the imf main list if it is not yet available
if not IsBound( IMFList ) then
IMFLoad( 0 );
fi;
# check the dimension for being in range
dim := args[1];
if dim < 1 or IMFRec.maximalDimension < dim then
Error( "dimension out of range" );
fi;
# check the Q-class number for being in range
q := args[2];
if q < 1 or IMFRec.numberQClasses[dim] < q then
Error( "Q-class number out of range" );
fi;
znums := IMFRec.bNumbers[dim][q];
# get the Z-class number and check it for being in range
if Length( args ) = 2 then
z := 1;
args[3] := 1;
else
z := args[3];
if z < 1 or Length( znums ) < z then
Error( "Z-class number out of range" );
fi;
fi;
# return the position number of the class to be handled
return znums[z];
end );
#############################################################################
##
#F IsomorphismPermGroupImfGroup( <M> ) . . . . . . . . . . . . . . . . . . .
#F IsomorphismPermGroupImfGroup( <M>, <n> ) . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "IsomorphismPermGroupImfGroup", function ( arg )
local base, degrees, gens, id, imfM, imfP, M, n, orbit, P, perms, phi,
reps, vec;
# check the given group for being an imf matrix group
M := arg[1];
if not IsImfMatrixGroup( M ) then
Error( "the given group is not an imf matrix group" );
fi;
imfM := ImfRecord( M );
# check the given orbit number for being in range
degrees := imfM.sizesOrbitsShortVectors;
reps := imfM.repsOrbitsShortVectors;
if Length( arg ) = 1 then
n := 1;
else
n := arg[2];
if not n in [ 1 .. Length( reps ) ] then
Error( "orbit number out of range" );
fi;
fi;
# compute the specified orbit of short vectors
gens := GeneratorsOfGroup( M );
orbit := OrbitShortVectors( gens, reps[n] );
# check the orbit size
if Length( orbit ) <> degrees[n] then
Error( "inconsistent orbit size" );
fi;
# construct the associated permutation group
perms := List( gens, g -> PermList(
List( orbit, vec -> PositionSorted( orbit, vec * g ) ) ) );
id := perms[1]^0;
P := Group( perms, id );
# define an approriate imf record
imfP := rec( );
# define some appropriate group attributes
SetSize( P, Size( M ) );
SetIsSolvableGroup( P, IsSolvableGroup( M ) );
SetLargestMovedPoint( P, degrees[n] );
SetImfRecord( P, imfP );
# if IsBound( imfM.isomorphismType ) then
# imfP.isomorphismType := imfM.isomorphismType;
# fi;
# imfP.matGroup := M;
# compute the information which will be needed to reconvert permutations
# to matrices
base := BaseShortVectors( orbit );
imfP.orbitShortVectors := orbit;
imfP.baseVectorPositions := base[1];
imfP.baseChangeMatrix := base[2];
# construct the associated isomorphism from M to P
phi := GroupHomomorphismByFunction(
M,
P,
function ( mat )
local imf;
imf := ImfRecord( P );
return PermList( List( imf.orbitShortVectors, v ->
PositionSorted( imf.orbitShortVectors, v*mat ) ) );
end,
function ( perm )
local imf;
imf := ImfRecord( P );
return imf.baseChangeMatrix * List( imf.baseVectorPositions, i ->
imf.orbitShortVectors[i^perm] );
end );
SetIsBijective( phi, true );
# if n = 1, save a nice monomorphism of M
if n = 1 and not HasNiceMonomorphism( M ) then
SetNiceMonomorphism( M, phi );
fi;
return phi;
end );
#############################################################################
##
#M IsomorphismPermGroup( <M> )
##
InstallMethod( IsomorphismPermGroup,
"imf matrix groups",
[IsMatrixGroup and IsFinite and IsImfMatrixGroup],
IsomorphismPermGroupImfGroup );
#############################################################################
##
#F OrbitShortVectors( <gens>, <rep> ) . . . . . . . . . . . . . . . . . . .
##
InstallGlobalFunction( "OrbitShortVectors", function ( gens, rep )
local generator, images, new, nextvec, null, orbit, vector;
orbit := [ ];
null := ListWithIdenticalEntries( Length( rep ), 0 );
if rep > null then
images := [ Immutable( rep ) ];
else
images := [ Immutable( -rep ) ];
fi;
while images <> [ ] do
Append( orbit, images );
new := [ ];
for generator in gens do
for vector in images do
nextvec := vector * generator;
if nextvec > null then
Add( new, nextvec );
else
Add( new, -nextvec );
fi;
od;
od;
new := Set( new );
SubtractSet( new, orbit );
images := new;
od;
Append( orbit, -orbit );
# The function Immutable in the following statement essentially speeds
# up the function PositionSorted in IsomorphismPermGroupImfGroup.
return Immutable( Set( orbit ) );
end );
#############################################################################
##
#E