Computing isometries of lattices

W. Plesken  B. Souvignier

Introduction. We report on some new ideas to calculate the group of automorphisms of a lattice with a positive definite quadratic form, which lead to an improvement of an algorithm described in [PlP 85] and [Sou 91]. To illustrate the reach of the algorithm e.g. 2 matrices generating the automorphism group of the Leech lattice can be calculated in less than 3 hours on a HP 9000/730 workstation. Moreover, the automorphism group of the densest known lattice Q_{32} in dimension 32 (cf. [Que 84]) is for the first time determined in this paper. The algorithm has successfully been used in various situation cf. for instance [Sch 92], [PlN 93], [PlP 93], or [Sou 94].

Notation. Let L be a ZZ-lattice of rank n, Φ : L × L → ZZ a positive definite bilinear form on L, B = (b_{1} … b_{n}) a ZZ-basis of L and F the Gram matrix of Φ with respect to B, i.e. F_{ij} := Φ(b_{i}, b_{j}). Denote by G the automorphism group of L and by G_{i} the pointwise stabilizer of b_{1}, …, b_{i−1} in G. Let S be the (finite) set of vectors v ∈ L of norm Φ(v, v) up to max(F_{ii}|1 ≤ i ≤ n).

The basic idea. For k ≤ n call (v_{1}, …, v_{k}) a k-partial automorphism if Φ(v_{i}, v_{j}) = F_{ij} for 1 ≤ i, j ≤ k. Obviously the n-partial automorphisms represent the automorphisms of L. Whereas Witt’s Theorem on extending partial isometries guarantees that every k-partial automorphism extends to an automorphism in case of vector spaces over fields, here it can happen that a k-partial automorphism can not even be extended to a (k+1)-partial automorphism. Because of the finiteness of S testing whether for k < n a k-partial automorphism extends to a (k+1)-partial automorphism can be checked in reasonable time. However, it is highly desirable in a backtrack search to reject as early as possible k-partial automorphisms not extending to automorphisms. One therefore has to find in addition to the scalar products further testable properties of k-partial automorphisms, which are restrictions of n-partial automorphisms.

The Fingerprint. One property, which was already used in the algorithm in [PlP 85], is that the number of extensions of a k-partial automorphism to a (k+1)- partial automorphism must be preserved by automorphisms. These numbers can also be used to obtain a better ordering for the b_{i}. This information is stored in a matrix, called fingerprint, which is calculated as follows: Suppose that the indices j_{1} … j_{i−1} are already chosen, then define f_{ik} by f_{ik} := 0 if k ∈ {j_{1} … j_{i−1}} and f_{ik} := |{v ∈ S|Φ(v, v) = F_{kk} and Φ(v, b_{j_{l}}) = F_{kj_{l}} for l = 1 … i − 1}| else. Now choose j_{i} such that f_{ij_{i}} is minimal among the f_{ik} ≠ 0. Then b_{i} ↦ b_{j_{i}} is a permutation of the basis vectors such that in each step the possible number of continuations of a partial automorphism is minimal. To avoid a mess of indices we assume for the rest of this paper that the permutation is the identity, i.e. j_{i} = i for all i. Define f_{i} := f_{ii}, then one has |G| ≤ ∏_{i=1}^{n} f_{i}, since f_{i} is an upper bound for the length of the orbit b_{i}G_{i}. A measure how ill-conditioned a lattice (and its basis) is for this algorithm is the product ∏_{i=k+1}^{n} f_{i}, where k is the minimal index such that f_{k} ≠ |b_{k}G_{k}|, since this is a (realistic) upper bound for the number of dead ends in the backtrack search after choosing a wrong image for b_{k}. Clearly this can only be analyzed a posteriori.

Vector sums. Especially for lattices, which do not have a big symmetry, the fingerprint alone does not suffice to detect dead ends early enough. Instead of counting the number of vectors with correct scalar products only, one can also take into account arbitrary combinations of scalar products and not only count the vectors having this combination of scalar products but use their sum. More precisely: For s = (s_{1}, …, s_{l}) ∈ ZZ^{l} and an l-partial automorphism \underline{v} = (v_{1}, …, v_{l}) define X_{s}(\underline{v}) := \{w ∈ S|Φ(w, v_{i}) = s_{i} for i = 1, …, l\} and \overline{X_{s}}(\underline{v}) := ∑_{w∈X_{s}(\underline{v})} w. Then for an automorphism φ of L one has \overline{X_{s}}(b_{1}, …, b_{l})φ = \overline{X_{s}}(b_{1}φ, …, b_{l}φ).

