
Blichfeldt's theorem is a
mathematical theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
in the
geometry of numbers Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in \mathbb R^n, and the study of these lattices provides fundamental informatio ...
, stating that whenever a
bounded set
:''"Bounded" and "boundary" are distinct concepts; for the latter see boundary (topology). A circle in isolation is a boundaryless bounded set, while the half plane is unbounded yet has a boundary.
In mathematical analysis and related areas of ...
in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions ...
has area
, it can be
translated
Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between ''transla ...
so that it includes at least
points of the
integer lattice
In mathematics, the -dimensional integer lattice (or cubic lattice), denoted , is the lattice in the Euclidean space whose lattice points are -tuples of integers. The two-dimensional integer lattice is also called the square lattice, or gri ...
. Equivalently, every bounded set of area
contains a set of
points whose coordinates all differ by integers.
This theorem can be generalized to other lattices and to higher dimensions, and can be interpreted as a continuous version of the
pigeonhole principle
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there m ...
. It is named after Danish-American mathematician
Hans Frederick Blichfeldt
Hans Frederick Blichfeldt (1873–1945) was a Danish-American mathematician at Stanford University, known for his contributions to group theory, the representation theory of finite groups, the geometry of numbers, sphere packing, and quadratic ...
, who published it in 1914. Some sources call it Blichfeldt's principle or Blichfeldt's lemma.
Statement and proof
The theorem can be stated most simply for points in the Euclidean plane, and for the integer lattice in the plane. For this version of the theorem, let
be any
measurable set
In mathematics, the concept of a measure is a generalization and formalization of geometrical measures ( length, area, volume) and other common notions, such as mass and probability of events. These seemingly distinct concepts have many simi ...
, let
denote its area, and round this number up to the next integer value,
. Then Blichfeldt's theorem states that
can be translated so that its translated copy contains at least
points with integer coordinates.
The basic idea of the proof is to cut
into pieces according to the squares of the integer lattice, and to translate each of those pieces by an integer amount so that it lies within the
unit square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and .
Cartesian coordinates
In a Cartesian coordina ...
having the
origin
Origin(s) or The Origin may refer to:
Arts, entertainment, and media
Comics and manga
* ''Origin'' (comics), a Wolverine comic book mini-series published by Marvel Comics in 2002
* ''The Origin'' (Buffy comic), a 1999 ''Buffy the Vampire Sl ...
as its lower right corner. This translation may cause some pieces of the unit square to be covered more than once, but if the combined area of the translated pieces is counted with
multiplicity it remains unchanged, equal to
. On the other hand, if the whole unit square were covered with multiplicity
its area would be
, less than
. Therefore, some point
of the unit square must be covered with multiplicity at least
. A translation that takes
to the origin will also take all of the
points of
that covered
to integer points, which is what was required.
More generally, the theorem applies to
-dimensional sets
, with
-dimensional volume
, and to an arbitrary
-dimensional
lattice (a set of points in
-dimensional space that do not all lie in any lower dimensional subspace, are separated from each other by some minimum distance, and can be combined by adding or subtracting their coordinates to produce other points in the same set). Just as the integer lattice divides the plane into squares, an arbitrary lattice divides its space into fundamental regions (called
parallelotopes) with the property that any one of these regions can be translated onto any other of them by adding the coordinates of a unique lattice point. If
is the
-dimensional volume of one of parallelotopes, then Blichfeldt's theorem states that
can be translated to include at least
points of
. The proof is as before: cut up
by parallelotopes, translate the pieces by translation vectors in
onto a single parallelotope without changing the total volume (counted with multiplicity), observe that there must be a point
of multiplicity at least
, and use a translation that takes
to the origin.
Instead of asking for a translation for which there are
lattice points, an equivalent form of the theorem states that
itself contains a set of
points, all of whose pairwise differences belong to the lattice. A strengthened version of the theorem applies to
compact set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", ...
s, and states that they can be translated to contain at least
points of the lattice. This number of points differs from
only when
is an integer, for which it is larger by one.
Applications
Minkowski's theorem
Minkowski's theorem
In mathematics, Minkowski's theorem is the statement that every convex set in \mathbb^n which is symmetric with respect to the origin and which has volume greater than 2^n contains a non-zero integer point (meaning a point in \Z^n that is not ...
, proved earlier than Blichfeldt's work by
Hermann Minkowski
Hermann Minkowski (; ; 22 June 1864 – 12 January 1909) was a German mathematician and professor at Königsberg, Zürich and Göttingen. He created and developed the geometry of numbers and used geometrical methods to solve problems in numb ...
, states that any convex set in the plane that is centrally symmetric around the origin, with area greater than four (or a compact symmetric set with area equal to four) contains a nonzero integer point. More generally, for a
-dimensional lattice
whose fundamental parallelotopes have volume
, any set centrally symmetric around the origin with volume greater than
contains a nonzero lattice point.
Although Minkowski's original proof was different, Blichfeldt's theorem can be used in a simple proof of Minkowski's theorem. Let
be any centrally symmetric set with volume greater than
(meeting the conditions of Minkowski's theorem), and scale it down by a factor of two to obtain a set
of volume greater than
. By Blichfeldt's theorem,
has two points
and
whose coordinatewise difference belongs to
. Reversing the shrinking operation,
and
belong to
. By symmetry
also belongs to
, and by convexity the midpoint of
and
belongs to
. But this midpoint is
, a nonzero point of
.
Other applications

Many applications of Blichfeldt's theorem, like the application to Minkowski's theorem, involve finding a nonzero lattice point in a large-enough set, but one that is not convex. For the proof of Minkowski's theorem, the key relation between the sets
and
that makes the proof work is that all differences of pairs of points in
belong to
. However, for a set
that is not convex,
might have pairs of points whose difference does not belong to
, making it unusable in this technique. One could instead find the largest centrally symmetric convex subset
, and then apply Minkowski's theorem to
, or equivalently apply Blichfeldt's theorem to
. However, in many cases a given non-convex set
has a subset
that is larger than
, whose pairwise differences belong to
. When this is the case, the larger size of
relative to
leads to tighter bounds on how big
needs to be sure of containing a lattice point.
For a centrally symmetric
star domain
In geometry, a set S in the Euclidean space \R^n is called a star domain (or star-convex set, star-shaped set or radially convex set) if there exists an s_0 \in S such that for all s \in S, the line segment from s_0 to s lies in S. This defin ...
, it is possible to use the
calculus of variations
The calculus of variations (or Variational Calculus) is a field of mathematical analysis that uses variations, which are small changes in functions
and functionals, to find maxima and minima of functionals: mappings from a set of functions t ...
to find the largest set
whose pairwise differences belong to
. Applications of this method include simultaneous
Diophantine approximation
In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria.
The first problem was to know how well a real number can be approximated by ...
, the problem of approximating a given set of irrational numbers by rational numbers that all have the same denominators.
Generalizations
Analogues of Blichfeldt's theorem have been proven for other sets of points than lattices, showing that large enough regions contain many points from these sets. These include a theorem for
Fuchsian group
In mathematics, a Fuchsian group is a discrete subgroup of PSL(2,R). The group PSL(2,R) can be regarded equivalently as a group of isometries of the hyperbolic plane, or conformal transformations of the unit disc, or conformal transformations ...
s, lattice-like subsets of
matrices, and for the sets of vertices of
Archimedean tiling
Euclidean plane tilings by convex regular polygons have been widely used since antiquity. The first systematic mathematical treatment was that of Kepler in his ''Harmonices Mundi'' (Latin: ''The Harmony of the World'', 1619).
Notation of Eucl ...
s.
Other generalizations allow the set
to be a
measurable function
In mathematics and in particular measure theory, a measurable function is a function between the underlying sets of two measurable spaces that preserves the structure of the spaces: the preimage of any measurable set is measurable. This is i ...
, proving that its sum over some set of translated lattice points is at least as large as its integral, or replace the single set
with a family of sets.
Computational complexity
A computational problem related to Blichfeldt's theorem has been shown to be complete for the
PPP complexity class, and therefore unlikely to be solvable in polynomial time. The problem takes as input a set of integer vectors forming the basis of a
-dimensional lattice
, and a set
of integer vectors, represented implicitly by a
Boolean circuit
In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible in ...
for testing whether a given vector belongs to
. It is required that the cardinality of
, divided by the volume of the fundamental parallelotope of
, is at least one, from which a discrete version of Blichfeldt's theorem implies that
includes a pair of points whose difference belongs to
. The task is to find either such a pair, or a point of
that itself belongs to
. The computational hardness of this task motivates the construction of a candidate for a
collision-resistant cryptographic hash function.
See also
*
Dot planimeter, a device for estimating the area of a shape by counting the lattice points that it contains
*
Pick's theorem
In geometry, Pick's theorem provides a formula for the area of a simple polygon with integer vertex coordinates, in terms of the number of integer points within it and on its boundary. The result was first described by Georg Alexander Pick in ...
, a more precise relationship between area and lattice points covered by a polygon with lattice-point vertices
References
External links
*{{mathworld, title=Blichfeldt's Theorem, id=BlichfeldtsTheorem, mode=cs2
Geometry of numbers
Theorems in geometry