Blichfeldt’s Theorem

The following theorem was proven by Blichfeldt1 in 1914:

Let $P$ be a set of points in $\newcommand{\R}{\mathbb{R}}\R^n$ which are invariant under translation by vectors in $\newcommand{\Z}{\mathbb{Z}}\Z^n$, and say that $[0,1)^n$ contains $N$ points of $P$. If $S$ is a set in $\R^n$ with volume $V(S)$ then there is some translation $\newcommand{\x}{\mathbf{x}}S+\x$ which contains at least $N\cdot V(S)$ points of $P$. Additionally, if $S$ is compact then there is some translation of $S$ which contains more than $N\cdot V(S)$ points of $P$.

To show this, let $\newcommand{\p}{\mathbf{p}}\newcommand{\c}{{,}~}\p_1\c\dotsc\c\p_N$ be the points of $P$ contained in $[0,1)^n$. Since $P$ is invariant under translation by $\Z^n$, every $\p\in P$ is equivalent to some $\p_i$ modulo $\Z^n$. Let $\nu_i(S)$ denote the number of points in $P\cap S$ congruent to $\p_i$, so

\[ \newcommand{\y}{\mathbf{y}}\nu_i(S) = \sum_{\y\in\Z^n}\chi_S(\p_i+\y) \]

where $\chi_S$ is the characteristic function of $S$. Then

\begin{align*}\newcommand{\d}{\,\mathrm{d}}
\int_{[0,1)^n}\nu_i(S+\x)\d\x &= \int_{[0,1)^n}\sum_{\y\in\Z^n}\chi_{S+\x}(\p_i+\y)\d\x \\
&= \int_{[0,1)^n}\sum_{\y\in\Z^n}\chi_S(\p_i+\y-\x)\d\x \\
&= \int_{(-1,0]^n}\sum_{\y\in\Z^n}\chi_S(\p_i+\y+\x)\d\x \\
&= \sum_{\y\in\Z^n}\int_{(-1,0]^n+\p_i+\y}\chi_S(\x)\d\x \\
&= \int_{\R^n}\chi_S(\x)\d\x \\
&= V(S)
\end{align*}

where the penultimate step follows since taking the set $(-1,0]^n+\p_i+\y$ for each $\y\in\Z^n$ will produce a tiling of all of $\R^n$ with no overlap.

Letting $\nu(S):=\lvert P\cap S\rvert=\sum_{i=1}^N\nu_i(S)$ and summing the above over $1\leq i\leq N$, we find that

\[ \int_{[0,1)^n}\nu(S+\x)\d\x = N\cdot V(S) . \]

By an averaging argument, there must be some $\x\in[0,1)^n$ such that $\nu(S+\x)/V([0,1)^n)\geq N\cdot V(S)$, i.e., the translation $S+\x$ contains at least $N\cdot V(S)$ points of $P$, as required.

Next, we consider the case where $S$ is compact (i.e., closed and bounded). Since $\nu(S+\x)$ is an integer, if $N\cdot V(S)$ is not an integer then it immediately follows that $\nu(S+\x)>N\cdot V(S)$. So suppose that $h:=N\cdot V(S)$ is an integer. Let $S_k:=(1+\frac{1}{k})S$, so that applying the above result on $S_k$ for each $k\geq1$ we have that there exists some $\x_k\in[0,1)^n$ such that $\nu(S_k+\x_k)\geq N\cdot V(S_k)>h$.

Since the $\x_k$ lie in $[0,1]^n$ which is compact, there must be some subsequence $\x_{k_j}$ which converges to a point $\x\in[0,1]^n$. By construction, each $S_{k_j}+\x_{k_j}$ contains at least $h+1$ points of $P$. Since $\bigcup_j S_{k_j}+\x_{k_j}$ is bounded, it contains a finite number of points of $P$. In particular, there are a finite number of ways of choosing $h+1$ points of $P$ from $\bigcup_j S_{k_j}+\x_{k_j}$. By the pigeonhole principle, there must be some choice $\p_1\c\dotsc\c\p_{h+1}\in P$ which appear infinitely often in the sets $S_{k_j}+\x_{k_j}$. Let $k’_j$ index a subsequence of these sets so that $\p_i\in S_{k’_j}+\x_{k’_j}$ for all $i$ and $j$.

The points $\p_i$ must in fact appear in $S+\x$; otherwise there would be some $\p_i$ with positive distance to $S+\x$, but the distance of the farthest point of $S_{k’_j}+\x_{k’_j}$ to $S+\x$ goes to $0$ as $j\to\infty$, contradicting the supposed positive distance that $\p_i\in S_{k’_j}+\x_{k’_j}$ is away from $S+\x$. As required, we have found some translation $S+\x$ which contains more than $h=N\cdot V(S)$ points of $P$.

Alternate statement

Sometimes Blichfeldt’s theorem is stated in the following form:

Let $S$ be a set in $\R^n$ with volume $V(S)>m$ for some $m\in\Z$ (if $S$ is compact we only require $V(S)\geq m$). Then $S$ contains $\x_1\c\dotsc\c\x_{m+1}$ distinct points whose differences $\x_i-\x_j$ all lie in $\Z^n$.

This is a simple corollary of what we’ve already shown. Take $P:=\Z^n$, so that $N=1$. The theorem tells us there is some $\x$ such that $S+\x$ contains at least $V(S)\geq m+1$ (or if $S$ is compact, more than $V(S)\geq m$) points of $P$. Thus we have there exist $\p_i\in P$ and $\x_i\in S$ with $\p_i=\x_i+\x$ for $1\leq i\leq m+1$. Then

\[ \x_i-\x_j = \p_i-\p_j \in \Z^n , \]

as required.

Generalization

Finally, Blichfeldt’s theorem can be generalized to apply to arbitrary lattice points, instead of just $\Z^n$. One possible way of stating it would be:

Let $L$ be a lattice in $\R^n$ with volume $\det(L)$, and $S$ be a set in $\R^n$ with volume $V(S)>m\det(L)$ for some $m\in\Z$ (if $S$ is compact we only require $V(S)\geq m\det(L)$). Then $S$ contains $\x_1\c\dotsc\c\x_{m+1}$ distinct points whose differences $\x_i-\x_j$ all lie in $L$.

The same argumentation as above suffices to show this, except that we replace $[0,1)^n$ (a fundamental region for $\Z^n$) in the argument with a fundamental region for $L$.