A lattice in Magma is a ℤ-module contained in ℚn or ℝn, together with a positive definite inner product. The information specifying a lattice is a basis, given by a sequence of elements in ℤn, ℚn or ℝn, and a bilinear product (·,·), given by (v,w) = vMwtr for a positive definite matrix M. Central to the lattice machinery in Magma is a highly optimized LLL algorithm. The LLL algorithm takes a basis of a lattice and returns a new basis of the lattice which is LLL-reduced which usually means that the vectors of the new basis have small norms. The Magma LLL algorithm is based on the FP-LLL algorithm of Schnorr and Euchner and the de Weger integral algorithm but includes various optimizations, with particular attention to different kinds of input matrices. The rigorous LLL of Nguyen and Stehlé will be implemented in a future release.
Creation of a lattice by a given generating matrix or basis matrix together with an optional inner product matrix
Creation of a lattice by a given Gram matrix
Construction of lattices from codes
Construction of lattices from algebraic number fields
Construction of special lattices, including the root lattices An, Dn, En; the laminated lattices Λn (including the Barnes-Wall lattice Λ16 and the Leech Lattice Λ24); the Kappa lattices Kn, etc.
Creation of and arithmetic with lattice elements
Inner product, norm, and length of lattice elements with respect to the inner product of the lattice
Conversion between a lattice element and its coordinates with respect to the basis of a lattice (in both directions)
Action on lattice elements by matrices
Creation of sublattices and superlattices, scaling of lattices
Creation of quotient lattices (abelian group with isomorphism)
Dual of a lattice, dual quotient of a lattice
Arithmetic on lattices: sum, intersection, direct sum, tensor product, exterior square, symmetric square
Conversion between lattices and ℤ-modules and ℚ-modules.
Several interesting lattices are directly accessible inside Magma using standard constructions, e.g., root lattices and preimages of linear codes. For each lattice, a LLL-reduced basis for the lattice is computed and stored internally when necessary and subsequently used for many operations. This gives maximum efficiency for the operations, yet all the operations are presented using the external ("user") basis of the lattice.
Rank, determinant, basis, basis matrix, inner product matrix, Gram matrix, centre density, testing for integrality and evenness, index in a superlattice
Minimum of a lattice (which can also be asserted)
Kissing number of a lattice
Theta series of a lattice
Enumeration of all short vectors of a lattice having norm in a given range
Enumeration of all shortest vectors of a lattice
Enumeration of all vectors of a lattice having squared distance from a vector (possibly) outside the lattice in a given range
Enumeration of all vectors of a lattice closest to a vector (possibly) outside the lattice
Process to enumerate short or close vectors of a lattice thereby allowing manual looping over short vectors having norm in a given range or close vectors having squared distance in a given range
Pure lattice of a lattice over ℤ or ℚ
Construction of a fundamental Voronoi cell of a small-dimensional lattice
Holes, deep holes and covering radius of a lattice
Successive minima of a lattice
Magma includes a highly optimized algorithm for enumerating all vectors of a lattice of a given norm. This algorithm is used for computing the minimum, the shortest vectors, short vectors in a given range, and vectors close to or closest to a given vector (possibly) outside the lattice. As an example, the 98280 (normalized) shortest vectors of the Leech lattice Λ24 are constructed in 6.8 seconds. The genus of the 12-dimensional Coxeter-Todd lattice K12 is enumerated in 16 seconds and has 16 classes of lattices and mass 4649359/4213820620800≈0.000001103359.
LLL reduction of lattices, basis matrices and Gram matrices (with numerous parameters)
Seysen reduction of lattices, basis matrices and Gram matrices (for reducing a lattice and its dual simultaneously)
Pairwise reduction of lattices, basis matrices and Gram matrices
Orthogonalization and orthonormalization (Cholesky decomposition) of a lattice
Testing matrices for positive or negative (semi-)definiteness
The LLL algorithm can operate on either a basis matrix or a Gram matrix (and will use the Gram method even if given a basis matrix and it is deemed appropriate) and can be controlled by many parameters (δ constant, exact de Weger integral method or Schnorr-Euchner floating point method, step and time limits, selection of methods, etc.). The LLL algorithm can reduce matrices with very large entries as well as matrices having large sizes (e.g., number of rows well over 500). Indefinite Gram matrices can also be reduced in some cases.
Automorphism group of a lattice
Subgroup of the automorphism group of a lattice fixing specified bilinear forms
Determination of whether two lattices are isometric
Determination of whether two lattices are isometric in such a way that specified bilinear forms are fixed
The computation of the automorphism group of a lattice and the testing of lattices for isometry is performed using the AUTO and ISOM programs of Bernd Souvignier. The automorphism group Co0 of the 24-dimensional Leech lattice Λ24 is found in 175 seconds.
Computation of the p-neighbour of a lattice with respect to a given vector and prime p
The sequence of p-neighbours a lattice at a prime p
The transitive closure of the p-neighbour relation of a lattice at a prime p
Spinor genus of an integral lattice, returned as a sequence of isometry representatives
Genus of an integral lattice, returned as a sequence of isometry representatives
Adjacency matrix of a sequence of lattices under the p-neighbour relation, for a sequence closed under the p-neighbour relation
p-Adic Jordan form for lattices
Creation of G-lattices with associated operations
Invariant lattice of a rational matrix group and the associated action (thus yielding an integral representation of the group)
Bravais group of a finite rational matrix group
Invariant sublattices of finite index
Space of invariant bilinear forms
Positive definite invariant form of a rational matrix group
Endomorphism ring
Centre of the endomorphism ring
Dimension of the space of invariant bilinear forms, the endomorphism algebra or its centre using a modular algorithm
The lattice machinery has been developed by Bernd Souvignier and Allan Steel.
Binary quadratic forms serve as a model for ideals in quadratic fields. Forms of negative discriminant are identified with lattices in the complex plane, which is the natural domain for modular forms and functions. The class of binary quadratic forms is placed here for its connections to this theory. Magma contains full functionality for forms of positive discriminant which extends beyond the applications in this context.
Prime form, random form
Reduction of forms
Composition and powering
Enumeration of reduced forms and reduced orbits
Treatment of fundamental and nonfundamental discriminants
Class number and class group
Action of SL(2,ℤ) and PSL(2,ℤ)
Evaluation of modular functions on quadratic forms
Discrete logarithm of a form (for imaginary quadratic fields)