Integral lattices are a fundamental topic in computational algebra, both for their own sake and also as the basis for numerous applications. For example, the LLL algorithm is used in such diverse places as polynomial factorisation, cryptography, solution of conics (and higher dimensional quadratic equations), computation of character tables of groups, and recognition of algebraic numbers from real, complex, or p-adic approximations. Indeed, these are all applications based on an ability to find short vectors in a lattice, while LLL itself actually has a number of additional uses. Magma additionally provides routines for other (stronger) types of reduction, such as the HKZ or BKZ algorithms, which can be of use in specific problems.
Magma also includes the best available algorithm for computing automorphism groups of lattices. Another novel feature is the ability to use the short vector enumeration routines to recognise the Θ-series of a lattice as a modular form, exploiting Atkin–Lehner involutions when applicable.
Additional functionality for lattices includes the computation of Voronoi cells, genus and neighbour theory, and Hermitian structures (including over quaternion algebras). Finally, Magma provides access to standard lattice constructions, and contains a version of the Nebe–Sloane lattice database.
As noted in the Introduction, the workhorse algorithm for lattice applications is typically the LLL algorithm of Lenstra, Lenstra, and Lovász. This works by finding a lattice basis for which an explicit (and small) bound can be given regarding the size of vectors in terms of linear combinations of the basis vectors. Although, in general, finding a vector having the smallest norm is an NP-complete problem, the LLL algorithm usually succeeds in finding lattice vectors that are nearly as short, and much closer to the true minimum than the typical worst-case bounds would imply.
The Magma LLL implementation is a modern robust version of the LLL2 algorithm by Nguyen and Stehlé, which handles underflow and numerical stability problems at very little cost of overhead, and provides completely rigourous bounds on the floating-point operations when desired. This was implemented by Stehlé during a two year secondment to the Magma group.
Magma also contains stronger forms of lattice reduction, most particularly BKZ (block Korkine–Zolotarev) and HKZ (a Hermite version, corresponding to the whole lattice as a block). These can be useful when searching for small vectors in a lattice (as described in the next subsection), as the enumeration cost can be notably smaller. Again the implementation is due to Stehlé.
Finally, Magma has routines for pair and Seysen reduction, the former being a much simplified reduction scheme (only pairs of vectors are considered in the conditions for a lattice to be reduced, rather than blocks as in LLL), while the latter is useful for (say) reducing a lattice and its dual simultaneously.
Magma contains a state-of-the-art implementation of short vector enumeration due to Stehlé. The method is completely rigorous (using explicit error bounds of Pujol and Stehlé), and additionally is more efficient than previous methods of Kannan and Fincke–Pohst or Schnorr–Euchner. Furthermore, in applications where an exact count of short vectors is not needed, one can use the idea of pruning arrays (essentially, search in the parts of the ellipsoids which contains the most volume) to expedite the process in a probabilistic manner.
These methods for finding short vectors were vital in the proofs of lattice extremality for 80-dimensional lattices that are described below. One would typically find, say, 105 short vectors of norm 10 in a given basis, apply a random transformation and re-apply LLL (and possibly BKZ), then find 105 short vectors in the next basis, etc. In the presence of a sufficiently large (known) automorphism group, this is a viable path to finding all vectors of a given length in a suitable manner.
The Θ-series of a lattice (usually taken to be integral) is defined as Θ(L) = ∑v q| v | , or possibly by replacing q→√q when the lattice is even. This is a modular form of weight d/2 where d is the lattice dimension (or rank), and thus specifying finitely many coefficients suffices to identify the Θ-series in the modular forms space. The level of the modular form is related to the determinant of lattice, essentially having the same prime divisors.
Watkins and Donnelly have worked out an efficient scheme to compute the modular form for a wide variety of lattices. In particular, their method uses the Atkin–Lehner involutions on the modular forms, as transferred to partial duals of the lattice, to reduce the amount of coefficients needed by a factor of 2w, where w is the number of such involutions (essentially the number of prime divisors of the level or lattice determinant). Given that the enumeration methods themselves scale in a manner dependent on the dimension, this is a tremendous time-gain in practice (easily a factor of a million or more in typical 32-dimensional cases). The method is most robust in dimensions divisible by 4 with lattices of square determinant; in this case, the modular form is for a Γ0 congruence subgroup, and the Atkin–Lehner involutions take a simpler form. In general, one can append a form of small dimension to reduce to this case, removing the effect of its Θ-series by taking a quotient in the final result.
In this manner, at the request of Neil Sloane, a modular form has been produced for almost all the lattices of dimension up to 36 in the Nebe–Sloane database.
Magma contains a hightly efficient backtrack search program to compute the automorphism group of a lattice. This was developed and implemented by W. Unger (Magma), and operates by finding images of basis vectors and using invariants (such as Bacher polynomials) which must be preserved by automorphisms. The input to the program is a (complete) list of short vectors, computing as previously described.
This has recently been used by G. Nebe to show that her new extremal unimodular 48-dimensional lattice has automorphism group of size 1200 (and no larger). This computation took two months and involved the 26,208,000 (pairs of) minimal vectors of norm 6. This example is particularly hard because there are very few useful invariants that are easy to compute, and so many images of the minimal vectors must be typically be considered.
Additional work of automorphism groups and extremal unimodular lattices has been done in Magma group by D. Stehlé and M. Watkins. For instance, they showed that a 80-dimensional lattice associated to the extended binary quadratic code of length 79 was indeed extremal (a long outstanding question), via enumerating 7,541,401,190,400 vectors of norm 10 and using the nonnegativity of the Θ-series. The process was expedited by use of the automorphism group, which here is SL2(F79). Watkins was later able to show extremality for another 80-dimensional lattice, and computed (provably) the full automorphism group for these examples and others of similar size.
Magma can also find automorphisms which fix an additional quadratic form (other than just the Gram matrix). This allows one to determine Hermitian automorphism groups over imaginary quadratic fields, and also over quaternionic structures. For instance, Magma takes 25 seconds to compute that the quaternionic automorphism group of the Leech lattice over the standard Hamiltonians has order 503,193,600. One can also invert the process; for instance, one can take the irreducible 6-dimensional representation of the group SU(3,3) and compute the invariant form for its G-module over the quaternion algebra ramified at 3 and ∞, realising the Coxeter–Todd lattice in this manner.