The functions in this section compute the automorphism group of a lattice
and test lattices for isometry. They are based on the
AUTO and ISOM programs of Bernd Souvignier.
Currently the lattices to which these functions are applied must be
exact (over Z or Q) and the associated Gram matrices must have
small integers.
AutomorphismGroup(L) : Lat -> GrpMat
Stabilizer: RngIntElt Default: 0
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
NaturalAction: Bool Default: false
This function computes the automorphism group G of a lattice L which is defined to be the group of those automorphisms of the Z-module underlying L which preserve the inner product of L. L must be an exact lattice (over Z or Q). The group G is returned as an integral matrix group of degree m acting on the coordinate vectors of L by multiplication where m is the rank of L. The coordinate vectors of L are the elements of the coordinate lattice C of L which has the same Gram matrix as L, but standard basis of degree m (C can be created using the function CoordinateLattice). G does not act on the elements of L, since there is no natural matrix action of the automorphism group on L in the case that the rank of L is less than its degree. However, if the rank of L equals its degree, then the parameter NaturalAction may be set to true, in which case the resulting group has the natural action on the basis vectors (not the coordinate vectors); note that in this case the resulting matrix group will have (non-integral) rational entries in general, even though the image under the group of an integral basis vector will always be integral.The algorithm uses a backtrack search to find images of the basis vectors. A vector is a possible image if it has the correct inner product with the images chosen so far. Additional invariants which have to be respected by automorphisms are used by default and are usually sufficient for a satisfying performance. For difficult examples the parameters described below allow to consider further invariants which are more sophisticated and harder to compute but often allow to cut down dead ends in the backtrack at an early stage.
The algorithm has to compute (and store) the short vectors of length up to the maximal diagonal entry of the Gram matrix of L. This restricts its general application to lattices of dimension up to about 40, since for lattices in higher dimensions the number of vectors of minimal length may be too large to store. However, the function can of course be applied to lattices in higher dimensions with a reasonable number of short vectors.
Setting the parameter Stabilizer := i will cause the function to compute only the point stabilizer of i basis vectors. These will in general not be the first i basis vectors, as the function permutes the basis to speed up the computation. In difficult examples it can be useful to compute stabilizers with respect to different bases and feed the subgroup generated by these into a subsequent run of the program.
The parameter Depth allows sometimes a glance at the future. Assume that i images have already been chosen. Fix a combination of i scalar products and let v be the sum over all vectors having this scalar product combination with the chosen images. Then v has to be the image of the corresponding vector when computed for the standard basis. In the case that v is linearly independent from the chosen images this means that by choosing i images the automorphism is prescribed on a space of dimension bigger than i. Setting the parameter Depth := j will cause the function to consider scalar product combinations with the last j chosen images. A reasonable value for the depth is 2, but in difficult examples it pays to increase it to 4 or 5.
In very hard examples one may want to use Bacher polynomials which are a combinatorial invariant that usually separates the orbits of the automorphism group on the short vectors. However, these are expensive to calculate and should only be used if one suspects that the automorphism group has many orbits on the short vectors. The parameter BacherDepth specifies to which depth the Bacher polynomials are used and should usually be chosen to be 1, since even small automorphism groups will have only very few (most likely 1) orbits on the vectors having correct scalar product with the first image. The Bacher polynomials are computed by counting pairs of vectors having a certain scalar product with other vectors. This scalar product is by default chosen to be half the norm of the vector, since this will usually be the value which occurs least frequent. The user can change the scalar product to a value s by setting BacherSCP := s.
In some situations one may already know a subgroup of the full automorphism group, either by the construction of the lattice or an earlier stabilizer computation. This subgroup can be made available by setting Generators := Q, where Q is a set or sequence containing the generators of the subgroup.
Stabilizer: RngIntElt Default: 0
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
This function computes the subgroup of the automorphism group of L which fixes also the forms given in the set or sequence F. The matrices in F are not required to be positive definite or even symmetric. This is for example useful to compute automorphism groups of lattices over algebraic number fields. The parameters are as above.
Stabilizer: RngIntElt Default: 0
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
This function computes the matrix group fixing all forms given in the sequence F. The first form in F must be symmetric and positive definite, while the others are arbitrary. The call of this function is equivalent to AutomorphismGroup( LatticeWithGram(F[1]), [ F[i] : i in [2..#F] ] ). This function can be used to compute the Bravais group of a matrix group G which is defined to be the full automorphism group of the forms fixed by G. The parameters are as above.
> L := Lattice("E", 8);
> G := AutomorphismGroup(L);
> #G; FactoredOrder(G);
696729600
[ <2, 14>, <3, 5>, <5, 2>, <7, 1> ]
> M := MatrixRing(Rationals(), 8);
> B := BasisMatrix(L);
> A := MatrixGroup<8, Rationals() | [B^-1 * M!G.i * B : i in [1 .. Ngens(G)]]>;
> A;
MatrixGroup(8, Rational Field)
Generators:
[ 0 0 -1/2 1/2 -1/2 1/2 0 0]
[ 0 0 1/2 1/2 1/2 1/2 0 0]
[ 0 0 -1/2 1/2 1/2 -1/2 0 0]
[-1/2 1/2 0 0 0 0 -1/2 1/2]
[ 0 0 -1/2 -1/2 1/2 1/2 0 0]
[-1/2 -1/2 0 0 0 0 -1/2 -1/2]
[-1/2 -1/2 0 0 0 0 1/2 1/2]
[ 1/2 -1/2 0 0 0 0 -1/2 1/2]
[ 1/4 1/4 1/4 -1/4 -3/4 -1/4 -1/4 -1/4]
[-1/4 -1/4 3/4 1/4 -1/4 1/4 1/4 1/4]
[-1/4 -1/4 -1/4 1/4 -1/4 1/4 1/4 -3/4]
[-1/4 -1/4 -1/4 1/4 -1/4 1/4 -3/4 1/4]
[ 1/4 -3/4 1/4 -1/4 1/4 -1/4 -1/4 -1/4]
[ 3/4 -1/4 -1/4 1/4 -1/4 1/4 1/4 1/4]
[-1/4 -1/4 -1/4 1/4 -1/4 -3/4 1/4 1/4]
[-1/4 -1/4 -1/4 -3/4 -1/4 1/4 1/4 1/4]
[1 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0]
[0 0 0 1 0 0 0 0]
[0 0 0 0 1 0 0 0]
[0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 1]
[0 0 0 0 0 0 1 0]
> [ #Orbit(A, b) : b in Basis(L) ];
[ 2160, 240, 240, 240, 240, 240, 240, 240 ]
> AutomorphismGroup(L: NaturalAction) eq A;
true
> L := Lattice("Kappa", 13);
> LL, T := PairReduce(L);
> time G2 := AutomorphismGroup(L : Stabilizer := 2);
Time: 1.710
> #G2;
48
> time GG2 := AutomorphismGroup(LL : Stabilizer := 2);
Time: 0.229
> #GG2;
48
> Z := IntegerRing();
> H := MatrixGroup< 13, Z | G2, [ T^-1*g*T : g in Generators(GG2) ] >;
> #H;
311040
> MatrixRing(Z, 13) ! -1 in H;
false
The pair reduction yields a different basis for the same lattice and both
2-point stabilizers have order 48. After transforming the automorphisms of LL
back to automorphisms of L, the two stabilizers generate a group of reasonable
size which still can be enlarged by an index of 2 by adding -I.
We thus obtain a group of order 622080 which turns out to be the full
automorphism group of the lattice L.
> time G := AutomorphismGroup(L); Time: 11.379 > #G; 622080
> L := Lattice("Lambda", 19);
> for i in [0..5] do
> time G := AutomorphismGroup(LLL(L) : Depth := i, Stabilizer := 2);
> end for;
Time: 405.880
Time: 77.670
Time: 77.020
Time: 38.170
Time: 20.479
Time: 35.689
This indicates that Depth := 4 is the optimal value and that the full
automorphism group might take very long without the depth parameter (it
takes in fact more than one hour).
> for i in [1..5] do > time G := AutomorphismGroup(LLL(L) : Depth := i); > end for; Time: 136.440 Time: 141.369 Time: 61.750 Time: 29.979 Time: 50.359 > G := AutomorphismGroup(LLL(L) : Depth := 4); > #G; 23592960 > DS := DerivedSeries(G); > [ #DS[i]/#DS[i+1] : i in [1..#DS-1] ]; [ 4, 3, 4 ] > [ IsElementaryAbelian(DS[i]/DS[i+1]) : i in [1..#DS-1] ]; [ true, true, true ] > H := DS[#DS]; > C := Core(G, Sylow(H, 2)); > Q := H/C; #Q, IsSimple(Q); 60 true > LS := LowerCentralSeries(C); > [ #LS[i]/#LS[i+1] : i in [1..#LS-1] ]; [ 256, 16, 2 ]Hence, G := ( Aut)(Lambda_(19)) has a series of normal subgroups with factors 2^2, 3, 2^2, A_5, 2^8, 2^4, 2.
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
This function determines whether the lattices L and M are isometric. The algorithm tries to construct a basis for the second lattice with inner products as given by the Gram matrix of the first lattice. The method is a backtrack search analogous to the one used to compute the automorphism group of a lattice. If the lattices are isometric, the function returns a transformation matrix T as a second return value such that F_2 = T F_1 T^(tr), where F_1 and F_2 are the Gram matrices of L and M, respectively.For isometric lattices the cost of finding an isometry is roughly the cost of finding one automorphism of the lattice. Again, the computation may be sped up by using the additional invariants described for the automorphism group computation.
In many applications one will check whether a lattice is isometric to one for which the automorphism group is already known. In this situation the automorphism group of the second lattice can be made available by setting Generators := Q, where Q is a set or sequence containing the generators of the group. Note however, that for isometric lattices this may slow down the computation, since generators for stabilizers have to be recomputed.
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
This function determines whether the lattices L and M are isometric with an isometry respecting also additional bilinear forms given by the sequences of Gram matrices F_1 and F_2. The return values and parameters are as above.
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
For two sequences of F_1 and F_2 of Gram matrices, determine whether a simultaneous isometry exists, i.e., a matrix T such that T F_1[i] T^(tr) = F_2[i] for i in [1..#F_1]. The first form in both sequences must be positive definite. The return values and parameters are as above.
> L := Lattice("Lambda", 16);
> LL := Lattice(ReedMullerCode(1, 4), "B");
> time bool, T := IsIsometric(L, LL : Depth := 4);
Time: 2.029
> bool;
true
> T * GramMatrix(L) * Transpose(T) eq GramMatrix(LL);
true
We can also show that L is a 2-modular lattice (i.e., isometric to its
rescaled dual).
> IsIsometric(L, Dual(L)); true [ 0 1 1 -1 1 -1 0 0 -1 1 -1 0 0 0 0 0] [-2 -3 -4 1 -2 3 -1 -2 0 1 -1 -1 1 1 1 -1] [-1 -1 -1 1 0 -1 0 -1 0 2 -1 -1 1 1 1 -1] [ 0 1 1 -1 1 0 0 0 -1 0 0 0 0 0 0 0] [ 0 -1 -2 0 -1 2 -1 -1 0 1 -1 0 1 0 0 0] [ 1 2 2 0 2 -3 0 0 -2 4 -2 -1 1 1 -1 -1] [-1 -1 -2 0 0 1 0 -1 0 0 0 -1 1 1 1 -1] [ 1 2 3 -1 2 -3 1 1 -1 0 0 0 0 0 -1 1] [ 0 1 1 0 2 -3 0 -1 -2 4 -2 -2 1 1 1 -1] [ 0 -1 -2 0 -2 3 -1 0 1 -1 0 1 0 0 -1 0] [ 0 0 1 1 0 -1 1 1 1 -1 0 1 0 0 -1 0] [ 0 -1 -1 1 -2 2 -1 0 1 0 0 1 0 -1 -1 0] [ 0 0 0 0 0 0 0 1 1 -1 0 1 0 0 -1 0] [ 0 -1 -2 0 -2 3 0 0 1 -2 0 1 1 0 -2 1] [ 0 1 1 -1 1 -1 0 0 -1 1 0 -1 0 0 1 0] [ 0 0 -1 -1 0 1 0 -1 -1 1 -1 -1 1 1 0 0]