A library of irreducible maximal finite integral matrix groups is provided with GAP. It contains Q-class representatives for all of these groups of dimension at most 24, and Z-class representatives for those of dimension at most 11 or of dimension 13, 17, 19, or 23.
The groups provided in this library have been determined by Wilhelm Plesken, partially as joint work with Michael Pohst, or by members of his institute (Lehrstuhl B für Mathematik, RWTH Aachen). In particular, the data for the groups of dimensions 2 to 9 have been taken from the output of computer calculations which they performed in 1979 (see PP77, PP80). The Z-class representatives of the groups of dimension 10 have been determined and computed by Bernd Souvignier (Sou94), and those of dimensions 11, 13, and 17 have been recomputed for this library from the circulant Gram matrices given in Ple85, using the stand-alone programs for the computation of short vectors and Bravais groups which have been developed in Plesken's institute. The Z-class representatives of the groups of dimensions 19 and 23 had already been determined in Ple85. Gabriele Nebe has recomputed them for us. Her main contribution to this library, however, is that she has determined and computed the Q-class representatives of the groups of non-prime dimensions between 12 and 24 (see PN95, NP95, Neb95).
The library has been brought into GAP format by Volkmar Felsch. He has applied several GAP routines to check certain consistency of the data. However, the credit and responsibility for the lists remain with the authors. We are grateful to Wilhelm Plesken, Gabriele Nebe, and Bernd Souvignier for supplying their results to GAP.
In the preceding acknowledgement, we used some notations that will also be needed in the sequel. We first define these.
Any integral matrix group G of dimension n is a subgroup of GLn(Z) as well as of GLn(Q) and hence lies in some conjugacy class of integral matrix groups under GLn(Z) and also in some conjugacy class of rational matrix groups under GLn(Q). As usual, we call these classes the Z-class and the Q-class of G, respectively. Note that any conjugacy class of subgroups of GLn(Q) contains at least one Z-class of subgroups of GLn(Z) and hence can be considered as the Q-class of some integral matrix group.
In the context of this library we are only concerned with Z-classes and Q-classes of subgroups of GLn(Z) which are irreducible and maximal finite in GLn(Z) (we will call them i.m.f. subgroups of GLn(Z)). We can distinguish two types of these groups:
First, there are those i.m.f. subgroups of GLn(Z) which are also maximal finite subgroups of GLn(Q). Let us denote the set of their Q-classes by Q1(n). It is clear from the above remark that Q1(n) just consists of the Q-classes of i.m.f. subgroups of GLn(Q).
Secondly, there is the set Q2(n) of the Q-classes of the remaining i.m.f. subgroups of GLn(Z), i.e., of those which are not maximal finite subgroups of GLn(Q). For any such group G, say, there is at least one class C Î Q1(n) such that G is conjugate under Q to a proper subgroup of some group H Î C. In fact, the class C is uniquely determined for any group G occurring in the library (though there seems to be no reason to assume that this property should hold in general). Hence we may call C the rational i.m.f. class of G. Finally, we will denote the number of classes in Q1(n) and Q2(n) by q1(n) and q2(n), respectively.
As an example, let us consider the case n = 4. There are 6 Z-classes of i.m.f. subgroups of GL4(Z) with representative subgroups G1, ¼, G6 of isomorphsim types G1 @ W(F4), G2 @ D12 \wr C2, G3 @ G4 @ C2 ×S5, G5 @ W(B4), and G6 @ (D12 Y D12) : C2. The corresponding Q-classes, R1, ¼, R6, say, are pairwise different except that R3 coincides with R4. The groups G1, G2, and G3 are i.m.f. subgroups of GL4(Q), but G5 and G6 are not because they are conjugate under GL4(Q) to proper subgroups of G1 and G2, respectively. So we have Q1(4) = { R1, R2, R3 }, Q2(4) = { R5, R6 }, q1(4) = 3, and q2(4) = 2.
The q1(n) Q-classes of i.m.f. subgroups of GLn(Q) have been determined for each dimension n £ 24. The current GAP library provides integral representative groups for all these classes. Moreover, all Z-classes of i.m.f. subgroups of GLn(Z) are known for n £ 11 and for n Î {13,17,19,23}. For these dimensions, the library offers integral representative groups for all Q-classes in Q1(n) and Q2(n) as well as for all Z-classes of i.m.f. subgroups of GLn(Z).
Any group G of dimension n given in the library is represented as the automorphism group G = Aut(F,L) = { g Î GLn(Z) \mid Lg = L and g F gtr = F } of a positive definite symmetric n ×n matrix F Î Zn ×n on an n-dimensional lattice L @ Z1 ×n (for details see e.g. PN95). GAP provides for G a list of matrix generators and the Gram matrix F.
The positive definite quadratic form defined by F defines a norm v F vtr for each vector v Î L, and there is only a finite set of vectors of minimal norm. These vectors are often simply called the short vectors. Their set splits into orbits under G, and G being irreducible acts faithfully on each of these orbits by multiplication from the right. GAP provides for each of these orbits the orbit size and a representative vector.
Like most of the other GAP libraries, the library of i.m.f. integral
matrix groups supplies an extraction function, ImfMatrixGroup.
However, as the library involves only 423 different groups, there is no
need for a selection or an example function. Instead, there are two
functions, ImfInvariants and DisplayImfInvariants, which provide some
Z-class invariants that can be extracted from the library without
actually constructing the representative groups themselves. The
difference between these two functions is that the latter one displays
the resulting data in some easily readable format, whereas the first one
returns them as record components so that you can properly access them.
We shall give an individual description of each of the library functions,
but first we would like to insert a short remark concerning their names:
Any self-explaining name of a function handling irreducible maximal
finite integral matrix groups would have to include this term in full
length and hence would grow extremely long. Therefore we have decided to
use the abbreviation Imf instead in order to restrict the names to some
reasonable length.
The first three functions can be used to formulate loops over the classes.
ImfNumberQQClasses( dim ) F
ImfNumberQClasses( dim ) F
ImfNumberZClasses( dim, q ) F
ImfNumberQQClasses returns the number q1(dim ) of Q-classes of
i.m.f. rational matrix groups of dimension dim. Valid values of dim
are all positive integers up to 24.
Note: In order to enable you to loop just over the classes belonging to Q1(dim ), we have arranged the list of Q-classes of dimension dim for any dimension dim in the library such that, whenever the classes of Q2(dim ) are known, too, i.e., in the cases dim £ 11 or dim Î {13,17,19,23}, the classes of Q1(dim ) precede those of Q2(dim ) and hence are numbered from 1 to q1(dim ).
ImfNumberQClasses returns the number of Q-classes of groups of
dimension dim which are available in the library. If dim £ 11 or
dim Î {13,17,19,23}, this is the number q1(dim ) + q2(dim ) of Q-classes of i.m.f. subgroups of GLdim(Z).
Otherwise, it is just the number q1(dim ) of Q-classes of
i.m.f. subgroups of GLdim(Q). Valid values of dim are all
positive integers up to 24.
ImfNumberZClasses returns the number of Z-classes in the q th Q-class of i.m.f. integral matrix groups of dimension
dim. Valid values of dim are all positive integers up to 11 and all
primes up to 23.
DisplayImfInvariants( dim, q ) F
DisplayImfInvariants( dim, q, z ) F
DisplayImfInvariants displays the following Z-class invariants of
the groups in the z th Z-class in the q th
Q-class of i.m.f. integral matrix groups of dimension dim:
IsomorphismPermGroup or
IsomorphismPermGroupImfGroup below),
If you specify the value 0 for any of the parameters dim, q, or z, the command will loop over all available dimensions, Q-classes of given dimension, or Z-classes within the given Q-class, respectively. Otherwise, the values of the arguments must be in range. A value z ¹ 1 must not be specified if the Z-classes are not known for the given dimension, i.e., if dim > 11 and dim \not Î {13,17,19,23}. The default value of z is 1. This value of z will be accepted even if the Z-classes are not known. Then it specifies the only representative group which is available for the q th Q-class. The greatest legal value of dim is 24.
gap> DisplayImfInvariants( 3, 1, 0 ); #I Z-class 3.1.1: Solvable, size = 2^4*3 #I isomorphism type = C2 wr S3 = C2 x S4 = W(B3) #I elementary divisors = 1^3 #I orbit size = 6, minimal norm = 1 #I Z-class 3.1.2: Solvable, size = 2^4*3 #I isomorphism type = C2 wr S3 = C2 x S4 = C2 x W(A3) #I elementary divisors = 1*4^2 #I orbit size = 8, minimal norm = 3 #I Z-class 3.1.3: Solvable, size = 2^4*3 #I isomorphism type = C2 wr S3 = C2 x S4 = C2 x W(A3) #I elementary divisors = 1^2*4 #I orbit size = 12, minimal norm = 2 gap> DisplayImfInvariants( 8, 15, 1 ); #I Z-class 8.15.1: Solvable, size = 2^5*3^4 #I isomorphism type = C2 x (S3 wr S3) #I elementary divisors = 1*3^3*9^3*27 #I orbit size = 54, minimal norm = 8 #I not maximal finite in GL(8,Q), rational imf class is 8.5 gap> DisplayImfInvariants( 20, 23 ); #I Q-class 20.23: Size = 2^5*3^2*5*11 #I isomorphism type = (PSL(2,11) x D12).C2 #I elementary divisors = 1^18*11^2 #I orbit size = 3*660 + 2*1980 + 2640 + 3960, minimal norm = 4
Note that the function DisplayImfInvariants uses a kind of shorthand to
display the elementary divisors. E. g., the expression 1*3^3*9^3*27 in
the preceding example stands for the elementary divisors
1,3,3,3,9,9,9,27. (See also the next example which shows that the
function ImfInvariants provides the elementary divisors in form of an
ordinary GAP list.)
In the description of the isomorphism types the following notations are used:
The groups involved are
Cn, Dn,
and Qn, respectively,
An and Sn, respectively,
GL(n,q), PGL(n,q),
SL(n,q), and PSL(n,q), respectively,
SU(n,q) and PSU(n,q), respectively,
Sp(n,q),
O+(8,2),
2+^(1+8),
3+^(1+2), 3+^(1+4), and 5+^(1+2), respectively,
G(2,3),
W(An), W(Bn), W(Dn), W(En),
and W(F4), respectively,
Co1,
Co2, Co3, HS, J2, M12, M22, M23, M24, and Mc,
respectively,
M10.
As mentioned above, the data assembled by the function
DisplayImfInvariants are ``cheap data'' in the sense that they can be
provided by the library without loading any of its large matrix files or
performing any matrix calculations. The following function allows you to
get proper access to these cheap data instead of just displaying them.
ImfInvariants( dim, q ) F
ImfInvariants( dim, q, z ) F
ImfInvariants returns a record which provides some Z-class
invariants of the groups in the z th Z-class in the
q th Q-class of i.m.f. integral matrix groups of dimension
dim. A value z ¹ 1 must not be specified if the Z-classes
are not known for the given dimension, i.e., if dim > 11 and dim \not Î {13,17,19,23}. The default value of z is 1. This value of z
will be accepted even if the Z-classes are not known. Then it
specifies the only representative group which is available for the
q th Q-class. The greatest legal value of dim is 24.
The resulting record contains six or seven components:
size
isSolvable true if G is solvable,
isomorphismType DisplayImfInvariants above),
elementaryDivisors ElementaryDivisorsMat,
see ElementaryDivisorsMat),
minimalNorm
sizesOrbitsShortVectors
maximalQClass Note that four of these data, namely the group size, the solvability, the isomorphism type, and the corresponding rational i.m.f. class, are not only Z-class invariants, but also Q-class invariants.
Note further that, though the isomorphism type is a Q-class invariant, you will sometimes get different descriptions for different Z-classes of the same Q-class (as, e.g., for the classes 3.1.1 and 3.1.2 in the last example above). The purpose of this behaviour is to provide some more information about the underlying lattices.
gap> ImfInvariants( 8, 15, 1 ); rec( size := 2592, isSolvable := true, isomorphismType := "C2 x (S3 wr S3)", elementaryDivisors := [ 1, 3, 3, 3, 9, 9, 9, 27 ], minimalNorm := 8, sizesOrbitsShortVectors := [ 54 ], maximalQClass := 5 ) gap> ImfInvariants( 24, 1 ).size; 10409396852733332453861621760000 gap> ImfInvariants( 23, 5, 2 ).sizesOrbitsShortVectors; [ 552, 53130 ] gap> for i in [ 1 .. ImfNumberQClasses( 22 ) ] do > Print( ImfInvariants( 22, i ).isomorphismType, "\n" ); od; C2 wr S22 = W(B22) (C2 x PSU(6,2)).S3 (C2 x S3) wr S11 = (C2 x W(A2)) wr S11 (C2 x S12) wr C2 = (C2 x W(A11)) wr C2 C2 x S3 x S12 = C2 x W(A2) x W(A11) (C2 x HS).C2 (C2 x Mc).C2 C2 x S23 = C2 x W(A22) C2 x PSL(2,23) C2 x PSL(2,23) C2 x PGL(2,23) C2 x PGL(2,23)
ImfMatrixGroup( dim, q ) F
ImfMatrixGroup( dim, q, z ) F
ImfMatrixGroup is the essential extraction function of this library
(note that its name has been changed from ImfMatGroup in GAP 3 to
ImfMatrixGroup in GAP 4). It returns a representative group, G
say, of the z th Z-class in the q th Q-class of
i.m.f. integral matrix groups of dimension dim. A value z ¹ 1
must not be specified if the Z-classes are not known for the given
dimension, i.e., if dim > 11 and dim \not Î {13,17,19,23}. The
default value of z is 1. This value of z will be accepted even if
the Z-classes are not known. Then it specifies the only representative
group which is available for the q th Q-class. The greatest
legal value of dim is 24.
gap> G := ImfMatrixGroup( 5, 1, 3 ); ImfMatrixGroup(5,1,3) gap> for m in GeneratorsOfGroup( G ) do PrintArray( m ); od; [ [ -1, 0, 0, 0, 0 ], [ 0, 1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ -1, -1, -1, -1, 2 ], [ -1, 0, 0, 0, 1 ] ] [ [ 0, 1, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 0, 0, 1 ] ]
The attributes Size and IsSolvable will be properly set in the
resulting matrix group G. In addition, it has two attributes
IsImfMatrixGroup and ImfRecord where the first one is just a logical
flag set to true and the latter one is a record. Except for the group
size and the solvability flag, this record contains the same components
as the resulting record of the function ImfInvariants described above
(see ImfInvariants), namely the components isomorphismType,
elementaryDivisors, minimalNorm, and sizesOrbitsShortVectors and,
if G is not a rational i.m.f. group, maximalQClass. Moreover, it has
the two components
form
repsOrbitsShortVectors
The last one of these components will be required by the function
IsomorphismPermGroup below.
Example:
gap> Size( G ); 3840 gap> imf := ImfRecord( G );; gap> imf.isomorphismType; "C2 wr S5 = C2 x W(D5)" gap> PrintArray( imf.form ); [ [ 4, 0, 0, 0, 2 ], [ 0, 4, 0, 0, 2 ], [ 0, 0, 4, 0, 2 ], [ 0, 0, 0, 4, 2 ], [ 2, 2, 2, 2, 5 ] ] gap> imf.elementaryDivisors; [ 1, 4, 4, 4, 4 ] gap> imf.minimalNorm; 4
If you want to perform calculations in such a matrix group G you should
be aware of the fact that the permutation group routines of GAP are
much more efficient than the matrix group routines. Hence we recommend
that you do your computations, whenever possible, in the isomorphic
permutation group which is induced by the action of G on one of the
orbits of the associated short vectors. You may call one of the following
functions IsomorphismPermGroup or IsomorphismPermGroupImfGroup to get
an isomorphism to such a permutation group (note that these GAP 4
functions have replaced the GAP 3 functions PermGroup and
PermGroupImfGroup).
IsomorphismPermGroup( G ) M
IsomorphismPermGroup returns an isomorphism, j say, from the
given i.m.f. integral matrix group G to a permutation group P : = j(G ) acting on a minimal orbit, S say, of short vectors of
G such that each matrix m Î G is mapped to the permutation
induced by its action on S.
Note that in case of a large orbit the construction of j may be space and time consuming. Fortunately, there are only five Q-classes in the library for which the smallest orbit of short vectors is of size greater than 20000, the worst case being the orbit of size 196560 for the Leech lattice ( dim = 24, q = 3).
The inverse isomorphism j-1 from P to G is constructed by determining a Q-base B Ì S of Q1 ×dim in S and, in addition, the associated base change matrix M which transforms B into the standard base of Z1 ×dim. This allows a simple computation of the preimage j-1(p) of any permutation p Î P as follows. If, for 1 £ i £ dim, bi is the position number in S of the ith base vector in B, it suffices to look up the vector whose position number in S is the image of bi under p and to multiply this vector by M to get the ith row of j-1(p).
You may use the functions Image and PreImage (see Image and
PreImage) to switch from G to P and back from P to G.
As an example, let us continue the preceding example and compute the solvable residuum of the group G.
gap> # Perform the computations in an isomorphic permutation group. gap> phi := IsomorphismPermGroup( G );; gap> P := Image( phi ); Group([ ( 1, 7, 6)( 2, 9)( 4, 5,10), ( 2, 3, 4, 5)( 6, 9, 8, 7) ]) gap> D := DerivedSubgroup( P ); Group([ ( 1, 2,10, 9)( 3, 8)( 4, 5)( 6, 7), ( 1, 6)( 2, 7, 9, 4)( 3, 8)( 5,10), ( 1, 5,10, 6)( 2, 8, 9, 3) ]) gap> Size( D ); 960 gap> IsPerfectGroup( D ); true gap> # We have found the solvable residuum of P, gap> # now move the results back to the matrix group G. gap> R := PreImage( phi, D ); <matrix group of size 960 with 3 generators> gap> for m in GeneratorsOfGroup( R ) do PrintArray( m ); od; [ [ -1, -1, -1, -1, 2 ], [ 0, -1, 0, 0, 0 ], [ 0, 0, 0, 1, 0 ], [ 0, 0, 1, 0, 0 ], [ -1, -1, 0, 0, 1 ] ] [ [ 0, 0, -1, 0, 0 ], [ 0, -1, 0, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ -1, -1, -1, -1, 2 ], [ 0, -1, -1, 0, 1 ] ] [ [ 0, -1, 0, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 1, 0, 0 ], [ -1, -1, -1, -1, 2 ], [ 0, -1, 0, -1, 1 ] ]
IsomorphismPermGroupImfGroup( G, n ) F
IsomorphismPermGroupImfGroup returns an isomorphism, j say,
from the given i.m.f. integral matrix group G to a permutation group
P acting on the n th orbit, S say, of short vectors of G
such that each matrix m Î G is mapped to the permutation induced
by its action on S.
The only difference to the above function IsomorphismPermGroup is that
you can specify the orbit to be used. In fact, as the orbits of short
vectors are sorted by increasing sizes, the function
IsomorphismPermGroup( G ) has been implemented such that it is
equivalent to IsomorphismPermGroupImfGroup( G, 1 ).
gap> ImfInvariants( 12, 9 ).sizesOrbitsShortVectors; [ 120, 300 ] gap> G := ImfMatrixGroup( 12, 9 ); ImfMatrixGroup(12,9) gap> phi1 := IsomorphismPermGroupImfGroup( G, 1 );; gap> P1 := Image( phi1 ); <permutation group of size 2400 with 2 generators> gap> LargestMovedPoint( P1 ); 120 gap> phi2 := IsomorphismPermGroupImfGroup( G, 2 );; gap> P2 := Image( phi2 ); <permutation group of size 2400 with 2 generators> gap> LargestMovedPoint( P2 ); 300
GAP 4 manual