Download Wolfram Notebook

A point lattice is the set of all integer linear combinations of a fixed linearly independent set of vectors in Euclidean space, or a translate of such a set.

In the plane, point lattices can be constructed having unit cells in the shape of a square, rectangle, hexagon, etc. Unless otherwise specified, point lattices may be taken to refer to points in a square array, i.e., points with coordinates , where , , ... are integers. Such an array is often called a grid or a mesh.

Point lattices are frequently simply called "lattices," which unfortunately conflicts with the same term applied to ordered sets treated in lattice theory. The integer grid is also a lattice under the coordinatewise ordering, but a general point lattice need not be a lattice in this order-theoretic sense. On the other hand, many lattices are not point lattices.

Properties of lattices are implemented in the Wolfram Language as LatticeData[lattice, prop].

Formally, a lattice is a discrete subgroup of Euclidean space, assuming it contains the origin. That is, a lattice is closed under addition and inverses, and every point has a neighborhood in which it is the only lattice point. The common examples are and . Usually, a lattice is defined to have full rank, i.e., a lattice in is the subgroup

where the are integers and are linearly independent vectors. Note that a lattice needs at most elements to generate it. For example, the subgroup requires two generators but is not discrete, and is not a lattice. The above illustration shows that the subgroup generated by 1 and is not a lattice by showing the points for successive integer values of .

For , let count the lattice points of in the square , and let count those visible from the origin. The fraction of lattice points visible from the origin, as derived in Castellanos (1988b, pp. 155-156), is

Thus is the limiting fraction as . It is also the limiting probability that two independent uniformly selected integers from are relatively prime, as .

For , it is possible to select lattice points with such that no three are in a straight line. The number of distinct solutions (not counting reflections and rotations) for , 3, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156, ... (OEIS A000769). This is the no-three-in-a-line problem. The corrected Guy-Kelly heuristic conjectures that, for every and all sufficiently large , at most lattice points can be selected with no three collinear, where

The original value arose from an error in the heuristic argument (Guy and Kelly 1968, Voutier 2026). The corrected bound remains conjectural. A related problem asks how many of the lattice points with can be selected with no four concyclic (Guy 1994, p. 241). At least can be selected by taking all points in one row.

A parallelogram whose edge vectors form an integer basis of has unit area (Hilbert and Cohn-Vossen 1999, pp. 33-34). Two opposite sides of unit length alone do not ensure unit area.

A special set of polygons defined on the regular lattice are the golygons. A necessary and sufficient condition that a linear transformation map a lattice onto itself is that its matrix in a lattice basis have integer entries and determinant . Thus it must be unimodular over the integers, not merely over the real numbers. Ajtai (1996) constructed a random class of integer lattices with the following property. If a probabilistic polynomial-time algorithm finds a short nonzero vector in a random lattice from this class with probability at least , then probabilistic polynomial-time algorithms solve three problems in every integer lattice with probability exponentially close to one. The problems are approximating the length of a shortest nonzero vector within a polynomial factor, finding a shortest nonzero vector when every vector within a specified polynomial factor of its length is parallel to it, and finding a basis whose maximum vector length is within a polynomial factor of the optimum. The fraction in the premise concerns random lattice instances, rather than a fraction of the vectors in one lattice basis. This result has potential applications to cryptography and authentication (Cipra 1996).

Assigning each point of the ambient Euclidean space to a nearest lattice point defines a lattice quantizer. At fixed covolume, its mean squared error is measured by the normalized second moment of a Voronoi cell (Conway and Sloane 1982).

See also

Barnes-Wall Lattice, Blichfeldt's Theorem, Brillouin Zone, Browkin's Theorem, Circle Lattice Points, Closest Vector Problem, Covolume, Coxeter-Todd Lattice, Ehrhart Polynomial, Elliptic Curve, Fundamental Parallelepiped, Gauss's Circle Problem, Golygon, Integration Lattice, Jarnick's Inequality, Lattice Path, Lattice Sum, Leech Lattice, Minkowski Convex Body Theorem, Modular Lattice, N-Cluster, No-Three-in-a-Line Problem, Nosarzewska's Inequality, Pick's Theorem, Random Walk, Reciprocal Lattice, Schinzel's Theorem, Schröder Number, Torus, Unit Lattice, Visible Point, Voronoi Polygon

Portions of this entry contributed by Matt Insall (author's link)

Portions of this entry contributed by Todd Rowland

Explore with Wolfram|Alpha

References

Ajtai, M. "Generating Hard Instances of Lattice Problems." Electronic Colloquium on Computational Complexity, TR96-007, Jan. 29, 1996. https://eccc.weizmann.ac.il/report/1996/007/.Apostol, T. Introduction to Analytic Number Theory. New York: Springer-Verlag, 1995.Castellanos, D. "The Ubiquitous ." Math. Mag. 61, 67-98, 1988a. https://doi.org/10.1080/0025570X.1988.11977350.Castellanos, D. "The Ubiquitous ." Math. Mag. 61, 148-163, 1988b. https://doi.org/10.1080/0025570X.1988.11977363.Cipra, B. "Lattices May Put Security Codes on a Firmer Footing." Science 273, 1047-1048, 1996.Conway, J. H. and Sloane, N. J. A. "Voronoi Regions of Lattices, Second Moments of Polytopes, and Quantization." IEEE Trans. Inform. Theory 28, 211-226, 1982. https://doi.org/10.1109/TIT.1982.1056483.Eppstein, D. "Lattice Theory and Geometry of Numbers." https://ics.uci.edu/~eppstein/junkyard/lattice.html.Gardner, M. "The Lattice of Integers." Ch. 21 in The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, pp. 208-219, 1984.Guy, R. K. "Gauss's Lattice Point Problem," "Lattice Points with Distinct Distances," "Lattice Points, No Four on a Circle," and "The No-Three-in-a-Line Problem." §F1, F2, F3, and F4 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 240-244, 1994.Guy, R. K. and Kelly, P. A. "The No-Three-in-Line Problem." Canad. Math. Bull. 11, 527-531, 1968. https://doi.org/10.4153/CMB-1968-062-3.Hammer, J. Unsolved Problems Concerning Lattice Points. London, England: Pitman, 1977.Hilbert, D. and Cohn-Vossen, S. "Regular Systems of Points." Ch. 2 in Geometry and the Imagination. New York: Chelsea, pp. 32-93, 1999.Knupp, P. and Steinberg, S. Fundamentals of Grid Generation. Boca Raton, FL: CRC Press, 1994.Nagell, T. "Lattice Points and Point Lattices." §11 in Introduction to Number Theory. New York: Wiley, pp. 32-34, 1951.Sloane, N. J. A. Sequence A000769/M3252 in "The On-Line Encyclopedia of Integer Sequences."Thompson, J. F.; Soni, B.; and Weatherill, N. Handbook of Grid Generation. Boca Raton, FL: CRC Press, 1998.Voutier, P. M. "On the Guy-Kelly Conjecture for the No-Three-in-Line Problem." 9 Mar 2026. https://arxiv.org/abs/2603.00215v2.

Referenced on Wolfram|Alpha

Point Lattice

Cite this as:

Weisstein, Eric W., with contributions by Matt Insall and Todd Rowland. "Point Lattice." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PointLattice.html

Subject classifications