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.

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 \times n\) matrix \(M\). The generating matrix can be specified by an \(r \times n\) matrix \(X\), an integer \(n\) with a sequence \(Q\) of ring elements of length \(rn\) (interpreted as a \(r\times 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\leq 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 \times n\) matrix \(X\), an integer \(n\) with a sequence \(Q\) of ring elements of length \(rn\) (interpreted as a \(r\times 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\leq 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\times n\) basis matrix and with inner product given by the \(n \times n\) matrix \(M\). The basis matrix \(B\) can be specified by an \(m \times n\) matrix \(B\), an integer \(n\) with a sequence \(Q\) of ring elements of length \(mn\) (interpreted as an \(m\times 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\times n\) basis matrix and with standard Euclidean inner product. The basis matrix \(B\) can be specified by an \(m \times n\) matrix \(B\), an integer \(n\) with a sequence \(Q\) of ring elements of length \(mn\) (interpreted as an \(m\times 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\times 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 \times 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 \({\mathbb{Z}}^n\) 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.

Module(L): Lat -> Lat#
ZLattice(L): Lat -> Lat#: Returns the lattice \(L\).

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.

TernaryQuadraticLattice(d): RngIntElt -> Lat#: For a cube-free integer \(d\), Constructs a positive definite ternary quadratic lattice of half-discriminant \(d\).

QuaternaryLatticeOfPrimeDiscriminant(p): RngIntElt -> Lat#: Constructs a positive-definite quaternary quadratic lattice of prime discriminant \(p\).

QuinaryLatticeOfPrimeDiscriminant(p): RngIntElt -> Lat#: Constructs a positive-definite quinary quadratic lattice of prime half-discriminant \(p\).

QuadraticLattice(n, d): RngIntElt, RngIntElt -> Lat#: Given a positive integer \(n \le 6\) and a discriminant \(d\), constructs a positive-definite quadratic lattice of dimension \(n\) and discriminant \(d\) using Minkowski’s description of the space of reduced forms.

RandomLattice(n, M): RngIntElt, RngIntElt -> Lat#

Positive: BoolElt                    Default: false

Generates a random lattice. If Positive is true, generates a positive definite lattice.

Example: Lattice Create (ex-d7d03e)#

We create the lattice in \({\mathbb{Z}}^3\) 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

Run in calculator

We next create a \(3\times 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]

Run in calculator

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

Run in calculator

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 := {\bf F}_{p}\). Construct the lattice \(L \subseteq {\mathbb{Z}}^n\) which is the full preimage of \(C\) under the natural epimorphism from \({\mathbb{Z}}^n\) onto \(K^n\).

Lattice(C, "B"): Code -> Lat#: Let \(C\) be a linear code of length \(n\) over a prime field \(K := {\bf F}_{p}\) such that all code words have coordinate sum 0. Construct the lattice \(L \subseteq {\mathbb{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).

Example: Code (ex-60a64b)#

The 16-dimensional Barnes-Wall lattice \(\Lambda_{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

Run in calculator

Lattices from Algebraic Number Fields#

Let \(K\) be an algebraic number field of degree \(n\) over \({\mathbb{Q}}\). Then \(K\) has \(n\) embeddings into the complex numbers, denoted by \(\sigma_1, \ldots, \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} = \overline{\sigma_{s+i}}\) for \(1 \leq i \leq t\). The \(T_2\)-norm \(K \rightarrow {\mathbb{R}}: \alpha \mapsto \sum_{i=1}^n |\sigma_i(\alpha)|^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 \({\mathbb{R}}^s \times {\mathbb{C}}^s = {\mathbb{R}}^n\). By rescaling the complex coordinates by \(\sqrt{2}\), we recover the \(T_2\)-norm of the element as its Euclidean norm under the embedding in \({\mathbb{R}}^n\). This embedding, given by

\[\alpha \mapsto \left( \sigma_1(\alpha), \ldots, \sigma_s(\alpha), \sqrt{2}\, {\rm Re}( \sigma_{s+1}(\alpha) ), \sqrt{2}\, {\rm Im}( \sigma_{s+1}(\alpha) ), \ldots, \sqrt{2}\, {\rm Im}( \sigma_{s+t}(\alpha) ) \right),\]

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 \({\mathbb{R}}^n\) generated by the images of the basis of \(O\) under the Minkowski map, followed by the isomorphism \(O \rightarrow 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 \({\mathbb{R}}^n\) generated by the images of the basis of \(I\) under the Minkowski map, followed by the isomorphism \(O \rightarrow L\).

MinkowskiSpace(K): FldNum -> KModTup, Map#: Construct the real inner product space \(V\) defined with respect to the inner product matrix of the \(T_2\)-norm on the number field \(K\), followed by the Minkowski map \(K \rightarrow V\).

Example: Order Lattice (ex-12a121)#

In this example we create the lattice corresponding to the equation order of the number field \({\mathbb{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)

Run in calculator

Similarly, we create the lattice defined by the ideal generated by \(w^2+1\), and verify the that the \(T_2\)-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
]

Run in calculator

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 [Nebe and Sloane, 2001]. 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 \(A_n\) and their duals for \(1 \leq n \leq 24\)
The root lattices \(D_n\) and their duals for \(1 \leq n \leq 24\)
The root lattices \(E_n\) and their duals for \(6 \leq n \leq 8\)
The laminated lattices \(\Lambda_n\) for \(1 \leq n \leq 24\) including the 16-dimensional Barnes-Wall lattice \(\Lambda_{16}\) and the Leech lattice \(\Lambda_{24}\)
The Kappa-lattices \(K_n\) and their duals for \(7 \leq n \leq 13\) including the Coxeter-Todd lattice \(K_{12}\)
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 \(A_n\) which is the zero-sum lattice in \({\mathbb{Q}}^{n+1}\).
B:: \(n \geq 2\): The root lattice \(B_n\) which is the standard lattice of dimension \(n\).
C:: \(n \geq 3\): The root lattice \(C_n\) which is the even sublattice of \({\mathbb{Z}}^n\) and is equal to \(D_n\).
D:: \(n \geq 3\): The root lattice \(D_n\) which is the even sublattice of \({\mathbb{Z}}^n\), also called the checkerboard lattice.
E:: \(6 \leq n \leq 8\): The root lattice \(E_n\), also called Gosset lattice.
F:: \(n = 4\): The root lattice \(F_4\) which is equal to \(D_4\).
G:: \(n = 2\): The root lattice \(G_2\) which is equal to \(A_2\).
Kappa:: \(1 \leq n \leq 13\): The Kappa-lattice \(K_n\). For \(n = 12\) this is the Coxeter-Todd lattice.
Lambda:: \(1 \leq n \leq 31\): The laminated lattice \(\Lambda_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).