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 Z or Q).
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 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). 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 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.
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.
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.
> 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("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 ]
Hence, G := (Aut)(Λ19) has a series of normal subgroups
with factors 22, 3, 22, A5, 28, 24, 2.
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. 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 F2 = T F1 Ttr, where F1 and F2 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 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.
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 F1 and F2. The return values and parameters are as above.
BacherDepth: RngIntElt Default: 0
LeftGenerators: [ GrpMatElt ] Default:
RightGenerators: [ GrpMatElt ] Default:
LeftVectors: Mtrx Default:
RightVectors: Mtrx Default:
For two sequences of F1 and F2 of Gram matrices, determine whether a simultaneous isometry exists, i.e., a matrix T such that T F1[i] Ttr = F2[i] for i in [1..#F1]. 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]
Let q be some power of an odd prime. A bilinear form b over Fq[t] is said to be definite if the corresponding quadratic form is anisotropic over the completion of Fq(t) at the infinite place (1/t).
The functions in this section compute automorphism groups and isometries of definite bilinear forms over Fq[t].
Canonical: Bool Default: false
ExtensionField: FldFin Default:
Let X be a symmetric n x 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 ∈GL(n, K[t]) such that G = T X Ttr 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 [Ger03]).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 GL(n, K[t]). The algorithm employed is [Kir12]. 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.
> 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
So the form G1 is invariant under Aut. Now we reduce the
second form X2. 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; trueThus the two forms X1 and X2 are isometric and T1 - 1T2 is an isometry.
ExtensionField: FldFin Default:
Computes the automorphism group of the definite bilinear form given by the symmetric matrix G over Fq[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 Fq via the optional argument ExtensionField to safe some time if q is large. The correctness of the algorithm does not depend on it.
ExtensionField: FldFin Default:
Tests whether two definite bilinear forms over Fq[t] are isometric. If so, the second return value is a matrix T ∈GL(n, q) such that T G1 Ttr = 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 Fq via the optional argument ExtensionField to safe some time if q is large. The correctness of the algorithm does not depend on it.
Returns a sequence Q which contains the shortest non-zero vectors with respect to a given definite bilinear form G over Fq[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.
Let G be a definite bilinear form of rank n over Fq[t] for some odd q. The function returns a sequence Q which contains all vectors in Fq[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.