Skip to main content

Minkowski's Convex Body Theorem

 Minkowski's Convex Body Theorem

Suppose $S$ is a convex set in an "n-dimensional" vector space in a lattice $L$ which is symmetric about the origin. Then, Minkowski's Theorem states that if the volume of the set $V(S) > 2^nd(L)$, then $S$ must contain at least one lattice point other than the origin.

Before diving deeper, let's first clearly understand some terms used in the theorem..

Convex

A set $C$ is said to be convex in $\mathbb{R}^n$ if for all points $a,b \in \mathbb{C}$, the segment joining the points $a$ and $b$ is completely contained in $C$. \newline

An example for a set in $\mathbb{R^2}$ is as follows. 



Symmetric about the origin

A set $C$ is said to be symmetric about the origin if for every point $x \in C$, $-x \in C$. In other words, the reflection of every point in $C$ across the origin must also be in $C$. For example




Lattice


A lattice is an array of points that differ in equal intervals in any dimension. The most widely used lattice is the well-known "integer lattice ($\mathbb{Z}^2$)". For example, non-integer lattices, are hexagonal and parallelogram lattices in the Euclidean Plane.



Determinant of a lattice


The determinant of a lattice L is the volume of the smallest area enclosed by the lattice point. This is represented by $d(L)$. For example, the determinant of the lattices in the above will just be the area of "1 hexagon" and "1 parallelogram formed by 4 adjacent lattice points" respectively.

Now, we understand what the theorem says completely. Let's move on to building the foundation for our proof.


Blichfeldt's Theorem


If R is a bounded set in $\mathbb{R}^2$ with area greater than 1, then R contains two distinct points $(x_1,y_1)$ and $(x_2,y_2)$ such that the point ${(x_2-x_1,y_2-y_1)}$ is an integer point in $\mathbb{R}^2$

Proof: Let $S = \{(x,y) | 0 \le x < 1 \text{and} 0 \le y <1\}$. For every point $a \in \mathbb{Z}^2$, define $S_a = S + a$ be the translation of $S$ along the line segment with endpoints $(0,0)$ and $a$. Note that $a$ will be the only integer point in $S_a$  Since, $R$ is bounded, we know that there will be a finite number of points $z$ such that $R_z = S_z \cap R$ is non empty. Let $R_z-z$ be the translation of $R_z$ back to $S$ along the line segment with endpoints $(0,0)$ and $z$. Since the translations are plane isometry, the area of the sets during translation will be preserved, thus, $A(R_z-z) = A(R_z)$. We have,
$$\sum_{z\in \mathbb{Z}^2}A(R_z-z) = \sum_{z \in \mathbb{Z}^2}A(R_z) = A(R) > 1$$
This means that that all the subsets $R_z$ are stacked one upon another after the translation. Since, the sum of area is greater than 1, we can say that, after the translation, there will be at least integer points $z_1$ and $z_2$ such that the areas of $(R_{z_1}-z_1)$ and $(R_{z_2}-z_2)$ overlap. That is, $(R_{z_1} - z_1) \cap (R_{z_2} - z_2) \neq \phi$. Define $r \in (R_{z_1} - z_1) \cap (R_{z_2} - z_2)$. Let $r+z_1 = r_{z_1} \in R_{z_1}$ and $r+z_2 = r_{z_2} \in R_{z_2}$ by definition. We have, 
$$r_{z_1} - r_{z_2} = (r+z_1) - (r+z_2) = z_1-z_2 \in \mathbb{Z}$$
Thus, there are two distinct points in R $r_{z_1}$ and $r_{z_2}$, whose difference in co-ordinates is an integer point. 

Remark: Note that this theorem is also true for "non-integer lattices", say $L$. The only difference would be that $R$ should have an area greater than $d(L)$. The proof will be similar to this.

This is an extremely helpful theorem which almost finishes the proof of "Minkowski's Theorem". Now, let's move on to prove a simpler version of "Minkowski's Convex Body Theorem".

Simpler version


Let $R$ be a convex region in $\mathbb{R}^2$ that is symmetric about the origin and has an area greater than $2^2d(\mathbb{Z}^2) = 4$. Then $R$ contains an integer point other than the origin.