The preprocessing of the algorithm consists of the computation of the fingerprint and of the vector sums. What is stored after the preprocessing is:

1) The fingerprint.

2) For each 1 ≤ l ≤ n:

a) a ZZ-basis B_{l} of the lattice generated by the \overline{X_{s}}(b_{1}, …, b_{l}), expressed as a linear combination of certain of the \overline{X_{s}}(b_{1}, …, b_{l}),

b) the scalar products of the vectors in B_{l},

c) the coordinates of all \overline{X_{s}}(b_{1}, …, b_{l}) with respect to B_{l}.

Since the number of vectors \overline{X_{s}} explodes for growing l, it turned out to be efficient to replace the sets X_{s} by sets X′_{s}(v_{1}, …, v_{l}) := {w ∈ S|Φ(w, v_{i}) = s_{i} for i = l_{0}, …, l} with l_{0} := max(1, l + 1 − d), where d is some chosen constant, which we call the depth parameter. The value d = 0 corresponds to the old method using only the fingerprint, the value d = 1 more or less to the old method using “types” for the elements of S in addition.

The backtrack search. Suppose that (v_{1} … v_{i−1}) is an (i-1)-partial automorphism and let C_{i} be the list of candidates for the image of b_{i} which have not yet been tested as a continuation of (v_{1} … v_{i−1}). Choose a vector v ∈ C_{i}, replace C_{i} by C_{i} − {v} and check whether the number of possible continuations of (v_{1}, …, v_{i−1}, v) is f_{i+1}. Then calculate the vector sums \overline{X_{s}}(v_{1}, …, v_{i−1}, v) and with the help of the coefficients stored in 2a) the “pseudo image” B′_{l} of the basis B_{l}. Now check, whether the scalar products of the vectors in B′_{l} coincide with those stored in 2b) and whether the linear combinations of the vectors in B′_{l} with the coefficients stored in 2c) coincide with the vector sums \overline{X_{s}}(v_{1}, …, v_{i−1}, v). If all conditions are fulfilled, set v_{i} := v and proceed to the next step, else choose the next vector from C_{i}. If C_{i} = ∅ decrease i until C_{i} ≠ ∅.

The stabilizer chain. What has been said so far, refers to the calculation of just one automorphism. To obtain the full group of automorphisms one follows the concept of strong generating sets as introduced in [Sim 71] with B as base for the action of G, i.e. one calculates a generating set G for G such that G_{i} is generated by G ∩ G_{i} for i = 1, …, n. For the construction of the set G one has two methods: Schreier generators lying in G_{i+1} are obtained as quotients of two elements in G_{i} mapping b_{i} to the same vector v. These are cheap, however do not increase the group H ≤ G constructed so far. On the other hand one obtains generators from the backtrack search. Here the fingerprint gives a good guideline: Let k be minimal such that |b_{k}H_{k}| < f_{k}, where H_{k} := ⟨G ∩ G_{k}⟩ and let C_{k} be the set of candidates for the image of b_{k} not lying in b_{k}H_{k}, then check for representatives v of the orbits of H_{k} on C_{k}, whether there exists γ ∈ G_{k} with b_{k}γ = v. If such a γ exists, replace G by G ∪ {γ}, H_{k} by ⟨H_{k}, γ⟩ and the orbits by their fusions under γ. If not, replace f_{k} by f_{k} − |vH_{k}|. Then remove vH_{k} from C_{k}.

Examples. An example showing the quality of the fingerprint is the Leech lattice. We choose a basis of norm 4 vectors. For our choice the values for f_{k} resp. |b_{k}G_{k}| are:

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 … 24 \\ f_{k} & 196560 & 4600 & 891 & 336 & 32 & 40 & 7 & 2 & 1 & 1 & 2 & 1 \\ |b_{k}G_{k}| & 196560 & 4600 & 891 & 336 & 32 & 40 & 6 & 2 & 1 & 1 & 2 & 1 \end{matrix}

