Point Lattice

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

(1)

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

			(2)
			(3)
			(4)

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

(5)

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).