TOPICS
Search

Point Lattice

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
LatticePoints

A point lattice is a regularly spaced array of points.

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 (m,n,...), where m, n, ... 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. Every "point lattice" is a lattice under the ordering inherited from the plane, although a point lattice may not be a sublattice of the plane, since the infimum operation in the plane need not agree with the infimum operation in the point lattice. On the other hand, many lattices are not point lattices.

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

Point lattice

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 Z subset R and Z^2 subset R^2. Usually, a lattice is defined to have full rank, i.e., a lattice in R^n is the subgroup

{a_1v_1+...a_nv_n},
(1)

where the a_i are integers and v_i are linearly independent vectors. Note that a lattice needs at most n elements to generate it. For example, the subgroup {a_1+a_2sqrt(2)} subset R requires two generators but is not discrete, and is not a lattice. The above illustration shows that the subgroup generated by 1 and 1/sqrt(2) is not a lattice by showing a+b/sqrt(2) for successive b in [0,1].

The fraction of lattice points visible from the origin, as derived in Castellanos (1988, pp. 155-156), is

(N^'(r))/(N(r))=((24)/(pi^2)r^2+O(rlnr))/(4r^2+O(r))
(2)
=(6/(pi^2)+O((lnr)/r))/(1+O(1/r))
(3)
=6/(pi^2).
(4)

Therefore, this is also the probability that two randomly picked integers will be relatively prime to one another.

For 2<=n<=32, it is possible to select 2n lattice points with x,y in [1,n] such that no three are in a straight line. The number of distinct solutions (not counting reflections and rotations) for n=2, 3, ..., are 1, 1, 4, 5, 11, 22, 57, 51, 156 ... (OEIS A000769). For large n, it is conjectured that it is only possible to select at most (c+epsilon)n lattice points with no three collinear, where

c=(2pi^2/3)^(1/3) approx 1.87
(5)

(Guy and Kelly 1968; Guy 1994, p. 242). The number of the n^2 lattice points x,y in [1,n] which can be picked with no four concyclic is O(n^(2/3)-epsilon) (Guy 1994, p. 241).

PointLatticeParallelograms

Any parallelogram on the lattice in which two opposite sides each have length 1 has unit area (Hilbert and Cohn-Vossen 1999, pp. 33-34).

A special set of polygons defined on the regular lattice are the golygons. A necessary and sufficient condition that a linear transformation transforms a lattice to itself is that it be unimodular. M. Ajtai has shown that there is no efficient algorithm for finding any fraction of a set of spanning vectors in a lattice having the shortest lengths unless there is an efficient algorithm for all of them (of which none is known). This result has potential applications to cryptography and authentication (Cipra 1996).

See also

Barnes-Wall Lattice, Blichfeldt's Theorem, Browkin's Theorem, Circle Lattice Points, Coxeter-Todd Lattice, Ehrhart Polynomial, Elliptic Curve, Gauss's Circle Problem, Golygon, Integration Lattice, Jarnick's Inequality, Lattice Path, Lattice Sum, Leech Lattice, Minkowski Convex Body Theorem, Modular Lattice, N-Cluster, Nosarzewska's Inequality, Pick's Theorem, Random Walk, 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

Apostol, T. Introduction to Analytic Number Theory. New York: Springer-Verlag, 1995.Castellanos, D. "The Ubiquitous Pi." Math. Mag. 61, 67-98, 1988.Cipra, B. "Lattices May Put Security Codes on a Firmer Footing." Science 273, 1047-1048, 1996.Eppstein, D. "Lattice Theory and Geometry of Numbers." http://www.ics.uci.edu/~eppstein/junkyard/lattice.html. Gardner, M. "The Lattice of Integer." 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.Hammer, J. Unsolved Problems Concerning Lattice Points. London: 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.

Referenced on Wolfram|Alpha

Point Lattice

Cite this as:

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

Subject classifications