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)>2nd(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 Rn if for all points a,bC, the segment joining the points a and b is completely contained in C. \newline

An example for a set in R2 is as follows. 



Symmetric about the origin

A set C is said to be symmetric about the origin if for every point xC, xC. 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 (Z2)". 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 R2 with area greater than 1, then R contains two distinct points (x1,y1) and (x2,y2) such that the point (x2x1,y2y1) is an integer point in R2

Proof: Let S={(x,y)|0x<1and0y<1}. For every point aZ2, define Sa=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 Sa  Since, R is bounded, we know that there will be a finite number of points z such that Rz=SzR is non empty. Let Rzz be the translation of Rz 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(Rzz)=A(Rz). We have,
zZ2A(Rzz)=zZ2A(Rz)=A(R)>1
This means that that all the subsets Rz 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 z1 and z2 such that the areas of (Rz1z1) and (Rz2z2) overlap. That is, (Rz1z1)(Rz2z2)ϕ. Define r(Rz1z1)(Rz2z2). Let r+z1=rz1Rz1 and r+z2=rz2Rz2 by definition. We have, 
rz1rz2=(r+z1)(r+z2)=z1z2Z
Thus, there are two distinct points in R rz1 and rz2, 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 R2 that is symmetric about the origin and has an area greater than 22d(Z2)=4. Then R contains an integer point other than the origin.


Proof: Define the set R={12x|xR}. 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)=14A(R)>1. By Blichfeldt's Theorem, there exists two distinct points m,nR such that mn is an integer point. Note that 2m,2nR. Since, R is symmetric about the origin, 2nR. 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
2m+(2n)2=mn should be in R. But since, mn is an integer point and m and n are distinct, the statement is proved.


Note that the symmetric condition yield that along with mn, the point (mn) 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 p1(mod4), we can always find some a,bZ, such that p=a2+b2


Proof: By, Fermat's Christmas Theorem, (1) is a quadratic residue modulo p. Thus, there exists some b such that q21(modp). Let z1=(1,q) and z2=(0,p). Define a lattice L such that z1, z2, (0,0) and (z1z2) 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={(x,y)|x2+y2<2p} in R2. We have,
V(C)=π2p2=2πp>4p=22d(L)
By "Minkwoski's Theorem", we know that C contains some point (a,b)L/{0}. Since, (a,b) can be written as a linear combination of z1 and z2, let (a,b)=az1+bz2=(a,aq+bp)R2, which implies
a2+b2=a2+(aq+bp)2(q2+1)a20(modp)
Since, 0<a2+b2<2p, we must have a2+b2=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

LMAO Revenge

Continuing the tradition of past years, our seniors at the Indian IMO camp(an unofficial one happened this year) once again conducted LMAO, essentially ELMO but Indian. Sadly, only those who were in the unofficial IMOTC conducted by Pranav, Atul, Sunaina, Gunjan and others could participate in that. We all were super excited for the problems but I ended up not really trying the problems because of school things and stuff yet I solved problem 1 or so did I think. Problem 1:  There is a   grid of real numbers. In a move, you can pick any real number  ,  and any row or column and replace every entry   in it with  .  Is it possible to reach any grid from any other by a finite sequence of such moves? It turned out that I fakesolved and oh my god I was so disgusted, no way this proof could be false and then when I was asked Atul, it turns out that even my answer was wrong and he didn't even read the proof, this made me even more angry and guess wha...

Functional Equations 101

Let's get to the math:  Let there be two sets X and Y. A function  from X to Y denoted as f:XY is assigning a value in Y for every element in X. We say that X is the domain of the function f and Y is the range.  A function f:Xy is said to be injective if f(x)=f(x)x=x To put it in a more abstract way, if there is some aY then there is at most one bX such that f(b)=a holds true.  A function is said to be surjective when for any aY there is at least one bX such that f(b)=a holds true.  A function is bijective if for every aY there is exactly one bX such that f(b)=x. Bijective functions are basically functions which are both injective and surjective.  Bonus: A function f:XX is known as an involution if f(f(x))=xxX  As an exercise, the readers should try to prove that every function th...

Some Wandering Through Orthic Triangles

 Hi, I am Emon and I it's been long since I posted last. Today I will try to give you some ideas on how to work with a special type of triangle, known as " Orthic Triangles ". In this post, I will mainly focus on problem-solving, but still, let me first give you some ideas on what exactly it is and what properties does it have... Definition (Orthic Triangle). Let ABC be a triangle and let D,E,F be the foot of the perpendiculars from A,B,C to BC,CA and AB, respectively. Then, DEF is known as the orthic triangle of ABC. Lemma 1 (Orthic Triangle). If DEF is the orthic triangle of ABC with orthocenter H, then the following conditions are satisfied : (i) AEHF is a cyclic quadrilateral with circumdiameter AH. (ii) BCEF is a cyclic quadrilateral with circumdiameter BC. (iii) H is the incenter of DEF. Lemma 2. ABE=ADE and ACF=ADF. (We can prove this w...