Automorphism Group and Isometry Testing

The functions in this section compute the automorphism group of a lattice and test lattices for isometry. Currently the lattices to which these functions are applied must be exact (over \({\mathbb{Z}}\) or \({\mathbb{Q}}\)).

AutomorphismGroup(L): Lat -> GrpMat

ProperAutomorphismGroup(L): Lat -> GrpMat

Stabilizer   : RngIntElt                        Default: 0
BacherDepth  : RngIntElt                        Default: -1
Generators   : [ GrpMatElt ]                    Default: 
NaturalAction: Bool                             Default: false
Decomposition: Bool                             Default: false
Vectors      : Mtrx                             Default: 

This function computes the automorphism group \(G\) of a lattice \(L\) which is defined to be the group of those automorphisms of the \({\mathbb{Z}}\)-module underlying \(L\) which preserve the inner product of \(L\). The proper automorphisms are the ones that also preserve orientation (have determinant \(1\)). \(L\) must be an exact lattice (over \({\mathbb{Z}}\) or \({\mathbb{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). 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, \(G\) does not act on the elements of \(L\). However, if the rank of \(L\) equals its degree, then the parameter NaturalAction may be set to \(\texttt{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 satisfactory performance. For difficult examples the parameters described below allow to consider further invariants which are more sophisticated and harder to compute, but often find dead ends in the backtrack at an early stage.

The algorithm computes and stores a set of short vectors in the lattice that spans the lattice and is guaranteed closed under the action of the automorphism group. This restricts its general application, as for high dimensional lattices the number of vectors of minimal length may be too large to work with. 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 chooses the basis to speed up the computation.

The parameter Depth is retained for compatibility with previous versions of Magma (which used Souvignier’s AUTO program) but it is now ignored. The improved backtrack search achieved by using ordered partition methods has made the Depth concept unnecessary.

In some 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 may 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. Setting BacherDepth to zero forbids the use of Bacher polynomial invariant. Setting it to anything else allows the algorithm to use this invariant at level 1. 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.

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.

Since V2.13, the algorithm has had the ability to first attempt to compute an orthogonal decomposition of \(L\) by considering the sublattices spanned by the set of shortest vectors, and if there is a non-trivial decomposition the automorphism group is computed via an algorithm of G. Nebe which computes the automorphism groups for the components and combines these. This decomposition method can be invoked by setting Decomposition to true.

When decomposition is suppressed, it is possible to supply the backtrack algorithm with the set of vectors to be used as domain for the search. To do this set the parameter Vectors to be a matrix so that the rows of the matrix give the lattice elements to be used. (Only one of a vector and its negative should be given.) To guarantee correctness of the result, the rows of the matrix should satisfy two conditions:

•

The rows, together with their negations, must be closed under the action of the full automorphism group, and

•

The sublattice of \(L\) generated by the rows of the matrix must equal \(L\).

These conditions are not checked by the code, and it is up to the user of this parameter to ensure the correctness of their input. For example, the function ShortVectorsMatrix returns a matrix which satisfies the first condition. If the first condition is not satisfied, there are no guarantees about what will happen. The second condition may be violated and still give a useful result. In particular, if the sublattice generated by the vectors given has finite index in the full lattice, then the final result will be the correct automorphism group. The problem is that the backtrack search may not be particularly efficient. This may still be better than working with a very large set of vectors satisfying the second condition.

AutomorphismGroup(L, F): Lat, [ AlgMatElt ] -> GrpMat

AutomorphismGroup(L, F): Lat, { AlgMatElt } -> GrpMat

Stabilizer : RngIntElt                        Default: 0
BacherDepth: RngIntElt                        Default: 0
Generators : [ GrpMatElt ]                    Default: 
Vectors    : Mtrx                             Default: 

This function computes the subgroup of the automorphism group of the lattice \(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.

AutomorphismGroup(F): [ AlgMatElt ] -> GrpMat

Stabilizer : RngIntElt                        Default: 0
BacherDepth: RngIntElt                        Default: 0
Generators : [ GrpMatElt ]                    Default: 

This function computes the matrix group fixing all forms given as matrices 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.

Example: Auto Action (ex-2d044f)

In this example we compute the automorphism group of the root lattice \(E_8\) and manually transform the action on the coordinates into an action on the lattice vectors. Note that this exactly the same as using the NaturalAction parameter for the function AutomorphismGroup.

> 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

Run in calculatorCopy input

Example: Auto L19 (ex-c6d08f)

> L := Lattice("Lambda", 19);
> time G := AutomorphismGroup(L);
Time: 0.300
> #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 ]

Run in calculatorCopy input

Hence, \(G := {\rm Aut}(\Lambda_{19})\) has a series of normal subgroups with factors \(2^2, 3, 2^2, A_5, 2^8, 2^4, 2\).

IsIsometric(L, M): Lat, Lat -> BoolElt, AlgMatElt

IsIsomorphic(L, M): Lat, Lat -> BoolElt, AlgMatElt

IsProperlyIsometric(L, M): Lat, Lat -> BoolElt, AlgMatElt

BacherDepth    : RngIntElt                        Default: 0
LeftGenerators : [ GrpMatElt ]                    Default: 
RightGenerators: [ GrpMatElt ]                    Default: 
LeftVectors    : Mtrx                             Default: 
RightVectors   : Mtrx                             Default: 
Decomposition  : BoolElt                          Default: false
NaturalAction  : BoolElt                          Default: false

This function determines whether the lattices \(L\) and \(M\) are (properly) isometric. 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. If they are properly isometric, return such \(T\) with \(\det(T) = 1\).

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 RightGenerators := 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. Similarly, generators for an automorphism group of the first lattice may be supplied as LeftGenerators.

Corresponding to the Vectors parameter for automorphism group calculation, the parameters LeftVectors and RightVectors allow the user to. As above, left refers to the first lattice, right to the second. Either both of these parameters can be set, or neither, an error results if just one is set. The restrictions on what constitutes correct values for these parameters are as for the Vectors parameter above. For correct isometry testing, the vectors given must be such that any isometry will map the left vectors into the union of the right vectors and their negatives. These conditions are not checked in the code, they are the responsibility of the user.

Corresponding to the NaturalAction parameter for automorphism group calculation, the parameter NaturalAction allows the user to get the natural action of the isometry 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 isometry of an integral basis vector will always be integral.

IsIsometric(L, F₁, M, F₂): Lat, [ AlgMatElt ], Lat, [ AlgMatElt ] -> BoolElt, AlgMatElt

IsIsomorphic(L, F₁, M, F₂): Lat, [ AlgMatElt ], Lat, [ AlgMatElt ] -> BoolElt, AlgMatElt

IsIsometric(L, M): Lat, Lat -> BoolElt, AlgMatElt

IsIsomorphic(L, M): Lat, Lat -> BoolElt, AlgMatElt

BacherDepth    : RngIntElt                        Default: 0
LeftGenerators : [ GrpMatElt ]                    Default: 
RightGenerators: [ GrpMatElt ]                    Default: 
LeftVectors    : Mtrx                             Default: 
RightVectors   : Mtrx                             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.

IsIsometric(F₁, F₂): [ AlgMatElt ], [ AlgMatElt ] -> BoolElt, AlgMatElt

IsIsomorphic(F₁, F₂): [ AlgMatElt ], [ AlgMatElt ] -> BoolElt, AlgMatElt

BacherDepth    : RngIntElt                        Default: 0
LeftGenerators : [ GrpMatElt ]                    Default: 
RightGenerators: [ GrpMatElt ]                    Default: 
LeftVectors    : Mtrx                             Default: 
RightVectors   : Mtrx                             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.

Example: Isom (ex-b3397d)

We construct the 16-dimensional Barnes-Wall lattice in two different ways and show that the so-obtained lattices are isometric.

> 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

Run in calculatorCopy input

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]

Run in calculatorCopy input

Automorphism Group and Isometry Testing over \({\mathbb{F}}_q[t]\)

Let \(q\) be some power of an odd prime. A bilinear form \(b\) over \({\mathbb{F}}_q[t]\) is said to be definite if the corresponding quadratic form is anisotropic over the completion of \({\mathbb{F}}_q(t)\) at the infinite place \((1/t)\).

The functions in this section compute automorphism groups and isometries of definite bilinear forms over \({\mathbb{F}}_q[t]\).

DominantDiagonalForm(X): Mtrx[RngUPol] -> Mtrx, Mtrx, GrpMat, FldFin

Canonical     : Bool                      Default: false
ExtensionField: FldFin                    Default: 

Let \(X\) be a symmetric \(n\times n\)-matrix of rank \(n\) over a polynomial ring \(K[t]\) where \(K\) denotes a field of characteristic different from \(2\). The function returns a symmetric matrix \(G\) and some \(T \in {\operatorname{GL}}(n, K[t])\) such that \(G = T X T^{tr}\) has dominant diagonal. I.e. the degrees of the diagonal entries of G are ascending and the degree of a non-diagonal entry is less than the degrees of the corresponding diagonal entries (see [Gerstein, 2003]).

If \(K\) is a finite field and \(X\) represents a definite form and Canonical is set to true, then the form \(G\) will be unique and the third return value will be the automorphism group of \(G\) i.e. the stabilizer of \(G\) in \({\operatorname{GL}}(n, K[t])\). The algorithm employed is [Kirschmer, 2012]. Note however, the uniqueness depends on some internal choices being made. Thus the fourth return value is a finite field \(E\) which must be given as the optional argument ExtensionField in subsequent runs over \(K\) to ensure that results are compatible (c.f. the following example). In particular, the defining polynomial and the primitive element of \(E\) are important for the uniqueness.

Example: DDF Fqt (ex-898cdb)

We test whether two definite forms over \({\mathbb{F}}_q[t]\) are isometric.

> R<t> := PolynomialRing( GF(5) );
> X1:= SymmetricMatrix([ t^3, t+1, 2*t^2+2*t+2 ] );
> X2:= SymmetricMatrix([ t^3, t^4+2*t+2, t^5+2*t^2+2*t+3 ]);
> G1, T1, Aut, E:= DominantDiagonalForm(X1 : Canonical);
> T1 * X1 * Transpose(T1) eq G1;
true
> GG:= [ Matrix(g) : g in Generators(Aut) ];
> forall{g : g in GG | g * G1 * Transpose(g) eq G1 };
true

Run in calculatorCopy input

So the form \(G_1\) is invariant under \(Aut\). Now we reduce the second form \(X_2\). To be able to compare the results, we have to provide the field \(E\) from above.

> G2, T2 := DominantDiagonalForm(X2 : Canonical, ExtensionField:= E);
> G1 eq G2;
true

Run in calculatorCopy input

Thus the two forms \(X_1\) and \(X_2\) are isometric and \(T_1^{-1}T_2\) is an isometry.

AutomorphismGroup(G): Mtrx[RngUPol] -> GrpMat, FldFin

ExtensionField: FldFin                    Default: 

Computes the automorphism group of the definite bilinear form given by the symmetric matrix \(G\) over \({\mathbb{F}}_q[t]\).

The second return value is a finite field as explained in DominantDiagonalForm above. It may be supplied for later calls over the same ground field \({\mathbb{F}}_q\) via the optional argument ExtensionField to safe some time if \(q\) is large. The correctness of the algorithm does not depend on it.

IsIsometric(G1, G2): Mtrx[RngUPol], Mtrx[RngUPol] -> BoolElt, Mtrx, FldFin

ExtensionField: FldFin                    Default: 

Tests whether two definite bilinear forms over \({\mathbb{F}}_q[t]\) are isometric. If so, the second return value is a matrix \(T \in {\operatorname{GL}}(n, q)\) such that \(T G1 T^{tr} = G2\).

The third return value is a finite field as explained in DominantDiagonalForm above. It may be supplied for later calls over the same ground field \({\mathbb{F}}_q\) via the optional argument ExtensionField to safe some time if \(q\) is large. The correctness of the algorithm does not depend on it.

ShortestVectors(G): Mtrx[RngUPol] -> SeqEnum

Returns a sequence \(Q\) which contains the shortest non-zero vectors with respect to a given definite bilinear form \(G\) over \({\mathbb{F}}_q[t]\) where \(q\) is odd. The sequence \(Q\) contains tuples \(<v,r>\) where \(v\) is a shortest vector and \(r\) denotes its norm with respect to \(G\).

ShortVectors(G, B): Mtrx[RngUPol], RngIntElt -> SeqEnum

Let \(G\) be a definite bilinear form of rank \(n\) over \({\mathbb{F}}_q[t]\) for some odd \(q\). The function returns a sequence \(Q\) which contains all vectors in \({\mathbb{F}}_q[t]^n\) whose norm with respect to \(G\) is at most \(B\). The sequence \(Q\) contains tuples \(<v,r>\) where \(v\) is such a short vector and \(r\) denotes its norm with respect to \(G\).