Creation of Lattices

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.

Contents

Elementary Creation of 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 a 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
Lattice(n, Q, M) : RngIntElt, [ RngElt ], AlgMatElt -> Lat
Lattice(S, M) : ModTupRng, 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 a 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.)
Lattice(X) : ModMatRngElt -> Lat
Lattice(n, Q) : RngIntElt, [ RngElt ] -> Lat
Lattice(S) : ModTupRng -> Lat
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 a 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.
LatticeWithBasis(B, M) : ModMatRngElt, AlgMatElt -> Lat
LatticeWithBasis(n, Q, M) : RngIntElt, [ RngElt ], AlgMatElt -> Lat
LatticeWithBasis(S, M) : ModTupRng, AlgMatElt -> Lat
    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 a 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.)
LatticeWithBasis(B) : ModMatRngElt -> Lat
LatticeWithBasis(n, Q) : RngIntElt, [ RngElt ] -> Lat
LatticeWithBasis(S) : ModTupRng -> Lat
    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 a 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.)
LatticeWithGram(F) : AlgMatElt -> Lat
LatticeWithGram(n, Q) : RngIntElt, [RngElt] -> Lat
    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 n2 or n + 1 choose 2. In the latter case, a sequence of length n2 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.)

StandardLattice(n) : RngIntElt -> Lat
Create the standard lattice Zn with standard Euclidean inner product.
CoordinateLattice(L) : Lat -> Lat
Constructs the lattice with the same Gram matrix as the lattice L, but with basis equal to the canonical basis of the free module of Rank(L) over the base ring of L. The identification of basis elements thus determines an isometry of lattices.
ScaledLattice(L,n) : Lat, RngIntElt -> Lat
ScaledLattice(L,n) : Lat, FldRatElt -> Lat
Constructs the coordinate lattice with Gram matrix equal to that of the lattice L scaled by the integer or rational n. The identification of basis elements thus determines an similitude of lattices.

Example Lat_LatticeCreate (H31E1)

We create the lattice in Z3 of degree 3 and rank 2 generated by the vectors (1, 2, 3) and (3, 2, 1) in four different ways. The first two (identical) lattices are represented by LLL-reduced bases since the Lattice function is used to create them, while the latter two (identical) lattices remain represented by the original basis since the LatticeWithBasis function is used to create them. 
> 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 true
We 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 BMBtr 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

Lattices from Linear Codes

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 ⊆Zn which is the full preimage of C under the natural epimorphism from Zn onto Kn.
Lattice(C, "B") : Code -> Lat
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 ⊆Zn which consists of all vectors reducing modulo p to a code word in C and whose coordinate sum is 0 modulo p2. The inner product matrix is set to the appropriate scalar matrix so that the Gram matrix is integral and primitive (its entries are coprime).

Example Lat_Code (H31E2)

