|
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
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 [PS97].
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.
Stabilizer: RngIntElt Default: 0
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] Default:
NaturalAction: Bool Default: false
TryDecomposition: Bool Default: true
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.
Since V2.13, the algorithm first attempts to compute an orthogonal
decomposition of L and if there is a non-trivial decomposition, then
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 suppressed by setting TryDecomposition
to {false}.
AutomorphismGroup(L, F) : Lat, AlgMatElt -> GrpMat
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 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
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
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 E8
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
In this example we demonstrate how stabilizers can be used
to obtain a big subgroup of the full automorphism group fairly quickly.
> 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: 0.020
> #G;
622080
We now show how the depth parameter can speed up the computation of
the automorphism group of a lattice quite significantly.
We first try the 2-point stabilizer with depth ranging from 0 to 5.
> L := Lattice("Lambda", 19);
> for i in [0..5] do
> time G := AutomorphismGroup(LLL(L) : Depth := i, Stabilizer := 2);
> end for;
Time: 1.400
Time: 1.710
Time: 1.910
Time: 0.790
Time: 0.830
Time: 1.280
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: 3.270
Time: 3.650
Time: 1.490
Time: 1.470
Time: 2.010
> 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)(Λ19) has a series of normal subgroups
with factors 22, 3, 22, A5, 28, 24, 2.
IsIsomorphic(L, M) : Lat, Lat -> BoolElt, AlgMatElt
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 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
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.
IsIsomorphic(L, F1, M, F()2) : Lat, [ AlgMatElt ], Lat, [ AlgMatElt ] -> BoolElt, AlgMatElt
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 F1 and F2.
The return values and parameters are as above.
IsIsomorphic(F1, F()2) : [ AlgMatElt ], [ AlgMatElt ] -> BoolElt, AlgMatElt
Depth: RngIntElt Default: 0
BacherDepth: RngIntElt Default: 0
BacherSCP: RngIntElt Default:
Generators: [ GrpMatElt ] 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.
This function determines whether the lattice L is isometric to a
sublattice of M. If so, 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.
In general, T will be defined over the rationals and not have
determinant +- 1.
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]
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
