View source for Lattice (group)

{{Short description|Periodic set of points}}
{{hatnote|Not to be confused with the partially ordered set, [[Lattice (order)]]. For other related uses, see [[Lattice (disambiguation)]].}}
{{One source|date=October 2022}}
[[File:Equilateral Triangle Lattice.svg|thumb|right|250px|A lattice in the [[Euclidean plane]]]]
{{Group theory sidebar |Discrete}}

In [[geometry]] and [[group theory]], a '''lattice''' in the [[real coordinate space]] <math>\mathbb{R}^n</math> 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 a [[subgroup]] of 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 a [[Delone set]]. More abstractly, a lattice can be described as a [[free abelian group]] of dimension <math>n</math> which [[linear span|spans]] the [[vector space]] <math>\mathbb{R}^n</math>. For any [[basis (linear algebra)|basis]] of <math>\mathbb{R}^n</math>, the subgroup of all [[linear combination]]s with [[integer]] coefficients 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 a [[regular tiling]] of a space by a [[primitive cell]].

Lattices have many significant applications in pure mathematics, particularly in connection to [[Lie algebra]]s, [[number theory]] and [[group theory]]. They also arise in applied mathematics in connection with [[coding theory]], in [[percolation theory]] to study connectivity arising from small-scale interactions, [[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 framework 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 model (physics)|lattice models]] are studied in [[physics]], often by the techniques of [[computational physics]].

==Symmetry considerations and examples==
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.<ref>{{Cite web |title=Symmetry in Crystallography Notes |url=http://xrayweb.chem.ou.edu/notes/symmetry.html |access-date=2022-11-06 |website=xrayweb.chem.ou.edu}}</ref> As a group (dropping its geometric structure) a lattice is a [[Finitely-generated abelian group|finitely-generated]] [[free abelian group]], and thus isomorphic to <math>\mathbb{Z}^n</math>.

A lattice in the sense of a 3-[[dimension]]al 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 (mathematics)|group action]] under 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 in <math>\mathbb{R}^n</math> is the subgroup <math>\mathbb{Z}^n</math>. More complicated examples include the [[E8 lattice]], which is a lattice in <math>\mathbb{R}^{8}</math>, and the [[Leech lattice]] in <math>\mathbb{R}^{24}</math>.   The [[period lattice]] in <math>\mathbb{R}^2</math> is central to the study of [[elliptic functions]], developed in nineteenth century mathematics; it generalizes to higher dimensions in the theory of [[abelian function]]s.  Lattices called [[root lattice]]s are important in the theory of [[simple Lie algebra]]s; for example, the E8 lattice is related to a Lie algebra that goes by the same name.

==Dividing space according to a lattice==
A lattice <math>\Lambda</math> in <math>\mathbb{R}^n</math> thus has the form
:<math>
\Lambda = \biggl\{ \sum_{i=1}^n a_i v_i \mathbin{\bigg\vert} a_i \in\mathbb{Z} \biggr\},
</math><!-- must use \mid instead of \vert with manual spacing, but it's currently broken -->
where {''v''<sub>1</sub>, ..., ''v''<sub>''n''</sub>} is a basis for <math>\mathbb{R}^n</math>. Different bases can generate the same lattice, but the [[absolute value]] of the [[determinant]] of the vectors ''v''<sub>''i''</sub> is uniquely determined by <math>\Lambda</math> and denoted by d(<math>\Lambda</math>). If one thinks of a lattice as dividing the whole of <math>\mathbb{R}^n</math> into equal [[polyhedron|polyhedra]] (copies of an ''n''-dimensional [[parallelepiped]], known as the ''[[fundamental region]]'' of the lattice), then d(<math>\Lambda</math>) is equal to the ''n''-dimensional [[volume]] of this polyhedron. This is why d(<math>\Lambda</math>) is sometimes called the '''covolume''' of the lattice. If this equals 1, the lattice is called [[unimodular lattice|unimodular]].

