Main Index Number Theory Geometric Number Theory
  Subject Index
comment on the page

Point Lattices

Point lattices play an important role in many branches of mathematics, e.g. integer programming, factoring polynomials with rational coefficients, integer factoring and diophantine approximation, to mention some of them.  

Let typeset structure be an ordered set of typeset structure independent (column) vectors typeset structure in an typeset structure-dimensional vector space typeset structure a field typeset structure. The elements of a set typeset structure of vectors  which may be written as linear combination of the elements of typeset structure

Overscript[g, ->] = g _ 1 Overscript[b _ 1, ->] + g _ 2 Overscript[b _ 2, ->] + ... + ... , arg3] g _ j Overscript[b _ j, ->],         g _ j ∈ F(1)

with integral coefficients typeset structure are called lattice vectors, and typeset structure is called a (vector) lattice, or just lattice. The vectors  typeset structure form the lattice basis of typeset structure.

Let typeset structure be the real vector space typeset structure.

A typical basis is the so called standard basis typeset structure given by column vectors with 1 in the typeset structureth position, typeset structure, and zero otherwise.

[Graphics:HTMLFiles/PointLattices_19.gif]

The linear independence of the basis vectors ensures the uniqueness of the coefficients typeset structure in (1).

A basis of a lattice typeset structure in not determined uniquely. If typeset structure is another basis of typeset structure, that is the vectors typeset structure span  typeset structure, then there are typeset structure such that

Overscript[b _ j, ->] = Underoverscript[∑, k = 1, arg3] b _ (k, j) Overscript[a _ k, ->], and   

Overscript[g, ->] = Underoverscript[∑, j = 1, arg3] g _ j(Underoverscript[∑, k ... N, 2 ··· N, N N(2)

Theorem 1. The components of the lattice vectors typeset structureare obtained by the matrix multiplication (2).

A typeset structure matrix typeset structure is called an integral unimodular matrix if all its elements are integral and its determinant typeset structure.

Theorem 2. The lattice bases typeset structure and typeset structure generate the same lattice if and only if one basis goes over to the other by means of an integral unimodular transformation.

There follows that if

a _ j = Underoverscript[∑, k = 1, arg3] a _ (k, j) Overscript[e _ k, ->],    ... bsp;   b _ j = Underoverscript[∑, k = 1, arg3] b _ (k, j) Overscript[e _ k, ->]

are two lattice bases of the same lattice typeset structure, then the determinants of the coefficient matrices typeset structure and typeset structure can differ only in sign. Hence the absolute value of these determinants depends only on the lattice typeset structure itself. It is called the lattice constant and it is denoted by typeset structure, that is typeset structure.

The lattice constant has an interesting geometric meaning.  To explain this associate with the vector space typeset structure the Euclidean point space typeset structurefor which the standard basis typeset structure serves as an orthogonal system. Then to each point typeset structure and each vector typeset structure we can associate a new point typeset structure from typeset structure. If one chooses a point typeset structure as origin, then typeset structure together with the basis  typeset structure form a Cartesian coordinate system typeset structure and we can map an arbitrary point typeset structure to the unique coordinate typeset structure-tuple typeset structure through the formula typeset structure. Thus the space typeset structure can be identified with typeset structure.

On the other hand, if typeset structure is a basis of the vector lattice typeset structure this construction allows to assign to every lattice vector lattice a point lattice, namely  

O + p _ 1 Overscript[a _ 1, ->] + p _ 2 Overscript[a _ 2, ->] + ... + p _ N Overscript[a ... ;]       with     (p _ 1, p _ 2, ..., p _ N) ∈ Z^N .

Moreover, we can assign to this basis the so called fundamental parallelepiped (or fundamental parallelogram if typeset structure)

F = {O + ξ _ 1 Overscript[a _ 1, ->] + ξ _ 2 Overscript[a _ 2, ->] + ... + ξ _ ... N, ->] ;      0 <= ξ _ i < 1 for    i = 1, 2. ..., N } .

Because

Underoverscript[∑, j = 1, arg3] ξ _ j Overscript[a _ j, ->] = Underoverscript[W ... = 1, arg3] (Underoverscript[∑, j = 1, arg3] a _ (k . j) ξ _ j) Overscript[e _ k, ->] ,

the coordinates typeset structure of a point typeset structure of the fundamental parallelepiped are given by typeset structure in typeset structure.  Using the fact that the standard basis typeset structure spans the unit typeset structure-dimensional cube of volume one, the volume of the fundamental parallelepiped is

vol(F) = ∫ Underscript[..., F] ∫ d x _ 1 ... d x _ N = ∫ _ 0^1 ... ∫ _ 0^1 | det(a _ (k, j)) | d ξ _ 1 ... d ξ _ N = | det(a _ (k, j)) | = d(L) .

Theorem 3. The volumes of the fundamental parallelepipeds of a lattice are independent of the chosen basis and are equal to the lattice constants.

The fundamental parallelepiped contains no further lattice points in its interior or boundary. Conversely, any set of lattice points with this property determines a lattice basis, and furthermore, it generates the same lattice.

Cite this web-page as:

Štefan Porubský: Point Lattices.

Page created  .