Lattices can be created in elementary ways whereby the basis matrix or a generating matrix and possibly also the inner product matrix are specified. Magma also provides functions for creating lattices from linear codes or algebraic number fields and for creating some special lattices.
This subsection describes the elementary ways of creating lattices by supplying the basis or the Gram matrix.
There are two ways of specifying the basis of a lattice at creation. First, a generating matrix can be specified whose rows need not be independent; the matrix is reduced to LLL-reduced form and zero rows are removed to yield a basis matrix. Secondly, a basis matrix (with independent rows) can be specified; this matrix is used for the basis matrix without any changes being made to it. As well as the basis, a particular inner product can also be specified by a symmetric positive definite matrix. By default (when a particular inner product matrix is not given), the inner product is taken to be the standard Euclidean product.
Instead of giving the basis one can also define a lattice by its Gram matrix
F which prescribes the inner products of the basis vectors. The basis is
taken to be the standard basis and the inner product matrix is taken as F so
that the Gram matrix for the lattice is also F.
Lattice(X, M) : ModMatRngElt, AlgMatElt -> Lat
CheckPositive: BoolElt Default: true
Construct the lattice L specified by the given generating matrix and with inner product given by the n x n matrix M. The generating matrix can be specified by an r x n matrix X, an integer n with a sequence Q of ring elements of length rn (interpreted as a r x n matrix), or an R-space S of dimension r and degree n. In each case, the generating matrix need not have independent rows (though it always will in the R-space case). The matrix is reduced to LLL-reduced form and zero rows are removed to yield a basis matrix B of rank m (so m <= r). The lattice L is then constructed to have rank m, degree n, basis matrix B and inner product matrix M. By default Magma checks that M is positive definite but by setting CheckPositive := false this check will be suppressed. (Unpredictable behaviour will follow if unchecked incorrect input is given.)
Construct the lattice L specified by the given generating matrix and with standard Euclidean inner product. The generating matrix can be specified by an r x n matrix X, an integer n with a sequence Q of ring elements of length rn (interpreted as a r x n matrix), or an R-space S of dimension r and degree n. In each case, the generating matrix need not have independent rows (though it always will in the R-space case). The matrix is reduced to LLL-reduced form and zero rows are removed to yield a basis matrix B of rank m (so m <= r). The lattice L is then constructed to have rank m, degree n, basis matrix B and standard Euclidean inner product.
CheckIndependent: BoolElt Default: true
CheckPositive: BoolElt Default: true
Construct the lattice L with the specified m x n basis matrix and with inner product given by the n x n matrix M. The basis matrix B can be specified by an m x n matrix B, an integer n with a sequence Q of ring elements of length mn (interpreted as an m x n matrix B), or an R-space S of dimension m and degree n (whose basis matrix is taken to be B). The rows of B must be independent (i.e., form a basis). The lattice L is then constructed to have rank m, degree n, basis matrix B and inner product matrix M. (Note that the basis matrix B is not reduced to LLL-reduced form as in the Lattice function.) By default Magma checks that the rows of the matrix B specifying the basis are independent but by setting CheckIndependent := false this check will be suppressed. By default Magma also checks that M is positive definite but by setting CheckPositive := false this check will be suppressed. (Unpredictable behaviour will follow if unchecked incorrect input is given.)
CheckIndependent: BoolElt Default: true
Construct the lattice L with the specified m x n basis matrix and with standard Euclidean inner product. The basis matrix B can be specified by an m x n matrix B, an integer n with a sequence Q of ring elements of length mn (interpreted as an m x n matrix B), or an R-space S of dimension m and degree n (whose basis matrix is taken to be B). The rows of B must be independent (i.e., form a basis). The lattice L is then constructed to have rank m, degree n, basis matrix B and standard Euclidean product. (Note that the basis matrix B is not reduced to LLL-reduced form as in the Lattice function.) By default Magma checks that the rows of the matrix B specifying the basis are independent but by setting CheckIndependent := false this check will be suppressed. (Unpredictable behaviour will follow if unchecked incorrect input is given.)
CheckPositive: BoolElt Default: true
Construct a lattice with the given Gram matrix. The Gram matrix F can be specified as a symmetric n x n matrix F, or an integer n and a sequence Q of ring elements of length n^2 or n + 1 choose 2. In the latter case, a sequence of length n^2 is regarded as an n x n matrix and a sequence of length n + 1 choose 2 as a lower triangular matrix determining a symmetric matrix F.This function constructs the lattice L of degree n having the standard basis and inner product matrix F, therefore having Gram matrix F as well. By default Magma checks that F is positive definite but by setting CheckPositive := false this check will be suppressed. (Unpredictable behaviour will follow if unchecked incorrect input is given.)
Create the standard lattice Z^n with standard Euclidean inner product.
> B := RMatrixSpace(IntegerRing(), 2, 3) ! [1,2,3, 3,2,1]; > B; [1 2 3] [3 2 1] > L1 := Lattice(B); > L1; Lattice of rank 2 and degree 3 Basis: ( 2 0 -2) ( 1 2 3) > L2 := Lattice(3, [1,2,3, 3,2,1]); > L2 eq L1; true > L3 := LatticeWithBasis(B); > L3; Lattice of rank 2 and degree 3 Basis: (1 2 3) (3 2 1) > L4 := LatticeWithBasis(3, [1,2,3, 3,2,1]); > L4 eq L3, L1 eq L3; true trueWe next create a 3 x 3 positive definite matrix M and create the lattice L with basis the same as above but also with inner product matrix M. We note the Gram matrix of the lattice which equals BMB^(tr) where B is the basis matrix.
> B := RMatrixSpace(IntegerRing(), 2, 3) ! [1,2,3, 3,2,1]; > M := MatrixRing(IntegerRing(), 3) ! [3,-1,1, -1,3,1, 1,1,3]; > M; [ 3 -1 1] [-1 3 1] [ 1 1 3] > IsPositiveDefinite(M); true > L := LatticeWithBasis(B, M); > L; Lattice of rank 2 and degree 3 Basis: (1 2 3) (3 2 1) Inner Product Matrix: [ 3 -1 1] [-1 3 1] [ 1 1 3] > GramMatrix(L); [56 40] [40 40]Finally, we create a lattice C with the same Gram matrix as the last lattice, but with standard basis. To do this we use the LatticeWithGram function. This lattice C is the coordinate lattice of L: it has the same Gram matrix as L but is not compatible with L since its inner product matrix is different to that of L.
> F := MatrixRing(IntegerRing(), 2) ! [56,40, 40,40]; > C := LatticeWithGram(F); > C; Standard Lattice of rank 2 and degree 2 Inner Product Matrix: [56 40] [40 40] > GramMatrix(C); [56 40] [40 40] > C eq CoordinateLattice(L); true > GramMatrix(C) eq GramMatrix(L); true
> C eq L;Runtime error in 'eq': Arguments are not compatible
This subsection presents some standard constructions (known as
constructions `A' and `B') to obtain lattices from linear codes.
In some cases the structural
invariants of these lattices
(e.g., minimum and kissing number, hence the centre density) can be
deduced from invariants of the codes; in general one still gets
estimates for the invariants of the lattices.
Lattice(C, "A") : Code -> Lat
Let C be a linear code of length n over a prime field K := GF(p). Construct the lattice L subseteq Z^n which is the full preimage of C under the natural epimorphism from Z^n onto K^n.
Let C be a linear code of length n over a prime field K := GF(p) such that all code words have coordinate sum 0. Construct the lattice L subseteq Z^n which consists of all vectors reducing modulo p to a code word in C and whose coordinate sum is 0 modulo p^2. The inner product matrix is set to the appropriate scalar matrix so that the Gram matrix is integral and primitive (its entries are coprime).
> C := ReedMullerCode(1, 4); > C: Minimal; [16, 5, 8] Reed-Muller Code (r = 1, m = 4) over GF(2) > L := Lattice(C, "B"); > L; Lattice of rank 16 and degree 16 Basis: (1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1) (0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1) (0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1) (0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 2) (0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1) (0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2) (0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 2) (0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 2) (0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1) (0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 2) (0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2) (0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 2) (0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 2) (0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 2) (0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2) (0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4) Inner Product denominator: 2
Let K be an algebraic number field of degree n over Q. Then K has n
embeddings into the complex numbers, denoted by sigma_1, ..., sigma_n.
By convention the first s of these are embeddings into the real numbers
and the last 2t are pairs of complex embeddings such that
sigma_(s + t + i) = /line(sigma_(s + i)) for 1 <= i <= t. The norm
N_(K/Q): K -> Q: alpha |-> prod_(i=1)^n sigma_i(alpha)
takes values in Z for elements in the maximal order of K, hence the
mapping alpha |-> N_(K/Q)^2(alpha) defines a positive definite
homogeneous form of degree 2n on K having integral values on the maximal
order.
We will use a rescaling of this homogeneous form to turn an order O in K
into a lattice. The norm of an element alpha in this lattice will be
2^t N_(K/Q)^2(alpha). The reason for the rescaling is that we want the
determinant of the lattice for O to be the discriminant of O.
MinkowskiMap(a) : FldNumElt -> [ FldReElt ]
Let K be an algebraic number field with s real and t pairs of complex embeddings into C denoted by sigma_1, ..., sigma_n. Then for an element a of K the image under the Minkowski map Psi is defined by Psi(a) := [ sigma_1(a), ..., sigma_s(a), sqrt(2) Re(sigma_(s + 1)(a)), sqrt(2) Im(sigma_(s + 1)(a)), ..., sqrt(2) Im(sigma_(s + t)(a)) ], which is a sequence of length n. With respect to the standard Euclidean inner product one has (Psi(a), Psi(a)) = 2^t N_(K/Q)(a).
Given an order O in a number field of degree n, create the lattice in R^n generated by the images of the basis of O under the Minkowski map.
Given an ideal I of an order O in a number field of degree n, create the lattice in R^n generated by the images of the basis of I under the Minkowski map.
> R<x> := PolynomialRing(Integers());
> K<w> := NumberField(x^3-15);
> E := EquationOrder(K);
> L := Lattice(E);
> L;
Lattice of rank 3 and degree 3 over Real Field of precision 20
Basis:
( 1 2.4662120743304701 6.0822019955734002)
( 1.414213562373095 -1.7438752816032172 -4.3007662756163029)
( 0 3.0204805898002556 -7.4491457008462104)
> B := Basis(E);
> [ MinkowskiMap(B[i]) : i in [1..3] ];
[
[ 1, 1, 1 ],
[ 2.4662120743304701, -1.2331060371652351 + 2.1358023074901034*i,
-1.2331060371652351 - 2.1358023074901034*i ],
[ 6.0822019955734002, -3.0411009977867001 - 5.2673414391149726*i,
-3.0411009977867001 + 5.2673414391149726*i ]
]
Similarly, we create the lattice defined by the ideal generated by z^2 + 1.
> z := E ! w; > I := ideal< E | z^2+1 >; > Lattice(I); Lattice of rank 3 and degree 3 over Real Field of precision 20 Basis: ( 226 17.4662120743304701 7.0822019955734002) ( 319.61226509631947 19.4693281539932078 -2.8865527132432079) ( 0 3.0204805898002556 -7.4491457008462104)
This subsection presents functions to construct some special lattices, namely root lattices, laminated lattices and Kappa-lattices.
A much wider variety of lattices can be found in a database provided by G. Nebe and N.J.A. Sloane at the web-site http://www.research.att.com/ { njas/lattices}. These lattices can easily be made accessible to Magma by a conversion script also available at this web-site. The database currently contains (at least):
Given a family name X as a string which is one of "A", "B", "C", "D", "E", "F", "G", "Kappa" or "Lambda", together with an integer n, construct a lattice subject to the following specifications:[Next] [Prev] [Right] [Left] [Up] [Index] [Root]To avoid irrational entries, each lattice is presented with inner product matrix taken to be the identity matrix divided by a suitable scale factor so that the Gram matrix is integral and primitive (its entries are coprime).
- The root lattice A_n which is the zero-sum lattice in Q^(n + 1).
- n >= 2: The root lattice B_n which is the standard lattice of dimension n.
- n >= 3: The root lattice C_n which is the even sublattice of Z^n and is equal to D_n.
- n >= 3: The root lattice D_n which is the even sublattice of Z^n, also called the checkerboard lattice.
- 6 <= n <= 8: The root lattice E_n, also called Gosset lattice.
- n = 4: The root lattice F_4 which is equal to D_4.
- n = 2: The root lattice G_2 which is equal to A_2.
- 1 <= n <= 13: The Kappa-lattice K_n. For n = 12 this is the Coxeter-Todd lattice.
- 1 <= n <= 31: The laminated lattice Lambda_n. For n = 16 this is the Barnes-Wall lattice, for n = 24 the Leech lattice.