$$ \newcommand{\dint}{\mathrm{d}} \newcommand{\vphi}{\boldsymbol{\phi}} \newcommand{\vpi}{\boldsymbol{\pi}} \newcommand{\vpsi}{\boldsymbol{\psi}} \newcommand{\vomg}{\boldsymbol{\omega}} \newcommand{\vsigma}{\boldsymbol{\sigma}} \newcommand{\vzeta}{\boldsymbol{\zeta}} \renewcommand{\vx}{\mathbf{x}} \renewcommand{\vy}{\mathbf{y}} \renewcommand{\vz}{\mathbf{z}} \renewcommand{\vh}{\mathbf{h}} \renewcommand{\b}{\mathbf} \renewcommand{\vec}{\mathrm{vec}} \newcommand{\vecemph}{\mathrm{vec}} \newcommand{\mvn}{\mathcal{MN}} \newcommand{\G}{\mathcal{G}} \newcommand{\M}{\mathcal{M}} \newcommand{\N}{\mathcal{N}} \newcommand{\S}{\mathcal{S}} \newcommand{\I}{\mathcal{I}} \newcommand{\diag}[1]{\mathrm{diag}(#1)} \newcommand{\diagemph}[1]{\mathrm{diag}(#1)} \newcommand{\tr}[1]{\text{tr}(#1)} \renewcommand{\C}{\mathbb{C}} \renewcommand{\R}{\mathbb{R}} \renewcommand{\E}{\mathbb{E}} \newcommand{\D}{\mathcal{D}} \newcommand{\inner}[1]{\langle #1 \rangle} \newcommand{\innerbig}[1]{\left \langle #1 \right \rangle} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\norm}[1]{\lVert #1 \rVert} \newcommand{\two}{\mathrm{II}} \newcommand{\GL}{\mathrm{GL}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\grad}[1]{\mathrm{grad} \, #1} \newcommand{\gradat}[2]{\mathrm{grad} \, #1 \, \vert_{#2}} \newcommand{\Hess}[1]{\mathrm{Hess} \, #1} \newcommand{\T}{\text{T}} \newcommand{\dim}[1]{\mathrm{dim} \, #1} \newcommand{\partder}[2]{\frac{\partial #1}{\partial #2}} \newcommand{\rank}[1]{\mathrm{rank} \, #1} \newcommand{\inv}1 \newcommand{\map}{\text{MAP}} \newcommand{\L}{\mathcal{L}} \DeclareMathOperator*{\argmax}{arg\,max} \DeclareMathOperator*{\argmin}{arg\,min} $$

Minkowski's, Dirichlet's, and Two Squares Theorem

Forest

Suppose we are standing at the origin of bounded regular forest in $ \mathbb{R}^2 $, with diameter of $26$m, and all the trees inside have diameter of $0.16$m. Can we see outside this forest? This problem can be solved using Minkowski’s Theorem. We will see the theorem itself first, and we shall see how can we answer that question. Furthermore, Minkowski’s Theorem can also be applied to answer two other famous theorems, Dirichlet’s Approximation Theorem, and Two Squares Theorem.

Theorem 1 (Minkowski’s Theorem)
Let $ C \subseteq \mathbb{R}^d $ be symmetric around the origin, convex, and bounded set. If $ \text{vol}(C) > 2^d $ then $ C $ contains at least one lattice point different from the origin.

Proof. Let $ C’ := \frac{1}{2} C = \{ \frac{1}{2} c \, \vert \, c \in C \} $. Assume that there exists non-zero integer $ v \in \mathbb{Z}^d \setminus \{ 0 \} $, such that the intersection between $ C’ $ and its translation wrt. $ v $ is non-empty.

Pick arbitrary $ x \in C’ \cap (C’ + v) $. Then $ x - v \in C’ $ by construction. By symmetry, $ v - x \in C’ $. As $ C’ $ is convex, then line segment between $ x $ and $ v - x $ is in $ C’ $. We particularly consider the midpoint of the line segment: $ \frac{1}{2}x + \frac{1}{2} (v - x) = \frac{1}{2} v \in C’ $. This immediately implies that $ v \in C $ by the definition of $ C’ $, which proves the theorem.

$ \square $

The claim that there exists non-zero integer $ v \in \mathbb{Z}^d \setminus \{ 0 \} $, such that $ C’ \cap (C’ + v) \neq \emptyset $ is not proven in this post. One can refer to Matoušek’s book for the proof.

Minkowsi_forest

Given Minkowski’s Theorem, now we can answer our original question. We assume the trees are just lattice points, and our visibility line is now a visibility strip, which has wide of $ 0.16 $m and length of $ 26 $m. We note that the preconditions of Minkowski’s Theorem are satisfied by this visibility strip, which has the volume of $ \approx 4.16 > 4 = 2^d $. Therefore, there exists a lattice point other than the origin inside our visibility strip. Thus our vision outside is blocked by the tree.

Now we look at two theorems that can be proven using Minkowski’s Theorem. The first one is about approximation of real number with a rational.

Theorem 2 (Dirichlet’s Approximation Theorem)
Let $ \alpha \in \mathbb{R} $. Then for all $ N \in \mathbb{N} $, there exists $ m \in \mathbb{Z}, n \in \mathbb{N} $ with $ n \leq N $ such that:

\[\left \vert \, \alpha - \frac{m}{n} \right \vert \lt \frac{1}{nN} \enspace .\]

Proof. Consider $ C := \{ (x, y) \in \mathbb{R}^2 \, \vert \, -N-\frac{1}{2} \leq x \leq N+\frac{1}{2}, \vert \alpha x - y \vert \lt \frac{1}{N} \} $. By inspection on the figure below, we can observe that $ C $ is convex, bounded, and symmetric around the origin.

Dirichlet

Observe also that the area of $ C $ is $ \text{vol}(C) = \frac{2}{N} (2N + 1) = 4 + \frac{2}{N} \gt 4 = 2^d $. Thus this construction satisfied the Minkowski’s Theorem’s preconditions. Therefore there exists lattice point $ (n, m) \neq (0, 0) $. As $ C $ is symmetric, we can always assume $ n \gt 0 $ thus $ n \in \mathbb{N} $. By definition of $ C $, $ n \leq N+\frac{1}{2} \implies n \leq N $ as $ N \in \mathbb{N} $. Futhermore, we have $ \vert \alpha n - m \vert \lt \frac{1}{N} $. This implies $ \left\vert \alpha - \frac{m}{n} \right\vert \lt \frac{1}{nN} $ which conclude the proof.

$ \square $

Our second application is the theorem saying that prime number $ p \equiv 1 \, (\text{mod } 4) $ can be written as a sum of two squares. For this we need the General Minkowski’s Theorem, which allows us to use arbitrary basis for our lattice.

Theorem 3 (General Minkowski’s Theorem) Let $ C \subseteq \mathbb{R}^d $ be symmetric around the origin, convex, and bounded set. Let $ \Gamma $ be the lattice in $ \mathbb{R}^d $. If $ \text{vol}(C) > 2^d \,\text{vol}(\Gamma) = 2^d \det \Gamma $, then $ C $ contains at least one lattice point in $ \Gamma $ different from the origin.

$ \square $

Theorem 4 (Two Squares Theorem)
Every prime number $ p \equiv 1 \, (\text{mod } 4) $ can be written by the sum of two squares $ p = a^2 + b^2 $ where $ a, b \in \mathbb{Z} $.

Proof. We need intermediate result which will not be proven here (refer to [1] for the proof): $ -1 $ is a quadratic residue modulo $ p $, that is, there exists $ q \lt p $ such that $ q^2 \equiv -1 \, (\text{mod } p) $.

Fix $ q $ and take the following basis for our lattice: $ z_1 := (1, q), \, z_2 := (0, p) $. The volume of this lattice is: $ \det \Gamma = \det \begin{bmatrix} 1 & 0 \\ q & p \end{bmatrix} = p $.

Define a convex, symmetric, and bounded body $ C := \{ (x, y) \in \mathbb{R}^2 \, \vert \, x^2 + y^2 \lt 2p \} $, i.e. $ C $ is an open ball around the origin with radius $ \sqrt{2p} $. Note:

\[\text{vol}(C) = \pi r^2 \approx 6.28p \gt 4p = 2^2 p = 2^d \det \Gamma \enspace ,\]

thus General Minkowski’s Theorem applies and there exists a lattice point $ (a, b) = i z_1 + j z_2 = (i, iq + jp) \neq (0, 0) $. Notice:

\[\begin{align} a^2 + b^2 &= i^2 + i^2 q^2 + 2ijpq + j^2 p^2 \\ &\equiv i^2 + i^2q^2 \, (\text{mod } p) \\ &\equiv i^2(1+q^2) \, (\text{mod } p) \\ &\equiv i^2(1-1) \, (\text{mod } p) \\ &\equiv 0 \, (\text{mod } p) \enspace . \end{align}\]

To go from 3rd to 4th line, we use our very first assumption, i.e. $ q^2 \equiv -1 \, (\text{mod } p) $. Therefore $ a^2 + b^2 $ has to be divisible by $ p $. Also, as $ (a, b) $ is in $ C $ this implies $ a^2 + b^2 \lt 2p $ by definition. Thus the only choice is $ a^2 + b^2 = p $. This proves the theorem.

$ \square $

References

Matoušek, Jiří. Lectures on discrete geometry. Vol. 212. New York: Springer, 2002.