Suppose we are standing at the origin of bounded regular forest in , with diameter of m, and all the trees inside have diameter of 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 be symmetric around the origin, convex, and bounded set. If then contains at least one lattice point different from the origin.
Proof. Let . Assume that there exists non-zero integer , such that the intersection between and its translation wrt. is non-empty.
Pick arbitrary . Then by construction. By symmetry, . As is convex, then line segment between and is in . We particularly consider the midpoint of the line segment: . This immediately implies that by the definition of , which proves the theorem.
The claim that there exists non-zero integer , such that is not proven in this post. One can refer to Matoušek’s book for the proof.
Fig. The Minkowski's theorem.
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 m and length of m. We note that the preconditions of Minkowski’s Theorem are satisfied by this visibility strip, which has the volume of . 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 . Then for all , there exists with such that:
Proof. Consider . By inspection on the figure below, we can observe that is convex, bounded, and symmetric around the origin.
Fig. The Dirichlet's approximation theorem.
Observe also that the area of is . Thus this construction satisfied the Minkowski’s Theorem’s preconditions. Therefore there exists lattice point . As is symmetric, we can always assume thus . By definition of , as . Futhermore, we have . This implies which conclude the proof.
Our second application is the theorem saying that prime number 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 be symmetric around the origin, convex, and bounded set. Let be the lattice in . If , then contains at least one lattice point in different from the origin.
Theorem 4 (Two Squares Theorem)
Every prime number can be written by the sum of two squares where .
Proof. We need intermediate result which will not be proven here (refer to [1] for the proof): is a quadratic residue modulo , that is, there exists such that .
Fix and take the following basis for our lattice: . The volume of this lattice is: .
Define a convex, symmetric, and bounded body , i.e. is an open ball around the origin with radius . Note:
thus General Minkowski’s Theorem applies and there exists a lattice point . Notice:
To go from 3rd to 4th line, we use our very first assumption, i.e. . Therefore has to be divisible by . Also, as is in this implies by definition. Thus the only choice is . This proves the theorem.
References
Matoušek, Jiří. Lectures on discrete geometry. Vol. 212. New York: Springer, 2002.