Proof: Define the set $R'= \left\{\frac{1}{2}x | x \in R\right\}$. Since $R'$ is just $R$ scaled down by a factor of $0.5$, it is also convex and symmetric about the origin. Moreover, $A(R') = \frac{1}{4} A(R) > 1$. By Blichfeldt's Theorem, there exists two distinct points $m,n \in R'$ such that $m-n$ is an integer point. Note that $2m, 2n \in R$. Since, $R$ is symmetric about the origin, $-2n \in R$. We know that $R$ is convex. Thus, every point on the line segment with endpoints $2m$ and $-2n$ lies inside $R$. Therefore, their midpoint also lies in $R$. We have
$$\frac{2m + (-2n)}{2} =  m-n$$ should be in $R$. But since, $m-n$ is an integer point and $m$ and $n$ are distinct, the statement is proved.


Note that the symmetric condition yield that along with $m-n$, the point $-(m-n)$ must also lie in $R$. Thus, there are at least 3 integer points in $R$.

Minkowski's Theorem for Arbitrary Lattices


For, arbitrary lattices, Minkowski's Theorem can be proved with the help of "Pick's Theorem". Although this will not be discussed in this blog, you can refer to its wonderful proof here

Applications of Minkowski's Theorem

The two squares theorem: For a prime $p \equiv 1 \pmod 4$, we can always find some $a,b \in \mathbb{Z}$, such that $p = a^2 + b^2$


Proof: By, Fermat's Christmas Theorem, $(-1)$ is a quadratic residue modulo $p$. Thus, there exists some $b$ such that $q^2 \equiv -1 \pmod p$. Let $z_1 = (1,q)$ and $z_2 = (0,p)$. Define a lattice $L$ such that $z_1$, $z_2$, $(0,0)$ and $(z_1-z_2)$ are all lattice points. Note that these four points form a parallelogram with area $p$. Thus, $d(L) = p$. \newline

Now consider a set $C = \left\{(x,y) | x^2 + y^2 < 2p\right\}$ in $\mathbb{R}^2$. We have,
$$V(C) = \pi\sqrt{2p}^2 = 2\pi p > 4p = 2^2d(L)$$
By "Minkwoski's Theorem", we know that $C$ contains some point $(a,b) \in L/\{0\}$. Since, $(a,b)$ can be written as a linear combination of $z_1$ and $z_2$, let $(a,b) = az_1 + bz_2 = (a, aq + bp) \in \mathbb{R}^2$, which implies
$$a^2 + b^2 = a^2 + (aq + bp)^2 \equiv (q^2 + 1)a^2 \equiv 0 \pmod p$$
Since, $0 < a^2 + b^2 < 2p$, we must have $a^2 + b^2 = p$. Hence, proved.


Post by Akshat Pandey.


About the guest blogger: Hi, I am Akshat Pandey, an 11th grader. I am an olympiad math freak who also enjoys playing the piano, badminton and table tennis. 



Post modified and set up by Sunaina Pati. This post is part of Akshat's lecture notes for Sophie fellowship's WeMP.  

Comments

Popular posts from this blog

Constructions in Number Theory

Hi, I am Emon, a ninth grader, an olympiad aspirant, hailing from Kolkata. I love to do olympiad maths and do some competitive programming in my leisure hours, though I take it seriously. I had written INOI this year. Today, I would be giving you a few ideas on how to Construct in Number Theory . Well, so we shall start from the basics and shall try to dig deeper into it with the help of some important and well-known theorems and perhaps, some fancy ones as well. Okay, so without further delay, let's start off... What do we mean by "Constructions"? If noticed, you can see that you often face with some problems in olympiad saying, "... Prove that there exists infinitely many numbers satisfying the given conditions" or "... Prove that there exists a number satisfying the above conditions." These are usually the construction-problems .  For example, let's consider a trivial example : Problem. Prove that there exist infinitely many integers $a$ such th

EGMO solutions, motivations and reviews ft. Atul, Pranjal and Abhay

The  European Girls' Mathematical Olympiad a.k.a EGMO 2022 just ended. Congrats to Jessica Wan from USA, Taisiia Korotchenko, and Galiia Sharafetdinova for the perfect scores! Moreover, the Indian girls brought home 4 bronze medals! By far, this is the best result the EGMO India Team has ever achieved! To celebrate the brilliant result, here's a compilation of EGMO 2022 solutions and motivations written by my and everyone's favorite IMOTCer Atul ! And along with that, we also have reviews of each problem written by everyone's favorite senior, Pranjal !  These solutions were actually found by Atul, Pranjal,  and Abhay  during the 3-hour live solve. In the live solve, they solved all the 6 problems in 3 hours 😍!!! Okie Dokie, I think we should get started with the problems! Enjoy! Problem 1:  Let $ABC$ be an acute-angled triangle in which $BC<AB$ and $BC<CA$. Let point $P$ lie on segment $AB$ and point $Q$ lie on segment $AC$ such that $P \neq B$, $Q \neq C$ and

Q&A with experts about bashing

Heyy everyone! From the title, you can see that we are going to talk about  BASH.  Yesss, we are going to discuss whether you really need to learn bash or not?  Let me first introduce myself, I am Pranav Choudhary, a 10th grader from Haryana(India). I like to do geo and combo the most :PP. Oki so let's begin! For those of you who don't know what bashing is, lemme give you a brief introduction first. Bashing is basically a technique used to solve Geometry Problems. In general, when you try a geo problem you might think of angles, similarities, and some other techniques (e.g. Inversion, spiral similarity etc). All of which are called synthetic geometry. But sometimes people use various other techniques called "bash" to solve the same problems.  Now there are different kinds of bashing techniques, e.g. - Coordinate bash, Trig Bash, Complex bash, Barycentric Coordinates. Let me give you a brief introduction to each of them.  Coordinate Bash : You set one point as the orig