Blichfeldt's Principle

# Blichfeldt's Principle

 Theorem (Blichfeldt's Principle):Let $S \subseteq \mathbb{R}^n$. If $\mathrm{volume} (S) > 1$ then there exists $\vec{x}, \vec{y} \in S$ with $\vec{x} \neq \vec{y}$ for which $(\vec{x} - \vec{y}) \in \mathbb{Z}^n$.
• Proof: Let $S \subseteq \mathbb{R}^n$ be such that $\mathrm{volume}(S) > 1$ and suppose instead that for all points $\vec{x}, \vec{y} \in S$ with $\vec{x} \neq \vec{y}$ we have that $\vec{x}- \vec{y} \not \in \mathbb{Z}^n$.
• For each $\vec{k} \in \mathbb{Z}^n$ let:
(1)
\begin{align} \quad S_{\vec{k}} = \left \{ \vec{x} \in S : \left \lfloor x_i \right \rfloor = k_i \: \mathrm{for \: each \:} i \right \} \end{align}
• Observe that $S_{\vec{k}} \subseteq S$ for each $\vec{k} \in \mathbb{Z}^n$. Also observe that:
(2)
\begin{align} \quad S = \bigcup_{\vec{k} \in \mathbb{Z}^n} S_{\vec{k}} \end{align}
• For each $\vec{k} \in \mathbb{Z}^n$ consider the set $S_{\vec{k}} - \vec{k} \subseteq [0, 1)^n$. Then $S_{\vec{k}} - \vec{k}$ is a translation of $S_{\vec{k}}$ and thus has the same volume as each $S_{\vec{k}}$. We claim that $S_{\vec{k}} - \vec{k}$ and $S_{\vec{l}} - \vec{l}$ are disjoint whenever $\vec{k} \neq \vec{l}$.
• Suppose that $\vec{k}, \vec{l} \in \mathbb{Z}^n$ are such that $\vec{k} \neq \vec{l}$. Suppose that $\vec{x} \in S_{\vec{k}} \cap S_{\vec{l}}$. Then there exists $\vec{y} \in S_{\vec{k}} -\vec{k}$ and $\vec{z} \in S_{\vec{l}} - \vec{l}$ such that:
(3)
\begin{align} \quad \vec{x} &= \vec{y} - \vec{k} \\ \quad \vec{x} &= \vec{z} - \vec{l} \end{align}
• Then we have that:
(4)
\begin{align} \quad \vec{y} - \vec{z} = (\vec{x} - \vec{k}) - (\vec{x} - \vec{l}) = \vec{l} - \vec{k} \in \mathbb{Z}^n \end{align}
• Which is a contradiction by the assumption that $\vec{y} - \vec{z} \not \in \mathbb{Z}^n$ for $\vec{y} \neq \vec{z}$. Therefore $S_{\vec{k}} - \vec{k} \cap S_{\vec{l}} - \vec{l} = \emptyset$ for all $\vec{k}, \vec{l} \in \mathbb{Z}^n$ with $\vec{k} \neq \vec{l}$.
• Therefore we have that:
(5)
\begin{align} \quad \mathrm{volume}(S) = \sum_{\vec{k} \in \mathbb{Z}^n} S_{\vec{k}} = \sum_{\vec{k} \in \mathbb{Z}^n} [S_{\vec{k}} - \vec{k}] \leq \mathrm{volume} ([0, 1)^n) = 1 \end{align}
• Which is a contradiction. Therefore this is some $\vec{x}, \vec{y} \in S$ with $\vec{x} \neq \vec{y}$ for which $\vec{x} - \vec{y} \in \mathbb{Z}^n$. $\blacksquare$