Blichfeldt's theorem
Blichfeldt's theorem is a mathematical theorem in the geometry of numbers, stating that whenever a bounded set in the Euclidean plane has area formula_1, it can be translated so that it includes at least formula_2 points of the integer lattice. Equivalently, any set with this area, in its original position, must contain some subset of formula_2 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. It is named after Danish-American mathematician Hans Frederick  Blichfeldt, 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 formula_4 be any measurable set, let formula_1 denote its area, and round this number up to the next integer value, formula_6. Then Blichfeldt's theorem states that formula_4 can be translated so that its translated copy contains at least formula_8 points with integer coordinates. The basic idea of the proof is to  cut formula_4 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 formula_1. On the other hand, if the whole unit square were covered with multiplicity formula_11 its area would be formula_11, less than formula_1. Therefore, some point formula_14  of the unit square must be covered with multiplicity at least formula_8. A translation that takes formula_14 to the origin will also take all of the formula_8 points of formula_4 that covered formula_14 to integer points, which is what was required. More generally, the theorem applies to formula_20-dimensional sets formula_4, with formula_20-dimensional volume formula_1, and to an arbitrary formula_20-dimensional lattice formula_25 (a set of points in formula_20-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 formula_27 is the formula_20-dimensional volume of one of parallelotopes, then Blichfeldt's theorem states that formula_4 can be translated to include at least formula_30 points of formula_25. The proof is as before: cut up formula_4 by parallelotopes, translate the pieces by translation  vectors in formula_33 onto a single parallelotope without changing the total volume (counted with multiplicity), observe that there must be a point formula_14 of multiplicity at least formula_30, and use a translation that takes formula_14 to the origin. Instead of asking for a translation for which there are formula_8 lattice points, an equivalent form of the theorem states that formula_4 itself contains a set of formula_8 points, all of whose pairwise differences belong to the lattice. A strengthened version of the theorem applies to compact sets, and states that they can be translated to contain at least formula_40 points of  the lattice. This number of points differs from formula_41 only when formula_1 is an integer, for which it is larger by one. Applications. Minkowski's theorem. 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. More generally, for a formula_20-dimensional lattice formula_25 whose fundamental parallelotopes have volume formula_27, any set centrally symmetric around the origin with volume greater than formula_46 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 formula_47 be any centrally symmetric set with volume greater than formula_46 (meeting the conditions of Minkowski's theorem), and scale it down by a factor of two to obtain a set formula_49 of volume greater than formula_27. By Blichfeldt's theorem, formula_49 has two points formula_14 and formula_53 whose coordinatewise difference belongs to formula_27. Reversing the shrinking operation, formula_55 and formula_56 belong to formula_47. By symmetry formula_58 also belongs to formula_47, and by convexity  the midpoint of formula_55 and formula_58 belongs to formula_47. But this midpoint is formula_63, a nonzero point of formula_27. 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 formula_47 and formula_49 that makes the proof work is that all differences of pairs of points in formula_49 belong to formula_47. However, for a set formula_47 that is not convex, formula_49 might have pairs of points  whose difference does not belong to formula_47, making it unusable in this technique. One could instead find the largest centrally symmetric convex subset formula_72, and then apply Minkowski's theorem to formula_73, or equivalently apply Blichfeldt's theorem to formula_74. However, in many cases a given non-convex set formula_47 has a subset formula_76 that is larger than formula_74, whose pairwise differences belong to formula_47. When this is the case, the larger size of formula_79 relative to formula_74 leads to tighter bounds on how big formula_47 needs to be sure of containing a lattice point. For a centrally symmetric star  domain, it is possible to use the calculus of variations to find the largest set formula_82 whose pairwise differences belong to formula_47. 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. 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 groups, lattice-like subsets of formula_84 matrices, and for the sets of vertices of Archimedean tilings. Other generalizations  allow the set formula_4 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 formula_4 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 formula_20-dimensional lattice formula_25, and a set formula_4 of integer vectors, represented implicitly by a Boolean  circuit for testing whether a given vector belongs to formula_4. It is required that the cardinality of formula_4, divided by the volume of the fundamental parallelotope of formula_25, is at least one, from which a discrete version of Blichfeldt's theorem implies that formula_4 includes a pair of points whose difference belongs to formula_25. The task is to find either such a pair, or a point of formula_4 that itself belongs to formula_25. The computational hardness of this task motivates the construction of a candidate for a collision-resistant cryptographic hash function.