The full automorphism group 2.Co_{1} of order 2^{22} · 3^{9} · 5^{4} · 7^{2} · 11 · 13 · 23 can be calculated in less than 3 hours CPU-time on a HP 9000/730. In contrast to that one has for a lattice in the genus of the 16-dimensional Barnes-Wall lattice (cf. [ScV 93] lattice L_{4} with root system 8C_{2}), generated by vectors of norm 2 and 4:

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ f_{k} & 32 & 30 & 28 & 26 & 16 & 4 & 3 & 2 & 16 & 8 & 3 & 2 & 4 & 2 & 4 & 2 \\ |b_{k}G_{k}| & 32 & 28 & 24 & 4 & 16 & 1 & 1 & 1 & 16 & 8 & 2 & 1 & 4 & 2 & 4 & 2 \end{matrix}

Choosing the depth d = 5 the automorphism group of order 2^{30} · 3 · 7 can be computed in 16 seconds. For d = 4 it takes already more than 5 minutes. Using only the fingerprint (d = 0) there was no result even after 50 hours. A really involved example is the densest known lattice Q_{32} in dimension 32, which is described in [Que 84]. With respect to some basis of norm 6 vectors one has:

\begin{matrix}k & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 … 32 \\ f_{k} & 261120 & 1520 & 192 & 2 & 189 & 4 & 3 & 1 \\ |b_{k}G_{k}| & 1920 & 2 & 1 & 1 & 18 & 1 & 3 & 1 \end{matrix}

With depth d = 4 it takes already 1 hour CPU-time to calculate G_{3} and then another 12 hours to calculate G_{2}, which would be impossible using only the fingerprint. For larger values of d the number of vector sums becomes too large to be stored. The full group G of automorphisms has order 2^{9} · 3^{4} · 5 and is absolutely irreducible as matrix group. It has the structure of the central product 2.A_{6} Y H extended by V_{4}, where H is the subdirect product of C_{3}^{2} : V_{4} and Q_{16} amalgamated over the common factor group V_{4}. The largest perfect subgroup of G is G^{(3)} ≅ 2.A_{6} and restricted to this subgroup the natural representation has two absolutely irreducible constituents of degree 4, each with multiplicity 4. The automorphism group leaves invariant a sublattice of Q_{32} of index 3^{8}, which decomposes into two copies of a 16-dimensional 6-modular lattice L with |Aut(L)| = 2^{10} · 3^{6} · 5 and 960 shortest vectors (of norm 6), cf. [PlN 93].

Variations. With minor modifications this algorithm can also be applied to other problems, e.g.:

1) Isometries between two lattices L and L′: the fingerprint and vector sums are calculated with respect to a basis B of L, then a basis of L′ having the same scalar products as the vectors in B is searched.

2) Bravais groups: the single Gram matrix, which is fixed by automorphisms can clearly be replaced by a collection of Gram matrices.

3) Automorphisms of lattices over number fields with a totally positive bilinear or hermitian form taking values in the ring of integers of the number field, cf. e.g. [Sch 92]: these lattices can be dealt with as lattices over ZZ with several ZZ-valued bilinear forms, at least one of which is symmetric and positive definite.

Bibliography

[PlN 93] W. Plesken, G. Nebe, Finite rational matrix groups. Preprint, 1993

[PlP 85] W. Plesken, M. Pohst, Constructing Integral Lattices With Prescribed Minimum.I. Math. Comp., Vol. 45, No. 171, pp. 209-221, 1985

[PlP 93] W. Plesken, M. Pohst, Constructing Integral Lattices With Prescribed Minimum.II. Math. Comp., Vol. 60, No. 202, pp. 817-825, 1993

[Que 84] H.-G. Quebbemann, A construction of integral lattices. Mathematika 31, pp. 137-140, 1984

[Sch 92] R. Scharlau, Unimodular lattices over real quadratic fields. Preprint 92-039, SFB 343 Universität Bielefeld, 1992

[ScV 93] R. Scharlau, B.B. Venkov, The genus of the Barnes-Wall lattice. Preprint, 1993

[Sim 71] C.C. Sims, Determining the conjugacy classes of a permutation group. Computers in Algebra and Number Theory, SIAM-AMS Proc. 4 pp. 191-195, 1971

[Sou 91] B. Souvignier, Die irreduziblen Bravaisgruppen in GL_{8}(ZZ). Diplomarbeit, RWTH Aachen, 1991

[Sou 94] B. Souvignier, Irreducible finite integral matrix groups of degree 8 and 10. To appear in Math. Comp., 1994 Lehrstuhl B für Mathematik Rheinisch-Westfälische Technische Hochschule Aachen Templergraben 64 D-52062 Aachen Germany