Blichfeldt's theorem

[2] This theorem can be generalized to other lattices and to higher dimensions, and can be interpreted as a continuous version of the pigeonhole principle.

[2] It is named after Danish-American mathematician Hans Frederick Blichfeldt, who published it in 1914.

denote its area, and round this number up to the next integer value,

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 having the origin 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

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

-dimensional volume of one of parallelotopes, then Blichfeldt's theorem states that

onto a single parallelotope without changing the total volume (counted with multiplicity), observe that there must be a point

lattice points, an equivalent form of the theorem states that

[2] A strengthened version of the theorem applies to compact sets, and states that they can be translated to contain at least

[1] Minkowski's theorem, proved earlier than Blichfeldt's work by Hermann Minkowski, 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.

, any set centrally symmetric around the origin with volume greater than

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

[2] 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

that makes the proof work is that all differences of pairs of points in

One could instead find the largest centrally symmetric convex subset

[6] For a centrally symmetric star domain, it is possible to use the calculus of variations to find the largest set

Applications of this method include simultaneous Diophantine approximation, the problem of approximating a given set of irrational numbers by rational numbers that all have the same denominators.

[6] 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 groups, lattice-like subsets of

matrices,[7] and for the sets of vertices of Archimedean tilings.

to be a measurable function, proving that its sum over some set of translated lattice points is at least as large as its integral, or replace the single set

[10] 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

, is at least one, from which a discrete version of Blichfeldt's theorem implies that

The computational hardness of this task motivates the construction of a candidate for a collision-resistant cryptographic hash function.

Blichfeldt's theorem, in the form that every plane set of area (here, an ellipse with area ) contains at least points (here, points), all of whose coordinates differ from each other by integers. The theorem is proved by cutting the set up by squares of the integer grid (top), translating each piece by an integer translation vector into a single unit square, finding a point in that unit square that is covered by many pieces (middle), and using the preimages of this point as the desired points (bottom).
An example of the increased power of Blichfeldt's theorem over Minkowski's theorem for finding lattice points in non-convex sets. The (closed) yellow set on the left has area 1, so can be translated to cover two points of any lattice whose fundamental region has volume 1, such as the red lattice. Therefore, the blue set on the left, the set of differences of pairs of points in , when centered on the origin, contains a nonzero lattice point. In contrast, the blue rectangle on the right, the largest convex subset of , has area too small for Minkowski's theorem to guarantee that it contains a nonzero lattice point, and the yellow rectangle within it is too small for Blichfeldt's theorem to find two points in it.