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.
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.
Inner product, norm, and length of lattice elements with respect to the inner product on the lattice
Rank, determinant, basis, basis matrix, inner product matrix, Gram matrix, testing for integrality and evenness, index in a superlattice
Sum, intersection, direct sum, tensor product, exterior square, symmetric square of lattices
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
Action on lattice elements by matrices
Several families of 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 and subsequently used for many operations.
Central to the lattice machinery in Magma is a highly optimized LLL algorithm which constructs a basis of the lattice which is LLL-reduced. Usually the vectors of the new basis have very small norms. The default method for LLL reduction in Magma is based on the rigorous floating-point LLL algorithm of Nguyen and Stehlé.
LLL reduction of lattices using the Nguyen-Stehlé floating-point method. This is actually a family of algorithms that allow the user to choose the degree of reduction ranging from a guaranteed LLL basis to much weaker but faster reduction.
LLL reduction of lattices using the exact de Weger integral method
LLL reduction of lattices using the Schnorr-Euchner deep insertion strategy
HKZ (Hermite-Korkine-Zolotarev) reduction of lattices, a stronger form of reduction than LLL
Gauss reduction is available for 2-dimensional lattices. This is guaranteed to produce a basis whose vectors have norms which achieve the minimum
Seysen reduction of a lattice L, that is, the construction of a lattice L' from L such that L' and its dual are simultaneously reduced
Pairwise reduction of lattices, basis matrices and Gram matrices
Orthogonalization and orthonormalization (Cholesky decomposition) of a lattice
Testing matrices for being positive or negative (semi-)definite
The Nguyen-Stehlé floating-point method for LLL reduction 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 may also be reduced in some cases.
Magma includes a highly optimized algorithm for enumerating all short vectors in a lattice with given norm. This algorithm, developed by Damien Stehlë, 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.
Enumeration of all shortest vectors of a lattice
Enumeration of all short vectors of a lattice having norm in a given range
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
Minimum, packing radius, kissing number
Hermite constant, centre density, density
Successive minima, theta series
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
As an example, the 98280 (normalized) shortest vectors of the Leech lattice Λ24 are constructed in 0.47 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
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.
In Magma, a G-lattice L is a lattice upon which a finite integral matrix group G acts by right multiplication. Magma provides support for computations with G-lattices. The most important operation is the calculation of the automorphism group of a lattice.
The computation of the automorphism group of a lattice (i.e. the largest matrix group that acts on the lattice) and the testing of lattices for isometry is performed within Magma using orthogonal decomposition (due to Gabi Nebe) and a backtrack search designed by Bill Unger in 2009. The backtrack search is based on the Plesken-Souvignier backtrack algorithm [PS97] together with ordered partition methods due to Leon.
Automorphism group of a lattice
Subgroup of the automorphism group of a lattice fixing specified bilinear forms
Determination as to whether two lattices are isometric
Determination as to whether two lattices are isometric in such a way that specified bilinear forms are fixed
Determination as to whether a simultaneous isometry exists between two sequences of lattices
Determination as to whether a lattice has an isometric embedding into a second lattice
The automorphism group of the 24-dimensional Leech lattice Λ24 is found in 18.760 seconds. The group has order 8315553613086720000 and is the double cover of the sporadic simple group Co1.
If G is a finite integral matrix group, then Magma uses the Plesken centering algorithm ([Ple74]) to construct all G-invariant sublattices of a given G-lattice L. The lattice of G-invariant sublattices of L can be explored in much the same way as the lattice of submodules of an A-module, where A is an algebra over a finite field.
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
Space of invariant bilinear forms
Symmetric forms, antisymmetric forms, positive definite symmetric form
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
G-invariant sublattices of finite index of either a G-lattice or integral matrix group
A G-invariant sublattice of a lattice G can be created as a lattice of subsets with respect to inclusion. All the standard operations for working with this lattice are provided: e.g., meet, join, maximal sublattices, minimal overlattices.
A quadratic form may be given either as a Magma lattice, as a multivariate polynomial or as a symmetric matrix. The major feature provided is Simon's algorithm for finding isotropic subspaces of integral forms.
Representation of a quadratic form either as a multivariate polynomial or as a symmetric matrix.
The p-signature of a form defined over the rationals, for p a prime
The p-excess of a form defined over the rationals, for p a prime
The Witt (or Hasse-Minkowski) invariant over Qq. The form must be defined over ℤ or Q.
Construction of an isotropic subspace using an algorithm due to Simon. The form must be defined over ℤ or Q. In many cases the subspace returned will be guaranteed to be a maximal totally isotropic subspace.
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. Magma contains full functionality for forms of positive discriminant.
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)