==Lattice points in convex sets==
[[Minkowski's theorem]] relates the number d(<math>\Lambda</math>) 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(<math>\Lambda</math>) as well.

{{see also|Integer points in polyhedra}}

==Computational lattice problems==
{{Main|Lattice problem}}
[[lattice problems|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 cryptography|public-key encryption]] schemes,<ref>{{Cite book|last1=Nguyen|first1=Phong|last2=Stern|first2=Jacques|title=Cryptography and Lattices |chapter=The Two Faces of Lattices in Cryptology |date=2001|volume=2146|pages=146–180|doi=10.1007/3-540-44670-2_12|series=Lecture Notes in Computer Science|isbn=978-3-540-42488-8}}</ref> and many [[Lattice-based cryptography|lattice-based cryptographic schemes]] are known to be secure under the assumption that certain lattice problems are [[Computational hardness assumption|computationally difficult]].<ref>{{Cite book|last=Regev|first=Oded|title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing |chapter=On lattices, learning with errors, random linear codes, and cryptography |date=2005-01-01|series=STOC '05|location=New York, NY, USA|publisher=ACM|pages=84–93|doi=10.1145/1060590.1060603|isbn=978-1581139600|citeseerx=10.1.1.110.4776|s2cid=53223958}}</ref>

==Lattices in two dimensions: detailed discussion==
[[File:2d-bravais.svg|thumb|Five lattices in the Euclidean plane]]
There are five 2D lattice types as given by the [[crystallographic restriction theorem]]. Below, the [[wallpaper group]] of the lattice is given in [[IUC notation|IUCr notation]], [[Orbifold notation]], and [[Coxeter 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. A [[List of planar symmetry groups#Wallpaper groups|full list of subgroups]] is 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 an ''n''-fold rotation then the lattice has ''n''-fold symmetry for even ''n'' and 2''n''-fold for odd ''n''.
{| class=wikitable width=780
|-
!cmm, (2*22), [&infin;,2<sup>+</sup>,&infin;]
!p4m, (*442), [4,4]
!p6m, (*632), [6,3]
|- valign=top align=center
|[[File:Rhombic Lattice.svg|150px]][[File:Wallpaper group diagram cmm.svg|100px]]<BR>'''[[rhombus|rhombic]] lattice'''<BR>also '''centered [[rectangle|rectangular]] lattice'''<BR>''isosceles triangular''
|[[File:SquareLattice.svg|150px]][[File:Wallpaper group diagram p4m square.svg|75px]]<BR>'''[[square lattice]]'''<BR>''right isosceles triangular''
|[[File:Equilateral Triangle Lattice.svg|150px]][[File:Wallpaper group diagram p6m.svg|100px]]<BR>'''[[hexagonal lattice]]'''<BR>(equilateral triangular lattice)
|-
!pmm, *2222, [&infin;,2,&infin;]
!p2, 2222, [&infin;,2,&infin;]<sup>+</sup>
!p3m1, (*333), [3<sup>[3]</sup>]
|- valign=top align=center
|[[File:Rectangular Lattice.svg|150px]][[File:Wallpaper group diagram pmm.svg|100px]]<BR>'''[[rectangular lattice]]'''<BR>also '''centered rhombic lattice'''<BR>''right triangular''
|[[File:Oblique Lattice.svg|150px]][[File:Wallpaper group diagram p2.svg|100px]]<BR>'''[[oblique lattice]]'''<BR>''scalene triangular''
|[[File:Equilateral Triangle Lattice.svg|150px]][[File:Wallpaper group diagram p3m1.svg|100px]]<BR>'''equilateral [[triangle|triangular]] lattice'''<BR>(hexagonal lattice)
|}

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. (Not [[Logical equivalence|logically equivalent]] but 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 the [[triangle]] being 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 a [[period lattice]]. If the vectors '''p''' and '''q''' generate the lattice, instead of '''p''' and '''q''' we can also take '''p''' and '''p'''-'''q''', etc. In general in 2D, we can take ''a'' '''p''' + ''b'' '''q''' and ''c'' '''p''' + ''d'' '''q''' for integers ''a'',''b'', ''c'' and ''d'' such that ''ad-bc'' is 1 or -1. This ensures that '''p''' and '''q''' themselves are integer linear combinations of the other two vectors.  Each pair '''p''', '''q''' defines a parallelogram, all with the same area, the magnitude of the [[cross product]]. One parallelogram fully defines the whole  object. Without further symmetry, this parallelogram is a [[fundamental pair of periods|fundamental parallelogram]].

[[File:ModularGroup-FundamentalDomain.svg|thumb|right|The [[fundamental domain]] of the [[period lattice]].]]
The vectors '''p''' and '''q''' can be represented by [[complex number]]s. 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 the [[modular group]]: <math>T: z\mapsto z+1</math> represents choosing a different third point in the same grid, <math>S: z\mapsto -1/z</math> 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, and ''i'' for 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.

==Lattices in three dimensions==
{{main|Bravais lattice}}
The 14 lattice types in 3D are called '''Bravais lattices'''. They are characterized by their [[space group]]. 3D patterns with translational symmetry of a particular type cannot have more, but may have less, symmetry than the lattice itself.

==Lattices in complex space==
A lattice in <math>\mathbb{C}^n</math> is a discrete subgroup of <math>\mathbb{C}^n</math> which spans <math>\mathbb C^n</math> as a real vector space. As the dimension of <math>\mathbb C^n</math> as a real vector space is equal to <math>2n</math>, a lattice in <math>\mathbb{C}^n</math> will be a free abelian group of rank <math>2n</math>.

For example, the [[Gaussian integer]]s <math>\mathbb Z[i] = \mathbb Z + i\mathbb Z</math> form a lattice in <math>\mathbb C = \mathbb{C}^1</math>, as <math>(1, i)</math> is a basis of <math>\mathbb C</math> over <math>\mathbb R</math>.

==In Lie groups==
{{Main|Lattice (discrete subgroup)}}
More generally, a '''lattice''' Γ in a [[Lie group]] ''G'' is a [[discrete subgroup]], such that the [[Quotient group|quotient]] ''G''/Γ is of finite measure, for the measure on it inherited from [[Haar measure]] on ''G'' (left-invariant, or right-invariant—the definition is independent of that choice). That will certainly be the case when ''G''/Γ is [[compact space|compact]], but that sufficient condition is not necessary, as is shown by the case of the [[modular group]] in [[SL2(R)|''SL''<sub>2</sub>('''R''')]], which is a lattice but where the quotient isn't compact (it has ''cusps''). There are general results stating the existence of lattices in Lie groups.

A lattice is said to be '''uniform''' or '''cocompact''' if ''G''/Γ is compact; otherwise the lattice is called '''non-uniform'''.

==Lattices in general vector spaces==
{{unreferenced section|date=April 2022}}
While we normally consider <math>\mathbb{Z}</math> lattices in <math>\mathbb{R}^n</math> this concept can be generalized to any finite-dimensional [[vector space]] over any [[Field (mathematics)|field]]. This can be done as follows:

Let ''K'' be a [[field (mathematics)|field]], let ''V'' be an ''n''-dimensional ''K''-[[vector space]], let <math>B = \{\mathbf{v}_1,\ldots, \mathbf{v}_n\}</math> be a ''K''-[[basis (linear algebra)|basis]] for ''V'' and let ''R'' be a [[Ring (mathematics)|ring]] contained within ''K''. Then the ''R'' lattice <math>\mathcal{L}</math> in ''V'' generated by ''B'' is given by:

:<math>\mathcal{L} = \biggl\{ \sum_{i=1}^{n} a_i \mathbf{v}_i \mathbin{\bigg\vert} a_i \in R\biggr\}.</math>

In general, different bases ''B'' will generate different lattices. However, if the [[Change of basis#General case|transition matrix]] ''T'' between the bases is in <math>\mathrm{GL}_n(R)</math> - the [[general linear group]] of ''R'' (in simple terms this means that all the entries of ''T'' are in ''R'' and all the entries of <math>T^{-1}</math> are in ''R'' - which is equivalent to saying that the [[determinant]] of ''T'' is in <math>R^*</math> - the [[unit group]] of elements in ''R'' with multiplicative inverses) then the lattices generated by these bases will be [[isomorphism|isomorphic]] since ''T'' induces an isomorphism between the two lattices.

Important cases of such lattices occur in number theory with ''K'' a [[p-adic field|''p''-adic field]] and ''R'' the [[p-adic integers|''p''-adic integer]]s.

For a vector space which is also an [[inner product space]], the [[dual lattice]] can be concretely described by the set

:<math>\mathcal{L}^* = \{\mathbf{v} \in V \mid \langle \mathbf{v},\mathbf{x} \rangle \in R\,\text{ for all }\,\mathbf{x} \in \mathcal{L}\},</math>

or equivalently as

:<math>\mathcal{L}^* = \{\mathbf{v} \in V \mid \langle \mathbf{v},\mathbf{v}_i \rangle \in R,\ i = 1, ..., n\}.</math>

== Related notions ==
* A '''primitive element''' of a lattice is an element that is not a positive integer multiple of another element in the lattice.{{citation needed|date=April 2020}}

==See also==
{{Div col}}
*[[Crystal system]]
*[[Hermite constant]]
*[[Lattice-based cryptography]]
*[[Lattice graph]]
*[[Lattice (module)]]
*[[Lattice (order)]]
*[[Mahler's compactness theorem]]
*[[Reciprocal lattice]]
*[[Unimodular lattice]]
{{Div col end}}

==Notes==
<references />

==References==
*{{Citation | last1=Conway | first1=John Horton | author1-link=John Horton Conway | last2=Sloane | first2=Neil J. A. | author2-link=Neil Sloane | title=Sphere Packings, Lattices and Groups | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=3rd | series=Grundlehren der Mathematischen Wissenschaften | isbn=978-0-387-98585-5 | mr=0920369 | year=1999 | volume=290 | url-access=registration | url=https://archive.org/details/spherepackingsla0000conw_b8u0 }}

==External links==
*[http://www.math.rwth-aachen.de/~Gabriele.Nebe/LATTICES/ Catalogue of Lattices (by Nebe and Sloane)]

{{Crystal systems}}

{{DEFAULTSORT:Lattice (Group)}}
[[Category:Lattice points| ]]
[[Category:Discrete groups]]
[[Category:Lie groups]]
[[Category:Analytic geometry]]