Lattice (group)

Ingeometryandgroup theory, alatticein thereal coordinate spaceRn{\displaystyle \mathbb {R} ^{n}}is an infinite set of points in this space with the properties that coordinate-wise addition or subtraction of two points in the lattice produces another lattice point, that the lattice points are all separated by some minimum distance, and that every point in the space is within some maximum distance of a lattice point. Closure under addition and subtraction means that a lattice must be asubgroupof the additive group of the points in the space, and the requirements of minimum and maximum distance can be summarized by saying that a lattice is aDelone set. More abstractly, a lattice can be described as afree abelian groupof dimensionn{\displaystyle n}whichspansthevector spaceRn{\displaystyle \mathbb {R} ^{n}}. For anybasisofRn{\displaystyle \mathbb {R} ^{n}}, the subgroup of alllinear combinationswithintegercoefficients of the basis vectors forms a lattice, and every lattice can be formed from a basis in this way. A lattice may be viewed as aregular tilingof a space by aprimitive cell.
Lattices have many significant applications in pure mathematics, particularly in connection toLie algebras,number theoryandgroup theory. They also arise in applied mathematics in connection withcoding theory, inpercolation theoryto study connectivity arising from small-scale interactions,cryptographybecause of conjectured computational hardness of severallattice problems, and are used in various ways in the physical sciences. For instance, inmaterials scienceandsolid-state physics, a lattice is a synonym for the framework of acrystalline structure, a 3-dimensional array of regularly spaced points coinciding in special cases with theatomormoleculepositions in acrystal. More generally,lattice modelsare studied inphysics, often by the techniques ofcomputational physics.
A lattice is thesymmetry groupof discretetranslational symmetryinndirections. 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 afinitely-generatedfree abelian group, and thus isomorphic toZn{\displaystyle \mathbb {Z} ^{n}}.
A lattice in the sense of a 3-dimensionalarray of regularly spaced points coinciding with e.g. theatomormoleculepositions in acrystal, or more generally, the orbit of agroup actionunder translational symmetry, is a translation 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 inRn{\displaystyle \mathbb {R} ^{n}}is the subgroupZn{\displaystyle \mathbb {Z} ^{n}}. More complicated examples include theE8 lattice, which is a lattice inR8{\displaystyle \mathbb {R} ^{8}}, and theLeech latticeinR24{\displaystyle \mathbb {R} ^{24}}.   Theperiod latticeinR2{\displaystyle \mathbb {R} ^{2}}is central to the study ofelliptic functions, developed in nineteenth century mathematics; it generalizes to higher dimensions in the theory ofabelian functions.  Lattices calledroot latticesare important in the theory ofsimple Lie algebras; for example, the E8 lattice is related to a Lie algebra that goes by the same name.
A latticeΛ{\displaystyle \Lambda }inRn{\displaystyle \mathbb {R} ^{n}}thus has the form
where {v1, ...,vn} is a basis forRn{\displaystyle \mathbb {R} ^{n}}. Different bases can generate the same lattice, but theabsolute valueof thedeterminantof the vectorsviis uniquely determined byΛ{\displaystyle \Lambda }and denoted by d(Λ{\displaystyle \Lambda }). If one thinks of a lattice as dividing the whole ofRn{\displaystyle \mathbb {R} ^{n}}into equalpolyhedra(copies of ann-dimensionalparallelepiped, known as thefundamental regionof the lattice), then d(Λ{\displaystyle \Lambda }) is equal to then-dimensionalvolumeof this polyhedron. This is why d(Λ{\displaystyle \Lambda }) is sometimes called thecovolumeof the lattice. If this equals 1, the lattice is calledunimodular.
Minkowski's theoremrelates the number d(Λ{\displaystyle \Lambda }) and the volume of a symmetricconvex setSto the number of lattice points contained inS. The number of lattice points contained in apolytopeall of whose vertices are elements of the lattice is described by the polytope'sEhrhart polynomial. Formulas for some of the coefficients of this polynomial involve d(Λ{\displaystyle \Lambda }) as well.
Computational lattice problemshave many applications in computer science. For example, theLenstra–Lenstra–Lovász lattice basis reduction algorithm(LLL) has been used in thecryptanalysisof manypublic-key encryptionschemes,and manylattice-based cryptographic schemesare known to be secure under the assumption that certain lattice problems arecomputationally difficult.
There are five 2D lattice types as given by thecrystallographic restriction theorem. Below, thewallpaper groupof the lattice is given inIUCr notation,Orbifold notation, andCoxeter notation, along with a wallpaper diagram showing the symmetry domains. Note that a pattern with this lattice of translational symmetry cannot have more, but may have less symmetry than the lattice itself. Afull list of subgroupsis available. For example, below the hexagonal/triangular lattice is given twice, with full 6-fold and a half 3-fold reflectional symmetry. If the symmetry group of a pattern contains ann-fold rotation then the lattice hasn-fold symmetry for evennand 2n-fold for oddn.
For the classification of a given lattice, start with one point and take a nearest second point. For the third point, not on the same line, consider its distances to both points. Among the points for which the smaller of these two distances is least, choose a point for which the larger of the two is least. (Notlogically equivalentbut in the case of lattices giving the same result is just "Choose a point for which the larger of the two is least".)
The five cases correspond to thetrianglebeing equilateral, right isosceles, right, isosceles, and scalene. In a rhombic lattice, the shortest distance may either be a diagonal or a side of the rhombus, i.e., the line segment connecting the first two points may or may not be one of the equal sides of the isosceles triangle. This depends on the smaller angle of the rhombus being less than 60° or between 60° and 90°.
The general case is known as aperiod lattice. If the vectorspandqgenerate the lattice, instead ofpandqwe can also takepandp-q, etc. In general in 2D, we can takeap+bqandcp+dqfor integersa,b,canddsuch thatad-bcis 1 or -1. This ensures thatpandqthemselves are integer linear combinations of the other two vectors.  Each pairp,qdefines a parallelogram, all with the same area, the magnitude of thecross product. One parallelogram fully defines the whole  object. Without further symmetry, this parallelogram is afundamental parallelogram.
The vectorspandqcan be represented bycomplex numbers. Up to size and orientation, a pair can be represented by their quotient. Expressed geometrically: if two lattice points are 0 and 1, we consider the position of a third lattice point. Equivalence in the sense of generating the same lattice is represented by themodular group:T:z↦z+1{\displaystyle T:z\mapsto z+1}represents choosing a different third point in the same grid,S:z↦−1/z{\displaystyle S:z\mapsto -1/z}represents choosing a different side of the triangle as reference side 0–1, which in general implies changing the scaling of the lattice, and rotating it. Each "curved triangle" in the image contains for each 2D lattice shape one complex number, the grey area is a canonical representation, corresponding to the classification above, with 0 and 1 two lattice points that are closest to each other; duplication is avoided by including only half of the boundary. The rhombic lattices are represented by the points on its boundary, with the hexagonal lattice as vertex, andifor the square lattice. The rectangular lattices are at the imaginary axis, and the remaining area represents the parallelogrammatic lattices, with the mirror image of a parallelogram represented by the mirror image in the imaginary axis.
The 14 lattice types in 3D are calledBravais lattices. They are characterized by theirspace group. 3D patterns with translational symmetry of a particular type cannot have more, but may have less, symmetry than the lattice itself.
A lattice inCn{\displaystyle \mathbb {C} ^{n}}is a discrete subgroup ofCn{\displaystyle \mathbb {C} ^{n}}which spansCn{\displaystyle \mathbb {C} ^{n}}as a real vector space. As the dimension ofCn{\displaystyle \mathbb {C} ^{n}}as a real vector space is equal to2n{\displaystyle 2n}, a lattice inCn{\displaystyle \mathbb {C} ^{n}}will be a free abelian group of rank2n{\displaystyle 2n}.
For example, theGaussian integersZ[i]=Z+iZ{\displaystyle \mathbb {Z} [i]=\mathbb {Z} +i\mathbb {Z} }form a lattice inC=C1{\displaystyle \mathbb {C} =\mathbb {C} ^{1}}, as(1,i){\displaystyle (1,i)}is a basis ofC{\displaystyle \mathbb {C} }overR{\displaystyle \mathbb {R} }.
More generally, alatticeΓ in aLie groupGis adiscrete subgroup, such that thequotientG/Γ is of finite measure, for the measure on it inherited fromHaar measureonG(left-invariant, or right-invariant—the definition is independent of that choice). That will certainly be the case whenG/Γ iscompact, but that sufficient condition is not necessary, as is shown by the case of themodular groupinSL2(R), which is a lattice but where the quotient isn't compact (it hascusps). There are general results stating the existence of lattices in Lie groups.
A lattice is said to beuniformorcocompactifG/Γ is compact; otherwise the lattice is callednon-uniform.
While we normally considerZ{\displaystyle \mathbb {Z} }lattices inRn{\displaystyle \mathbb {R} ^{n}}this concept can be generalized to any finite-dimensionalvector spaceover anyfield. This can be done as follows:
LetKbe afield, letVbe ann-dimensionalK-vector space, letB={v1,…,vn}{\displaystyle B=\{\mathbf {v} _{1},\ldots ,\mathbf {v} _{n}\}}be aK-basisforVand letRbe aringcontained withinK. Then theRlatticeL{\displaystyle {\mathcal {L}}}inVgenerated byBis given by:
In general, different basesBwill generate different lattices. However, if thetransition matrixTbetween the bases is inGLn(R){\displaystyle \mathrm {GL} _{n}(R)}- thegeneral linear groupofR(in simple terms this means that all the entries ofTare inRand all the entries ofT−1{\displaystyle T^{-1}}are inR- which is equivalent to saying that thedeterminantofTis inR∗{\displaystyle R^{*}}- theunit groupof elements inRwith multiplicative inverses) then the lattices generated by these bases will beisomorphicsinceTinduces an isomorphism between the two lattices.
Important cases of such lattices occur in number theory withKap-adic fieldandRthep-adic integers.
For a vector space which is also aninner product space, thedual latticecan be concretely described by the set
or equivalently as