Lattice (group)

In geometry and group theory, a lattice in R n {displaystyle mathbb {R} ^{n}} is a subgroup of the additive group R n {displaystyle mathbb {R} ^{n}} which is isomorphic to the additive group Z n {displaystyle mathbb {Z} ^{n}} , and which spans the real vector space R n {displaystyle mathbb {R} ^{n}} . In other words, for any basis of R n {displaystyle mathbb {R} ^{n}} , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice. A lattice may be viewed as a regular tiling of a space by a primitive cell. In geometry and group theory, a lattice in R n {displaystyle mathbb {R} ^{n}} is a subgroup of the additive group R n {displaystyle mathbb {R} ^{n}} which is isomorphic to the additive group Z n {displaystyle mathbb {Z} ^{n}} , and which spans the real vector space R n {displaystyle mathbb {R} ^{n}} . In other words, for any basis of R n {displaystyle mathbb {R} ^{n}} , the subgroup of all linear combinations with integer coefficients of the basis vectors forms a lattice. A lattice may be viewed as a regular tiling of a space by a primitive cell. Lattices have many significant applications in pure mathematics, particularly in connection to Lie algebras, number theory and group theory. They also arise in applied mathematics in connection with coding theory, in cryptography because of conjectured computational hardness of several lattice problems, and are used in various ways in the physical sciences. For instance, in materials science and solid-state physics, a lattice is a synonym for the 'frame work' of a crystalline structure, a 3-dimensional array of regularly spaced points coinciding in special cases with the atom or molecule positions in a crystal. More generally, lattice models are studied in physics, often by the techniques of computational physics. A lattice is the symmetry group of discrete translational symmetry in n directions. A pattern with this lattice of translational symmetry cannot have more, but may have less symmetry than the lattice itself. As a group (dropping its geometric structure) a lattice is a finitely-generated free abelian group, and thus isomorphic to Z n {displaystyle mathbb {Z} ^{n}} . A lattice in the sense of a 3-dimensional array of regularly spaced points coinciding with e.g. the atom or molecule positions in a crystal, or more generally, the orbit of a group action under translational symmetry, is a translate of the translation lattice: a coset, which need not contain the origin, and therefore need not be a lattice in the previous sense. A simple example of a lattice in R n {displaystyle mathbb {R} ^{n}} is the subgroup Z n {displaystyle mathbb {Z} ^{n}} . More complicated examples include the E8 lattice, which is a lattice in R 8 {displaystyle mathbb {R} ^{8}} , and the Leech lattice in R 24 {displaystyle mathbb {R} ^{24}} . The period lattice in R 2 {displaystyle mathbb {R} ^{2}} is central to the study of elliptic functions, developed in nineteenth century mathematics; it generalises to higher dimensions in the theory of abelian functions. Lattices called root lattices are important in the theory of simple Lie algebras; for example, the E8 lattice is related to a Lie algebra that goes by the same name. A typical lattice Λ {displaystyle Lambda } in R n {displaystyle mathbb {R} ^{n}} thus has the form where {v1, ..., vn} is a basis for R n {displaystyle mathbb {R} ^{n}} . Different bases can generate the same lattice, but the absolute value of the determinant of the vectors vi is uniquely determined by Λ, and is denoted by d(Λ).If one thinks of a lattice as dividing the whole of R n {displaystyle mathbb {R} ^{n}} into equal polyhedra (copies of an n-dimensional parallelepiped, known as the fundamental region of the lattice), then d(Λ) is equal to the n-dimensional volume of this polyhedron. This is why d(Λ) is sometimes called the covolume of the lattice. If this equals 1, the lattice is called unimodular. Minkowski's theorem relates the number d(Λ) and the volume of a symmetric convex set S to the number of lattice points contained in S. The number of lattice points contained in a polytope all of whose vertices are elements of the lattice is described by the polytope's Ehrhart polynomial. Formulas for some of the coefficients of this polynomial involve d(Λ) as well. Computational lattice problems have many applications in computer science. For example, the Lenstra–Lenstra–Lovász lattice basis reduction algorithm (LLL) has been used in the cryptanalysis of many public-key encryption schemes, and many lattice-based cryptographic schemes are known to be secure under the assumption that certain lattice problems are computationally difficult.