Among the lattice points with , a classical lower bound gives subsets
of at least
points with no four collinear or concyclic,
for every
and all sufficiently large (Guy 1994, p. 241; Ghosal et al. 2026, p. 1889).
Dong and Xu (2025, p. 2) give algebraic constructions with points under the same restriction, where denotes little-O notation.
A probabilistic construction gives at least points for all sufficiently large (Ghosal et al. 2026, p. 1909).
Any nondegenerate parallelogram on the lattice in which two adjacent sides each have length 1 has unit area (Hilbert and Cohn-Vossen
1999, pp. 33-34).
Ajtai (1996) showed that a probabilistic polynomial-timealgorithm for finding a short nonzerovector in a specified random class of integer lattices, with
probability at least , would yield probabilistic polynomial-timealgorithms that approximate the length
of a shortest nonzerovector
within a polynomial factor in every integer lattice, with probability
exponentially close to 1. This result has potential applications to cryptography
and authentication (Cipra 1996).
that are integers.
In two dimensions, these points
form a square array, often called a grid
or a mesh.
, let 
count the lattice points
in the square ![[-r,r]^2](/images/equations/IntegerLattice/Inline4.svg)
and let 
count those visible
from the origin. Their fraction,
as derived in Castellanos (1988, pp. 155-156), is
is 
. If a pair of integers
is chosen from 
with all 
ordered pairs equally likely, then the probability
that they are relatively prime tends to 
as 
.
lattice points 
with 
, a classical lower bound gives subsets
of at least 
points with no four collinear or concyclic,
for every 
and all sufficiently large 
(Guy 1994, p. 241; Ghosal et al. 2026, p. 1889).
Dong and Xu (2025, p. 2) give algebraic constructions with 
points under the same restriction, where 
denotes little-O notation.
A probabilistic construction gives at least 
points for all sufficiently large 
(Ghosal et al. 2026, p. 1909).
, would yield probabilistic polynomial-time algorithms that approximate the length
of a shortest nonzero vector
within a polynomial factor in every integer lattice, with probability
exponentially close to 1. This result has potential applications to cryptography
and authentication (Cipra 1996).
