|
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).
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 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 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.
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.
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.
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
> 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 2 2, 3, 2 2, A 5, 2 8, 2 4, 2.
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 F2 = T F1 Ttr, where F1 and
F2 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.
IsIsomorphic(L, F1, M, F()2) : 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 F1 and F2.
The return values and parameters are as above.
IsIsomorphic(F1, F()2) : [ AlgMatElt ], [ AlgMatElt ] -> BoolElt, AlgMatElt
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.
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
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.
We test whether two definite forms over 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
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
Thus the two forms X 1 and X 2 are isometric and T 1 - 1T 2
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.
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|