The 16-dimensional Barnes-Wall lattice Λ16 can be constructed from the first order Reed-Muller code of length 16 using construction `B'. Note that the inner product matrix is the identity matrix divided by 2 so that the Gram matrix is integral and primitive. 
> 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

Lattices from Algebraic Number Fields

Let K be an algebraic number field of degree n over Q. Then K has n embeddings into the complex numbers, denoted by σ1, ..., σ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 σs + t + i = /line(σs + i) for 1 ≤i ≤t. The T2-norm K -> R: α |-> ∑i=1n |σi(α)|2 defines a positive definite norm on K in which an order or ideal is a positive definite lattice. We restrict to the r real embeddings and the first s complex embeddings to obtain an embedding of a rank n order or ideal Rs x Cs = Rn. By rescaling the complex coordinates by Sqrt(2), we recover the T2-norm of the element as its Euclidean norm under the embedding in Rn. This embedding, given by

α |-> ( σ1(α), ..., σs(α), Sqrt(2) (Re)( σs + 1(α) ), Sqrt(2) (Im)( σs + 1(α) ), ..., Sqrt(2) (Im)( σs + t(α) ) ),

is called the Minkowski map on K.

MinkowskiLattice(O) : RngOrd -> Lat, Map
Lattice(O) : RngOrd -> Lat, Map
Given an order O in a number field of degree n, create the lattice L in Rn generated by the images of the basis of O under the Minkowski map, followed by the isomorphism O -> L.
MinkowskiLattice(I) : RngOrdIdl -> Lat, Map
Lattice(I) : RngOrdIdl -> Lat, Map
Given an ideal I of an order O in a number field of degree n, create the lattice in Rn generated by the images of the basis of I under the Minkowski map, followed by the isomorphism O -> L.
MinkowskiSpace(K) : FldNum -> KModTup, Map
Construct the real inner product space V defined with respect to the inner product matrix of the T2-norm on the number field K, followed by the Minkowski map K -> V.

Example Lat_OrderLattice (H31E3)

In this example we create the lattice corresponding to the equation order of the number field Q(root 3 of 15). For comparison we apply the Minkowski map to the elements of the basis for the order. 
> P<x> := PolynomialRing(Integers());
> R := EquationOrder(NumberField(x^3-15));
> w := R![0,1,0];
> L, f := MinkowskiLattice(R);
> L;
Lattice of rank 3 and degree 3 over Real Field
Basis:
Lattice of rank 3 and degree 3 over Real field of precision 30
Basis:
(1.00000000000000000000000000000 1.41421356237309504880168872421
    0.000000000000000000000000000000)
(2.46621207433047010149161132315 -1.74387528160321720079629694216
    3.02048058980025565688335869988)
(6.08220199557340018489844499774 -4.30076627561630297914843739812
    -7.44914570084621027635727295139)
> B := Basis(R);
> f(B[2]);
> f(B[2]);
(2.46621207433047010149161132315 -1.74387528160321720079629694216
    3.02048058980025565688335869988)
Similarly, we create the lattice defined by the ideal generated by w2 + 1, and verify the that the T2-norm, given by Length on the number field, agrees with the norm of the lattice image. 
> I := ideal< R | w^2+1 >;
> L, f := Lattice(I);
> B := Basis(I);
> [ Length(B[k]) : k in [1..3] ];
[ 113.9795433448711545671225095419565069230968018982624192080454
3346320196288153038584473344161989557225281060164140817511930289
049332599978630989750057117093892447723724,
693.246605986720200554695334993213407259633012131529936960318255
6345313709169384387254042929336529027528589276741384648056766427
8812020993502245102110970371559009076524,
4216.46589035691627937357288301497314034052453149249823527965295
1232760419192679099060699351691798691646069328322562756396547517
8203732351663613772502545069466948994156 ]
> [ Norm(f(B[k])) : k in [1..3] ];
[ 113.979543344871154567122509542,
693.246605986720200554695334993, 4216.46589035691627937357288302
]

Special Lattices

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 [NS01a]. 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):

The root lattices An and their duals for 1 ≤n ≤24
The root lattices Dn and their duals for 1 ≤n ≤24
The root lattices En and their duals for 6 ≤n ≤8
The laminated lattices Λn for 1 ≤n ≤24 including the 16-dimensional Barnes-Wall lattice Λ16 and the Leech lattice Λ24
The Kappa-lattices Kn and their duals for 7 ≤n ≤13 including the Coxeter-Todd lattice K12
The perfect lattices up to dimension 7
The 3-dimensional Bravais lattices
Various interesting lattices in dimensions 20, 24, 28, 32, 40, 80, 105 including, e.g., some of the densest known lattices in dimension 32.
Lattice(X, n) : MonStgElt, RngIntElt -> Lat
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:
A:
The root lattice An which is the zero-sum lattice in Qn + 1.
B:
n ≥2: The root lattice Bn which is the standard lattice of dimension n.
C:
n ≥3: The root lattice Cn which is the even sublattice of Zn and is equal to Dn.
D:
n ≥3: The root lattice Dn which is the even sublattice of Zn, also called the checkerboard lattice.
E:
6 ≤n ≤8: The root lattice En, also called Gosset lattice.
F:
n = 4: The root lattice F4 which is equal to D4.
G:
n = 2: The root lattice G2 which is equal to A2.
Kappa:
1 ≤n ≤13: The Kappa-lattice Kn. For n = 12 this is the Coxeter-Todd lattice.
Lambda:
1 ≤n ≤31: The laminated lattice Λn. For n = 16 this is the Barnes-Wall lattice, for n = 24 the Leech lattice.

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).

V2.28, 13 July 2023